A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences.

*(English)*Zbl 1451.90166This paper deals with optimization problems of the form
\[
\min_{x\in X}f(x),\tag{P}
\]
where \(f:\mathbb{R}^{n}\longrightarrow \mathbb{R}\) and \(X=\left\{ x\in\mathbb{R}^{n}\mid h(x) =0_{m},\,g(x) \leq 0_{p}\right\}\), with \(h:\mathbb{R}^{n}\longrightarrow \mathbb{R}^{m}\) and \(g:\mathbb{R}^{n}\longrightarrow \mathbb{R}^{p}\), and \(f,g,h\in \mathcal{C}^{1}\left( \mathbb{R}^{n}\right)\). Following the Powell-Hestenes-Rockafellar (PHR) augmented Lagrangian approach, the authors associate, with a given penalty parameter \(\rho >0\) and Lagrange multiplier estimates \(\lambda \in \mathbb{R}^{m}\) and \(\mu \in \mathbb{R}_{+}^{p}\), the augmented Lagrangian function
\[
L_{\rho}\left( x,\lambda ,\mu \right) =f(x) +\frac{\rho}{2}\left( \sum\limits_{i=1}^{m}\left( h_{i}(x) +\frac{\lambda _{i}}{\rho}\right) ^{2}+\sum\limits_{j=1}^{p}\max \left\{ 0,g_{j}(x) +\frac{\mu _{j}}{\rho}\right\} ^{2}\right).
\]
Each step of the PHR augmented Lagrangian algorithm for (P) consists in the minimization of \(L_{\rho}\) for some \(\rho >0\). Once the approximate solution is found, the penalty parameter \(\rho\), as well as the multiplier estimates \(\lambda\) and \(\mu\), are updated and a new iteration starts.

An element \(x^{\ast}\in X\) satisfies the approximate Karush-Kuhn-Tucker (AKKT) condition for (P) if there exists a sequence \(\left\{\left( x^{k},\lambda ^{k},\mu ^{k}\right) \right\} \subset \mathbb{R}^{n+m}\times \mathbb{R}_{+}^{p}\) such that \[ x^{k}\longrightarrow x^{\ast},\ \nabla _{x}L\left( x^{k},\lambda^{k},\mu ^{k}\right) \longrightarrow 0_{n},\text{ and }\min \left\{-g\left(x^{k}\right) ,\mu ^{k}\right\} \longrightarrow 0_{m}, \tag{1} \] where \(L\) denotes the ordinary Lagrangian of (P). In that case, \(x^{k}\) is called an AKKT point and \(\left\{ x^{k}\right\}\) an AKKT sequence. Many constraint qualifications (CQs) have been proposed to guarantee that a given AKKT point is stationary, that is, satisfies the classical Karush-Kuhn-Tucker necessary optimality conditions for \(\left( P\right)\). Most of these CQs are based on either rank and/or positive linear dependence assumptions (among them the so-called cone continuity property, CCP in short) or pseudonormality and quasi-normality. In order to unify both types of CQs, this paper introduces a new constraint qualification called positive approximate Karush-Kuhn-Tucker (PAKKT) regularity, which consists in the existence of some element \(x^{\ast}\in X\) and an associated sequence \(\left\{ \left( x^{k},\lambda ^{k},\mu^{k}\right) \right\} \subset \mathbb{R}^{n+m}\times \mathbb{R}_{+}^{p}\) such that (1) holds together with \[ \lambda _{i}^{k}h_{i}\left( x^{k}\right) >0 \text{ if }\lim\limits_{k}\frac{\left\vert \lambda _{i}^{k}\right\vert}{\left\Vert \left( 1,\lambda^{k},\mu ^{k}\right) \right\Vert _{\infty}}>0,\tag{2} \] and \[ \mu _{j}^{k}g_{j}\left( x^{k}\right) >0 \text{ if }\lim\limits_{k}\frac{\left\vert \mu _{j}^{k}\right\vert}{\left\Vert \left( 1,\lambda ^{k},\mu^{k}\right) \right\Vert _{\infty}}>0.\tag{3} \] In that case, \(x^{k}\) is said to be a PAKKT point and \(\left\{ x^{k}\right\}\) a PAKKT sequence. The PAKKT points are AKKT points (as they satisfy (1)) whose sequences of multipliers satisfy the positivity conditions (2) and (3).

The paper shows that PAKKT-regularity is strictly weaker than both quasi-normality and CCP. It is also proved that the PHR augmented Lagrangian method converges under the new PAKKT-regularity CQ. Thus, the paper provides the first known example of a practical algorithm, the mentioned PHR augmented Lagrangian one, which converges under quasi-normality.

