# The ICICS/CS Reading Room

## UBC CS TR-2006-26 Summary

- Exact regularization of convex programs, November 18, 2006 Michael P. Friedlander and Paul Tseng, 25 pages
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\'c, 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.

If you have any questions or comments regarding this page please send mail to
help@cs.ubc.ca.