Worst-case evaluation complexity of a quadratic penalty method for nonconvex optimization

Abstract

This paper addresses the worst-case evaluation complexity of a version of the standard quadratic penalty method for smooth nonconvex optimization problems with constraints. The method analysed allows inexact solution of the subproblems and do not require prior knowledge of the Lipschitz constants related with the problem. When an approximate feasible point is used as starting point, it is shown that the referred method takes at most $\mathcal{O}(\log ({\sigma }_0^{-1}{ϵ}^{-2}))$ outer iterations to generate an ϵ-approximate KKT point, where ${\sigma }_0$ is the first penalty parameter. For equality constrained problems, this bound yields to an evaluation complexity bound of $\mathcal{O}\left({ϵ}^{-4}\right)$, when ${\sigma }_0={ϵ}^{-2}$ and suitable first-order methods are used as inner solvers. For problems having only linear equality constraints, an evaluation complexity bound of $\mathcal{O}\left({ϵ}^{-(p+1)/p}\right)$ is established when appropriate p-order methods ($p\ge 2$) are used as inner solvers. Illustrative numerical results are also presented and corroborate the theoretical predictions. 

Keywords:

• Nonlinear programming
• quadratic penalty method
• worst-case complexity
• high-order methods

AMS SUBJECT CLASSIFICATIONS:

• 90C30
• 49M30
• 65Y20

Acknowledgments

The author is very grateful to three anonymous referees, whose comments helped to improve the paper.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 By introducing a vector $z\in {\mathbb{R}}^{m-m_e}$ of additinal variables, problem (1(1) $\begin{array}{rl}\underset{x\in {\mathbb{R}}^n}{min}& f(x),\end{array}$(1) )–(3(3) $\begin{array}{rl}& c_i(x)\ge 0,i=m_e+1,\dots ,m,\end{array}$(3) ) can be formulated as an equality constrained problem, namely: $\begin{array}{lll}\underset{(x,z)\in {\mathbb{R}}^n\times {\mathbb{R}}^{m-m_e}}{min}& f(x),& \\ \mathrm{s}.\mathrm{t}.& c_i(x)=0,& i=1,\dots ,m_e,\\ & c_i(x)-z_{i-m_e}^2=0,& i=m_e+1,\dots ,m.\end{array}$

2 The monotonicity of ${\mathcal{M}}_1$ ensures that $x_{k+1}$ satisfies (12(12) $Q(x_{k+1},{\sigma }_k)\le min\{Q(x_k,{\sigma }_k),Q(x_0,{\sigma }_k)\},$(12) ).

3 Note that such $x_0$ is an infeasible point with $|\Vert x_0{\Vert }^2-1{|}^2={ϵ}^2/2$.

4 Algorithm A (in Appendix 1) with $d_k=-\mathrm{\nabla }F(y_k)$, $\beta =0.5$ and $\rho ={10}^{-4}$.

Additional information

Funding

The work was partially supported by the National Council for Scientific and Technological Development (CNPq) (Conselho Nacional de Desenvolvimento Científico e Tecnológico) – Brazil [grant number 312777/2020-5].

Notes on contributors

Geovani Nunes Grapiglia

Geovani Nunes Grapiglia obtained his doctoral degree in Mathematics in 2014 from Universidade Federal do Paraná (UFPR), Brazil. Currently he is an Assistant Professor at Université catholique de Louvain (UCLouvain). His research covers the development, analysis and application of optimization methods, with works ranging from derivative-free methods for non-convex optimization to accelerated high-order methods for convex optimization.