{'fraction_non_alphanumeric': 0.03675094429509647, 'fraction_numerical': 0.012998945111784121, 'mean_word_length': 4.575412635173591, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Inexact Proximal Alternating Direction Method for Non-convex and Non-smooth Matrix Factorization and Beyond

Since Non-convex and Non-smooth Matrix Factorization (NNMF) problems have great realistic significance in applications, they attract extensive attention in the fields of image processing and machine learning. We in this paper propose an inexact proximal alternating direction (IPAD) method for solving various complex NNMF problems. Our IPAD method is not a single algorithm, but a general and flexible framework which can fuse various numerical methods into. With a special designed error condition, the convergence properties of IPAD are analyzed for a general formulation, and can be extended to a wider range of problems. Moreover, an implementation method for checking the inexactness criterion is theoretically analyzed, which is more valid than the previously naive criteria in practice. Our IPAD algorithm is applied to a widely-concerned sparse dictionary learning problem on both synthetic and real-world data. The experimental results with detailed analyses and discussions are given to verify the efficiency of IPAD method.


Introduction
Being as an imperative tool for multivariate data analysis, matrix factorization (MF) has been widely used in the fields of pattern recognition and machine learning, signal and image processing, etc. More specifically, such applications include gene expression classification [5], hyperspectral unmixing [19], image restoration [30], and so on.
Considering the ill-posedness of the classic MF [11,22] which factorizes the matrices without additional constraints, not a few literatures concentrate on introducing auxiliary constraints on the decomposed matrices in order to incor-porate prior knowledge and reflect the characteristics of the issues more comprehensively [9,18,36]. Before revisiting some well-known MF techniques, we provide the general formulation of MF as follows: where the regularization functions r 1 and r 2 denote the additional constraints that respectively act on the to-be factorized vectors/matrices A and B; at the same time, A and B are restricted to the constraint sets S 1 and S 2 ; the coupling part in the loss function L is employed to describe the data recovery ability of AB to the input data I. This general formulation covers numerous MF techniques. One of the most well-known MF techniques, principal component analysis (PCA) [22], actually does not make any assumptions on the factorized components, however, it can also be written in the form of (1). On the other hand, the variants of sparse PCA (SPCA) incorporate sparse constraints, such as lasso constraint [29], 0 penalty [21] and elastic-net regularization [37] to the classic PCA [22]. In nonnegative matrix factorization (NMF), both components are constrained to be non-negative in accordance with biological evidences [23,33]. The two factorized components in sparse dictionary learning (SDL) are called "dictionary" and "codes", respectively. Many literatures have posted the superiority on restricting the dictionary with normalized bases while at the same time constraining the sparsity of codes with various non-convex sparse penalties [30,2]. Since SDL is a powerful tool to represent diverse kinds of data in image processing, machine learning and neural computing [16], its algorithms and applications have gained wider attentions and further discussions from researchers.
MF problems formulated as (1) with simple or without constraints have been relatively well-studied [18]: their designed algorithms usually yield satisfactory results [23,31]. However, the simple-constrained or unconstrained MF techniques are far less effective than the ones with complex constraints. The special-designed constraints, absorbing various prior knowledge and reflecting the properties of the issues in a more comprehensive way, have great realistic significance and play an important role in real-world applications. In SDL problem, for example, using sparse and nonconvex regularizers enable much more flexibility to adapt the representation to the data under an over-complete dictionary [30]. An orthogonal constraint is added on NMF to minimize the redundancy between different bases [24] and then result in some sparseness in the factorized components. Those effective but complex constraints, e.g., the non-convex space regularization in SDL and the orthogonal constraint in NMF, mainly exist in the regularization part and are always non-smooth and even non-convex functions [21,30]. Due to their complexities, few algorithms are designed for solving the non-convex and non-smooth MF (NNMF) problems with rigid convergence analyses. Considering the great realistic significance of NNMF problems in practice, we in this paper focus on proposing a general algorithm framework for effectively and efficiently solving these complex NNMF problems. From the observation that it is either impossible or extremely hard for calculating the exact solutions of the subproblems in NNMF, but the subproblems can be easily solved by other efficient numerical methods. Thus, we employ an alternating method to update each variable in a cyclic order; and each of the two subproblems are allowed to be solved approximately. We name our algorithm framework as inexact proximal alternating direction (IPAD) method, which is originally designed for solving NNMF problems, but can be extended to solving a wider range of non-convex problems in applications. Different from previously used inexact strategies, IPAD method theoretically give rigid implementations of the stopping criteria for inner algorithms, which is more rigid and robust in practice. In the existing literature, there are a few papers on designing and analyzing inexact algorithms [28,20] for convex optimization problems with linear constraints. However, no literature has shown the convergence analyses on using inexact skills under non-convex framework. As far as we know, we are the first to fuse various numerical methods into a general algorithm framework and at the same time give rigorous convergence analyses for non-convex and non-smooth optimization problems. Here, we list the main contributions in this paper as follows: 1. We propose an algorithm framework named IPAD for solving various complex NNMF problems (1). Our IPAD is not a single algorithm for solving NNMF problems, but a general algorithm framework that can fuse various efficient numerical methods into.
2. Our IPAD method is proved to achieve the best convergence result in general non-convex and non-smooth problems. Moreover, the stopping criterion of ours is theoretically analyzed and is more valid than the commonly used one. Since the convergence of IPAD is established on general optimization problem, thus it can be applied to more applications beyond NNMF.
3. We apply IPAD to a specific problem, i.e., SDL problem with 0 penalty, on both synthetic and real-world data. The experimental results verify the efficiency of IPAD for solving the NNMF problem (1).

Inexact Proximal Alternating Direction
In this section, we present the detailed implementation of our proposed IPAD method. To simplify the subsequent derivations, we prefer proposing IPAD method and analyzing its properties on a general and concise formulation: where the function L(I − AB) in (1) is a coupling case corresponding to the function H(x, y) in (2); the regularization r 1 (A) and an indicator function 1 X S1 (A) compose f (x) in (2); similarly, g(Y) is equal to r 2 (B) + X S2 (B). Moreover, we give some assumptions on the objective function in (2): (1) f and g are proper, lower semi-continuous functions; (2) H is a C 1 function and its gradient is Lipschitz continuous on a bounded set; (3) Ψ is a coercive, Kurdyka-Łojasiewicz (KŁ) function 2 .
Remark 1 It should be mentioned that the most frequently used L(A, B) = I − AB 2 is a KŁ function which also satisfies the second assumption. On the other hand, regularizers like 0 penalty, p norm, SCAD [14], MCP [35] and indicator functions are all KŁ functions and at the same time satisfy the first assumption. Since the finite sums of KŁ functions are also KŁ functions [6], thus not a few models in NNMF problems satisfy these three assumptions.

Algorithm Implementation
We have the observation that it is either impossible or extremely hard for calculating the exact solutions of the subproblems in NNMF, but they can be easily solved by other efficient numerical methods. This perception motivates us to propose an algorithm to solve the subproblems approximately and then obtain the inexact solutions x t+1 and y t+1 by some numerical methods. Specifically, our IPAD method employs an alternative technique, which updates the variables x t+1 and y t+1 in a cyclic order: where η t 1 and η t 2 are two proximal parameters added on each subproblem respectively.
Since in most cases, it is extremely hard to obtain the exact solutions of the two subproblems in NNMF problems, thus various iterative numerical methods can be employed to computing inexact solutions, described as the approximately equals in the Eq. (3). Let's take an example here: when facing the well-known K-SVD technique [13,26], i.e. a SDL problem with 1 regularizer, both the two subproblems in Eq. (3) are convex. Then, various efficient numerical methods designed under convex framework like homotopy method [12], FISTA [4] and ADMM [7,18] can be applied to solving these two subproblems.
After calculating the inexact solutions x t and y t of (3) by some numerical methods, we first compute intermediate variables x t and y t as the solutions of two specific proximal mappings 3 , which are assumed to be easily-solved: where variables v t x and v t y in Eq. (4) are obtained by computing the following equalities: After getting the intermediate variables x t and y t from x t and y t , we compute two "errors" e t x and e t y for measuring the differences between x t and x t , y t and y t , respectively. Specifically, the well-designed "errors", e t x and e t y are calculated in a special way: Then, these two "errors" are used for checking whether the stopping criteria (7) are satisfied.

Criterion 2
The two "errors", e t x and e t y calculated by Eq. (6) must satisfy the following conditions: where parameters C x and C y are two positive integers defined before the iteration starts.
3 prox τ σ (x) ∈ arg minz σ(z)+ τ 2 z−x 2 denotes proximal mapping to proper, lower semi-continuous function σ The two parameters C x and C y in Eq. (7) have restricted relationships with the proximal parameters η t 1 and η t 2 , which will be claimed later in Assumption 11. Then, once the criteria (7) are satisfied, we re-assign x t to x t and y t to y t . Then x t and y t become the final solutions of their corresponding subproblems at t-th step. For clarity, we give the main steps of IPAD in Alg. 1.
Algorithm 1 IPAD for solving problem (2). 1: Setting parameters: Compute inexact x t by some numerical methods. Re-assign x t = x t . 10: Compute inexact y t by some numerical methods.

12:
Calculate intermediate variable y t by Eq. (4). 13: Compute error e t y by Eq. (6). 14: end while 15: Re-assign y t = y t . 16: end while From the descriptions of the algorithm implementation, our IPAD method seems to be an unusual and complicated algorithm. However, the essence of IPAD can be summed up in a few words. Firstly, IPAD is an alternating method which updates each variable in a cyclic order. Secondly, at each step, the inner algorithms employ iterative processes to compute inexact solutions. In addition, the inner algorithms stop when reaching the special stopping criteria (7).

Discussions: why inexactness is better?
Solving subproblems inexactly is a common use in practical literatures. For example, the authors in [32] solve a linear subproblem by 2-step Gauss-Seidel iterations and receive good-enough solutions under the suggestions of [8]. Moreover, the authors of a lately NNMF-related paper [18] stop all the inner iterations at fixed steps and achieve acceptable approximations of the exact solutions.
The great success of using inexact strategies in practice have attracted our attentions on proposing an efficient inexact algorithm framework for solving complex NNMF problems. However, the previously used implementations and the corresponding stopping criteria usually lack theoretical support. Almost all the stopping criteria are designed from experience, e.g., a 2-step Gauss-Seidel is "good-enough" in [32]. Different from the previously naive criteria used in applications, our implementation of the inexactness and the corresponding stopping criteria are designed in theory.

Proposition 3
The "errors", e t x and e t y calculated under our suggestions exactly describe the inexactness of (3).
To make the discussions in this section be more readable, we give the detailed proof of the Proposition 3 at the end of this paper in Appendix A.
The above Proposition 3 implies the following equalities: where g t+1 x ∈ ∂f (x t+1 ) and g t+1 y ∈ ∂g(y t+1 ) 4 . The above equalities are exactly the first-order optimality conditions of Eq. (3) by regarding e t x and e t y as the inexactness. We want to mention that e t x and e t y can not be directly calculated by Eq. (8) since g t x and g t y are unattainable in practice. Thus, our special implementation is applicable and at the same time is more rigid than previously used inexact strategies.
On the other hand, except for IPAD, there are a few literatures on designing converged algorithms for non-convex problems. Another popular converged algorithm is proximal alternating linearized method (PALM) [6], which is established with the global convergence property, the whole sequence converges to a critical point of the problem, which as far as we know, is so far the best convergence result for non-convex and non-smooth optimization problems. Since PALM ensures explicit solutions of the subproblems by linearizing the coupling part H(x, y), thus it attracts much more attentions in applications and can also be applied for solving NNMF 5 : However, the pursuit of closed-form solutions of the subproblems does not ensure the efficiency of the whole algorithm (see Section 4.2). At the same time, for NNMF problems, it requires computing the exact Lipschitz constants at every iteration, which is not an easy work in practice. An alternative way is to estimate as small upper bound [3] as possible to speed up the convergence [34], however, estimating a tight upper bound is sometimes extremely hard and timeconsuming. Furthermore, we can see from the experiments (in Section 4) that our inexact algorithm framework IPAD is more flexible and efficient than the PALM.

Discussions: a more flexible framework
Though the main procedure of our IPAD method is the same with many previously inexact techniques [18], our IPAD method (3) does not restrict specific formulae for solving the two subproblems of x t and y t . Which means, one can apply totally different numerical methods for solving different subproblems. This flexibility of our IPAD method is especially welcomed in practice: since the constraints added on the two factorized components are always quite different from each other, efficient algorithms for solving specific subproblems should be carefully chosen.
Furthermore, no matter what it is, arbitrarily applying two inner algorithms still ensure the global convergence property of the whole algorithm as long as the stopping criteria (7) and the parameter conditions (11) are satisfied. From this perspective, our IPAD method is not a single algorithm for solving NNMF, it is an algorithm framework that can fuse other efficient numerical methods into. In addition, through blending the algorithms into our IPAD framework, some previous inexact methods applied to NNMF applications [25,18] can also be proved to achieve the global convergence property.

Convergence Analyses of IPAD
In this section, we provide the theoretical support for IPAD method 6 . The strategic point on analyzing the convergence properties of IPAD is regarding x t+1 and y t+1 as the exact solutions on solving the following subproblems: This equivalent conversion is rigid since the first-order optimality conditions of (10) are exactly the same with Eq. (8). However, it should be emphasized that x t+1 and y t+1 are not computed by directly minimizing (10); this equivalent conversion is nothing but assisting in theoretical analyses. Before proposing the key lemma for the main theorem, we give the requirements on {η t 1 } t∈N and {η t 2 } t∈N .

Assumption 4
The proximal parameters {η t 1 } t∈N and {η t 2 } t∈N should satisfy to ensure the whole IPAD algorithm converges.
Remark 5 Together with the Criterion 2 and the Eq. (3), we can see from the Assumption 4 that: if C x and C y are set too large, than it relatively reduce the inner iterations but at the same time converges with a tiny step size. On the other side, if C x and C y are set too small, than it converges with relatively large step size but will increase the inner iterations. Thus, these parameters are balances that should be chosen carefully in practice.
Then with the help of the above assumption (11), we can obtain the main theorem in Theorem 6: our proposed IPAD has the best convergence property, that is, the global convergence property in general non-convex problems.
Theorem 6 Under the Assumption 11 and suppose the sequence {(x t , y t )} t∈N generated by IPAD is bounded. Then {(x t , y t )} t∈N is a Cauchy sequence that converges to a critical point (x * , y * )of Ψ.
The two assertions in the following key lemma is the cornerstone for proving the main convergence theorem. Obviously, the objective function Ψ is sufficiently descent (Eq. (12) in Lemma 7) during iterations, which together with the second assertion ensures that there is a subsequence of {z t } t∈N that converges to a critical point of the problem. By further combining the KŁ property, we have the global convergence property for our proposed IPAD method as claimed in Theorem 6.
Lemma 7 Suppose that the sequence {(x t , y t )} t∈N generated by IPAD is bounded. Then the following two assertions hold under the Assumption 11: For the convergence rate, our IPAD method shares the same result with PALM when the desingularising function 7 φ(s) = C θ s θ : [0, µ) → R + of Ψ is satisfied with positive constant C and θ ∈ [0, 1). Specifically, IPAD converges in a finite number of steps when θ equals 1. For θ ∈ [0, 1 2 ) and θ ∈ ( 1 2 , 1), IPAD converges with a sublinear rate and a linear rate respectively. Though the convergence rate of IPAD is the same with PALM in theory (the convergence rate is not affected by the algorithm but the objective function Ψ [15]), the experimental results in Section 4 verify the efficiency of our algorithm.

Remark 8
Our IPAD method can be applied to a general multi-block problem: 7 See the definition of KŁ function in supplemental material.
All the convergence properties conducted on problem 2 can be straightforwardly extended to this multi-block case.
Since not a few problems in signal and image processing, machine learning and pattern recognition can be formulated or reformulated as this general formulation, thus our IPAD method can be applied for solving a wider range of applications beyond NNMF.

Experiments
We consider a widely-concerned SDL problem with 0 penalty, which is formulated as: where · 0 denotes the 0 penalty that counts the number of non-zero elements of W. The indicator function X acts on ∀i} is defined for real-world data to enhance the stability of the model [2]. Moreover, we denote S(W) = λ W 0 + X W (W) to simplify the deduction.
It is observed that problem (15) is a special case of problem (2). Thus, PALM can be applied to solve (15) by computing Lipschitz constants at every iteration. Moreover, since it is extremely hard to get exact solutions of the subproblems of (15), our IPAD inexactly solves the following problems to get D t+1 and W t+1 : As far as we know, few efficient numerical methods are designed for solving the non-convex subproblem (16). We apply a proximal iterative hard-thresholding (PITH) algorithm [1,17] to solve this subproblem. On the other hand, for subproblem (17), we apply ADMM [7] for solving it. All the algorithms compared in this paper are implemented by Matlab R2013b and are tested on a PC with 8 GB of RAM and Intel Core i5-4200M CPU.

