Path Following in the Exact Penalty Method of Convex Programming

Technical Summary: Path Following in the Exact Penalty Method of Convex Programming

Problem Statement
The paper addresses the challenge of solving constrained convex optimization problems, specifically minimizing a convex objective function $f(x)$ subject to affine equality constraints and convex inequality constraints. Classical penalty methods transform these into a sequence of unconstrained problems by adding a penalty term that grows indefinitely (typically quadratic), requiring the penalty constant $\rho \to \infty$ to recover the constrained solution. This often leads to ill-conditioning. The exact penalty method offers an alternative by replacing squared penalties with absolute value penalties (using $L_1$ norms for inequalities and equalities), theoretically recovering the exact constrained solution for a finite value of $\rho$. However, the non-differentiability (kinks) of the exact penalty function and the unknown magnitude of the required finite $\rho$ have historically hindered its practical application in nonlinear programming.

Methodology
The authors propose a path following strategy that circumvents the difficulties of the exact penalty method by treating the penalty constant $\rho$ as a continuous parameter. Instead of optimizing at a single, large $\rho$, the algorithm traces the solution $x(\rho)$ as a continuous function starting from the unconstrained solution ($\rho=0$) and increasing $\rho$ until the constraints are satisfied.

The core of the methodology relies on the following steps:

1. Stationarity Conditions: The solution path is characterized by the stationarity condition of the surrogate function $E_\rho(x) = f(x) + \rho \sum |g_i(x)| + \rho \sum \max\{0, h_j(x)\}$. This involves subgradients for the non-differentiable penalty terms.
2. Piecewise Smoothness: The solution path is piecewise smooth. "Kinks" occur when the solution hits a constraint boundary, slides along it, or exits it.
3. Ordinary Differential Equations (ODEs): Between kinks, the path is smooth. The authors derive an ODE that describes the evolution of the primal variables $x$ and the Lagrange multipliers ($\lambda, \omega$) with respect to $\rho$. This is achieved by applying the implicit function theorem to the system of stationarity and active constraint equations.
   • For general convex programs, the ODE involves the Hessian of the objective and the gradients of active constraints.
   • For Quadratic Programming (QP) with affine constraints, the path is piecewise linear, allowing for exact calculation of the next "event" (hitting or escaping a constraint) without numerical integration.
   • For general convex problems, the authors suggest using standard ODE solvers (e.g., Matlab's ODE45) to advance the solution segment by segment, correcting with Newton's steps if necessary.
4. Handling Rank Deficiency: In cases where the objective is not strictly convex or constraints are redundant (e.g., image denoising), the authors propose reparameterization (e.g., null-space methods or adding regularization terms) to ensure the invertibility of the system matrices required for the ODE.

Key Contributions

• Feasibility of Exact Path Following: The paper demonstrates that the non-differentiability of exact penalties is not a barrier to optimization if one follows the solution path continuously. The kinks are managed by detecting "events" where constraints become active or inactive.
• Derivation of Path ODEs: The authors provide a rigorous derivation of the differential equations governing the solution path for general convex programs, linking the change in the penalty constant to the change in primal and dual variables.
• Specialization to QP: The paper highlights that for quadratic programming with affine constraints, the path is piecewise linear, enabling highly efficient "large jump" algorithms similar to those used in Lasso regression.
• Diverse Applications: The framework is applied to a wide range of problems, including:
  • Projection onto convex sets.
  • Nonnegative Least Squares (NNLS) and Nonnegative Matrix Factorization (NNMF).
  • Quadratically Constrained Quadratic Programming (QCQP).
  • Geometric Programming (via log-exponential transformation).
  • Semidefinite Programming (SDP), utilizing the minimum eigenvalue as a convex constraint.
  • Image Denoising: The paper applies the method to the Rudin-Osher-Fatemi (ROF) model and anisotropic total variation, showing how the path following reveals the entire regularization path from a blank image to the denoised result.

Results
The paper presents numerical examples illustrating the mechanics of the algorithm:

• Projection: The path follows a vector field toward the feasible region, hitting and sliding along boundaries.
• NNLS/NNMF: The algorithm efficiently solves subproblems, with the path being piecewise linear.
• QCQP & Geometric Programming: The trajectories successfully navigate complex feasible regions (intersections of disks) and non-linear constraints, converging to the constrained minimum.
• Image Denoising: The method successfully reconstructs a noisy image of a lighthouse. The path follows the solution as $\rho$ decreases (in the context of regularization), revealing the image structure as noise is removed. The computational cost is shown to be comparable to state-of-the-art methods for a single $\rho$, but with the added benefit of providing the entire solution path.

Significance and Claims
The authors position this work as a modest assessment of the feasibility and versatility of exact path following for constrained optimization. They explicitly state that a direct performance comparison with interior point methods is reserved for future, more practically oriented papers.

The significance claimed in the paper includes:

1. Conceptual Link: It is the first exploration of path following specifically as an implementation of the exact penalty method, bridging a gap between penalty methods and homotopy/continuation methods.
2. Insight into Regularization: In the context of inverse problems (like image denoising), the method provides a complete view of the solution path, offering insight into how penalties and predictors interact, rather than just finding a single optimal point.
3. Algorithmic Simplicity: The approach is straightforward to implement in environments with robust ODE solvers (like Matlab), avoiding the complex barrier machinery of interior point methods while avoiding the ill-conditioning of classical quadratic penalty methods.
4. Robustness: The authors suggest that path following may be more reliable than competing methods in nonconvex settings for separating global from local minima, though this is noted as a potential future direction rather than a proven result in the current text.

The paper concludes by acknowledging limitations, such as the potential for excessive computational cost when navigating a very large number of constraints, and suggests future generalizations to non-convex problems and different penalty structures.