An element \(x^{\ast}\in X\) satisfies the approximate Karush-Kuhn-Tucker (AKKT) condition for (P) if there exists a sequence \(\left\{\left( x^{k},\lambda ^{k},\mu ^{k}\right) \right\} \subset \mathbb{R}^{n+m}\times \mathbb{R}_{+}^{p}\) such that \[ x^{k}\longrightarrow x^{\ast},\ \nabla _{x}L\left( x^{k},\lambda^{k},\mu ^{k}\right) \longrightarrow 0_{n},\text{ and }\min \left\{-g\left(x^{k}\right) ,\mu ^{k}\right\} \longrightarrow 0_{m}, \tag{1} \] where \(L\) denotes the ordinary Lagrangian of (P). In that case, \(x^{k}\) is called an AKKT point and \(\left\{ x^{k}\right\}\) an AKKT sequence. Many constraint qualifications (CQs) have been proposed to guarantee that a given AKKT point is stationary, that is, satisfies the classical Karush-Kuhn-Tucker necessary optimality conditions for \(\left( P\right)\). Most of these CQs are based on either rank and/or positive linear dependence assumptions (among them the so-called cone continuity property, CCP in short) or pseudonormality and quasi-normality. In order to unify both types of CQs, this paper introduces a new constraint qualification called positive approximate Karush-Kuhn-Tucker (PAKKT) regularity, which consists in the existence of some element \(x^{\ast}\in X\) and an associated sequence \(\left\{ \left( x^{k},\lambda ^{k},\mu^{k}\right) \right\} \subset \mathbb{R}^{n+m}\times \mathbb{R}_{+}^{p}\) such that (1) holds together with \[ \lambda _{i}^{k}h_{i}\left( x^{k}\right) >0 \text{ if }\lim\limits_{k}\frac{\left\vert \lambda _{i}^{k}\right\vert}{\left\Vert \left( 1,\lambda^{k},\mu ^{k}\right) \right\Vert _{\infty}}>0,\tag{2} \] and \[ \mu _{j}^{k}g_{j}\left( x^{k}\right) >0 \text{ if }\lim\limits_{k}\frac{\left\vert \mu _{j}^{k}\right\vert}{\left\Vert \left( 1,\lambda ^{k},\mu^{k}\right) \right\Vert _{\infty}}>0.\tag{3} \] In that case, \(x^{k}\) is said to be a PAKKT point and \(\left\{ x^{k}\right\}\) a PAKKT sequence. The PAKKT points are AKKT points (as they satisfy (1)) whose sequences of multipliers satisfy the positivity conditions (2) and (3).

The paper shows that PAKKT-regularity is strictly weaker than both quasi-normality and CCP. It is also proved that the PHR augmented Lagrangian method converges under the new PAKKT-regularity CQ. Thus, the paper provides the first known example of a practical algorithm, the mentioned PHR augmented Lagrangian one, which converges under quasi-normality.

Reviewer: Miguel Angel Goberna (Alicante)

##### MSC:

90C46 | Optimality conditions and duality in mathematical programming |

90C30 | Nonlinear programming |

65K05 | Numerical mathematical programming methods |

##### Keywords:

augmented Lagrangian methods; global convergence; constraint qualifications; quasi-normality; sequential optimality conditions##### Software:

ALGENCAN
PDF
BibTeX
Cite

\textit{R. Andreani} et al., SIAM J. Optim. 29, No. 1, 743--766 (2019; Zbl 1451.90166)

Full Text:
DOI

##### References:

[1] | J. Abadie, On the Kuhn–Tucker theorem, in Nonlinear Programming, J. Abadie, ed., John Wiley, New York, 1967, pp. 21–36. · Zbl 0183.22803 |

[2] | R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, On augmented Lagrangian methods with general lower-level constraints, SIAM J. Optim., 18 (2007), pp. 1286–1309, . · Zbl 1151.49027 |

[3] | R. Andreani, G. Haeser, and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization, 60 (2011), pp. 627–641, . · Zbl 1225.90123 |

[4] | R. Andreani, G. Haeser, M. L. Schuverdt, and P. J. S. Silva, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135 (2012), pp. 255–273, . · Zbl 1262.90162 |

[5] | R. Andreani, G. Haeser, M. L. Schuverdt, and P. J. S. Silva, Two new weak constraint qualifications and applications, SIAM J. Optim., 22 (2012), pp. 1109–1135, . · Zbl 1302.90244 |

[6] | R. Andreani, J. M. Martínez, and M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification, J. Optim. Theory Appl., 125 (2005), pp. 473–485, . · Zbl 1125.90058 |

