Abstract
In this paper we theoretically show that interior-point methods based on self-concordant barriers possess favorable global complexity beyond their standard application area of convex optimization. To do that we propose first- and second-order methods for non-convex optimization problems with general convex set constraints and linear constraints. Our methods attain a suitably defined class of approximate first- or second-order KKT points with the worst-case iteration complexity similar to unconstrained problems, namely $O(\varepsilon^{-2})$ (first-order) and $O(\varepsilon^{-3/2})$ (second-order), respectively.
1. Introduction
Interior-point methods (IPMs) have long been established as the gold standard for solving convex optimization problems. By utilizing barrier functions to navigate the interior of a feasible region, IPMs avoid the complexities associated with the boundary until the final stages of convergence. However, the application of these methods to non-convex optimization—a field increasingly relevant due to deep learning and sparse recovery—has remained relatively underdeveloped.
In the non-convex regime, practitioners typically rely on projection-based methods to handle constraints. While effective for simple sets (like boxes or balls), calculating projections onto complex convex sets can be computationally prohibitive. This paper bridges the gap by extending the elegant barrier approach of IPMs to non-convex objectives, providing the first rigorous theoretical complexity analysis for such algorithms.
2. Problem Formulation and Barrier Functions
The authors consider the problem of minimizing a non-convex objective function $f(x)$ subject to linear equality constraints and membership in a general closed convex set $\bar{K}$:
$$\min f(x) \quad \text{s.t.} \quad Ax = b, \quad x \in \bar{K}$$
To handle the set constraint $x \in \bar{K}$ without explicit projections, the framework employs a self-concordant barrier (SCB) function $h(x)$. This barrier function is defined such that it approaches infinity as $x$ nears the boundary of $\bar{K}$. The optimization then focuses on a "potential function":
$$F_\mu(x) = f(x) + \mu h(x)$$
where $\mu$ is a barrier parameter. This approach ensures that the iterates remain within the relative interior of the feasible set, a property known as strict feasibility. This is particularly advantageous for problems where the objective function is only well-defined or differentiable within the interior of the constraints (e.g., certain sparsity-inducing penalties).
3. Proposed Algorithms
The paper introduces two primary algorithms: the First-Order Adaptive Barrier Method (FOABM) and the Second-Order Adaptive Barrier Method (SOABM).
3.1 FOABM (First-Order)
FOABM utilizes a quadratic model of the potential function. A key feature of this algorithm is its adaptivity; it does not require prior knowledge of the Lipschitz constant of the gradient. Instead, it employs a backtracking line search to determine appropriate step sizes dynamically. By using the local norm induced by the Hessian of the barrier function, FOABM naturally scales its steps to respect the geometry of the constraints.
3.2 SOABM (Second-Order)
SOABM incorporates second-order information via a cubic-regularized model, including the Hessian of the objective $f$. This method can be viewed as a damped version of a cubic-regularized Newton’s method, specifically tailored to the local geometry defined by the barrier. This allows the algorithm to navigate the non-convex landscape more efficiently than first-order methods by utilizing curvature information.
4. Theoretical Contributions and Complexity
A significant challenge in this research was defining what constitutes a "solution" in the presence of barriers and non-convexity, especially when the objective might be non-differentiable at the boundary. The authors propose new "approximate KKT" conditions ($\varepsilon$-KKT and $(\varepsilon_1, \varepsilon_2)$-2KKT) that are compatible with interior-point iterates.
The core theoretical results demonstrate that these algorithms achieve "complexity parity" with unconstrained optimization:
- FOABM is proven to reach an $\varepsilon$-KKT point within $O(\varepsilon^{-2})$ iterations.
- SOABM reaches an $(\varepsilon_1, \varepsilon_2)$-2KKT point within $O(\max\{\varepsilon_1^{-3/2}, \varepsilon_2^{-3/2}\})$ iterations.
These results are remarkable because they show that the addition of complex convex constraints does not degrade the worst-case iteration complexity compared to the unconstrained case. You essentially get the benefits of constraints "for free" in terms of big-O complexity.
5. Conclusion and Future Work
This work provides a foundational theoretical framework for applying interior-point logic to non-convex problems. While the paper focuses on rigorous proof rather than numerical experiments, it sets the stage for a new class of constrained optimization solvers that avoid expensive projections.
Future research directions include the development of versions that can handle inexact solutions to the search direction subproblems—a necessity for large-scale practical applications—and extending the framework to include non-linear functional constraints.
Summary updated