Synthetic Data
We generate synthetic data with different sizes to help analyze the property of IPAD (see Tab. 1). All the algorithms for the synthetic data stop when satisfying: where Ψ t is the objective value at step t. Iteration Number Iteration Number Iteration Number Iteration Number Iteration Number Iteration Number Iteration Number Iteration Number Iteration Number

Efficiency of Inexact Strategy
To show the respective effects of using inexact strategies on different subproblems, we propose IPAD-PITH which obtains W t+1 by PITH but keeps D-subproblem the same as PALM 8 . We also design IPAD-ADMM that computes D t+1 by ADMM but remains W-subproblem the same as PALM. The comparisons in Tab. 1 among PALM, IPAD-PITH 8 Due to the space limit, detailed implementations of all the algorithms mentioned in Section 4 are given in supplemental material. and IPAD-ADMM show that inexact strategies help reduce the iteration steps: both the IPAD-PITH and IPAD-ADMM converges with less iterations than PALM. However, the performances of IPAD-PITH and IPAD-ADMM are quite different in inner iterations. We can see from Fig. 1(d) that IPAD-ADMM uses few inner steps during iterations. However, IPAD-PITH reaches the maximum inner steps (set as 20) at almost every iteration. This from one side shows that ADMM is suitable for solving (17) but PITH is less efficient for solving (15). On the other side it is caused by the problems themselves: (17) has unique solution 9 but problem (16) is a challenging NP hard problem and only suboptimal solution can be found in polynomial time. Since PITH converges with unexpected time, thus we only test it on the data with relatively low dimension (n = 64).
We also apply inexact strategies to both subproblems of D and W. Since PITH is time-consuming for solving (16), thus we reduce the maximum inner step to 2 for PITH. We name this algorithm as IPAD-P2A. Then we can see from the Fig. 1 and Tab. 1 that IPAD-P2A uses less iteration steps and sometimes converges faster to an optimal solution.
Remark 9 Though Theorem 6 is proved for applying the inexact strategy to both subproblems, the two hybrid forms of IPAD, i.e. IPAD-PITH and IPAD-ADMM, are also converged. Furthermore, a hybrid IPAD which optionally combines PALM, PAM and IPAD can be proved to have global convergence property for solving problem (2) 10 .