[7] | R. Andreani, J. M. Martínez, and B. F. Svaiter, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim., 20 (2010), pp. 3533–3554, . · Zbl 1217.90148 |

[8] | R. Andreani, J. M. Martínez, A. Ramos, and P. J. S. Silva, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26 (2016), pp. 96–110, . · Zbl 1329.90162 |

[9] | R. Andreani, J. M. Martínez, A. Ramos, and P. J. S. Silva, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res., 43 (2018), pp. 693–1050, . |

[10] | R. Andreani, L. D. Secchin, and P. J. S. Silva, Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints, SIAM J. Optim., 28 (2018), pp. 2574–2600, . · Zbl 1406.90114 |

[11] | D. P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena Scientific, Nashua, NH, 1996. · Zbl 0572.90067 |

[12] | D. P. Bertsekas, Nonlinear Programming, 2nd ed., Athena Scientific, Nashua, NH, 1999. |

[13] | D. P. Bertsekas, A. E. Ozdaglar, and P. Tseng, Enhanced Fritz John conditions for convex programming, SIAM J. Optim., 16 (2006), pp. 766–797, . · Zbl 1113.90119 |

[14] | E. G. Birgin, R. A. Castillo, and J. M. Martínez, Numerical comparison of augmented Lagrangian algorithms for nonconvex problems, Comput. Optim. Appl., 31 (2005), pp. 31–55, . · Zbl 1101.90066 |

[15] | E. G. Birgin and J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, Philadelphia, PA, 2014, . · Zbl 1339.90312 |

[16] | L. F. Bueno, G. Haeser, and F. N. Rojas, Optimality Conditions and Constraint Qualifications for Generalized Nash Equilibrium Problems and Their Practical Implications, Technical report, , 2017. · Zbl 1422.91049 |

[17] | S. Dempe, Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52 (2003), pp. 333–359, . · Zbl 1140.90493 |

[18] | N. Echebest, M. D. Sánchez, and M. L. Schuverdt, Convergence results of an augmented Lagrangian method using the exponential penalty function, J. Optim. Theory Appl., 168 (2016), pp. 92–108, . · Zbl 1332.65077 |

[19] | L. Guo and G.-H. Lin, Notes on some constraint qualifications for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 156 (2013), pp. 600–616, . · Zbl 1280.90115 |

[20] | G. Haeser, O. Hinder, and Y. Ye, On the Behavior of Lagrange Multipliers in Convex and Non-Convex Infeasible Interior Point Methods, Technical report, , 2017. |

[21] | G. Haeser and M. L. Schuverdt, On approximate KKT condition and its extension toÂ continuous variational inequalities, J. Optim. Theory Appl., 149 (2011), pp. 528–539, . · Zbl 1220.90130 |

[22] | M. R. Hestenes, Otimization Theory: The Finite Dimensional Case, John Wiley, New York, 1975. |

[23] | A. F. Izmailov, M. V. Solodov, and E. I. Uskov, Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints, SIAM J. Optim., 22 (2012), pp. 1579–1606, . · Zbl 1274.90385 |

[24] | C. Kanzow and A. Schwartz, Mathematical programs with equilibrium constraints: Enhanced Fritz John-conditions, new constraint qualifications, and improved exact penalty results, SIAM J. Optim., 20 (2010), pp. 2730–2753, . · Zbl 1208.49016 |

[25] | J. M. Martínez and B. F. Svaiter, A practical optimality condition without constraint qualifications for nonlinear programming, J. Optim. Theory Appl., 118 (2003), pp. 117–133, . · Zbl 1033.90090 |

[26] | J. M. Martínez and E. A. Pilotta, Inexact Restoration Methods for Nonlinear Programming: Advances and Perspectives, Springer, Boston, MA, 2005, pp. 271–291, . · Zbl 1118.90319 |

[27] | L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim., 10 (2000), pp. 963–981, . · Zbl 0999.90037 |

[28] | R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, 1st ed., Grundlehren Math. Wiss. 317, Springer, Berlin, Heidelberg, 1998, . · Zbl 0888.49001 |

[29] | M. D. Sánchez and M. L. Schuverdt, A Second Order Convergence Augmented Lagrangian Method Using Non-Quadratic Penalty Functions, Opsearch, submitted. |

[30] | H. Scheel and S. Scholtes, Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity, Math. Oper. Res., 25 (2000), pp. 1–22, . · Zbl 1073.90557 |

[31] | J. J. Ye and J. Zhang, Enhanced Karush–Kuhn–Tucker condition and weaker constraint qualifications, Math. Program., 139 (2013), pp. 353–381, . · Zbl 1285.90078 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.