Path Following in the Exact Penalty Method of Convex Programming

Area of Science:

• Optimization
• Numerical Analysis
• Applied Mathematics

Background:

• Classical penalty methods iteratively approximate constrained solutions.
• Exact penalty methods use absolute value penalties for finite solutions but face practical challenges.
• Existing methods struggle with the unknown penalty constant and kinks in the penalty function.

Purpose of the Study:

• To introduce and examine a path-following strategy for constrained optimization.
• To overcome limitations of traditional exact penalty methods in nonlinear programming.
• To demonstrate the versatility of path following across diverse optimization problems and inverse problems.

Main Methods:

• Tracing the solution as a continuous function of the penalty constant.
• Starting from the unconstrained solution and increasing the penalty constant.
• Numerically solving ordinary differential equations for piecewise smooth paths in general convex programming.

Main Results:

• Path following successfully traces solutions for various optimization problems, including quadratic programming and convex programming.
• The method demonstrates piecewise linear and piecewise smooth solution paths.
• Applications include projection onto convex sets, nonnegative least squares, and semidefinite programming.

Conclusions:

• Path following provides a robust alternative to traditional penalty methods.
• The strategy is effective for a wide range of optimization problems and regularized estimation in inverse problems.
• This approach offers a unified framework for solving constrained optimization and inverse problems.