A perturbation view of level-set methods for convex optimization
- PDF / 512,871 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 55 Downloads / 203 Views
A perturbation view of level-set methods for convex optimization Ron Estrin1 · Michael P. Friedlander2 Received: 21 January 2020 / Accepted: 4 June 2020 © The Author(s) 2020
Abstract 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. Keywords Convex analysis · Duality · Level-set methods
1 Introduction Duality in convex optimization may be interpreted as a notion of sensitivity of an optimization problem to perturbations of its data. Similar notions of sensitivity appear in numerical analysis, where the effects of numerical errors on the stability of the computed solution are of central concern. Indeed, backward-error analysis ([16], §1.5) describes the related notion that computed approximate solutions may be considered as exact solutions of perturbations of the original problem. It is natural, then, to ask if duality can help us understand the behavior of a class of numerical algorithms
B
Michael P. Friedlander [email protected] Ron Estrin [email protected]
1
Institute for Computational and Mathematical Engineering, Stanford University, Stanford, CA, USA
2
Department of Computer Science and Department of Mathematics, University of British Columbia, Vancouver, BC V6R 1Y8, Canada
123
R. Estrin, M. P. Friedlander
for convex optimization. In this paper, we describe how the level-set method [2,5,6] produces an incorrect solution when applied to a problem for which strong duality fails to hold. In other words, the level-set method cannot succeed if there does not exist a dual pairing that is tight. This failure of strong duality indicates that the stated optimization problem is brittle, in the sense that its value as a function of small perturbations to its data is discontinuous; this violates a vital assumption needed for the level-set method to succeed. Consider the convex optimization problem minimize f (x) subject to g(x) ≤ 0, x∈X
(P)
where f and g are closed proper convex functions that map Rn to the extended real line R ∪ {∞}, and X is a convex set in Rn . Let the optimal value τ p∗ of (P) be finite, which indicates that that (P) is feasible. In the context of level-set methods, we may think of the constraint g(x) ≤ 0 as representing a computational challenge. For example, there may not exist any efficient algorithm to compute the projection onto the constraint set { x ∈ X | g(x) ≤ 0 }. In many important cases, the objective function has a u
Data Loading...
