Research map / Optimization / Nonconvex and smooth optimization
Barrier Algorithms for Constrained Non-Convex Optimization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes first- and second-order interior-point (self-concordant barrier) methods for non-convex objectives with general convex set and linear equality constraints, achieving O(eps^-2) and O(eps^-3/2) complexity to approximate KKT points.
Problem
Non-convex constrained optimization with general convex set constraints and linear equality constraints, where practical projection onto the feasible set is costly and the objective may be non-differentiable at the relative boundary.
Approach
Uses a self-concordant barrier potential F_mu = f + mu*h with search directions from quadratic (first-order) or cubic-regularized (second-order) models over the tangent space of the affine constraints, regularized by the local Hessian-of-barrier norm, with adaptive Lipschitz line search and feasibility guaranteed by Dikin ellipsoid step sizes.
Key results
- First-order method AHBA reaches an eps-KKT point in O(eps^-2) outer iterations, adaptive to the gradient Lipschitz constant.
- Second-order method SAHBA reaches an (eps1,eps2)-2KKT point in O(max{eps1^-3/2, eps2^-3/2}) iterations under local Hessian Lipschitz assumption relative to the barrier's local norm.
- Complexity matches unconstrained non-convex optimal rates; paper reports no numerical experiments.
Limitations
- No numerical experiments are provided to validate practical performance.
- Algorithms assume exact solution of search-direction subproblems; inexact implementation left to future work.
- Requires local smoothness conditions relative to the barrier's local norm, which reduce to standard Lipschitz assumptions only on bounded sets.
Experimental setup
Metrics: iteration complexity epsilon-KKT point guarantee
Builds on: cubic regularized Newton method self-concordant barriers adaptive gradient descent with backtracking
Closest papers by meaning
- Zeroth-Order Methods for Constrained Nonconvex Nonsmooth Stochastic Optimization (ICML 2024 · similarity 0.87)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.87)
- A Differentiable Interior-Point Method in Single Precision (NeurIPS 2026 · similarity 0.86)
- The Computational Complexity of Finding Second-Order Stationary Points (ICML 2024 · similarity 0.86)
- A Universal Transfer Theorem for Convex Optimization Algorithms Using Inexact First-order Oracles (ICML 2024 · similarity 0.86)
- Optimization over Sparse Support-Preserving Sets: Two-Step Projection with Global Optimality Guarantees (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.