Exact regularization of convex programs

M. P. Friedlander, P. Tseng
SIAM Journal on Optimization, 18(4):1326–1350, 2007

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

Experiments

To reproduce the experiments in this paper, download the following file:

cpreg.zip (2M)

This archive contains the AMPL data files which fully describe the LPs, and the DIMACS SDPs and SOCPs used in the numerical experiments. It also contains Matlab and Python scripts that generate the data needed to reproduce the tables in the report. To unpack the archive and solve the unregularized and regularized versions of the LPs described in the paper, run (from the commandline)

>> unzip cpreg.zip
>> cd cpreg
>> python run_random_lps.py
>> python run_infeas_lps.py

Note that you will need Ampl and CPLEX installed. The data for Tables 6.1 ad 6.2 of the paper can now be found in the files lp_sparse.out and lp_infeas.out, respectively. To solve the unregularized and regularized version of the SDPs and SOCPs, run (from within Matlab)

>> rundimacs

You will need to have SeDuMi installed.

BiBTeX

@article{FrieTsen:2007,
  author = {Michael P. Friedlander and Paul Tseng},
  title = {Exact Regularization of Convex Programs},
  publisher = {SIAM},
  year = {2007},
  journal = {SIAM Journal on Optimization},
  volume = {18},
  number = {4},
  pages = {1326-1350},
  keywords = {convex program; conic program; linear program;
    regularization; exact penalization;
    Lagrange multiplier; degeneracy; sparse solutions;
    interior-point algorithms},
  url = {http://link.aip.org/link/?SJE/18/1326/1},
  doi = {10.1137/060675320}
}