Aplicação de métodos Lagrangeano aumentado a problemas com restrições do tipo complementaridade
DOI:
https://doi.org/10.5540/03.2025.011.01.0351Keywords:
Lagrangeano aumentado, Segunda ordem, Restrições de complementaridade, Restrição de cardinalidadeAbstract
Dois problemas típicos na literatura são considerados: problemas de programação matemática com restrições de complementaridade (do inglês, MPCC) e problemas com restrição de cardinalidade (do inglês, MPCaC). Ambos não satisfazem a maioria das condições de qualificação estabelecidas, logo não há garantia de que métodos convirjam a pontos KKT. A convergência de métodos Lagrangeano aumentado (LA) clássicos em MPCCs foi considerada na literatura. Recentemente, um novo método LA para MPCCs com boa convergência teórica foi proposto e, mais tarde, estendido à MPCaCs. Embora similar à MPCC, MPCaCs são, de certa forma, menos degenerados, o que permite maior flexibilidade para confecção de algoritmos especializados. Neste trabalho destacamos avanços no estudo de MPCCs e MPCaCs, com ênfase em contribuições recentes do autor na convergência de um método LA de segunda ordem aplicado aos problemas considerados.
Downloads
References
R. Andreani, E. G. Birgin, J. M. Martínez e M. L. Schuverdt. “On augmented Lagrangian methods with general lower-level constraints”. Em: SIAM Journal on Optimization 18.4 (2007), pp. 1286–1309. doi:10.1137/060654797.
R. Andreani, E. G. Birgin, J. M. Martínez e M. L. Schuverdt. “Second-order negative-curvature methods for box-constrained and general constrained optimization”. Em: Computational Optimization and Applications 45.2 (2010), pp. 209–236. doi:10.1007/s10589-009-9240-y.
R. Andreani, G. Haeser, L. M. Mito, A. Ramos e L. D. Secchin. “On the best achievable quality of limit points of augmented Lagrangian schemes”. Em: Numerical Algorithms 90.2 (2022), pp. 851–877. doi:10.1007/s11075-021-01212-8.
R. Andreani, G. Haeser, L. D. Secchin e P. J. S. Silva. “New sequential optimality conditions for mathematical programs with complementarity constraints and algorithmic consequences”. Em: SIAM Journal on Optimization 29.4 (2019), pp. 3201–3230. doi:10.1137/18M121040X.
R. Andreani e L. D. Secchin. “A note on the convergence of an augmented Lagrangian algorithm to second-order stationary points”. Em: Proceeding Series of the Brazilian Society of Computational and Applied Mathematics. Vol. 6. 1. Sociedade Brasileira de Matemática Aplicada e Computacional, 2018. doi:10.5540/03.2018.006.01.0303.
R. Andreani, L. D. Secchin e P. J. S. Silva. “Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints”. Em: SIAM Journal on Optimization 28.3 (2018), pp. 2574–2600. doi:10.1137/17M1125698.
M. Bucher e A. Schwartz. “Second-order optimality conditions and improved convergence results for regularization methods for cardinality-constrained optimization problems”. Em: Journal of Optimization Theory and Applications 178.2 (2018), pp. 383–410. doi:10.1007/s10957-018-1320-7.
O. P. Burdakov, C. Kanzow e A. Schwartz. “Mathematical programs with cardinality constraints: reformulation by complementarity-type conditions and a regularization method”. Em: SIAM Journal on Optimization 26.1 (2016), pp. 397–425. doi:10.1137/140978077.
L. Guo e Z. Deng. “A new augmented Lagrangian method for MPCCs – theoretical and numerical comparison with existing augmented Lagrangian methods”. Em: Mathematics of Operations Research 47.2 (2022), pp. 1229–1246. doi:10.1287/moor.2021.1165.
A. F. Izmailov, M. V. Solodov e E. I. Uskov. “Global convergence of augmented Lagrangian methods applied to optimization problems with degenerate constraints, including problems with complementarity constraints”. Em: SIAM Journal on Optimization 22.4 (2012), pp. 1579–1606. doi:10.1137/120868359.
X. Jia, C. Kanzow, Patrick M. e G. Wachsmuth. “An augmented Lagrangian method for optimization problems with structured geometric constraints”. Em: Mathematical Programming 199.1–2 (2023), pp. 1365–1415. doi:10.1007/s10107-022-01870-z.
C. Kanzow, A. B. Raharja e A. Schwartz. “An augmented Lagrangian method for cardinality-constrained optimization problems”. Em: Journal of Optimization Theory and Applications 189.3 (2021), pp. 793–813. doi:10.1007/s10957-021-01854-7.
C. Kanzow, A. B. Raharja e A. Schwartz. “Sequential optimality conditions for cardinality-constrained optimization problems with applications”. Em: Computational Optimization and Applications 80.1 (2021), pp. 185–211. doi:10.1007/s10589-021-00298-z.
J. C. A. Medeiros, A. A. Ribeiro, M. Sachine e L. D. Secchin. A practical second-order optimality condition for cardinality-constrained problems with application to an augmented Lagrangian method. Rel. técn. Submetido. 2022.
L. D. Secchin. “Aplicação de métodos de Lagrangiano aumentado a problemas de otimização com restrições de complementariedade”. Tese de doutorado. Unicamp, 2018.
