In unconstrained nonconvex optimization, the worst-case complexity bounds for finding approximate stationary points are well-established. To find an $\epsilon$-approximate first-order stationary point ($\|\nabla f(x)\| \leq \epsilon$), standard gradient descent requires $O(\epsilon^{-2})$ iterations. To find a second-order stationary point (where the Hessian is also nearly positive semidefinite, indicating the algorithm has escaped saddle points), second-order methods typically require $O(\epsilon^{-3/2})$ iterations.
Historically, introducing constraints—whether simple bounds, linear inequalities, or complex conic geometries—was believed to inherently degrade these bounds. The conventional wisdom suggested that navigating boundaries, computing projections, or avoiding infeasible regions introduced unavoidable computational overhead that worsened worst-case complexity.
However, a profound realization has emerged across recent optimization literature: constrained nonconvex optimization can achieve exact complexity parity with unconstrained optimization. The fundamental theoretical limits of finding local minima are not penalized by the presence of constraints.
Smoothing the Geometry: Nonconvex Barrier Methods
How do we prevent constraints from destroying our iteration complexity? The core intuition lies in transforming the sharp, hard boundaries of a constrained set into a smooth, manageable landscape using barrier functions. This effectively turns a constrained problem into a sequence of unconstrained-like subproblems, avoiding the need for expensive and trajectory-disrupting projection steps.
In classical convex optimization, interior-point methods rely on self-concordant barriers to ensure polynomial-time convergence. Dvurechensky et al. extended this intuition to nonconvex settings by utilizing generalized self-concordant barriers. By doing so, the authors demonstrated that first-order interior-point methods can achieve an iteration complexity of $O(\epsilon^{-2})$ for finding stationary points, matching the unconstrained lower bound.
The reason this works is that the barrier function prevents the algorithm from making abrupt, illegal steps across the boundary, while its specific self-concordant curvature ensures that the gradient of the penalized objective does not oscillate wildly relative to the function's local smoothness. This theme was generalized further by Dvurechensky et al. and Dvurechensky et al. to general convex and conic constraints. They proved that first-order barrier methods consistently hit the $O(\epsilon^{-2})$ bound, while second-order variants achieve the optimal $O(\epsilon^{-3/2})$ rate without ever needing projection steps.
Escaping Saddles Under Constraints
Finding a first-order stationary point is not always enough; in nonconvex landscapes, algorithms can get trapped in saddle points. In unconstrained optimization, second-order methods or perturbed gradient methods escape these saddles efficiently by exploiting directions of negative curvature. But what happens when a saddle point lies directly on, or near, a constraint boundary?
Nouiehed et al. showed that the theoretical iteration complexity for finding second-order stationary points remains completely invariant when moving from unconstrained to linearly constrained nonconvex optimization. To achieve this without explicit, computationally prohibitive Hessian storage, O'Neill et al. combined a log-barrier function with a "capped" Conjugate Gradient (CG) method for bound-constrained problems, matching the $O(\epsilon^{-3/2})$ unconstrained complexity. Similarly, He et al. achieved the same $O(\epsilon^{-3/2})$ rate for general conic constraints using a Newton-CG barrier framework.
Unconstrained Landscape:
Saddle Point ──> [Negative Curvature Direction] ──> Escape to Local Minimum
Constrained Landscape (with Barrier):
Boundary Wall ──> [Steep Barrier Gradient]
│
Saddle Point ──────────▼─> [Feasible Subspace Direction] ──> Smooth Escape
Why does this work? When an algorithm approaches a constraint boundary, the active constraints restrict the directions of feasible movement. However, by using a barrier or a trust-region subproblem that respects the local constraint geometry, the algorithm can isolate the subspace of feasible directions. If a saddle point possesses a direction of negative curvature within this feasible subspace, the algorithm can exploit it to escape, exactly as it would in an unconstrained space.
To ensure this condition holds widely, Lu et al. demonstrated that a "strict complementarity" condition holds for almost all practical problem instances. This means the boundary geometry rarely creates degenerate traps that would make escaping saddle points NP-hard, allowing polynomial-time convergence in practice. For cases where constraints are more complex, such as nonconvex equality constraints, He et al. showed that combining Newton-CG with an Augmented Lagrangian framework can still dramatically reduce the iteration complexity to $\tilde{O}(\epsilon^{-3.5})$, bypassing traditional regularity bottlenecks.
Level Constraints and Sequential Convexification
Another powerful mechanism for achieving complexity parity is the reformulation of nonconvex functional constraints into a sequence of simpler, level-set bounded subproblems. Instead of tackling the nonconvex constraints directly—which often leads to severe feasibility issues—we can use proximal or level-set techniques to bound constraint violations systematically.
Boob et al. and Boob et al. introduced the Level Constrained Proximal Gradient (LCPG) method. This framework transforms a problem with nonconvex functional constraints into a sequence of subproblems where the objective or constraints are linearized or regularized. Remarkably, this approach achieves a gradient complexity comparable to unconstrained optimization algorithms, even in challenging nonsmooth or stochastic settings.
The intuition here is that by tracking a "level" of acceptable objective and constraint values, the algorithm can make steady progress toward optimality without getting stuck in highly infeasible regions. For problems exhibiting "hidden convexity" despite nonconvex functional constraints, Fatkhullin et al. showed that constraint-shifting techniques allow first-order methods to find global solutions with the exact same oracle complexity as unconstrained solvers.
The Broader Complexity Landscape
This parity is not an empirical fluke; it reflects a fundamental structural relationship between constrained and unconstrained domains. In fact, Hollender et al. analyzed the computational complexity classes of finding stationary points, demonstrating a surprising structural hierarchy: finding stationary points in unconstrained domains can actually be computationally more complex in a total search problem sense than finding Karush-Kuhn-Tucker (KKT) points in constrained domains. Constrained domains restrict the search space and provide boundary structures that algorithms can exploit to guide their search.
When constraints are highly irregular or non-smooth, such as weakly convex functional constraints, the complexity naturally scales up—requiring $O(\epsilon^{-4})$ evaluations in deterministic settings, as shown by Lin et al.. Yet, even in these challenging regimes, techniques like the "ghost penalties" framework proposed by Facchinei et al. demonstrate that clever regularizations can accelerate convergence back toward the ideal unconstrained baselines. Ultimately, whether through barriers, level-set tracking, or augmented Lagrangians, modern optimization shows that constraints do not inherently dictate a slower rate of convergence.
Key Foundational Work
A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees (2019) — contributed 2 concept elements to this direction.
Generalized Self-concordant Hessian-barrier algorithms (2019) — contributed 1 concept elements to this direction.
Generalized Majorization-Minimization for Non-Convex Optimization (2019) — contributed 1 concept elements to this direction.