Abstract
In this work we introduce a relaxed version of the constant positive linear dependence constraint qualification (CPLD) that we call RCPLD. This development is inspired by a recent generalization of the constant rank constraint qualification by Minchenko and Stakhovski that was called RCRCQ. We show that RCPLD is enough to ensure the convergence of an augmented Lagrangian algorithm and that it asserts the validity of an error bound. We also provide proofs and counter-examples that show the relations of RCRCQ and RCPLD with other known constraint qualifications. In particular, RCPLD is strictly weaker than CPLD and RCRCQ, while still stronger than Abadie’s constraint qualification. We also verify that the second order necessary optimality condition holds under RCRCQ.
Similar content being viewed by others
References
Abadie J.: On the Kuhn-Tucker theorem. In: Abadie, J. (ed.) Nonlinear Programming, pp. 21–36. Wiley, New York (1967)
Andreani R., Birgin E.G., Martínez J.M., Schuverdt M.L.: On augmented Lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007)
Andreani R., Birgin E.G., Martínez J.M., Schuverdt M.L.: Augmented Lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 112, 5–32 (2008)
Andreani R., Echagüe C.E., Schuverdt M.L.: Constant-rank condition and second-order constraint qualification. J. Optim. Theory Appl. 146(2), 255–266 (2010)
Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization (2011). doi:10.1080/02331930903578700
Andreani R., Martínez J.M., Schuverdt M.L.: On the relation between constant positive linear dependence condition and quasinormality constraint qualification. J. Optim. Theory Appl. 125, 473–485 (2005)
Arutyunov A.V.: Perturbations of extremum problems with constraints and necessary optimality conditions. J. Sov. Math. 54, 1342–1400 (1991)
Bertsekas D.P.: Nonlinear Programming. 2nd edn. Athena Scientific, Belmont (1999)
Birgin, E., Bueno, L.F., Krejić, N., Martınez, J.M.: Low Order-Value approach for solving VaR-constrained optimization problems. J. Global Optim. (2011). doi:10.1007/s10898-011-9656-7
Diniz-Ehrhardt M.A., Martínez J.M., Pedroso L.G.: Derivative-free methods for nonlinear programming with general lower-level constraints. Comput. Appl. Math. 30(1), 19–52 (2011)
Giorgi G., Guerraggio A.: On the notion of tangent cone in mathematical programming. Optimization 25(1), 11–23 (1992)
Haeser G.: On the global convergence of interior-point nonlinear programming algorithms. Comput. Appl. Math. 29(2), 125–138 (2010)
Haeser, G., Schuverdt, M.L.: Approximate KKT condition for continuous variational inequality problems. J. Optim. Theory Appl. (2011). doi:10.1007/s10957-011-9802-x
Hestenes M.R.: Optimization Theory: The Finite Dimensional Case. Wiley, New York (1975)
Janin R.: Directional derivative of the marginal function in nonlinear programming. Math. Program. Stud. 21, 110–126 (1984)
Lu, S.: Relation between the constant rank and the relaxed constant rank constraint qualifications. Optimization (2010). doi:10.1080/02331934.2010.527972
Mangasarian O.L., Fromovitz S.: The Fritz John optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967)
Minchenko, L., Stakhovski, S.: On relaxed constant rank regularity condition in mathematical programming. Optimization (2011). doi:10.1080/02331930902971377
Minchenko L., Tarakanov A.: On error bounds for quasinormal programs. J. Optim. Theory Appl. 148, 571–579 (2010)
Pang J.-S.: Error bound in mathematical programming. Math. Program. 79, 299–332 (1997)
Qi L., Wei Z.: On the constant positive linear dependence condition and its application to SQP methods. SIAM J. Optim. 10, 963–981 (2000)
Rockafellar R.T.: Lagrange multipliers and optimality. SIAM Rev. 35(2), 183–238 (1993)
Schuverdt, M.L.: Métodos de Lagrangiano aumentado com convergência utilizando a condiç ão de dependência linear positiva constante. PhD thesis, IMECC-UNICAMP, Departamento de Matemática Aplicada, Campinas-SP, Brazil (2006). http://www.libdigi.unicamp.br/document/?code=vtls000375801
Solodov, M.: Wiley Encyclopedia of Operations Research and Management Science, Chapter Constraint Qualifications. Wiley (2010). doi:10.1002/9780470400531
Author information
Authors and Affiliations
Corresponding author
Additional information
This work was supported by PRONEX-Optimization (PRONEX-CNPq/FAPERJ E-26/171.510/2006-APQ1), Fapesp (Grants 2006/53768-0 and 2009/09414-7) and CNPq (Grants 300900/2009-0, 303030/2007-0 and 474138/2008-9).
The second author would like to acknowledge that he was a research assistant at the University of São Paulo while this work was carried out.
Rights and permissions
About this article
Cite this article
Andreani, R., Haeser, G., Schuverdt, M.L. et al. A relaxed constant positive linear dependence constraint qualification and applications. Math. Program. 135, 255–273 (2012). https://doi.org/10.1007/s10107-011-0456-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-011-0456-0