Complexity of an inexact proximal-point penalty method for constrained smooth non-convex optimization

Qihang Lin (), Runchao Ma () and Yangyang Xu ()
Additional contact information
Qihang Lin: University of Iowa
Runchao Ma: University of Iowa
Yangyang Xu: Rensselaer Polytechnic Institute

Computational Optimization and Applications, 2022, vol. 82, issue 1, No 8, 175-224

Abstract: 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. This 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 this approach 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 $$\varepsilon$$ ε -stationary point. When the constraint functions are convex, we show a complexity result of $$\tilde{O}(\varepsilon ^{-5/2})$$ O ~ ( ε - 5 / 2 ) to produce an $$\varepsilon$$ ε -stationary point under the Slater’s condition. When the constraint functions are non-convex, the complexity becomes $${\tilde{O}}(\varepsilon ^{-3})$$ O ~ ( ε - 3 ) if a non-singularity condition holds on constraints and otherwise $$\tilde{O}(\varepsilon ^{-4})$$ O ~ ( ε - 4 ) if a feasible initial solution is available.

Keywords: Constrained optimization; Nonconvex optimization; Proximal-point method; Penalty method (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-022-00358-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:82:y:2022:i:1:d:10.1007_s10589-022-00358-y

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-022-00358-y

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().