advertisement

EXACT REGULARIZATION OF CONVEX PROGRAMS MICHAEL P. FRIEDLANDER∗ AND PAUL TSENG† November 18, 2006 Abstract. The regularization of a convex program is exact if all solutions of the regularized problem are also solutions of the original problem for all values of the regularization parameter below some positive threshold. For a general convex program, we show that the regularization is exact if and only if a certain selection problem has a Lagrange multiplier. Moreover, the regularization parameter threshold is inversely related to the Lagrange multiplier. We use this result to generalize an exact regularization result of Ferris and Mangasarian (1991) involving a linearized selection problem. We also use it to derive necessary and sufficient conditions for exact penalization, similar to those obtained by Bertsekas (1975) and by Bertsekas, Nedić, and Ozdaglar (2003). When the regularization is not exact, we derive error bounds on the distance from the regularized solution to the original solution set. We also show that existence of a “weak sharp minimum” is in some sense close to being necessary for exact regularization. We illustrate the main result with numerical experiments on the ℓ1 regularization of benchmark (degenerate) linear programs and semidefinite/second-order cone programs. The experiments demonstrate the usefulness of ℓ1 regularization in finding sparse solutions. Key words. convex program, conic program, linear program, regularization, exact penalization, Lagrange multiplier, degeneracy, sparse solutions, interior-point algorithms 1. Introduction. A common approach to solving an ill-posed problem—one whose solution is not unique or is acutely sensitive to data perturbations—is to construct a related problem whose solution is well behaved and deviates only slightly from a solution of the original problem. This is known as regularization, and deviations from solutions of the original problem are generally accepted as a trade-off for obtaining solutions with other desirable properties. However, it would be more desirable if solutions of the regularized problem are also solutions of the original problem. We study necessary and sufficient conditions for this to hold, and their implications for general convex programs. Consider the general convex program (P) minimize x f (x) subject to x ∈ C, where f : Rn → R is a convex function, and C ⊆ Rn is a nonempty closed convex set. In cases where (P) is ill-posed or lacks a smooth dual, a popular technique is to regularize the problem by adding a convex function to the objective. This yields the regularized problem (Pδ ) minimize f (x) + δφ(x) x subject to x ∈ C, where φ : Rn → R is a convex function and δ is a nonnegative regularization parameter. The regularization function φ may be nonlinear and/or nondifferentiable. ∗ Department of Computer Science, University of British Columbia, Vancouver V6T 1Z4, BC, Canada (mpf@cs.ubc.ca). Research supported by the National Science and Engineering Council of Canada. † Department of Mathematics, University of Washington, Seattle, Washington 98195, USA (tseng@math.washington.edu). Research supported by National Science Foundation Grant DMS0511283. 1 2 MICHAEL P. FRIEDLANDER AND PAUL TSENG In general, solutions of the regularized problem (Pδ ) need not be solutions of (P). (Here and throughout, “solution” is used in lieu of “optimal solution.”) We say that the regularization is exact if the solutions of (Pδ ) are also solutions of (P) for all values of δ below some positive threshold value δ̄. We choose the term exact to draw an analogy with exact penalization that is commonly used for solving constrained nonlinear programs. An exact penalty formulation of a problem can recover a solution of the original problem for all values of the penalty parameter beyond a threshold value. See, for example, [4, 5, 9, 21, 24, 31] and, for more recent discussions, [7, 15]. Exact regularization can be useful for various reasons. If a convex program does not have a unique solution, exact regularization may be used to select solutions with desirable properties. In particular, Tikhonov regularization [45], which corresponds to φ(x) = kxk22 , can be used to select a least two-norm solution. Specialized algorithms for computing least two-norm solutions of linear programs (LPs) have been proposed by [25, 26, 27, 30, 33, 48], among others. Saunders [42] and Altman and Gondzio [1] use Tikhonov regularization as a tool for influencing the conditioning of the underlying linear systems that arise in the implementation of large-scale interior-point algorithms for LPs. Bertsekas [4, Proposition 4] and Mangasarian [30] use Tikhonov regularization to form a smooth convex approximation of the dual LP. More recently, there has been much interest in ℓ1 regularization, which corresponds to φ(x) = kxk1 . Recent work related to signal processing has focused on using LPs to obtain sparse solutions (i.e., solutions with few nonzero components) of underdetermined systems of linear equations Ax = b (with the possible additional condition x ≥ 0); for examples, see [13, 12, 14, 18]. In machine learning and statistics, ℓ1 regularization of linear least-squares problems (sometimes called lasso regression) plays a prominent role as an alternative to Tikhonov regularization; for examples, see [19, 44]. Further extensions to regression and maximum likelihood estimation are studied in [2, 41], among others. There have been some studies of exact regularization for the case of differentiable φ, mainly for LP [4, 30, 34], but to our knowledge there has been only one study, by Ferris and Mangasarian [20], for the case of nondifferentiable φ. However, their analysis is mainly for the case of strongly convex φ and thus is not applicable to regularization functions such as the one-norm. In this paper, we study exact regularization of the convex program (P) by (Pδ ) for a general convex φ. Central to our analysis is a related convex program that selects solutions of (P) of least φ-value: (Pφ ) minimize x φ(x) subject to x ∈ C, f (x) ≤ p∗ , where p∗ denotes the optimal value of (P). We assume a nonempty solution set of (P), which we denote by S, so that p∗ is finite and (Pφ ) is feasible. Clearly, any solution of (Pφ ) is also a solution of (P). The converse, however, does not generally hold. In §2 we prove our main result: the regularization (Pδ ) is exact if and only if the selection problem (Pφ ) has a Lagrange multiplier µ∗ . Moreover, the solution set of (Pδ ) coincides with the solution set of (Pφ ) for all δ < 1/µ∗ ; see Theorem 2.1 and Corollary 2.2. A particular case of special interest is conic programs, which correspond to f (x) = cTx and C = {x ∈ K | Ax = b}, (1.1) EXACT REGULARIZATION OF CONVEX PROGRAMS 3 where A ∈ Rm×n , b ∈ Rm , c ∈ Rn , and K ⊆ Rn is a nonempty closed convex cone. In the further case where K is polyhedral, (Pφ ) always has a Lagrange multiplier. Thus we extend a result obtained by Mangasarian and Meyer for LPs [34, Theorem 1]; their (weaker) result additionally assumes differentiability (but not convexity) of φ on S, and proves that existence of a Lagrange multiplier for (Pφ ) implies existence of a common solution x∗ of (P) and (Pδ ) for all positive δ below some threshold. In general, however, (Pφ ) need not have a Lagrange multiplier even if C has nonempty interior. This is because the additional constraint f (x) = cTx ≤ p∗ may exclude points in the interior of C. We discuss this further in §2. 1.1. Applications. We present four applications of our main result. The first three show how to extend existing results in convex optimization. The fourth shows how exact regularization can be used in practice. Linearized selection (§3). In the case where f is differentiable, C is polyhedral, and φ is strongly convex, Ferris and Mangasarian [20, Theorem 9] show that the regularization (Pδ ) is exact if and only if the solution of (Pφ ) is unchanged when f is replaced by its linearization at any x̄ ∈ S. We generalize this result by relaxing the strong convexity assumption on φ; see Theorem 3.2. Exact penalization (§4). We show a close connection between exact regularization and exact penalization by applying our main results to obtain necessary and sufficient conditions for exact penalization of convex programs. The resulting conditions are similar to those obtained by Bertsekas [4, Proposition 1], Mangasarian [31, Theorem 2.1], and Bertsekas, Nedić, and Ozdaglar [7, §7.3]; see Theorem 4.2. Error bounds (§5). We show that in the case where f is continuously differentiable, C is polyhedral, and S is bounded, a necessary condition for exact regularization with any φ is that f have a “weak sharp minimum” [10, 11] over C. In the case where the regularization is not exact, we derive error bounds on the distance from each solution of the regularized problem (Pδ ) to S in terms of δ and the growth rate of f on C away from S. Sparse solutions (§6). As an illustration of our main result, we apply exact ℓ1 regularization to select sparse solutions of conic programs. In §6.1 we report numerical results on a set of benchmark LPs from the Netlib [36] test set and on a set of randomly generated LPs with prescribed dual degeneracy (i.e., nonunique primal solutions). Analogous results are reported in §6.2 for a set of benchmark semidefinite programs (SDPs) and second-order cone programs (SOCPs) from the DIMACS test set [37]. The numerical results highlight the effectiveness of this approach for inducing sparsity in the solutions obtained via an interior-point algorithm. 1.2. Assumptions. The following assumptions hold implicitly throughout. Assumption 1.1 (Feasibility and finiteness). The feasible set C is nonempty and the solution set S of (P) is nonempty. Assumption 1.2 (Bounded level sets). The level set {x ∈ S | φ(x) ≤ β} is bounded for each β ∈ R, and inf x∈C φ(x) > −∞. (For example, this assumption holds when φ is coercive.) Assumption 1.1 implies that the optimal value p∗ of (P) is finite. Assumptions 1.1 and 1.2 together ensure that the solution set of (Pφ ), denoted by S φ , is nonempty and compact, and that the solution set of (Pδ ), denoted by S δ , is nonempty and compact for all δ > 0. The latter is true because, for any δ > 0 and β ∈ R, any point x in the level set {x ∈ C | f (x) + δφ(x) ≤ β} satisfies f (x) ≥ p∗ and φ(x) ≥ inf x′ ∈C φ(x′ ), so that φ(x) ≤ (β − p∗ )/δ and f (x) ≤ β − δ inf x′ ∈C φ(x′ ). Assumptions 1.1 and 1.2 then 4 MICHAEL P. FRIEDLANDER AND PAUL TSENG imply that φ, f , and C have no nonzero recession direction in common, so the above level set must be bounded [40, Theorem 8.7]. Our results can be extended accordingly if the above assumptions are relaxed to the assumption that S φ 6= ∅ and S δ 6= ∅ for all δ > 0 below some positive threshold. 2. Main results. Ferris and Mangasarian [20, Theorem 7] prove that if the objective function f is linear, then \ Sδ ⊆ Sφ (2.1) 0<δ<δ̄ for any δ̄ > 0. However, an additional constraint qualification on C is needed to ensure that the set on the left-hand side of (2.1) is nonempty (see [20, Theorem 8]). The following example shows that the set can be empty: minimize x x3 subject to x ∈ K, (2.2) where K = {(x1 , x2 , x3 ) | x21 ≤ x2 x3 , x2 ≥ 0, x3 ≥ 0}, i.e., K defines the cone of 2 × 2 symmetric positive semidefinite matrices. Clearly K has a nonempty interior, and the solutions have the form x∗1 = x∗3 = 0, x∗2 ≥ 0, with p∗ = 0. Suppose that the convex regularization function φ is φ(x) = |x1 − 1| + |x2 − 1| + |x3 |. (2.3) (Note that φ is coercive, but not strictly convex.) Then (Pφ ) has the singleton solution set S φ = {(0, 1, 0)}. However, for any δ > 0, (Pδ ) has the unique solution x1 = 1 , 2(1 + δ −1 ) x2 = 1, x3 = 1 , 4(1 + δ −1 )2 which converges to the solution of (Pφ ) as δ → 0, but is never equal to it. Therefore S δ differs from S φ for all δ > 0 sufficiently small. Note that the left-hand side of (2.1) can be empty even when φ is strongly convex and infinitely differentiable. As an example, consider the strongly convex quadratic regularization function φ(x) = |x1 − 1|2 + |x2 − 1|2 + |x3 |2 . As with (2.3), it can be shown in this case that S δ differs from S φ = {(0, 1, 0)} for all δ > 0 sufficiently small. In particular, (δ/2, 1, δ 2 /4) is feasible for (Pδ ), and its objective function value is strictly less than that of (0, 1, 0). Thus the latter cannot be a solution of (Pδ ) for any δ > 0. In general, one can show that as δ → 0, each cluster point of solutions of (Pδ ) belongs to S φ . Moreover, there is no duality gap between (Pφ ) and its dual because S φ is compact (see [40, Theorem 30.4(i)]). However, the supremum in the dual problem might not be attained, in which case there would be no Lagrange multiplier for (Pφ )— and hence no exact regularization property. Thus additional constraint qualifications are needed when f is not affine or C is not polyhedral. The following theorem and corollary are our main results. They show that the regularization (Pδ ) is exact if and only if the selection problem (Pφ ) has a Lagrange multiplier µ∗ . Moreover, S δ = S φ for all δ < 1/µ∗ . Parts of our proof bear similarity to the arguments used by Mangasarian and Meyer [34, Theorem 1], who consider 5 EXACT REGULARIZATION OF CONVEX PROGRAMS the two cases µ∗ = 0 and µ∗ > 0 separately in proving the “if” direction. However, instead of working with the KKT conditions for (P) and (Pδ ), we work with saddlepoint conditions. Theorem 2.1. (a) For any δ > 0, S ∩ S δ ⊆ S φ . (b) If there exists a Lagrange multiplier µ∗ for (Pφ ), then S ∩ S δ = S φ for all δ ∈ (0, 1/µ∗ ]. (c) If there exists δ̄ > 0 such that S ∩ Sδ̄ 6= ∅, then 1/δ̄ is a Lagrange multiplier for (Pφ ), and S ∩ S δ = S φ for all δ ∈ (0, δ̄]. (d) If there exists δ̄ > 0 such that S ∩ Sδ̄ 6= ∅, then S δ ⊆ S for all δ ∈ (0, δ̄). Proof. Part (a). Consider any x∗ ∈ S ∩ S δ . Then, because x∗ ∈ S δ , f (x∗ ) + δφ(x∗ ) ≤ f (x) + δφ(x) for all x ∈ C. Also, x∗ ∈ S, so f (x) = f (x∗ ) = p∗ for all x ∈ S. This implies that φ(x∗ ) ≤ φ(x) for all x ∈ S. Thus x∗ ∈ S φ , and it follows that S ∩ S δ ⊆ S φ . Part (b). Assume that there exists a Lagrange multiplier µ∗ for (Pφ ). We consider the two cases µ∗ = 0 and µ∗ > 0 in turn. First, suppose that µ∗ = 0. Then, for any solution x∗ of (Pφ ), x∗ ∈ arg min φ(x), x∈C or, equivalently, φ(x∗ ) ≤ φ(x) for all x ∈ C. (2.4) Also, x∗ is feasible for (Pφ ), so x∗ ∈ S. Thus f (x∗ ) ≤ f (x) for all x ∈ C. Multiplying the inequality in (2.4) by δ ≥ 0 and adding it to the above inequality yields f (x∗ ) + δφ(x∗ ) ≤ f (x) + δφ(x) for all x ∈ C. Thus x∗ ∈ S δ for all δ ∈ [0, ∞). Second, suppose that µ∗ > 0. Then, for any solution x∗ of (Pφ ), x∗ ∈ arg min φ(x) + µ∗ (f (x) − p∗ ), x∈C or, equivalently, x∗ ∈ arg min f (x) + x∈C 1 φ(x). µ∗ 6 MICHAEL P. FRIEDLANDER AND PAUL TSENG Thus f (x∗ ) + 1 1 φ(x∗ ) ≤ f (x) + ∗ φ(x) for all x ∈ C. µ∗ µ Also, x∗ is feasible for (Pφ ), so that x∗ ∈ S. Therefore f (x∗ ) ≤ f (x) for all x ∈ C. Then, for any λ ∈ [0, 1], multiplying the above two inequalities by λ and 1 − λ, respectively, and summing them yields f (x∗ ) + λ λ φ(x∗ ) ≤ f (x) + ∗ φ(x) for all x ∈ C. µ∗ µ Thus x∗ ∈ S δ for all δ ∈ [0, 1/µ∗ ]. The above arguments show that S φ ⊆ S δ for all δ ∈ [0, 1/µ∗ ], and therefore φ S ⊆ S ∩S δ for all δ ∈ (0, 1/µ∗ ]. By part (a) of the theorem, we must have S φ = S ∩S δ as desired. Part (c). Assume that there exists δ̄ > 0 such that S ∩ Sδ̄ 6= ∅. Then for any x∗ ∈ S ∩ Sδ̄ , we have x∗ ∈ Sδ̄ , and thus x∗ ∈ arg min f (x) + δ̄φ(x), x∈C or, equivalently, 1 x∗ ∈ arg min φ(x) + (f (x) − p∗ ). δ̄ x∈C By part (a), x∗ ∈ S φ . This implies that any x ∈ S φ attains the minimum because φ(x) = φ(x∗ ) and f (x) = p∗ . Therefore 1/δ̄ is a Lagrange multiplier for (Pφ ). By part (b), S ∩ S δ = S φ for all δ ∈ (0, δ̄]. Part (d). To simplify notation, define fδ (x) = f (x) + δφ(x). Assume that there exists a δ̄ > 0 such that S ∩ Sδ̄ 6= ∅. Fix any x∗ ∈ S ∩ Sδ̄ . For any δ ∈ (0, δ̄) and any x ∈ C \ S, we have fδ̄ (x∗ ) ≤ fδ̄ (x) and f (x∗ ) < f (x). Because 0 < δ/δ̄ < 1, this implies that δ δ δ δ ∗ ∗ ∗ fδ (x ) = fδ̄ (x ) + 1 − f (x ) < fδ̄ (x) + 1 − f (x) = fδ (x). δ̄ δ̄ δ̄ δ̄ Because x∗ ∈ C, this shows that x ∈ C \ S cannot be a solution of (Pδ ), and so S δ ⊆ S, as desired. Theorem 2.1 shows that existence of a Lagrange multiplier µ∗ for (Pφ ) is necessary and sufficient for exact regularization of (P) by (Pδ ) for all 0 < δ < 1/µ∗ . Coerciveness of φ on S is needed only to ensure that S φ is nonempty. If δ = 1/µ∗ , then S δ need not be a subset of S. For example, suppose that n = 1, C = [0, ∞), f (x) = x, and φ(x) = |x − 1|. Then µ∗ = 1 is the only Lagrange multiplier for (Pφ ), but S1 = [0, 1] 6⊆ S = {0}. If S δ is a singleton for δ ∈ (0, 1/µ∗ ], such as when φ is strictly convex, then Theorem 2.1(b) and S φ 6= ∅ imply that S δ ⊆ S. EXACT REGULARIZATION OF CONVEX PROGRAMS 7 The following corollary readily follows from Theorem 2.1(b)–(c) and S φ 6= ∅. Corollary 2.2. (a) If there exists a Lagrange multiplier µ∗ for (Pφ ), then S δ = S φ for all δ ∈ (0, 1/µ∗ ). (b) If there exists δ̄ > 0 such that Sδ̄ = S φ , then 1/δ̄ is a Lagrange multiplier for (Pφ ), and S δ = S φ for all δ ∈ (0, δ̄]. 2.1. Conic programs. Conic programs (CPs) correspond to (P) with f and C given by (1.1). They include several important problem classes. LPs correspond to K = Rn+ (the nonnegative orthant); SOCPs correspond to ( ) n−1 X soc soc soc n 2 2 K = Kn1 × · · · × KnK with Kn := x ∈ R xi ≤ xn , xn ≥ 0 i=1 (a product of second-order cones); SDPs correspond to K = Sn+ (the cone of symmetric positive semidefinite n × n real matrices). CPs are discussed in detail in [3, 8, 35, 38], among others. It is well known that when K is polyhedral, the selection problem (Pφ ), with f and C given by (1.1), must have a Lagrange multiplier [40, Theorem 28.2]. In this important case, Corollary 2.2 immediately yields the following exact-regularization result for polyhedral CPs. Corollary 2.3. Suppose that f and C have the form given by (1.1) and that K is polyhedral. Then there exists a positive δ̄ such that S δ = S φ for all δ ∈ (0, δ̄). Corollary 2.3 extends [34, Theorem 1], which additionally assumes differentiability (though not convexity) of φ on S and proves a weaker result that there exists a common solution x∗ ∈ S ∩ S δ for all positive δ below some threshold. If S is furthermore bounded, then an “excision lemma” of Robinson [39, Lemma 3.5] can be applied to show that S δ ⊆ S for all positive δ below some threshold. This result is still weaker than Corollary 2.3 however. 2.2. Relaxing the assumptions on the regularization function. The assumption that φ is coercive on S and is bounded from below on C (Assumption 1.2) ensures that the selection problem (Pφ ) and the regularized problem (Pδ ) have solutions. This assumption is preserved under the introduction of slack variables for linear inequality constraints. For example, if C = {x ∈ K | Ax ≤ b} for some closed convex set K, A ∈ Rm×n , and b ∈ Rm , then φ̃(x, s) = φ(x) with C˜ = {(x, s) ∈ K × [0, ∞)m | Ax + s = b} also satisfies Assumption 1.2. Here φ̃(x, s) depends only on x. Can Assumption 1.2 be relaxed? Suppose that φ(x) depends only on a subset of coordinates xJ and is coercive with respect to xJ , where xJ = (xj )j∈J and J ⊆ {1, . . . , n}. Using the assumption that (P) has a feasible point x∗ , it is readily seen that (Pδ ) has a solution with respect to xJ for each δ > 0, i.e., the minimization in (Pδ ) is attained at some xJ . For an LP (f linear and C polyhedral) it can be shown that (Pδ ) has a solution with respect to 8 MICHAEL P. FRIEDLANDER AND PAUL TSENG all coordinates of x. However, in general this need not be true, even for an SOCP. An example is q n = 3, f (x) = −x2 + x3 , C = {x | x21 + x22 ≤ x3 }, and φ(x) = |x1 − 1|. p Here, p∗ = 0 (since x21 + x22 − x2 ≥ 0 always) and solutions are of the form (0, ξ, ξ) for all ξ ≥ 0. pFor any δ > 0, (Pδ ) has optimal value of zero (achieved by setting x1 = 1, x3 = 1 + x22 , and taking x2 → ∞) but has no solution. In general, if we define fb(xJ ) := min (xj )j6∈J |x∈C f (x), then it can be shown, using convex analysis results [40], that fb is convex and lower semicontinuous—i.e., the epigraph of fb is convex and closed. Then (Pδ ) is equivalent to minimize fb(xJ ) + δφ(xJ ), xJ with φ viewed as a function of xJ . Thus, we can in some sense reduce this case to the one we currently consider. Note that fb may not be real-valued, but this does not pose a problem with the proof of Theorem 2.1. 3. Linearized selection. Ferris and Mangasarian [20] develop a related exactregularization result for the special case where f is differentiable, C is polyhedral, and φ is strongly convex. They show that (Pδ ) is an exact regularization if the solution set of the selection problem (Pφ ) is unchanged when f is replaced by its linearization at any x̄ ∈ S. In this section we show how Theorem 2.1 and Corollary 2.2 can be applied to generalize this result. We begin with a technical lemma, closely related to some results given by Mangasarian [32]. Lemma 3.1. Suppose that f is differentiable on Rn and is constant on the line segment joining two points x∗ and x̄ in Rn . Then ∇f (x∗ )T (x − x∗ ) = ∇f (x̄)T (x − x̄) for all x ∈ Rn . (3.1) Moreover, ∇f is constant on the line segment. Proof. Because f is convex differentiable and is constant on the line segment joining x∗ and x̄, ∇f (x∗ )T (x̄ − x∗ ) = 0. Because f is convex, f (y) − f (x̄) ≥ f (y) − f (x∗ ) ≥ ∇f (x∗ )T (y − x∗ ) for all y ∈ Rn . Fix any x ∈ Rn . Taking y = x̄ + α(x − x̄) with α > 0 yields f (x̄ + α(x − x̄)) − f (x̄) ≥ ∇f (x∗ )T (x̄ + α(x − x̄) − x∗ ) = α∇f (x∗ )T (x − x̄). Dividing both sides by α and then taking α → 0 yields in the limit ∇f (x̄)T (x − x̄) ≥ ∇f (x∗ )T (x − x̄) = ∇f (x∗ )T (x − x∗ ). (3.2) Switching x̄ and x∗ in the above argument yields an inequality in the opposite direction. Thus (3.1) holds, as desired. 9 EXACT REGULARIZATION OF CONVEX PROGRAMS By taking x = α(∇f (x∗ ) − ∇f (x̄)) in (3.2) (where the inequality is now replaced by equality) and letting α → ∞, we obtain that k∇f (x∗ ) − ∇f (x̄)k22 = 0 and hence that ∇f (x∗ ) = ∇f (x̄). This shows that ∇f is constant on the line segment. Suppose that f is differentiable at every x̄ ∈ S, and consider a variation of the selection problem (Pφ ) in which the constraint is linearized about x̄: (Pφ,x̄ ) minimize x φ(x) ∇f (x̄)T (x − x̄) ≤ 0. subject to x ∈ C, Lemma 3.1 shows that the feasible set of (Pφ,x̄ ) is the same for all x̄ ∈ S. Since f is convex, the feasible set of (Pφ,x̄ ) contains S, which is the feasible set of (Pφ ). Let S φ,x̄ denote the solution set of (Pφ,x̄ ). In general S φ 6= S φ,x̄ . In the case where φ is strongly convex and C is polyhedral, Ferris and Mangasarian [20, Theorem 9] show that exact regularization (i.e., S φ = S δ for all δ > 0 sufficiently small) holds if and only if S φ = S φ,x̄ . By using Theorem 2.1, Corollary 2.2, and Lemma 3.1, we can generalize this result by relaxing the assumption that φ is strongly convex. Theorem 3.2. Suppose that f is differentiable on C. (a) If there exists a δ̄ > 0 such that Sδ̄ = S φ , then S φ ⊆ S φ,x̄ for all x̄ ∈ S. (3.3) (b) If C is polyhedral and (3.3) holds, then there exists a δ̄ > 0 such that S δ = S φ for all δ ∈ (0, δ̄). Proof. Part (a). Suppose that there exists a δ̄ > 0 such that Sδ̄ = S φ . Then by Corollary 2.2, µ∗ := 1/δ̄ is a Lagrange multiplier for (Pφ ), and for any x∗ ∈ S φ , x∗ ∈ arg min φ(x) + µ∗ f (x). (3.4) x∈C Because φ and f are real-valued and convex, x∗ and µ∗ satisfy the optimality condition 0 ∈ ∂φ(x∗ ) + µ∗ ∇f (x∗ ) + NC (x∗ ). Then x∗ satisfies the KKT condition for the linearized selection problem minimize x∈C φ(x) subject to ∇f (x∗ )T (x − x∗ ) ≤ 0, (3.5) and is therefore a solution of this problem. By Lemma 3.1, the feasible set of this problem remains unchanged if we replace ∇f (x∗ )T (x−x∗ ) ≤ 0 with ∇f (x̄)T (x−x̄) ≤ 0 for any x̄ ∈ S. Thus x∗ ∈ S φ,x̄ . The choice of x∗ was arbitrary, and so S φ ⊆ S φ,x̄ . Part (b). Suppose that C is polyhedral and (3.3) holds. By Lemma 3.1, the solution set of (Pφ,x̄ ) remains unchanged if we replace ∇f (x̄)T (x− x̄) ≤ 0 by ∇f (x∗ )T (x− x∗ ) ≤ 0 for any x∗ ∈ S φ . The resulting problem (3.5) is linearly constrained and therefore has a Lagrange multiplier µ̄ ∈ R. Moreover, µ̄ is independent of x∗ . By Corollary 2.2(a), the problem minimize φ(x) + µ∗ ∇f (x∗ )T x x∈C 10 MICHAEL P. FRIEDLANDER AND PAUL TSENG has the same solution set as (3.5) for all µ∗ > µ̄. The necessary and sufficient optimality condition for this convex program is 0 ∈ ∂φ(x) + µ∗ ∇f (x∗ ) + NC (x). Because (3.3) holds, x∗ satisfies this optimality condition. Thus (3.4) holds for all µ∗ > µ̄ or, equivalently, x∗ ∈ S δ for all δ ∈ (0, 1/µ̄). Because µ̄ is independent of x∗ , this shows that S φ ⊆ S δ for all δ ∈ (0, 1/µ̄). And because ∅ 6= S φ ⊆ S, it follows that S ∩ S δ 6= ∅ for all δ ∈ (0, 1/µ̄). By Theorem 2.1(a) and (d), S δ ⊆ S φ for all δ ∈ (0, 1/µ̄). Therefore S δ = S φ for all δ ∈ (0, 1/µ̄). In the case where φ is strongly convex, S φ and S φ,x̄ are both singletons, so (3.3) is equivalent to S φ = S φ,x̄ for all x̄ ∈ S. Thus, when C is also polyhedral, Theorem 3.2 reduces to [20, Theorem 9]. Note that in Theorem 3.2(b) the polyhedrality of C is needed only to ensure the existence of a Lagrange multiplier for (3.5), and can be relaxed by assuming an appropriate constraint qualification. In particular, if C is given by inequality constraints, then it suffices that (Pφ,x̄ ) has a feasible point that strictly satisfies all nonlinear constraints [40, Theorem 28.2]. Naturally, (3.3) holds if f is linear. Thus Theorem 3.2(b) is false if we drop the polyhedrality assumption on C, as we can find examples of convex coercive φ, linear f , and closed convex (but not polyhedral) C for which exact regularization fails; see example (2.2). 4. Exact penalization. In this section we show a close connection between exact regularization and exact penalization by applying Corollary 2.2 to obtain necessary and sufficient conditions for exact penalization of convex programs. Consider the convex program m minimize φ(x) subject to x ∈ C, g(x) := gi (x) i=1 ≤ 0, (4.1) x where φ, g1 , . . . , gm are real-valued convex functions defined on Rn , and C ⊆ Rn is a nonempty closed convex set. The penalized form of (4.1) is minimize x φ(x) + σP (g(x)) subject to x ∈ C, (4.2) where σ is a positive penalty parameter and P : Rm → [0, ∞) is a convex function having the property that P (u) = 0 if and only if u ≤ 0; see [7, §7.3]. A well-known example of such a penalty function is P (u) = kmax{0, u}kp , (4.3) where k · kp is the p-norm (1 ≤ p ≤ ∞) [22, §14.3]. The conjugate and polar functions of P [40, §§12, 15] are defined, respectively, by P ∗ (w) := sup wTu − P (u) u and P ◦ (w) := sup u6≤0 wTu . P (u) Note that P ◦ (αw) = αP ◦ (w) for all α ≥ 0. For P given by (4.3), P ◦ (w) equals the q-norm of w whenever w ≥ 0, where 1/p + 1/q = 1. The following lemma gives key properties of these functions that are implicit in the analysis of [7, §7.3]. Lemma 4.1. Suppose that P : Rm → [0, ∞) is a convex function and P (u) = 0 if and only if u = 0. Then (a) P (u) ≤ P (v) whenever u ≤ v; and EXACT REGULARIZATION OF CONVEX PROGRAMS 11 (b) = ∞ ∗ P (w) > 0 =0 if w 6≥ 0; if w ≥ 0 and P ◦ (w) > 1; if w ≥ 0 and P ◦ (w) ≤ 1. Proof. Part (a). Fix any u, v ∈ Rm with u < v, and define π(α) := P (u + α(v − u)) for all α ∈ R. We have u + α(v − u) < 0 for all α < 0 sufficiently negative, in which case π(α) = 0. Because π is convex, this implies that π is nondecreasing and hence π(0) ≤ π(1)—i.e., P (u) ≤ P (v). Thus P (u) ≤ P (v) whenever u < v. Because P is continuous on Rm [40, Theorem 10.1], this yields P (u) ≤ P (v) whenever u ≤ v. Part (b). Fix any w ∈ Rm . If wi < 0 for some i ∈ {1, . . . , m}, then by letting ui → −∞ and setting all other components of u to zero, we obtain wTu − P (u) = wi ui → ∞ and thus P ∗ (w) = ∞. If w ≥ 0 and P ◦ (w) > 1, then wTu > P (u) for some u 6≤ 0 and thus P ∗ (w) ≥ wTu − P (u) > 0. If w ≥ 0 and P ◦ (w) ≤ 1, then wTu ≤ 0 = P (u) for all u ≤ 0, and wTu ≤ P (u) for all u 6≤ 0, so that wTu ≤ P (u) for all u ∈ Rm (with equality holding when u = 0). Therefore P ∗ (w) = 0. Theorem 4.2. Suppose that (4.1) has a nonempty compact solution set. If there exist Lagrange multipliers y ∗ for (4.1), then the penalized problem (4.2) has the same solution set as (4.1) for all σ > P ◦ (y ∗ ). Conversely, if (4.1) and (4.2) have the same solution set for some σ = µ∗ > 0, then (4.1) and (4.2) have the same solution set for all σ ≥ µ∗ , and there exists a Lagrange multiplier vector y ∗ for (4.1) with µ∗ ≥ P ◦ (y ∗ ). Proof. Set f (x) = P g(x) for all x ∈ Rn . By the convexity of g1 , . . . , gm , P , and Lemma 4.1(a), f is a convex function and thus (4.2) is a convex program. Moreover, any feasible point x∗ of (4.1) is a solution of (P) with optimal value p∗ = 0. Accordingly, we identify (4.2) with (Pδ ) (where φ is the regularization function and δ = 1/σ is the regularization parameter), and we identify the problem minimize φ(x) subject to x ∈ C, P g(x) ≤ 0 (4.4) x with (Pφ ). Assumptions 1.1 and 1.2 are satisfied because (4.1) has a nonempty compact solution set. A primal-dual solution pair (x∗ , y ∗ ) of (4.1) satisfies the KKT conditions 0 ∈ ∂φ(x) + m X yi ∂gi (x) + NC (x), y ≥ 0, g(x) ≤ 0, y Tg(x) = 0. (4.5) i=1 By [40, Theorem 23.5], the subdifferential of P at u has the expression ∂P (u) = {w | wTu = P (u) + P ∗ (w)}. If u ≤ 0, then P (u) = 0 and, by Lemma 4.1(b), wTu = P ∗ (w) only if w ≥ 0 and P ◦ (w) ≤ 1. This implies that ∂P (u) = {w | w ≥ 0, P ◦ (w) ≤ 1, wTu = 0} for all u ≤ 0. 12 MICHAEL P. FRIEDLANDER AND PAUL TSENG We can then express the KKT conditions for (4.4) as w ≥ 0 m X P ◦ (w) ≤ 1 , wi ∂gi (x) + NC (x), 0 ∈ ∂φ(x) + µ i=1 µ≥0 g(x) ≤ 0, wTg(x) = 0. (4.6) Comparing (4.5) and (4.6) and using the positive homogeneous property of P ◦ , we see that they are equivalent in the sense that (x∗ , y ∗ ) satisfies (4.5) if and only if (x∗ , µ∗ ) satisfies (4.6), where µ∗ w∗ = y ∗ and µ∗ = P ◦ (y ∗ ), for some w∗ ≥ 0 with P ◦ (w∗ ) ≤ 1. Note that µ∗ is a Lagrange multiplier for (4.4). Therefore, by Corollary 2.2(a), (4.2) and (4.4) have the same solution set for all σ > µ∗ = P ◦ (y ∗ ). Conversely, suppose that (4.2) and (4.4) have the same solution set for σ = µ∗ > 0. Then (Pδ ) and (Pφ ) have the same solution set for δ = 1/µ∗ . By Corollary 2.2(b), µ∗ is a Lagrange multiplier for (Pφ ), and (Pδ ) and (Pφ ) have the same solution set for all δ ∈ (0, 1/µ∗ ]. Therefore, (4.1) and (4.2) have the same solution set for all σ ≥ µ∗ . Moreover, for any x∗ ∈ S φ there exists a vector w∗ such that (x∗ , µ∗ , w∗ ) satisfies (4.6), and so y ∗ := µ∗ w∗ is a Lagrange multiplier vector for (4.1) that satisfies P ◦ (y ∗ ) = µ∗ P ◦ (w∗ ) ≤ µ∗ . We can consider a minimum P ◦ -value Lagrange multiplier vector y ∗ and, similarly, a minimum exact penalty parameter σ. Theorem 4.2 asserts that these two quantities are equal—that is, ( ) ( ) inf P ◦ (y ∗ ) inf σ = . such that y ∗ ∈ Rm is a Lagrange such that (4.2) has the same multiplier for (4.1) solution set as (4.1) Theorem 4.2 shows that the existence of Lagrange multipliers y ∗ with P ◦ (y ∗ ) < ∞ is necessary and sufficient for exact penalization. There has been much study of sufficient conditions for exact penalization; see, e.g., [4], [5, Proposition 4.1], and [9]. The results in [4, Propositions 1 and 2] assume the existence of Lagrange multipliers P y ∗ and, for the case of separable P (i.e., P (u) = i Pi (ui )), prove necessary and sufficient conditions on P and y ∗ for exact penalization. For separable P , the condition P ◦ (y ∗ ) ≤ σ reduces to yi∗ ≤ σ lim ui ↓0 Pi (ui ) , ui i = 1, . . . , m, (4.7) as derived in [4, Proposition 1]. A similar result was obtained in [31, Theorem 2.1] for the further special case of Pi (ui ) = max{0, ui }. Thus Theorem 4.2 may be viewed as a generalization of these results. (For the standard quadratic penalty Pi (ui ) = max{0, ui }2 , the right-hand side of (4.7) is zero, so (4.7) holds only if yi∗ = 0, i.e., the constraint gi (x) ≤ 0 is redundant.) The results in [9, Corollary 2.5.1 and Theorem 5.3] assume either the linearindependence or Slater constraint qualifications in order to ensure existence of Lagrange multipliers. Theorem 4.2 is partly motivated by and very similar to the necessary and sufficient conditions obtained in [7, Proposition 7.3.1]. The connection with exact regularization, however, appears to be new. EXACT REGULARIZATION OF CONVEX PROGRAMS 13 Although our results for exact regularization can be used to deduce results for exact penalization, the reverse direction does not appear possible. In particular, applying exact penalization to the selection problem (Pφ ) yields a penalized problem very different from (Pδ ). 5. Error bounds and weak sharp minimum. Even when exact regularization cannot be achieved, we can still estimate the distance from S δ to S in terms of δ and the growth rate of f away from S. We study this type of error bound in this section. Theorem 5.1. (a) For any δ̄ > 0, ∪0<δ≤δ̄ S δ is bounded. (b) Suppose that there exist τ > 0, γ ≥ 1 such that f (x) − p∗ ≥ τ dist(x, S)γ for all x ∈ C, (5.1) where dist(x, S) = minx∗ ∈S kx − x∗ k2 . Then, for any δ̄ > 0 there exists τ ′ > 0 such that dist(xδ , S)γ−1 ≤ τ ′ δ for all xδ ∈ S δ , δ ∈ (0, δ̄]. Proof. Part (a). Fix any x∗ ∈ S and any δ̄ > 0. For any δ ∈ (0, δ̄] and xδ ∈ S δ , f (x∗ ) + δφ(x∗ ) ≥ f (xδ ) + δφ(xδ ) ≥ f (x∗ ) + δφ(xδ ), and thus φ(x∗ ) ≥ φ(xδ ). Using φ(xδ ) ≥ inf x∈C φ(x), we have, similarly, that f (xδ ) ≤ f (x∗ ) + δ φ(x∗ ) − inf φ(x) ≤ f (x∗ ) + δ̄ φ(x∗ ) − inf φ(x) . x∈C x∈C This shows that ∪0<δ≤δ̄ S δ ⊆ {x ∈ C | φ(x) ≤ β, f (x) ≤ β} for some β ∈ R. Since φ, f , and C have no nonzero recession direction in common (see Assumptions 1.1 and 1.2), the second set is bounded and therefore so is the first set. Part (b). For any δ > 0 and xδ ∈ S δ , let x∗δ ∈ S satisfy kxδ − x∗δ k2 = dist(xδ , S). Then f (x∗δ ) + δφ(x∗δ ) ≥ f (xδ ) + δφ(xδ ) ≥ f (x∗δ ) + τ kxδ − x∗δ kγ2 + δφ(xδ ), which implies that τ kxδ − x∗δ kγ2 ≤ δ φ(x∗δ ) − φ(xδ ) . Because φ is convex and real-valued, φ(xδ ) ≥ φ(x∗δ ) + ηδT (xδ − x∗δ ) ≥ φ(x∗δ ) − kηδ k2 kxδ − x∗δ k2 , for some ηδ ∈ ∂φ(x∗δ ). Combining the above two inequalities yields τ kxδ − x∗δ kγ−1 ≤ δkηδ k2 . 2 By part (a), xδ lies in a bounded set for all δ > 0, so x∗δ lies in a bounded subset of S for all δ > 0. Then ηδ lies in a bounded set [40, Theorem 24.7], so that kηδ k2 is uniformly bounded. This proves the desired bound. 14 MICHAEL P. FRIEDLANDER AND PAUL TSENG Error bounds of the form (5.1) have been much studied, especially in the cases of linear growth (γ = 1) and quadratic growth (γ = 2); see [6, 10, 11, 28, 29, 46] and references therein. In general, it is known that (5.1) holds for some τ > 0 and γ ≥ 1 whenever f is analytic and C is bounded [28, Theorem 2.1]. Theorem 5.1 does not make much use of the convexity of f and φ, and it readily extends to nonconvex f and φ. In the case of γ = 1 in (5.1) (i.e., f has a “weak sharp minimum” over C), Theorem 5.1(b) implies that dist(xδ , S) = 0 for all xδ ∈ S δ —i.e., S δ ⊆ S, whenever δ < 1/τ ′ . In this case, then, S δ = S φ whenever δ < 1/τ ′ and S δ 6= ∅. This gives another exact-regularization result. The following result shows that it is nearly necessary for f to have a weak sharp minimum over C in order for there to be exact regularization by any strongly convex quadratic regularization function. Theorem 5.2. Suppose that f is continuously differentiable on Rn and S is bounded. If there does not exist τ > 0 such that (5.1) holds with γ = 1, then either (i) there exists a strongly convex quadratic function of the form φ(x) = kx − xbk22 (b x ∈ Rn ) and a scalar δ̄ > 0 for which S δ 6= S φ for all δ ∈ (0, δ̄]; or (ii) for every sequence xk ∈ C \ S, k = 1, 2, . . . , satisfying f (xk ) − p∗ → 0, dist(xk , S) k (5.2) k −s ∗ ∗ 6∈ C and every cluster point (x∗ , v ∗ ) of {(sk , kxxk −s k k )}, we have x + αv 2 k k k k for all α > 0, where s ∈ S satisfies kx − s k2 = dist(x , S). If case (ii) occurs, then C is not polyhedral, and for any x̄ ∈ S, S = arg min ∇f (x̄)Tx. (5.3) x∈C Proof. Suppose that there does not exist τ > 0 such that (5.1) holds with γ = 1. Then there exists a sequence xk ∈ C \ S, k = 1, 2, . . . , that satisfies (5.2). Let sk ∈ S satisfy kxk − sk k2 = dist(xk , S). Let v k = (xk − sk )/kxk − sk k2 , so that kv k k2 = 1. Because S is bounded, {sk } is bounded. By passing to a subsequence if necessary, we can assume that (sk , v k ) → some (x∗ , v ∗ ). Because sk is the nearest point projection of xk onto S, we have v k ∈ NS (sk ), i.e., (x − sk )T v k ≤ 0 for all x ∈ S. Taking the limit yields v ∗ ∈ NS (x∗ ), i.e., (x − x∗ )T v ∗ ≤ 0 for all x ∈ S. Note that {xk } need not converge to x∗ or even be bounded. Now, consider the auxiliary sequence y k = sk + ǫk (xk − sk ) with ǫk = 1 , max{k, kxk − sk k2 } k = 1, 2, . . . . Then ǫk ∈ (0, 1], y k ∈ C \ S, (y k − sk )/ky k − sk k2 = v k for all k, and y k − sk → 0 (so y k → x∗ ). Also, the convexity of f implies f (y k ) ≤ (1 − ǫk )f (sk ) + ǫk f (xk ) which, together with ky k − sk k2 = ǫk kxk − sk k2 and f (sk ) = p∗ , implies 0≤ f (y k ) − f (sk ) ǫk f (xk ) − ǫk f (sk ) f (xk ) − p∗ ≤ = → 0. ky k − sk k2 ky k − sk k2 dist(xk , S) (5.4) EXACT REGULARIZATION OF CONVEX PROGRAMS 15 Because f (y k ) − f (sk ) = ∇f (sk )T (y k − sk ) + o(ky k − sk k2 ) and f is continuously differentiable, (5.4) and y k − xk → 0 yield, in the limit, ∇f (x∗ )T v ∗ = 0. (5.5) Let fδ (x) = f (x) + δφ(x), with φ(x) = kx − (x∗ + v ∗ )k22 . Because v ∗ ∈ NS (x∗ ), we have S φ = {x∗ }. Suppose that there exists α > 0 such that x∗ + αv ∗ ∈ C. Then, for any β ∈ (0, α], fδ (x∗ + βv ∗ ) = f (x∗ + βv ∗ ) + kβv ∗ − v ∗ k22 = f (x∗ ) + β∇f (x∗ )T v ∗ + o(β) + δ(β − 1)2 kv ∗ k22 = f (x∗ ) + o(β) + δ(1 − 2β + β 2 ) = fδ (x∗ ) + o(β) − δβ(2 − β), where the third equality uses (5.5) and kv ∗ k2 = 1. Thus x∗ + βv ∗ ∈ C and fδ (x∗ + βv ∗ ) < fδ (x∗ ) for all β > 0 sufficiently small, implying S δ 6= S φ . Therefore, if case (ii) does not occur, then case (i) must occur. Suppose that case (ii) occurs. First, we claim that, for any x̄ ∈ S, ∇f (x̄)T (x − x̄) > 0 for all x ∈ C \ S.1 Fix any x̄ ∈ S. Because ∇f (x̄)T (x − x̄) = 0 for all x ∈ S, this yields (5.3). Next, we claim that C cannot be polyhedral. If C were polyhedral, then the minimization in (5.3) would be an LP, for which weak sharp minimum holds. Then there would exist τ > 0 such that ∇f (x̄)T (x − x̄) ≥ τ dist(x, S) for all x ∈ C. Because f is convex and thus f (x) − p∗ = f (x) − f (x̄) ≥ ∇f (x̄)T (x − x̄) for all x ∈ C, this would imply that (5.1) holds with γ = 1, contradicting our assumption. An example of case (ii) occurring in Theorem 5.2 is n = 2, f (x) = x2 , and C = {x ∈ R2 | x21 ≤ x2 }. Here S = {(0, 0)}, p∗ = 0, and f (x) − p∗ x2 1 = =p dist(x, S) kxk2 (x1 /x2 )2 + 1 for all x ∈ C \ S. The right-hand side goes to 0 if and only if x1 /x2 → ∞, in which case x/kxk2 → (±1, 0), and α(±1, 0) 6∈ C for all α > 0. Interestingly, we can still find φ(x) = 1 If this were false, then there would exist x̄ ∈ S and x ∈ C \ S such that ∇f (x̄)T (x − x̄) = 0. (∇f (x̄)T (x − x̄) < 0 cannot occur because x̄ ∈ S.) Let s ∈ S satisfy kx − sk2 = dist(x, S). By Lemma 3.1, ∇f (s)T (x − s) = 0. Then for xk = s + (x − s)/k, we would have xk ∈ C \ S, f (xk ) − f (s) = o(1/k), and dist(xk , S) = kx − sk2 /k, so xk satisfies (5.2) and sk = s for k = 1, 2, . . . . Because (sk , xk −sk ) kxk −sk k2 → (s, contradict case (ii) occurring. x−s ) kx−sk2 x−s and s + α kx−sk 2 ∈ C for all α ∈ (0, kx − sk2 ], this would 16 MICHAEL P. FRIEDLANDER AND PAUL TSENG kx − xbk22 for which S δ 6= S φ for all δ > 0 sufficiently small. For example, take φ(x) = (x1 − 1)2 + (x2 − 1)2 . Then (Pδ ) becomes x2 + δ(x1 − 1)2 + δ(x2 − 1)2 minimize x subject to x21 ≤ x2 . It is straightforward to check that (0, 0) does not satisfy the necessary optimality conditions for (Pδ ) for all δ > 0. This raises the question of whether case (ii) is subsumed by case (i) when C is not polyhedral. In §8, we give an example showing that the answer is “no”. 6. Sparse solutions. In this section we illustrate a practical application of Corollary 2.2. Our aim is to find sparse solutions of linear and conic programs that may not have unique solutions. To this end, we let φ(x) = kxk1 , which clearly satisfies the required Assumption 1.2. (In general, however, some components of x may be more significant or be at different scales, in which case we may not wish to regularize all components or regularize them equally.) Regularization based on the one-norm has been used in many applications, with the goal of obtaining sparse or even sparsest solutions of underdetermined systems of linear equations and least-squares problems. Some recent examples include [14, 16, 17, 18]. The AMPL model and data files and the Matlab scripts used to generate all of the numerical results presented in the following subsections can be obtained at http://www.cs.ubc.ca/∼mpf/exactreg/. 6.1. Sparse solutions of linear programs. For underdetermined systems of linear equations Ax = b that arise in fields such as signal processing, the studies in [13], [14], and [18] advocate solving kxk1 minimize x subject to Ax = b (and possibly x ≥ 0), (6.1) in order to obtain a sparse solution. This problem can be recast as an LP and be solved efficiently. The sparsest solution is given by minimizing the so-called zeronorm, kxk0 , which counts the number of nonzero components in x. However, the combinatorial nature of this minimization makes it computationally intractable for all but the simplest instances. Interestingly, there exist reasonable conditions under which a solution of (6.1) is a sparsest solution; see [13, 18]. Following this approach, we use Corollary 2.2 as a guide for obtaining least onenorm solutions of a generic LP, minimize x cTx subject to Ax = b, l ≤ x ≤ u, (6.2) by solving its regularized version, minimize x cTx + δkxk1 subject to Ax = b, l ≤ x ≤ u. (6.3) The vectors l and u are lower and upper bounds on x. In many of the numerical tests given below, the exact ℓ1 regularized solution of (6.2) (given by (6.3) for smallenough values of δ) is considerably sparser than the solution obtained by solving (6.2) directly. In each instance, we solve the regularized and unregularized problems with the same interior-point solver. We emphasize that, with an appropriate choice of the regularization parameter δ, the solution of the regularized LP is also a solution of the original LP. EXACT REGULARIZATION OF CONVEX PROGRAMS 17 We use two sets of test instances in our numerical experiments. The instances of the first set are randomly generated using a degenerate LP generator described in [23]. Those of the second set are derived from the infeasible LPs in the Netlib collection (http://www.netlib.org/lp/infeas/). Both sets of test instances are further described in §§6.1.1–6.1.2. We follow the same procedure for each test instance. First, we solve the LP (6.2) to obtain an unregularized solution x∗ and the optimal value p∗ := cTx∗ . Next, we solve (Pφ ), reformulated as an LP, to obtain a Lagrange multiplier µ∗ and the threshold value δ̄ = 1/µ∗ . Finally, we solve (6.3) with δ := δ̄/2, reformulated as an LP, to obtain a regularized solution x∗δ . We use the log-barrier interior-point algorithm implemented in CPLEX 9.1 to solve each LP. The default CPLEX options are used, except for crossover = 0 and comptol = 1e-10. Setting crossover = 0 forces CPLEX to use the interior-point algorithm only, and to not “cross over” to find a vertex solution. In general, we expect the interior-point algorithm to find the analytic center of the solution set (see [47, Theorems 2.16 and 2.17]), which tends to be less sparse than vertex solutions. The comptol option tightens CPLEX’s convergence tolerance from its default of 1e-8 to its smallest allowable setting. We do not advocate such a tight tolerance in practice, but the higher accuracy aids in computing the sparsity of a computed solution, which we determine as kxk0 = card{xi | |xi | > ǫ }, (6.4) where ǫ = 10−8 is larger than the specified convergence tolerance. 6.1.1. Randomly generated LPs. Six dual-degenerate LPs were constructed using Gonzaga’s Matlab generator [23]. This Matlab program accepts as inputs the problem size and the dimensions of the optimal primal and dual faces, Dp and Dd , respectively. Gonzaga shows that these quantities must satisfy 0 ≤ Dp ≤ n − m − 1 and 0 ≤ Dd ≤ m − 1. (6.5) The six LPs are constructed with parameters n = 1000, m = 100, Dd = 0, and various levels of Dp set as 0%, 20%, 40%, 60%, 80%, and 100% of the maximum of 899 (given by (6.5)). The instances are respectively labeled random-0, random-20, random-40, and so on. Table 6.1 summarizes the results. We confirm that in each instance the optimal values of the unregularized and regularized problems are nearly identical (at least to within the specified tolerance), so each regularized solution is exact. Except for the “control” instance random-0, the regularized solution x∗δ has a strictly lower one-norm, and is considerably sparser than the unregularized solution x∗ . 6.1.2. Infeasible LPs. The second set of test instances is derived from a subset of the infeasible Netlib LPs. For each infeasible LP, we discard the original objective, and instead form the problem minimize x kAx − bk1 subject to l ≤ x ≤ u, inf (P ) and its regularized counterpart minimize x kAx − bk1 + δkxk1 subject to l ≤ x ≤ u. inf (Pδ ) 18 MICHAEL P. FRIEDLANDER AND PAUL TSENG Table 6.1 Randomly generated LPs with increasing dimension of the optimal primal face. The arrows indicate differences between values in neighboring columns: → indicates that the value to the right is the same; ց indicates that the value to the right is lower; ր indicates that the value to the right is larger. LP random-0 random-20 random-40 random-60 random-80 random-100 cTx∗ cTx∗δ kx∗ k1 2.5e−13 5.6e−13 3.8e−12 3.9e−14 9.1e−12 1.8e−16 1.0e−13 6.6e−13 3.7e−12 9.2e−11 8.4e−13 3.2e−12 9.1e+01 2.9e+02 4.9e+02 6.7e+02 8.9e+02 1.0e+03 kx∗δ k1 kx∗ k0 kx∗δ k0 → 9.1e+01 100 278 459 637 816 997 2.0e+02 ց 2.9e+02 ց 3.6e+02 ց 4.6e+02 ց 5.4e+02 ց → ց ց ց ց ց 100 100 100 101 100 102 δ̄ 1.5e−04 2.2e−02 2.9e−02 3.3e−02 2.1e−01 1.1e−01 inf The unregularized problem (P ) models the plausible situation where we wish to fit a set of infeasible equations in the least one-norm sense. But because the one-norm inf is not strictly convex or the equations are underdetermined, a solution of (P ) may inf not be unique, and the regularized problem (Pδ ) is used to further select a sparse solution. The following infeasible Netlib LPs were omitted because CPLEX returned an inf inf error message during the solution of (P ) or (Pδ ): lpi-bgindy, lpi-cplex2, lpi-gran, lpi-klein1, lpi-klein2, lpi-klein3, lpi-qual, lpi-refinery, and lpi-vol1. Table 6.2 summarizes the results. We can see that the regularized solution x∗δ is exact (i.e., cTx∗δ = cTx∗ ) and has a one-norm lower than or equal to that of the unregularized solution x∗ in all instances. In twelve of the twenty instances, x∗δ is sparser than x∗ . In five of the instances, they have the same sparsity. In three of the instances (lpi-galenet, lpi-itest6, and lpi-woodinfe), x∗δ is actually less sparse, even though its one-norm is lower. 6.2. Sparse solutions of semidefinite/second-order cone programs. In §6.1 we used Corollary 2.2 to find sparse solutions of LPs. In this section, we report our numerical experience in finding sparse solutions of SDPs and SOCPs that may not have unique solutions. These are conic programs (P) with f and C given by (1.1), and K being the Cartesian product of real space, orthant, second-order cones, and semidefinite cones. The regularized problem (Pδ ) can be put in the conic form minimize cTx + δeT(u + v) subject to Ax = b, x,u,v x − u + v = 0, (6.6) 2n (x,u, v) ∈ K × [0, ∞) , where e is the vector of ones. The selection problem (Pφ ) can also be put in conic form: minimize eT(u + v) subject to Ax = b, x,u,v,s x − u + v = 0, 2n+1 (x,u, v, s) ∈ K × [0, ∞) cTx + s = p∗ , (6.7) . As in §6.1, we first solve (P) to obtain x∗ and the optimal value p∗ := cTx∗ . Then (6.7) is solved to obtain Lagrange multiplier µ∗ and the corresponding threshold value 19 EXACT REGULARIZATION OF CONVEX PROGRAMS Table 6.2 Least one-norm residual solutions of the infeasible Netlib LPs. LP lpi-bgdbg1 lpi-bgetam lpi-bgprtr lpi-box1 lpi-ceria3d lpi-chemcom lpi-cplex1 lpi-ex72a lpi-ex73a lpi-forest6 lpi-galenet lpi-gosh lpi-greenbea lpi-itest2 lpi-itest6 lpi-mondou2 lpi-pang lpi-pilot4i lpi-reactor lpi-woodinfe cTx∗ cTx∗δ kx∗ k1 3.6e+02 5.4e+01 1.9e+01 1.0e+00 2.5e−01 9.8e+03 3.2e+06 1.0e+00 1.0e+00 8.0e+02 2.8e+01 4.0e−02 5.2e+02 4.5e+00 2.0e+05 1.7e+04 2.4e−01 3.3e+01 2.0e+00 1.5e+01 3.6e+02 5.4e+01 1.9e+01 1.0e+00 2.5e−01 9.8e+03 3.2e+06 1.0e+00 1.0e+00 8.0e+02 2.8e+01 4.0e−02 5.2e+02 4.5e+00 2.0e+05 1.7e+04 2.4e−01 3.3e+01 2.0e+00 1.5e+01 1.6e+04 6.0e+03 4.7e+03 5.2e+02 8.8e+02 1.5e+05 2.4e+09 4.8e+02 4.6e+02 4.0e+05 1.0e+02 1.5e+04 1.4e+06 2.3e+01 4.8e+05 3.2e+06 1.4e+06 6.9e+05 1.5e+06 3.6e+03 kx∗δ k1 1.3e+04 5.3e+03 ց 3.0e+03 ց 2.6e+02 → 8.8e+02 ց 3.8e+04 ց 1.5e+09 ց 3.0e+02 ց 3.0e+02 → 4.0e+05 ց 9.2e+01 ց 7.1e+03 ց 5.6e+05 → 2.3e+01 ց 4.6e+05 ց 2.7e+06 ց 8.2e+04 ց 5.1e+04 ց 1.1e+06 ց 2.0e+03 ց ց kx∗ k0 518 633 25 261 1780 711 3811 215 211 54 10 9580 3658 7 12 297 536 773 569 60 kx∗δ k0 437 441 ց 20 → 261 ց 1767 ց 591 ց 3489 → 215 → 211 → 54 ր 11 ց 1075 ց 1609 → 7 ր 14 ց 244 ց 336 ց 627 ց 357 ր 87 ց ց δ̄ 3.3e−03 3.4e−04 3.7e−01 9.9e−01 6.7e−04 3.1e−01 1.0e−02 1.6e−01 1.6e−01 1.2e−03 6.3e−01 3.9e−05 1.1e−04 6.5e−01 4.8e−01 9.5e−02 1.4e−06 3.6e−06 4.1e−05 5.0e−01 δ̄ := 1/µ∗ . Finally, we solve (6.6) with δ = δ̄/2 to obtain x∗δ . All three problems—(P), (6.6), and (6.7)—are solved using the Matlab toolbox SeDuMi (version 1.05) [43], which is a C implementation of a log-barrier primal-dual interior-point algorithm for solving SDP/SOCP. The test instances are drawn from the DIMACS Implementation Challenge library [37], a collection of nontrivial medium-to-large SDP/SOCP arising from applications. We omit those instances for which either (P) is infeasible (e.g., filtinf1) or if one of (P), (6.6), (6.7) cannot be solved because of insufficient memory (e.g., torusg3-8). All runs were performed on a PowerPC G5 with 2GB of memory running Matlab 7.3b. Table 6.3 summarizes the results. For most of the instances, SeDuMi finds only an inaccurate solution (info.numerr=1) for at least one of (P), (6.6), (6.7). For most instances, however, SeDuMi also finds a value of µ∗ that seems reasonable. In some instances (nb_L2_bessel, nql30, nql80, qssp30, qssp60, qssp180, sch_100_100_scal, sch_200_100_scal, truss8), the computed multiplier µ∗ is quite large relative to the solution accuracy, and yet cTx∗δ matches cTx∗ in the first three significant digits; this suggests that the regularization is effectively exact. For nb_L2, sch_100_50_scal, and sch_100_100_orig, the discrepancies between cTx∗δ and cTx∗ may be attributed to a SeDuMi numerical failure or primal infeasibility in solving either (P) or (6.7) (thus yielding inaccurate µ∗ ), or (6.6). For hinf12, SeDuMi solved all three problems accurately, and µ∗ looks reasonable, whereas for hinf13, SeDuMi solved all three problems inaccurately, but µ∗ still looks reasonable. Yet cTx∗δ is lower than cTx∗ in both instances. We do not yet have an explanation for this. The regularized solution x∗δ has a one-norm lower than or equal to that of the unregularized solution x∗ in all instances except hinf12, where kx∗δ k1 is 1% higher (this small difference does not appear in Table 6.3). Solution sparsity is measured by 20 MICHAEL P. FRIEDLANDER AND PAUL TSENG Table 6.3 Least one-norm solutions of the feasible DIMACS SDP/SOCPs. Three different types of SeDuMi failures are reported: a numerical error; b primal infeasibility detected in solving (6.7); c numerical error in solving (6.7). The “schedule” instances have been abbreviated from sched 100 50 orig to sch 100 50 o, etc. SDP/SOCP nb nb L1 nb L2 nb L2 bessel copo14 copo23 filter48 socp minphase hinf12 hinf13 nql30 nql60 nql180 nql30old nql60old nql180old qssp30 qssp60 qssp180 sch 50 50 o sch 50 50 s sch 100 50 o sch 100 50 s sch 100 100 o sch 100 100 s sch 200 100 o sch 200 100 s truss5 truss8 cTx∗ -5.07e−02 -1.30e+01 -1.63e+00 -1.03e−01 -3.11e−12 -8.38e−12 1.42e+00 5.98e+00 -3.68e−02 -4.53e+01 -9.46e−01 -9.35e−01 -9.28e−01 -9.46e−01 -9.35e−01 a -9.31e−01 -6.50e+00 -6.56e+00 -6.64e+00 2.67e+04 7.85e+00 1.82e+05 6.72e+01 7.17e+05 2.73e+01 1.41e+05 5.18e+01 1.33e+02 1.33e+02 cTx∗δ kx∗ k1 -5.07e−02 -1.30e+01 -1.63e+00 -1.03e−01 -2.13e−10 -3.73e−09 1.42e+00 5.98e+00 -7.11e−02 -4.51e+01 -9.46e−01 -9.35e−01 -9.28e−01 -9.46e−01 -9.35e−01 a -9.29e−01 -6.50e+00 -6.56e+00 -6.64e+00 2.67e+04 7.85e+00 1.82e+05 b 8.69e+01 a 3.95e+02 2.73e+01 1.41e+05 5.18e+01 1.33e+02 1.33e+02 2.2e+0 3.1e+3 3.1e+1 1.0e+1 4.6e+0 6.6e+0 7.6e+2 1.6e+1 1.0e+0 2.8e+4 5.8e+3 2.3e+4 2.1e+5 5.5e+3 2.2e+4 1.9e+5 4.5e+3 1.8e+4 1.6e+5 5.6e+4 1.1e+2 4.9e+5 6.0e+4 1.8e+6 1.6e+5 4.4e+5 7.8e+4 2.1e+3 7.9e+3 ց kx∗δ k1 kx∗ k0 kx∗δ k0 2.1e+0 142 2407 847 131 2128 9430 3284 2304 138 322 6301 25201 226776 7502 29515 227097 7383 29163 260283 1990 497 3131 5827 12726 17574 24895 37271 3301 11914 139 1613 → 847 ր 133 ց 224 ց 575 ց 3282 → 2304 ր 194 ց 318 → 6301 → 25201 ց 226767 ց 6244 ց 23854 ց 211744 → 7383 → 29163 → 260283 ր 2697 ր 600 ց 3040 ր 7338 ր 18240 ց 16488 ց 16561 ց 37186 → 3301 ց 11911 → 3.1e+3 → 3.1e+1 9.7e+0 2.0e+0 ց 2.0e+0 → 7.6e+2 → 1.6e+1 → 1.0e+0 ց 2.1e+4 ց 2.8e+3 ց 1.1e+4 ց 1.0e+5 ց 1.0e+3 ց 4.0e+3 ց 6.8e+4 → 4.5e+3 → 1.8e+4 → 1.6e+5 → 5.6e+4 → 1.1e+2 → 4.9e+5 ց 1.3e+4 ց 8.4e+2 → 1.6e+5 → 4.4e+5 → 7.8e+4 ց 1.5e+3 ց 5.2e+3 ց ց ց ց δ̄ 7.6e−3 1.2e−5 2.1e−5 2.7e−6 4.7e−1 4.7e−1 1.1e−6 5.8e−2 5.1e+0 2.8e−4 1.0e−7 1.4e−6 6.3e−8 3.2e−5 2.0e−5 1.4e−8 4.1e−7 1.2e−6 c 3.8e−7 8.7e−3 1.1e−5 2.4e−4 6.1e−3 1.3e−0 1.8e−8 4.3e−4 4.0e−8 1.6e−5 1.7e−7 the zero-norm defined in (6.4), where ǫ is based on the relative optimality gap ǫ= cTx∗δ − bTyδ∗ 1 + kbkkyδ∗ k + kckkx∗δ k of the computed solution of (6.6). For 52% of the instances, the regularized solution is sparser than the unregularized solution. For 28% of the instances, the solutions have the same sparsity. For the remaining six instances, the regularized solution is actually less sparse, even though its one-norm is lower (nb_L2_bessel, sch_100_50_s, sch_100_100_o) or the same (hinf12, sch_50_50_o, sch_50_50_s). SeDuMi implements an interior-point algorithm, so it is likely to find the analytic center of the solution set of (P). The selection problem (6.7) is generally much harder to solve than (P) or (6.6). For example, on nb_L2_bessel, SeDuMi took 18, 99, and 16 iterations to solve (P), (6.7), and (6.6), respectively, and on truss8 SeDuMi took, respectively, 24, 117, and EXACT REGULARIZATION OF CONVEX PROGRAMS 21 35 iterations. This seems to indicate that regularization is more efficient than solving the selection problem as a method for finding sparse solutions. 7. Discussion. We see from the numerical results in §6 that regularization can provide an effective way of selecting a solution with desirable properties, such as sparsity. However, finding the threshold value δ̄ for exact regularization entails first solving (P) to obtain p∗ , and then solving (Pφ ) to obtain µ∗ and setting δ̄ = 1/µ∗ ; see Corollary 2.2. Can we find a δ < δ̄ from (P) without also solving (Pφ )? Consider the case of a CP, in which f and C have the form (1.1). Suppose that a value of δ < δ̄ has been guessed (with δ̄ unknown), and a solution x∗ of the regularized problem (Pδ ) is obtained. By Corollary 2.2, x∗ is also a solution of (Pφ ). Suppose also that there exist Lagrange multipliers y ∗ ∈ Rm and z ∗ ∈ K∗ for (P), where K∗ is the dual cone of K given by K∗ := {y ∈ Rn | y Tx ≥ 0 for all x ∈ K}. Then (y ∗ , z ∗ ) satisfy, among other conditions, ATy ∗ + z ∗ = c and bTy ∗ = p∗ . Suppose, furthermore, that there exist Lagrange multipliers yφ∗ ∈ Rm , zφ∗ ∈ K∗ , and µ∗ ≥ 0 for (Pφ ) that satisfy, among other conditions, 0 ∈ ∂φ(x∗ ) − (ATyφ∗ + zφ∗ − µ∗ c). Then, analogous to the proof of Theorem 2.1, we can construct Lagrange multipliers for (Pδ ) as follows: Case 1: µ∗φ = 0. The Lagrange multipliers for (Pδ ) are given by yδ∗ := y ∗ + δyφ∗ and zδ∗ := z ∗ + δzφ∗ . Case 2: µ∗φ > 0. The Lagrange multipliers for (Pδ ) are given by yδ∗ := (1 − λ)y ∗ + λ ∗ y µ∗φ φ and zδ∗ := (1 − λ)z ∗ + λ ∗ z , µ∗φ φ for any λ ∈ [0, 1]. The Lagrange multipliers (yδ∗ , zδ∗ ) obtained for the regularized problem are therefore necessarily perturbed. Therefore, it is not possible to test the computed triple (x∗ , yδ∗ , zδ∗ ) against the optimality conditions for the original CP in order to verify that x∗ is indeed an exact solution. In practice, if it were prohibitively expensive to solve (P) and (Pφ ), we might adopt an approach suggested by Lucidi [27] and Mangasarian [33] for Tikhonov regularization. They suggest solving the regularized problem successively with decreasing values δ1 > δ2 > · · · . If successive regularized solutions do not change, then it is likely that a correct regularization parameter has been obtained. We note that in many instances, the threshold values δ̄ shown in Tables 6.1 and 6.2 are comfortably large, and a value such as δ = 10−4 would cover 85% of the these cases. Acknowledgments. Sincere thanks to Dimitri Bertsekas for suggesting Lemma 4.1(a) and bringing to our attention the paper [4]. We also thank Kevin LeytonBrown for generously giving us access to his CPLEX installation for the numerical experiments presented in §6. 22 MICHAEL P. FRIEDLANDER AND PAUL TSENG x2 x3 x2 S C Sk (1, 1/k, 0) (1/k, 0, 0) x1 (a) x1 (b) Fig. 8.1. (a) The feasible set C. (b) The solution set S and S k . 8. Appendix. In this appendix, we give an example of f and C that satisfy the assumptions of Theorem 5.2 and for which weak sharp minimum fails to hold and yet exact regularization holds for φ(x) = kx − xbk22 and any xb ∈ ℜn . Consider the example n = 3, f (x) = x3 , and k C = [0, 1]3 ∩ ∩∞ , k=2 C where C k = {x ∈ R3 | x1 − (k − 1)x2 − k 2 x3 ≤ 1/k}. Each C k is a half-space in R3 , so C is a closed convex set. Moreover, C is bounded and nonempty (since 0 ∈ C); see Figure 8.1(a). Clearly p∗ = 0 and S = {x ∈ C | x3 = 0}. (8.1) First, we show that weak sharp minimum fails to hold, i.e., there does not exist τ > 0 such that (5.1) holds with γ = 1. Let H k be the hyperplane forming the boundary set of C k , i.e., H k = {x ∈ R3 | x1 − (k − 1)x2 − k 2 x3 = 1/k}. Let xk be the intersection point of H k , H k+1 and the x1 x3 -plane. Direct calculation yields xk1 = 1 − (1 + 1/k)−3 , k(1 − (1 + 1/k)−2 ) xk2 = 0, xk3 = xk1 − 1/k , k2 (8.2) for k = 2, 3, . . . . Since C ⊂ C k , we have from (8.1) that S ⊂ S k , where we let S k = {x ∈ C k | x3 = 0}; see Figure 8.1(b). Thus dist(xk , S) ≥ dist(xk , S k ) ≥ dist((xk1 , 0, 0), S k ). 3 (8.3) 3 k k Since limα→1 1−α 1−α2 = 2 , (8.2) implies that kx1 → 3/2, i.e., x1 = 1.5/k + o(1/k). The point in S k nearest to (xk1 , 0, 0) lies on the line through (1/k, 0, 0) and (1, 1/k, 0) (with slope 1/(k − 1) in the x1 x2 -plane), from which it follows that dist((xk1 , 0, 0), S k ) = 0.5/k 2 +o(1/k 2 ). Since xk3 = 1.5/k 3 +o(1/k 3 ) by (8.2), this together with (8.3) implies xk3 xk3 ≤ = O(1/k) → 0. dist(xk , S k ) dist((xk1 , 0, 0), S k ) EXACT REGULARIZATION OF CONVEX PROGRAMS 23 Moreover, for any ℓ ∈ {2, 3, . . . }, we have from (8.2) and letting α = ℓ/k that xk1 − (ℓ − 1)xk2 − ℓ2 xk3 − 1 1 = 1 − α2 xk1 − 1 − α3 ℓ ℓ 1 = (1 − α) (1 + α)xk1 − 1 + α + α2 ℓ 1 − (1 + 1/k)−3 1 (1 − α) 2 (1 + α) − 1 + α + α = k 1 − (1 + 1/k)−2 α −2 1 (1 + 1/k) (1 − α) − (1 + α) = k 1 + (1 + 1/k)−1 α(1 + α) 2 2 2 k k (1 − α ) − = k (2k + 1)(k + 1) ℓ(k + ℓ) 2 (1 − α ) (2k + ℓ + 1)(ℓ − k − 1) = , k (2k + 1)(k + 1)ℓ(k + ℓ) where the second equality uses 1 − α2 = (1 − α)(1 + α), 1 − α3 = (1 − α)(1 + α + α2 ); the fourth equality uses the same identities but with (1 + 1/k)−1 in place of α. By considering the two cases ℓ ≤ k and ℓ ≥ k + 1, it is readily seen that the above right-hand side is non-positive. This in turn shows that xk ∈ C ℓ for ℓ = 2, 3, . . . , and hence xk ∈ C. Second, fix any xb ∈ R3 and let φ(x) = kx − xbk22 . Let x∗ = arg minx∈S φ(x) and fδ (x) = f (x) + δφ(x). Suppose x∗ 6= 0. Then C is polyhedral in a neighborhood N of x∗ . Since xδ = arg minx∈C fδ (x) converges to x∗ as δ → 0, we have that xδ ∈ C ∩ N for all δ > 0 below some positive threshold, in which case exact regularization holds (see Corollary 2.3). Suppose x∗ = 0. Then xb = −∇φ(x∗ ) ∈ NS (x∗ ) = (−∞, 0]2 × R, where the second equality follows from [0, ∞)2 × {0} being the tangent cone of S at 0. Thus xb2 ≤ 0, xb3 ≤ 0 and we see from ∇fδ (x∗ ) = (0, 0, 1)T − δ xb that ∇fδ (x∗ ) ≥ 0 for all δ ∈ [0, δ̄], where δ̄ = ∞ if xb3 ≤ 0 and δ̄ = 1/b x3 if xb3 > 0. Because C ⊂ [0, ∞)3 this implies that, for δ ∈ [0, δ̄], ∇fδ (x∗ )T(x − x∗ ) = ∇fδ (x∗ )Tx ≥ 0 for all x ∈ C. Because x∗ ∈ C and fδ is strictly convex for δ ∈ (0, δ̄], this implies that x∗ = arg minx∈C fδ (x) for all δ ∈ (0, δ̄]. Hence exact regularization holds. REFERENCES [1] A. Altman and J. Gondzio, Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11 (1999), pp. 275–302. [2] F. R. Bach, R. Thibaux, and M. I. Jordan, Computing regularization paths for learning multiple kernels, in Advances in Neural Information Processing Systems (NIPS) 17, L. Saul, Y. Weiss, and L. Bottou, eds., Morgan Kaufmann, San Mateo, CA, 2005. [3] A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2 of MPS/SIAM Series on Optimization, Society of Industrial and Applied Mathematics, Philadelphia, 2001. 24 MICHAEL P. FRIEDLANDER AND PAUL TSENG [4] D. P. Bertsekas, Necessary and sufficient conditions for a penalty method to be exact, Math. Program., 9 (1975), pp. 87–99. , Constrained Optimization and Lagrange Multiplier Methods, Academic Press, New [5] York, 1982. [6] , A note on error bounds for convex and nonconvex programs, Comput. Optim. Appl., 12 (1999), pp. 41–51. [7] D. P. Bertsekas, A. Nedić, and A. E. Ozdaglar, Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 2003. [8] S. Boyd and L. Vandenberghe, Convex Optimization, Cambridge University Press, New York, 2004. [9] J. V. Burke, An exact penalization viewpoint of constrained optimization, SIAM J. Control Optim., 29 (1991), pp. 968–998. [10] J. V. Burke and S. Deng, Weak sharp minima revisited. II. Application to linear regularity and error bounds, Math. Program., 104 (2005), pp. 235–261. [11] J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM J. Control Optim., 31 (1993), pp. 1340–1359. [12] E. J. Candés, J. Romberg, and T. Tao, Stable signal recovery from incomplete and inaccurate measurements. To appear in Comm. Pure Appl. Math., 2005. , Robust uncertainty principles: Exact signal reconstruction from highly incomplete fre[13] quency information, IEEE Trans. Info. Theory, 52 (2006), pp. 489–509. [14] S. S. Chen, D. L. Donoho, and M. A. Saunders, Atomic decomposition by basis pursuit, SIAM Rev., 43 (2001), pp. 129–159. [15] A. R. Conn, N. I. M. Gould, and Ph. L. Toint, Trust-Region Methods, MPS-SIAM Series on Optimization, Society of Industrial and Applied Mathematics, Philadelphia, 2000. [16] D. L. Donoho and M. Elad, Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization, Proc. Nat. Acad. Sci. USA, 100 (2003), pp. 2197–2202. [17] D. L. Donoho, M. Elad, and V. Temlyakov, Stable recovery of sparse overcomplete representations in the presence of noise, IEEE Trans. Info. Theory, 52 (2006), pp. 6–18. [18] D. L. Donoho and J. Tanner, Sparse nonnegative solution of underdetermined linear equations by linear programming, Proc. Nat. Acad. Sci. USA, 102 (2005), pp. 9446–9451. [19] B. Efron, T. Hastie, I. Johnstone, and R. Tibshirani, Least angle regression, Ann. Statist., 32 (2004), pp. 407–499. [20] M. C. Ferris and O. L. Mangasarian, Finite perturbation of convex programs, Appl. Math. Optim., 23 (1991), pp. 263–273. [21] R. Fletcher, An ℓ1 penalty method for nonlinear constraints, in Numerical Optimization 1984, P. T. Boggs, R. H. Byrd, and R. B. Schnabel, eds., Philadelphia, 1985, Society of Industrial and Applied Mathematics, pp. 26–40. [22] , Practical Methods of Optimization, John Wiley and Sons, New York, second ed., 1987. [23] C. C. Gonzaga, Generation of degenerate linear programming problems, tech. rep., Dept. of Mathematics, Federal University of Santa Catarina, Brazil, April 2003. [24] S.-P. Han and O. L. Mangasarian, Exact penalty functions in nonlinear programming, Math. Program., 17 (1979), pp. 251–269. [25] C. Kanzow, H. Qi, and L. Qi, On the minimum norm solution of linear programs, J. Optim. Theory Appl., 116 (2003), pp. 333–345. [26] S. Lucidi, A finite algorithm for the least two-norm solution of a linear program, Optimization, 18 (1987), pp. 809–823. [27] , A new result in the theory and computation of the least-norm solution of a linear program, J. Optim. Theory Appl., 55 (1987), pp. 103–117. [28] Z.-Q. Luo and J.-S. Pang, Error bounds for analytic systems and their applications, Math. Program., 67 (1994), pp. 1–28. , eds., Error bounds in mathematical programming, Math. Program., vol. 88, 2000. [29] [30] O. L. Mangasarian, Normal solutions of linear programs, Math. Program. Study, 22 (1984), pp. 206–216. [31] , Sufficiency of exact penalty minimization, SIAM J. Control Optim., 23 (1985), pp. 30– 37. [32] , A simple characterization of solution sets of convex programs, Oper. Res. Lett., 7 (1988), pp. 21–26. [33] , A Newton method for linear programming, J. Optim. Theory Appl., 121 (2004), pp. 1– 18. [34] O. L. Mangasarian and R. R. Meyer, Nonlinear perturbation of linear programs, SIAM J. Control Optim., 17 (1979), pp. 745–752. [35] Y. E. Nesterov and A. Nemirovski, Interior-Point Polynomial Algorithms in Convex Pro- EXACT REGULARIZATION OF CONVEX PROGRAMS [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] 25 gramming, vol. 14 of Studies in Applied Mathematics, Society of Industrial and Applied Mathematics, Philadelphia, 1994. NETLIB linear programming library, 2006. G. Pataki and S. Schmieta, The DIMACS library of semidefinite-quadratic-linear programs, Tech. Rep. Preliminary draft, Computational Optimization Research Center, Columbia University, New York, July 2002. J. Renegar, A Mathematical View of Interior-Point Methods in Convex Optimization, MPS/SIAM Series on Optimization, Society of Industrial and Applied Mathematics, Philadelphia, 2001. S. M. Robinson, Local structure of feasible sets in nonlinear programming, part II: Nondegeneracy, Math. Program. Study, 22 (1984), pp. 217–230. R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970. S. Sardy and P. Tseng, On the statistical analysis of smoothing by maximizing dirty markov random field posterior distributions, J. Amer. Statist. Assoc., 99 (2004), pp. 191–204. M. A. Saunders, Cholesky-based methods for sparse least squares: The benefits of regularization, in Linear and Nonlinear Conjugate Gradient-Related Methods, L. Adams and J. L. Nazareth, eds., Society of Industrial and Applied Mathematics, Philadelphia, 1996, pp. 92–100. J. F. Sturm, Using Sedumi 1.02, a Matlab toolbox for optimization over symmetric cones (updated for Version 1.05), tech. rep., Department of Econometrics, Tilburg University, Tilburg, The Netherlands, August 1998 – October 2001. R. Tibshirani, Regression shrinkage and selection via the Lasso, J. Royal. Statist. Soc B., 58 (1996), pp. 267–288. A. N. Tikhonov and V. Y. Arsenin, Solutions of Ill-Posed Problems, V. H. Winston and Sons, Washington, D.C., 1977. Translated from Russian. Z. Wu and J. J. Ye, On error bounds for lower semicontinuous functions, Math. Program., 92 (2002), pp. 301–314. Y. Ye, Interior-Point Algorithms: Theory and Analysis, Wiley, Chichester, UK, 1997. Y.-B. Zhao and D. Li, Locating the least 2-norm solution of linear programs via a pathfollowing method, SIAM J. Optim., 12 (2002), pp. 893–912.