Inexact Proximal-Point Penalty Methods for Constrained Non-Convex Optimization

Abstract

In this paper, an inexact proximal-point penalty method is studied for constrained optimization problems, where the objective function is non-convex, and the constraint functions can also be non-convex. The proposed method approximately solves a sequence of subproblems, each of which is formed by adding to the original objective function a proximal term and quadratic penalty terms associated to the constraint functions. Under a weak-convexity assumption, each subproblem is made strongly convex and can be solved effectively to a required accuracy by an optimal gradient-based method. The computational complexity of the proposed method is analyzed separately for the cases of convex constraint and non-convex constraint. For both cases, the complexity results are established in terms of the number of proximal gradient steps needed to find an $\epsilon$-stationary point. When the constraint functions are convex, we show a complexity result of $\tilde{O}({\epsilon }^{-5/2})$ to produce an $\epsilon$-stationary point under the Slater's condition. When the constraint functions are non-convex, the complexity becomes $\tilde{O}({\epsilon }^{-3})$ if a non-singularity condition holds on constraints and otherwise $\tilde{O}({\epsilon }^{-4})$ if a feasible initial solution is available.

arXiv commentsubmitted to journal; corrected a few ? in references

References in corpus (27)

• Composite Self-Concordant Minimization
• Complexity and performance of an Augmented Lagrangian algorithm
• Convergence of Bregman alternating direction method with multipliers for nonconvex composite problems
• Stochastic subgradient method converges at the rate $O(k^{-1/4})$ on weakly convex functions
• On the Complexity of an Augmented Lagrangian Method for Nonconvex Optimization
• On the Convergence Rate of Stochastic Mirror Descent for Nonsmooth Nonconvex Optimization
• Convergence rate bounds for a proximal ADMM with over-relaxation stepsize parameter for solving nonconvex linearly constrained problems
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• Algorithms for stochastic optimization with functional or expectation constraints
• Gradient Primal-Dual Algorithm Converges to Second-Order Stationary Solutions for Nonconvex Distributed Optimization
• Adaptive Augmented Lagrangian Methods: Algorithms and Practical Numerical Experience
• First-order methods for constrained convex programming based on linearized augmented Lagrangian function
• Convergence to Second-Order Stationarity for Constrained Non-Convex Optimization
• Primal-dual stochastic gradient method for convex programs with many functional constraints
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• Iteration-complexity of an inexact proximal accelerated augmented Lagrangian method for solving linearly constrained smooth nonconvex composite optimization problems
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• A Richer Theory of Convex Constrained Optimization with Reduced Projections and Improved Rates
• Iteration-complexity of a Jacobi-type non-Euclidean ADMM for multi-block linearly constrained nonconvex programs
• Solving Non-smooth Constrained Programs with Lower Complexity than $\mathcal{O}(1/\epsilon )$: A Primal-Dual Homotopy Smoothing Approach
• Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective
• Optimal Convergence for Stochastic Optimization with Multiple Expectation Constraints
• Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives
• Accelerated Stochastic Algorithms for Nonconvex Finite-sum and Multi-block Optimization
• SNAP: Finding Approximate Second-Order Stationary Solutions Efficiently for Non-convex Linearly Constrained Problems
• A Log-Barrier Newton-CG Method for Bound Constrained Optimization with Complexity Guarantees
• A Primal-Dual Algorithmic Framework for Constrained Convex Minimization

Cited by in corpus (8)

• QPALM: A Proximal Augmented Lagrangian Method for Nonconvex Quadratic Programs
• WeMix: How to Better Utilize Data Augmentation
• A global dual error bound and its application to the analysis of linearly constrained nonconvex optimization
• Rate-improved Inexact Augmented Lagrangian Method for Constrained Nonconvex Optimization
• Augmented Lagrangian based first-order methods for convex-constrained programs with weakly-convex objective
• A Feasible Level Proximal Point Method for Nonconvex Sparse Constrained Optimization
• Dual Descent ALM and ADMM
• An Accelerated Inexact Dampened Augmented Lagrangian Method for Linearly-Constrained Nonconvex Composite Optimization Problems