Path following in the exact penalty method of convex programming

DOI10.1007/S10589-015-9732-XzbMATH Open1343.90063DBLPjournals/coap/ZhouL15arXiv1201.3593OpenAlexW2115944913WikidataQ36047827 ScholiaQ36047827MaRDI QIDQ493687FDOQ493687

Authors: Hua Zhou, Kenneth Lange 

Publication date: 4 September 2015

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

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 $infty$, 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.

Full work available at URL: https://arxiv.org/abs/1201.3593

Recommendations

• A path following algorithm for a class of convex programming problems
• Penalty/barrier path-following in linearly constrained optimization
• Path-Following Methods for Linear Programming
• An inexact proximal path-following algorithm for constrained convex minimization
• Publication:4863214
• Path-following Methods for a Class of Constrained Minimization Problems in Function Space
• A weighted path-following method for linearly constrained convex programming
• Exterior minimum-penalty path-following methods in semidefinite programming
• Path-following barrier and penalty methods for linearly constrained problems

zbMATH Keywords

convex programmingexact penaltypath following

Mathematics Subject Classification ID

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

Cites Work

• Nonlinear total variation based noise removal algorithms
• Least angle regression. (With discussion)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The solution path of the generalized lasso
• Linear and nonlinear programming.
• Algorithms and applications for approximate nonnegative matrix factorization
• A new approach to variable selection in least squares problems
• Title not available (Why is that?)
• Semidefinite Programming
• The Split Bregman Method for L1-Regularized Problems
• Numerical analysis for statisticians
• Learning the parts of objects by non-negative matrix factorization
• An algorithm for total variation minimization and applications
• Nonlinear optimization.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Best approximation in inner product spaces
• An Algorithm for Restricted Least Squares Regression
• Title not available (Why is that?)
• A tutorial on geometric programming
• Interior Methods for Nonlinear Optimization
• Non-Linear Programming Via Penalty Functions
• MM algorithms for geometric and signomial programming
• Title not available (Why is that?)
• Title not available (Why is that?)
• Theory of globally convergent probability-one homotopies for nonlinear programming
• Digital Circuit Optimization via Geometric Programming
• Numerical Linear Algebra Aspects of Globally Convergent Homotopy Methods
• On the Bumpy Road to the Dominant Mode
• The geometric programming dual to the extinction probability problem in simple branching processes
• Geometric Programming: Methods, Computations and Applications
• Maximum likelihood estimates for multinomial probabilities via geometric programming
• Geometric Programming
• A generic path algorithm for regularized statistical estimation

Cited In (9)

• Path-following barrier and penalty methods for linearly constrained problems
• Path-Following Methods for Linear Programming
• On the structure of regularization paths for piecewise differentiable regularization terms
• Iterative Method for Non-Stationary Mixed Variational Inequalities
• Several path-following methods for a class of gradient constrained variational inequalities
• Title not available (Why is that?)
• Path-following Methods for a Class of Constrained Minimization Problems in Function Space
• Title not available (Why is that?)
• MM algorithms for geometric and signomial programming

Uses Software

• Matlab
• ConvexLAR

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)