Remark 10
It is observed that IPAD-P2A can not be seen as a special case of the hybrid IPAD since it contains one inexact strategy for D and two-steps prox-linear iterations for W. But fortunately, the experimental results verify the convergence of IPAD-P2A and we can also prove the convergence from theoretical analyses 11 .
By comparing the algorithms, all the inexact strategies of our IPAD method perform better than PALM and are verified to be practicable, converged and efficient. However, a less efficient numerical method for solving subproblem indeed reduce the efficiency of the whole algorithm. Therefore, we should carefully choose effective numerical methods for solving subproblems.

Other Comparisons
At last, we compare INV that solves W t+1 in the same way as PALM but treats D t+1 as the solution of a linear system 9 See supplemental material for detailed discussions. 10 See the proof in supplemental material. 11 See supplemental material for detailed proof. first and then project the solution on set D. Though this strategy seems to be efficient in practice [3], it lacks theoretical guarantee. Firstly, D t+1 calculated by INV is not an exact solution of (17) 12 . Secondly, it is computed without measure the inexactness. So applying INV sometimes creates oscillations during iterations ( Fig. 1(f)) and the performances of INV are unstable especially in real-world applications (see the experimental results in Section 4.2). Thus we do not recommend using it in practice.
In the end, we compare the computational cost of PALM, IPAD-ADMM and INV at every iteration. Since these three algorithms share the same updates of W t+1 , the only difference of the computational cost lies in the update of D t+1 . We list the computational cost of updating D t+1 for only once. The number of the dominant operations of PALM is O(m 3 + mnp + mn). Calculating D t+1 by IPAD-ADMM will cost O(m 3 n + m 2 p + mnp + mn). The last algorithm, INV has O(m 3 n + m 2 p + mnp + mn) calculations.
Though INV seems to take more operations than PALM, the experimental results in Tab. 1 do not match this expectation: INV converges with more steps but uses less time. We should mention that the calculations O(m 3 n) comes from using Gauss-Elimination to obtain an inverse of matrix. However, the inversion process in Matlab may employ more efficient methods. This may be the reason for causing the contradiction between theory and practice.

