×

zbMATH — the first resource for mathematics

A perturbation view of level-set methods for convex optimization. (English) Zbl 07311801
Summary: Level-set methods for convex optimization are predicated on the idea that certain problems can be parameterized so that their solutions can be recovered as the limiting process of a root-finding procedure. This idea emerges time and again across a range of algorithms for convex problems. Here we demonstrate that strong duality is a necessary condition for the level-set approach to succeed. In the absence of strong duality, the level-set method identifies \(\epsilon\)-infeasible points that do not converge to a feasible point as \(\epsilon\) tends to zero. The level-set approach is also used as a proof technique for establishing sufficient conditions for strong duality that are different from Slater’s constraint qualification.
MSC:
90C25 Convex programming
90C46 Optimality conditions and duality in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aravkin, AY; Burke, J.; Friedlander, MP, Variational properties of value functions, SIAM J. Optim., 23, 3, 1689-1717 (2013) · Zbl 1286.65071
[2] Aravkin, AY; Burke, JV; Drusvyatskiy, D.; Friedlander, MP; Roy, S., Level-set methods for convex optimization, Math Progr. Ser. B, 174, 1-2, 359-390 (2018) · Zbl 1421.90111
[3] Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, MPS/SIAM Series on Optimization, vol (2001) · Zbl 0986.90032
[4] Society of Industrial and Applied Mathematics, Philadelphia
[5] van den Berg, E., Friedlander, M.P.: SPGL1: A solver for large-scale sparse reconstruction. http://www.cs.ubc.ca/labs/scl/spgl1 (2007)
[6] van den Berg, E.; Friedlander, MP, Probing the pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, 890-912 (2008) · Zbl 1193.49033
[7] van den Berg, E.; Friedlander, MP, Probing the Pareto frontier for basis pursuit solutions, SIAM J. Sci. Comput., 31, 2, 890-912 (2008) · Zbl 1193.49033
[8] van den Berg, E.; Friedlander, MP, Sparse optimization with least-squares constraints, SIAM J. Optim., 21, 4, 1201-1229 (2011) · Zbl 1242.49061
[9] van den Berg, E., Friedlander, M.P.: SPGL1: A solver for large-scale sparse reconstruction. https://www.cs.ubc.ca/ mpf/spgl1/ (2013)
[10] Borwein, J.; Lewis, AS, Convex analysis and nonlinear optimization: theory and examples (2010), Berlin: Springer, Berlin
[11] Boyd, S., Vandenberghe, L.: Convex optimization. Cambridge University Press, Cambridge (2004). 10.1017/CBO9780511804441. · Zbl 1058.90049
[12] Candès, EJ; Strohmer, T.; Voroninski, V., PhaseLift: exact and stable signal recovery from magnitude measurements via convex programming, Commun. Pure Appl. Math., 66, 8, 1241-1274 (2013) · Zbl 1335.94013
[13] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM J. Sci. Comput., 20, 1, 33-61 (1998) · Zbl 0919.94002
[14] Chen, SS; Donoho, DL; Saunders, MA, Atomic decomposition by basis pursuit, SIAM Rev., 43, 1, 129-159 (2001) · Zbl 0979.94010
[15] Conn, A.R., Gould, N.I.M., Toint, PhL: Trust-Region Methods. Society of Industrial and Applied Mathematics, Philadelphia, MPS-SIAM Series on Optimization (2000)
[16] Higham, N.J.: Accuracy and stability of numerical algorithms, vol. 80. Society for Industrial and Applied Mathematics, (2002) · Zbl 1011.65010
[17] Lemaréchal, C.; Nemirovskii, A.; Nesterov, Y., New variants of bundle methods, Math. Program., 69, 111-147 (1995) · Zbl 0857.90102
[18] Markowitz, H.M.: Mean-Variance Analysis in Portfolio Choice and Capital Markets. Frank J, Fabozzi Associates, New Hope, Pennsylvania (1987)
[19] Marquardt, D., An algorithm for least-squares estimation of nonlinear parameters, SIAM J. Appl. Math., 11, 431-441 (1963) · Zbl 0112.10505
[20] Morrison, D.D.: Methods for nonlinear least squares problems and convergence proofs. In: Lorell J, Yagi F (eds) Proceedings of the Seminar on Tracking Programs and Orbit Determination, Jet Propulsion Laboratory, Pasadena, USA, pp 1-9 (1960)
[21] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton
[22] Rockafellar, R.T., Wets, R.J.B.: Variational Analysis, vol 317. Springer, 3rd printing (1998) · Zbl 0888.49001
[23] Waldspurger, I.; d’Aspremont, A.; Mallat, S., Phase recovery, maxcut and complex semidefinite programming, Math. Program., 149, 1-2, 47-81 (2015) · Zbl 1329.94018
[24] Wiegert, J.: The sagacity of circles: A history of the isoperimetric problem. https://www.maa.org/press/periodicals/convergence/the-sagacity-of-circles-a-history-of-the-isoperimetric-problem, accessed: 2018-07-25 (2010)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.