Introduction
In convex optimization, diverse problem templates—ranging from constrained minimization and minimax problems to nonsmooth dual programs—are often treated as distinct mathematical entities requiring specialized algorithmic approaches. Many of these problems can be unified under the umbrella of monotone inclusions: the task of finding a point where the sum of two operators (typically one representing an objective gradient and another representing constraints or nonsmooth components) contains zero.
While first-order methods like proximal gradient descent are widely used for their simplicity, they often struggle to achieve high-accuracy solutions efficiently. Conversely, second-order methods like Newton's method offer superior convergence rates but have traditionally been difficult to generalize to nonsmooth or constrained settings without restrictive structural assumptions. This research introduces "self-concordant inclusions," a framework that bridges this gap by extending the geometry of self-concordant barriers to the broader world of monotone operators.
The Framework: Self-Concordant Inclusions
The core innovation of this work is the extension of self-concordant barrier theory—a cornerstone of smooth interior-point methods—to monotone inclusions. By associating a monotone operator with a parametric "central path" through a self-concordant barrier function, the authors create a unified structure for solving complex optimization problems.
The Generalized Newton Step
Rather than a standard Newton step, which requires smoothness, the authors utilize a scaled resolvent mapping. This approach linearizes the barrier component while maintaining the integrity of the monotone operator. Effectively, this creates a second-order proximal step that can handle the multi-valued and nonsmooth nature of general operators.
To ensure practical applicability, the framework incorporates a two-phase strategy:
- Phase 1 (Initialization): An auxiliary homotopy problem is solved to locate a starting point near the central path.
- Phase 2 (Path-Following): The algorithm follows the central path toward the optimal solution by iteratively decreasing a penalty parameter $t$.
Crucially, the framework supports inexact computation of Newton directions, which is essential for large-scale applications where exact linear system solutions are computationally prohibitive.
Theoretical Complexity and Convergence
The proposed path-following scheme achieves the gold-standard iteration complexity of $O(\sqrt{\nu} \log(1/\epsilon))$, where $\nu$ is the parameter of the self-concordant barrier. This result is significant because it matches the best-known theoretical bounds for smooth interior-point methods, despite the inclusion of nonsmooth or multi-valued operators.
Furthermore, the authors introduce a new Generalized Newton Decrement. This metric provides a rigorous, implementable stopping criterion for inclusions, allowing the algorithm to detect local quadratic convergence—where the error vanishes extremely rapidly once the iterates are sufficiently close to the solution.
Numerical Results
The framework was evaluated against industry-standard solvers (Mosek, SDPT3, SeDuMi, and SDPNAL+) across several templates, including maximum eigenvalue minimization and cluster recovery via Semidefinite Programming (SDP) relaxation.
- Efficiency Gains: In cluster recovery tasks, the proposed algorithm outperformed Mosek by up to 18x and SeDuMi by up to 290x. This efficiency stems from the algorithm's ability to work directly on the inclusion/dual form, avoiding the dimensionality explosion that occurs when converting problems into standard SDP formats.
- Robustness: On sparse and low-rank matrix approximation problems, the method demonstrated superior stability in satisfying positive definiteness constraints compared to specialized solvers like SDPNAL+.
- Convergence Behavior: Numerical experiments confirmed the theoretical prediction of local quadratic convergence for both full-step and damped-step variants.
Limitations and Future Outlook
While the framework offers significant theoretical and practical advantages, it is not without trade-offs. As a second-order method, the computational cost per iteration is higher than that of first-order methods due to the need to solve complex subproblems involving Hessian matrices. Additionally, the method requires the feasible set to have a known self-concordant barrier, which, while common for many sets (cones, boxes, etc.), is not universal.
Future research may focus on extending this framework to even broader classes of problems, such as geometric programming or more complex conic optimization tasks, further solidifying self-concordant inclusions as a foundational tool for high-performance convex optimization.
Summary updated