Real-world Data
We apply IPAD to real-world data on image denoising problem [13,10]. We only compare PALM, INV and IPAD-ADMM in this section and all the algorithms terminates when reaching D t+1 −D t / D t < 1e −2 . The patches in each image, of size 8 × 8, are regularly sampled in an overlapping manner. The noisy images are obtained by adding Gaussian randomly noises with level σ = 15, 20, 25, 30, see Tab. 2. We apply IPAD to 7 images and select some experimental results 13 in Fig. 2-4. 12 See supplemental material for detailed analyses. 13 See supplemental material for more results.  As shown in Tab. 2, PALM seems to converge quickly but get bad recovered results. However, the truth is: the large upper bound (D t+1 ) D t+1 2 of the Lipschitz constant emphasizes the function of the proximal term. So it causes tiny differences between D t+1 and D t . Thus, PALM does not converge when reaching the stopping criterion; on the contrary, it converges quite slow.
For the failure of using PALM, we adopt the strategy used in [2], which regards the problem (15) as a m + 1block problem: solving {d i } m i=1 separately by PALM. We name this algorithm as mPALM and show the results in Tab. 2. This time, mPALM does converge when reaching the stopping criterion. However, mPALM seems to use more time for one iteration (see Tab. 2). We must emphasize that all the algorithms are implemented by Matlab without optimization. We code mPALM in a normal way but the iteration time seems to be inconsistent to [2]. Since the detailed code for [2] is not provided so that we cannot tell the reasons for causing this inconsistency. But we admit that the computational time of all the compared algorithms will be reduced by optimizing them carefully. Though the iterative time of mPALM does not match with the results in [2], we can see from the Tab. 2 that our IPAD-ADMM uses comparative time with the results posted in [2] but at the same time better recovers the noisy images.
On the other hand, the vibration of INV causes more iteration steps than IPAD-ADMM for converging. Thus our carefully designed algorithm, IPAD-ADMM performs more stable than the commonly used INV and is efficient for the real-world applications.

