Revista de la
Unión Matemática Argentina
Sequential optimality conditions for optimization problems with additional abstract set constraints
Nadia Soledad Fazzio, María Daniela Sánchez, and María Laura Schuverdt

Volume 67, no. 1 (2024), pp. 257–279    

Published online: May 21, 2024

https://doi.org/10.33044/revuma.2260

Download PDF

Abstract

The positive approximate Karush–Kuhn–Tucker sequential condition and the strict constraint qualification associated with this condition for general scalar problems with equality and inequality constraints have recently been introduced. In this paper, we extend them to optimization problems with additional abstract set constraints. We also present an extension of the approximate Karush–Kuhn–Tucker sequential condition and its related strict constraint qualification. Furthermore, we explore the relations between the new constraint qualification and other constraint qualifications known in the literature as Abadie, quasi-normality and the approximate Karush–Kuhn–Tucker regularity constraint qualification. Finally, we introduce an augmented Lagrangian method for solving the optimization problem with abstract set constraints and we show that it is possible to obtain global convergence under the new condition.

References

  1. J. Abadie, On the Kuhn-Tucker theorem, in Nonlinear Programming (NATO Summer School, Menton, 1964), North-Holland, Amsterdam, 1967, pp. 19–36.  MR  Zbl
  2. P.-A. Absil, R. Mahony, and R. Sepulchre, Optimization algorithms on matrix manifolds, Princeton University Press, Princeton, NJ, 2008.  DOI  MR  Zbl
  3. 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 no. 4 (2007), 1286–1309.  DOI  MR  Zbl
  4. R. Andreani, E. G. Birgin, J. M. Martínez, and M. L. Schuverdt, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math. Program. 111 no. 1-2, Ser. B (2008), 5–32.  DOI  MR  Zbl
  5. R. Andreani, N. S. Fazzio, M. L. Schuverdt, and L. D. Secchin, A sequential optimality condition related to the quasi-normality constraint qualification and its algorithmic consequences, SIAM J. Optim. 29 no. 1 (2019), 743–766.  DOI  MR  Zbl
  6. R. Andreani, W. Gómez, G. Haeser, L. M. Mito, and A. Ramos, On optimality conditions for nonlinear conic programming, Math. Oper. Res. 47 no. 3 (2022), 2160–2185.  DOI  MR  Zbl
  7. R. Andreani, G. Haeser, M. L. Schuverdt, L. D. Secchin, and P. J. S. Silva, On scaled stopping criteria for a safeguarded augmented Lagrangian method with theoretical guarantees, Math. Program. Comput. 14 no. 1 (2022), 121–146.  DOI  MR  Zbl
  8. R. Andreani, G. Haeser, L. D. Secchin, and P. J. S. Silva, New sequential optimality conditions for mathematical programs with complementarity constraints and algorithmic consequences, SIAM J. Optim. 29 no. 4 (2019), 3201–3230.  DOI  MR  Zbl
  9. R. Andreani, G. Haeser, and J. M. Martínez, On sequential optimality conditions for smooth constrained optimization, Optimization 60 no. 5 (2011), 627–641.  DOI  MR  Zbl
  10. 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 no. 1-2, Ser. A (2012), 255–273.  DOI  MR  Zbl
  11. 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 no. 1 (2016), 96–110.  DOI  MR  Zbl
  12. R. Andreani, J. M. Martinez, and M. L. Schuverdt, On the relation between constant positive linear dependence condition and quasinormality constraint qualification, J. Optim. Theory Appl. 125 no. 2 (2005), 473–485.  DOI  MR  Zbl
  13. 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 no. 6 (2010), 3533–3554.  DOI  MR  Zbl
  14. R. Andreani, A. Ramos, A. A. Ribeiro, L. D. Secchin, and A. R. Velazco, On the convergence of augmented Lagrangian strategies for nonlinear programming, IMA J. Numer. Anal. 42 no. 2 (2022), 1735–1765.  DOI  MR  Zbl
  15. R. Bergmann and R. Herzog, Intrinsic formulation of KKT conditions and constraint qualifications on smooth manifolds, SIAM J. Optim. 29 no. 4 (2019), 2423–2444.  DOI  MR  Zbl
  16. D. P. Bertsekas, Nonlinear programming, second ed., Athena Scientific, Belmont, MA, 1999.  MR  Zbl
  17. D. P. Bertsekas, A. Nedić, and A. E. Ozdaglar, Convex analysis and optimization, Athena Scientific, Belmont, MA, 2003.  MR  Zbl
  18. D. P. Bertsekas and A. E. Ozdaglar, Pseudonormality and a Lagrange multiplier theory for constrained optimization, J. Optim. Theory Appl. 114 no. 2 (2002), 287–343.  DOI  MR  Zbl
  19. E. G. Birgin and J. M. Martínez, A box-constrained optimization algorithm with negative curvature directions and spectral projected gradients, in Topics in numerical analysis, Comput. Suppl. 15, Springer, Vienna, 2001, pp. 49–60.  DOI  MR  Zbl
  20. E. G. Birgin and J. M. Martínez, Large-scale active-set box-constrained optimization method with spectral projected gradients, Comput. Optim. Appl. 23 no. 1 (2002), 101–125.  DOI  MR  Zbl
  21. E. G. Birgin and J. M. Martínez, Practical augmented Lagrangian methods for constrained optimization, Fundamentals of Algorithms 10, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2014.  DOI  MR  Zbl
  22. E. G. Birgin, J. M. Martínez, and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optim. 10 no. 4 (2000), 1196–1211.  DOI  MR  Zbl
  23. E. G. Birgin, J. M. Martínez, and M. Raydan, Algorithm 813: SPG – software for convex-constrained optimization, ACM Trans. Math. Softw. 27 no. 3 (2001), 340–349.  DOI  Zbl
  24. E. G. Birgin, J. M. Martínez, and M. Raydan, Inexact spectral projected gradient methods on convex sets, IMA J. Numer. Anal. 23 no. 4 (2003), 539–559.  DOI  MR  Zbl
  25. E. G. Birgin, J. M. Martínez, and M. Raydan, Spectral projected gradient methods, in Encyclopedia of optimization, Springer, Boston, 2009, pp. 3652–3659.  DOI
  26. E. Börgens, C. Kanzow, P. Mehlitz, and G. Wachsmuth, New constraint qualifications for optimization problems in Banach spaces based on asymptotic KKT conditions, SIAM J. Optim. 30 no. 4 (2020), 2956–2982.  DOI  MR  Zbl
  27. L. F. Bueno, G. Haeser, F. Lara, and F. N. Rojas, An augmented Lagrangian method for quasi-equilibrium problems, Comput. Optim. Appl. 76 no. 3 (2020), 737–766.  DOI  MR  Zbl
  28. L. F. Bueno, G. Haeser, and F. N. Rojas, Optimality conditions and constraint qualifications for generalized Nash equilibrium problems and their practical implications, SIAM J. Optim. 29 no. 1 (2019), 31–54.  DOI  MR  Zbl
  29. J. Dutta, K. Deb, R. Tulshyan, and R. Arora, Approximate KKT points and a proximity measure for termination, J. Global Optim. 56 no. 4 (2013), 1463–1499.  DOI  MR  Zbl
  30. W. Fenchel, Convex cones, sets and functions, Logistic Project Report, Department of Mathematics, Princeton University, 1953.  Zbl
  31. M. L. Flegel, C. Kanzow, and J. V. Outrata, Optimality conditions for disjunctive programs with application to mathematical programs with equilibrium constraints, Set-Valued Anal. 15 no. 2 (2007), 139–162.  DOI  MR  Zbl
  32. G. Giorgi, B. Jiménez, and V. Novo, Approximate Karush–Kuhn–Tucker condition in multiobjective optimization, J. Optim. Theory Appl. 171 no. 1 (2016), 70–89.  DOI  MR  Zbl
  33. G. Haeser and M. L. Schuverdt, On approximate KKT condition and its extension to continuous variational inequalities, J. Optim. Theory Appl. 149 no. 3 (2011), 528–539.  DOI  MR  Zbl
  34. M. R. Hestenes, Calculus of variations and optimal control theory, John Wiley & Sons, New York-London-Sydney, 1966.  MR  Zbl
  35. M. R. Hestenes, Optimization theory: The finite dimensional case, Pure and Applied Mathematics, John Wiley & Sons, New York, 1975.  MR  Zbl
  36. C. Kanzow, D. Steck, and D. Wachsmuth, An augmented Lagrangian method for optimization problems in Banach spaces, SIAM J. Control Optim. 56 no. 1 (2018), 272–291.  DOI  MR  Zbl
  37. A. E. Ozdaglar and D. P. Bertsekas, The relation between pseudonormality and quasiregularity in constrained optimization, Optim. Methods Softw. 19 no. 5 (2004), 493–506.  DOI  MR  Zbl
  38. L. Qi and Z. Wei, On the constant positive linear dependence condition and its application to SQP methods, SIAM J. Optim. 10 no. 4 (2000), 963–981.  DOI  MR  Zbl
  39. A. Ramos, Two new weak constraint qualifications for mathematical programs with equilibrium constraints and applications, J. Optim. Theory Appl. 183 no. 2 (2019), 566–591.  DOI  MR  Zbl
  40. A. Ramos, Mathematical programs with equilibrium constraints: a sequential optimality condition, new constraint qualifications and algorithmic consequences, Optim. Methods Softw. 36 no. 1 (2021), 45–81.  DOI  MR  Zbl
  41. R. T. Rockafellar, Convex analysis, Princeton Mathematical Series, No. 28, Princeton University Press, Princeton, NJ, 1970.  MR  Zbl
  42. R. T. Rockafellar and R. J.-B. Wets, Variational analysis, Grundlehren der mathematischen Wissenschaften 317, Springer-Verlag, Berlin, 1998.  DOI  MR  Zbl
  43. N. V. Tuyen, Y.-B. Xiao, and T. Q. Son, On approximate KKT optimality conditions for cone-constrained vector optimization problems, J. Nonlinear Convex Anal. 21 no. 1 (2020), 105–117.  MR  Zbl
  44. W. H. Yang, L.-H. Zhang, and R. Song, Optimality conditions for the nonlinear programming problems on Riemannian manifolds, Pac. J. Optim. 10 no. 2 (2014), 415–434.  MR  Zbl