Research map / Optimization / Nonconvex and smooth optimization
Inexact Augmented Lagrangian Methods for Conic Optimization: Quadratic Growth and Linear Convergence
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.
Establishes quadratic growth and error bounds for primal and dual SDPs under strict complementarity, and proves linear convergence of both primal and dual iterates of inexact ALMs applied to SDPs.
Problem
Whether the primal iterates of augmented Lagrangian methods applied to semidefinite programs converge linearly (an open question), in addition to the known linear convergence of dual iterates and KKT residuals.
Approach
Derives new quadratic growth and error bound properties for primal and dual SDPs over any compact set (using a new characterization of the preimage of the subdifferential of exact penalty functions), then combines these with the PPM–ALM connection to show that inexact ALM iterates converge linearly in both primal and dual, assuming strict complementarity and a bounded primal solution set.
Key results
- Inexact ALM on Max-Cut and linear SVM shows linear convergence of cost gaps and KKT residuals to at least 1e-5 accuracy.
- Theorem 3 proves linear convergence of primal iterates of inexact ALM under strict complementarity and bounded primal solution set, answering an open question.
- Quadratic growth and error bounds hold over any compact set (not only a small unknown neighborhood) for both indicator and exact penalty formulations.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Apply the inexact ALM (15) | Max-Cut · Max-Cut (G1, G2, G3; 20×20 submatrices) | relative primal and dual cost gaps and KKT residuals: 10−5 | Helped |
| Apply the inexact ALM (15) | Linear SVM · Linear SVM | relative primal and dual cost gaps and KKT residuals: 10−5 | Helped |
Surprising findings
- Primal linear convergence of ALM holds under strict complementarity alone, without the stronger Lipschitz condition on the augmented Lagrangian previously needed.
Limitations
- Requires strict complementarity and a bounded primal solution set.
- Numerical experiments are small-scale (20x20 Max-Cut submatrices, 10x100 SVM) and oscillation in tails is not theoretically explained.
Experimental setup
Datasets: Max-Cut SDP relaxation instances from G-set (first 20x20 submatrix) randomly generated linear SVM data
Benchmarks: Max-Cut SDP (G-set subproblems) linear SVM
Metrics: relative primal and dual cost gap relative feasibility residuals KKT residuals
Baselines: SDPNAL+
Builds on: Rockafellar proximal point connection to ALM Luque PPM linear convergence Cui et al. convex composite conic ALM Drusvyatskiy-Lewis quadratic growth SDPNAL+
Closest papers by meaning
- An Inexact Augmented Lagrangian Framework for Nonconvex Optimization with Nonlinear Constraints (NeurIPS 2019 · similarity 0.89)
- Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints (ICML 2025 · similarity 0.86)
- Accelerated Algorithms for Constrained Nonconvex-Nonconcave Min-Max Optimization and Comonotone Inclusion (ICML 2024 · similarity 0.85)
- Toward a Unified Theory of Gradient Descent under Generalized Smoothness (ICML 2025 · similarity 0.84)
- Adaptive and Optimal Second-order Optimistic Methods for Minimax Optimization (NeurIPS 2024 · similarity 0.84)
- Exploring Jacobian Inexactness in Second-Order Methods for Variational Inequalities: Lower Bounds, Optimal Algorithms and Quasi-Newton Approximations (NeurIPS 2024 · similarity 0.84)
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.