Conclusion and Future Work
In this paper, we propose a general and flexible algorithm framework named IPAD for solving NNMF problems, which achieves the best convergence result for nonconvex and non-smooth problems. Different from previously used inexact strategies, IPAD method gives rigid implementations of the stopping criteria, which is more robust than the previously used ones in practice. Moreover, we verify from the experimental results that IPAD is efficient and effective for solving a SDL problem with 0 penalty.
Since our IPAD method can be straightforwardly extended to a general multi-block non-convex and non-smooth problem, it can be applied to a wider range of applications beyond NNMF, like discriminative learning problems, optimizations on manifolds and tensor decompositions. Moreover, the iterative process of IPAD can be more improved: a random version of IPAD is welcomed to avoid local optimal; a hybrid form of IPAD is more flexible in practice just as claimed in the last section. At the moment, considering the generality and flexibility of IPAD method, we are focusing on discovering its connections with some frameworks in neural network; and then try to optimize those network structures to obtain more robust results.

Appendix A: proof of Proposition 3
Proof From the calculations in Eq. (4), we can deduce the following equalities together with Eq. (6).
Since x t is re-assigned by x t after the stopping criterion in (7) is satisfied, thus we replace the x t in Eq. (19) with x t and get the following equality The above deductions can be similarly extended to the case of y t . Together with Eq. (5), we have , y t = prox 1 g (v t y + e t y ).
where g t+1 x ∈ ∂f (x t+1 ) and g t+1 y ∈ ∂g(y t+1 ). The above equalities are exactly the first-order optimality conditions of (3) by regarding e t x and e t y as the inexactness.