# Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs

arXiv: https://arxiv.org/abs/1802.03504 · HTML: https://mlsanity.com/paper/1802.03504/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Feb 2018.

## Built on by (most cited first, 15 of 15)

- [What is a Good Metric to Study Generalization of Minimax Learners?](https://mlsanity.com/paper/2206.04502/) (2022)
- [A Single-Loop Gradient Descent and Perturbed Ascent Algorithm for Nonconvex Functional Constrained Optimization](https://mlsanity.com/paper/2207.05650/) (2022)
- [Oracle Complexity of Single-Loop Switching Subgradient Methods for Non-Smooth Weakly Convex Functional Constrained Optimization](https://mlsanity.com/paper/2301.13314/) (2023)
- [A Newton-CG based augmented Lagrangian method for finding a second-order stationary point of nonconvex equality constrained optimization with complexity guarantees](https://mlsanity.com/paper/2301.03139/) (2023)
- [Proximal Oracles for Optimization and Sampling](https://mlsanity.com/paper/2404.02239/) (2024)
- [Stochastic Smoothed Primal-Dual Algorithms for Nonconvex Optimization with Linear Inequality Constraints](https://mlsanity.com/paper/2504.07607/) (2025)
- [Projection-Free Functional Constrained Optimization for Risk Aversion and Sparsity Control](https://mlsanity.com/paper/2210.05108/) (2022)
- [Damped Proximal Augmented Lagrangian Method for weakly-Convex Problems with Convex Constraints](https://mlsanity.com/paper/2311.09065/) (2023)
- [Communication Efficient Cooperative Edge AI via Event-Triggered Computation Offloading](https://mlsanity.com/paper/2501.02001/) (2025)
- [The inexact power augmented Lagrangian method for constrained nonconvex optimization](https://mlsanity.com/paper/2410.20153/) (2024)
- [Inexact Moreau Envelope Lagrangian Method for Non-Convex Constrained Optimization under Local Error Bound Conditions on Constraint Functions](https://mlsanity.com/paper/2502.19764/) (2025)
- [First-order Methods for Affinely Constrained Composite Non-convex Non-smooth Problems: Lower Complexity Bound and Near-optimal Methods](https://mlsanity.com/paper/2307.07605/) (2023)
- [A Penalty-Based Guardrail Algorithm for Non-Decreasing Optimization with Inequality Constraints](https://mlsanity.com/paper/2405.01984/) (2024)
- [A User Manual for cuHALLaR: A GPU Accelerated Low-Rank Semidefinite Programming Solver](https://mlsanity.com/paper/2508.15951/) (2025)
- [Global Optimality for Constrained Exploration via Penalty Regularization](https://mlsanity.com/paper/2604.28144/) (2026)

## Abstract (arXiv)

This paper analyzes the iteration-complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs. More specifically, the objective function is of the form f + h where f is a differentiable function whose gradient is Lipschitz continuous and h is a closed convex function with bounded domain. The method, basically, consists of applying an accelerated inexact proximal point method for solving approximately a sequence of quadratic penalized subproblems associated to the linearly constrained problem. Each subproblem of the proximal point method is in turn approximately solved by an accelerated composite gradient (ACG) method. It is shown that the proposed scheme generates a ρ-approximate stationary point in at most calO(ρ-3) ACG iterations. Finally, numerical results showing the efficiency of the proposed method are also given.