Path following in the exact penalty method of convex programming

DOI10.1007/S10589-015-9732-XMaRDI QIDQ493687zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Hua Zhou, Kenneth Lange

Publication date 4 September 2015

Published in Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.3593, http://europepmc.org/articles/pmc4565725

zbMATH Keywords

convex programming exact penalty path following

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Convex programming (90C25)

Abstract: Classical penalty methods solve a sequence of unconstrained problems that put greater and greater stress on meeting the constraints. In the limit as the penalty constant tends to

i n f t y

, one recovers the constrained solution. In the exact penalty method, squared penalties are replaced by absolute value penalties, and the solution is recovered for a finite value of the penalty constant. In practice, the kinks in the penalty and the unknown magnitude of the penalty constant prevent wide application of the exact penalty method in nonlinear programming. In this article, we examine a strategy of path following consistent with the exact penalty method. Instead of performing optimization at a single penalty constant, we trace the solution as a continuous function of the penalty constant. Thus, path following starts at the unconstrained solution and follows the solution path as the penalty constant increases. In the process, the solution path hits, slides along, and exits from the various constraints. For quadratic programming, the solution path is piecewise linear and takes large jumps from constraint to constraint. For a general convex program, the solution path is piecewise smooth, and path following operates by numerically solving an ordinary differential equation segment by segment. Our diverse applications to a) projection onto a convex set, b) nonnegative least squares, c) quadratically constrained quadratic programming, d) geometric programming, and e) semidefinite programming illustrate the mechanics and potential of path following. The final detour to image denoising demonstrates the relevance of path following to regularized estimation in inverse problems. In regularized estimation, one follows the solution path as the penalty constant decreases from a large value.

Review text

The authors propose a following path method for constrained convex programming problems in the context of an exact penalty method. The path is parameterized by the penalty constant and consists of the optimal solutions of the corresponding penalized problems; the parameter increases from its initial value \(0\). The path is built by numerically solving a differential equation satisfied by the Lagrange multipliers of the penalized problems. The method is illustrated by several examples, including quadratic programming, geometric programming and semidefinite programming. The authors have developed a \textsc{Matlab} code, which they offer to share with interested researchers.

Recommendations

Cites work

Cited in

(11)

Describes a project that uses

Uses Software

This page was built for publication: Path following in the exact penalty method of convex programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q493687)