A perturbation view of level-set methods for convex optimization

R. Estrin, M. P. Friedlander
Optimization Letters, arXiv:2001.06511, 2020

PDF arXiv


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 ε-infeasible points that do not converge to a feasible point as ε 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.


  Author = {Ron Estrin and Michael P. Friedlander},
  Title = {A perturbation view of level-set methods for convex optimization},
  Year = {2020},
  Eprint = {arXiv:2001.06511},
  Note = {To appear in Optimization Letters}