Abstract
Composite optimization offers a powerful modeling tool for a variety of applications and is often numerically solved by means of proximal gradient methods. In this paper, we consider fully nonconvex composite problems under only local Lipschitz gradient continuity for the smooth part of the objective function. We investigate an adaptive scheme for PANOC-type methods, namely accelerated linesearch algorithms requiring only the simple oracle of proximal gradient. While including the classical proximal gradient method, our theoretical results cover a broader class of algorithms and provide convergence guarantees for accelerated methods with possibly inexact computation of the proximal mapping. These findings have also significant practical impact, as they widen scope and performance of existing, and possibly future, general purpose optimization software that invoke PANOC as inner solver.
Introduction
Composite optimization problems, typically formulated as the minimization of $\phi(x) = f(x) + g(x)$, where $f$ is smooth and $g$ is nonsmooth, are ubiquitous in engineering and machine learning. From Model Predictive Control (MPC) in robotics to regularized regression, the Proximal Gradient (PG) method and its accelerated variants, such as PANOC (Proximal Averaged Newton-type method for Optimal Control), have become standard solvers. However, these methods traditionally rely on the assumption of a global Lipschitz constant for the gradient of $f$. This paper introduces PANOC+, an evolution of the algorithm designed to operate under the more realistic assumption of local Lipschitz continuity.
The Limitation of Global Lipschitz Continuity
The requirement for a global Lipschitz constant $L$—meaning the gradient $\nabla f$ does not change faster than $L$ across the entire domain—is often violated in practice. For instance, in Augmented Lagrangian subproblems or simple functions like $f(x) = |x|^3$, no such global constant exists. Applying standard PANOC to these problems can lead to mathematical divergence, where iterates escape to infinity. Furthermore, traditional algorithms assume an "exact" proximal oracle for $g$, which is often computationally prohibitive in complex constrained environments.
The PANOC+ Framework
PANOC+ addresses these challenges through two primary innovations:
1. Synchronized Adaptive Stepsize Selection
In the original PANOC, the proximal stepsize ($\gamma$) and the update direction dampening ($\tau$) were adjusted with a degree of independence. PANOC+ intertwines these variables. When the proximal stepsize is updated to account for local curvature, the direction linesearch resets. This synchronization ensures that the algorithm's merit function—the Forward-Backward Envelope (FBE)—remains a valid surrogate for the objective, preventing the "mismatch" that previously caused divergence.
2. Inexact Proximal Oracles
Recognizing that the proximal mapping $prox_{\gamma g}(x)$ cannot always be computed exactly, the authors extend the convergence theory to allow for inexact solutions. PANOC+ only requires a point that sufficiently improves the objective relative to the previous iteration. This makes the algorithm significantly more robust for real-world applications where constraints are complex.
Theoretical and Numerical Results
The authors provide a rigorous convergence proof for PANOC+ under local Lipschitz continuity, a significant advancement over the global assumptions of prior work. Numerical experiments highlight the practical benefits:
- Convergence Stability: In a 1D case study ($f(x) = \frac{2}{9}|x|^3$), PANOC+ successfully converges while the original PANOC diverges.
- Monotonicity: PANOC+ exhibits a steady, monotone decrease in the FBE merit function, avoiding the erratic behavior seen in non-adaptive methods.
- Efficiency: By avoiding "bad" steps through its nested linesearch, PANOC+ often requires fewer total function evaluations than its predecessors, despite the added complexity of the adaptive rules.
Conclusion and Impact
PANOC+ bridges the gap between theoretical optimization and practical engineering requirements. By relaxing the Lipschitz requirements and allowing for inexactness, it serves as an ideal inner solver for Augmented Lagrangian Methods. Its integration into general-purpose software like OpEn (Optimization Engine) promises to enhance the reliability of high-dimensional optimization in fields such as aerospace and robotics.
Summary updated