Optimization Online


Exact regularization of convex programs

Michael P. Friedlander (mpf***at***cs.ubc.ca)
Paul Tseng (tseng***at***math.washington.edu)

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, Nedic, 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 L1 regularization of benchmark (degenerate) linear programs and semidefinite/second-order cone programs. The experiments demonstrate the usefulness of L1 regularization in finding sparse solutions.

Keywords: convex program, conic program, linear program, regularization, exact penalization, Lagrange multiplier, degeneracy, sparse solutions, interior-point algorithms

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Department of Computer Science Tech. Rep. TR-2006-26, November 2006, University of British Columbia.

Download: [PDF]

Entry Submitted: 11/19/2006
Entry Accepted: 11/19/2006
Entry Last Modified: 11/19/2006

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society