Exact regularization of convex programs

TitleExact regularization of convex programs
Publication TypeJournal Article
Year of Publication2007
AuthorsMichael P. Friedlander, Paul Tseng
JournalSIAM Journal on Optimization
Volume18
Number4
Page1326-1350
Month05
KeywordsOptimization, SLIM
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 [Appl. Math. Optim., 23(1991), pp. 266–273] involving a linearized selection problem. We also use it to derive necessary and sufficient conditions for exact penalization, similar to those obtained by Bertsekas [Math. Programming, 9(1975), pp. 87–99] and by Bertsekas, Nedi , Ozdaglar [Convex Analysis and Optimization, Athena Scientific, Belmont, MA, 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.

URLhttp://www.cs.ubc.ca/ mpf/2007-exact-regularization.html
DOI10.1137/060675320
Citation Keyfriedlander2007SJOero