×

zbMATH — the first resource for mathematics

An augmented Lagrangian algorithm for nonlinear semidefinite programming applied to the covering problem. (English) Zbl 1449.90278
Summary: In this work, we present an Augmented Lagrangian algorithm for nonlinear semidefinite problems (NLSDPs), which is a natural extension of its consolidated counterpart in nonlinear programming. This method works with two levels of constraints; one that is penalized and other that is kept within the subproblems. This is done to allow exploiting the subproblem structure while solving it. The global convergence theory is based on recent results regarding approximate Karush-Kuhn-Tucker optimality conditions for NLSDPs, which are stronger than the usually employed Fritz John optimality conditions. Additionally, we approach the problem of covering a given object with a fixed number of balls with a minimum radius, where we employ some convex algebraic geometry tools, such as Stengle’s Positivstellensatz and its variations, which allows for a much more general model. Preliminary numerical experiments are presented.
MSC:
90C22 Semidefinite programming
90C46 Optimality conditions and duality in mathematical programming
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Andreani, R.; Birgin, Eg; Martínez, Jm; Schuverdt, Ml, On augmented Lagrangian methods with general lower-level constraint, SIAM J Optim, 18, 4, 1286-1309 (2008) · Zbl 1151.49027
[2] Andreani, R.; Birgin, Eg; Martínez, Jm; Schuverdt, Ml, Augmented Lagrangian methods under the constant positive linear dependence constraint qualification, Math Program, 111, 5-32 (2008) · Zbl 1163.90041
[3] Andreani, R.; Haeser, G.; Martínez, Jm, On sequential optimality conditions for smooth constrained optimization, Optimization, 60, 5, 627-641 (2011) · Zbl 1225.90123
[4] Andreani, R.; Haeser, G.; Schuverdt, Ml; Silva, Pjs, Two new weak constraint qualifications and applications, SIAM J Optim, 22, 3, 1109-1135 (2012) · Zbl 1302.90244
[5] Andreani, R.; Haeser, G.; Schuverdt, Ml; Silva, Pjs, A relaxed constant positive linear dependence constraint qualification and applications, Math Program, 135, 1-2, 255-273 (2012) · Zbl 1262.90162
[6] Andreani, R.; Martínez, Jm; Santos, Lt, Newton’s method may fail to recognize proximity to optimal points in constrained optimization, Math Program, 160, 547-555 (2016) · Zbl 1356.90137
[7] Andreani, R.; Martínez, Jm; Ramos, A.; Silva, Pjs, A cone-continuity constraint qualification and algorithmic consequences, SIAM J Optim, 26, 1, 96-110 (2016) · Zbl 1329.90162
[8] Andreani, R.; Fazzio, Ns; Schuverdt, Ml; Secchin, Ld, A sequential optimality condition related to the quasinormality constraint qualification and its algorithmic consequences, SIAM J Optim, 29, 1, 743-766 (2017) · Zbl 1451.90166
[9] Andreani, R.; Haeser, G.; Viana, Ds, Optimality conditions and global convergence for nonlinear semidefinite programming, Math Program (2017)
[10] Andreani, R.; Haeser, G.; Ramos, A.; Silva, Pjs, A second-order sequential optimality condition associated to the convergence of algorithms, IMA J Numer Anal, 37, 4, 1902-1929 (2017) · Zbl 1433.90156
[11] Andreani, R.; Martínez, Jm; Ramos, A.; Silva, Pjs, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math Oper Res, 43, 3, 693-717 (2018)
[12] Andreani, R.; Secchin, Ld; Silva, Pjs, Convergence properties of a second order augmented Lagrangian method for mathematical programs with complementarity constraints, SIAM J Optim, 3, 28, 2574-2600 (2018) · Zbl 1406.90114
[13] Bezdek K (1979) Optimal covering of circles. Ph.D. Thesis, University of Budapest (1979) · Zbl 0467.52008
[14] Bezdek, K., Über einige kreisüberdeckungen, Beiträge Algebra Geom, 14, 7-13 (1983) · Zbl 0507.52009
[15] Birgin, Eg; Martínez, Jm, Practical augmented Lagrangian methods for constrained optimization (2014), Philadelphia: Society for Industrial and Applied Mathematics (SIAM), Philadelphia · Zbl 1339.90312
[16] Birgin, Eg; Martínez, Jm; Raydan, M., Nonmonotone spectral projected gradient methods on convex sets, SIAM J Optim, 10, 4, 1196-1211 (2000) · Zbl 1047.90077
[17] Birgin, Eg; Martínez, Jm; Raydan, M., Spectral projected gradient methods: review and perspectives, J Stat Softw, 60, 3, 1-21 (2014)
[18] Birgin, Eg; Gardenghi, Jl; Martínez, Jm; Santos, Sa; Toint, Phl, Evaluation complexity for nonlinear constrained optimization using unscaled KKT conditions and high-order models, SIAM J Optim, 26, 951-967 (2016) · Zbl 1335.90094
[19] Birgin, Eg; Krejic, N.; Martínez, Jm, On the minimization of possibly discontinuous functions by means of pointwise approximations, Optim Lett, 11, 8, 1623-1637 (2017) · Zbl 1386.90142
[20] Birgin, Eg; Haeser, G.; Ramos, A., Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points, Comput Optim Appl, 69, 1, 51-75 (2018) · Zbl 1411.90316
[21] Bonnans, J. Frédéric; Shapiro, Alexander, Perturbation Analysis of Optimization Problems (2000), New York, NY: Springer New York, New York, NY · Zbl 0966.49001
[22] Bueno, Lf; Haeser, G.; Rojas, Fn, Optimality conditions and constraint qualifications for generalized nash equilibrium problems and their practical implications, SIAM J Optim, 29, 1, 31-54 (2019) · Zbl 1422.91049
[23] Choi, Md; Lam, Ty; Reznick, B., Sums of squares of real polynomials, Proc Symp Pure Math, 58, 2, 103-126 (1995) · Zbl 0821.11028
[24] Demyanov, Jh, On the maximization of a certain nondifferentiable function, J Optim Theory Appl, 7, 75-89 (1971) · Zbl 0191.17201
[25] Diniz-Ehrhardt, Ma; Gomes-Ruggiero, Ma; Martínez, Jm; Santos, Sa, Augmented Lagrangian algorithms based on the spectral projected gradient method for solving nonlinear programming problems, J Optim Theory Appl, 123, 3, 497-517 (2004) · Zbl 1186.90109
[26] Dutta, J.; Deb, K.; Tulshyan, R.; Arora, R., Approximate KKT points and a proximity measure for termination, J Glob Optim, 56, 4, 1463-1499 (2013) · Zbl 1297.90150
[27] Fejes Tóth G (2005) Thinnest covering of a circle by eight, nine or ten congruent circles. Mathematical Sciences Research Institute Publications, vol 52. Cambridge University Press, Cambridge, pp 361-376 · Zbl 1097.52006
[28] Fiala J, Kocvara M, Stingl M (2013) Penlab: a matlab solver for nonlinear semidefinite optimization. arXiv:1311.5240
[29] Gáspár, Z.; Tarnai, T., Covering a square by equal circles, El Math, 50, 167-170 (1995) · Zbl 0847.52018
[30] Gáspár, Z.; Tarnai, T.; Hincz, K., Partial covering of a circle by equal circles. Part I: the mechanicalmodels, J Comput Geom, 5, 104-125 (2014) · Zbl 1408.52031
[31] Gáspár, Z.; Tarnai, T.; Hincz, K., Partial covering of a circle by equal circles. Part II: the case of 5 circles, J Comput Geom, 5, 126-149 (2014) · Zbl 1408.52032
[32] Haeser, G., A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms, Comput Optim Appl, 70, 2, 615-639 (2018) · Zbl 1391.90636
[33] Haeser, G.; Melo, Vv, Convergence detection for optimization algorithms: approximate-KKT stopping criterion when Lagrange multipliers are not available, Oper Res Lett, 43, 5, 484-488 (2015) · Zbl 1408.90281
[34] Haeser, G.; Schuverdt, Ml, On approximate KKT condition and its extension to continuous variational inequalities, J Optim Theory Appl, 149, 3, 528-539 (2011) · Zbl 1220.90130
[35] Haeser G, Hinder O, Ye Y (2017) On the behavior of Lagrange multipliers in convex and non-convex infeasible interior point methods. arXiv:1707.07327
[36] Heppes, A.; Melissen, H., Covering a rectangle with equal circles, Period Math Hung, 34, 65-81 (1997) · Zbl 0880.52008
[37] Huang, Xx; Teo, Kl; Yang, Xq, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Acta Math Sin, 22, 5, 1283-1296 (2006) · Zbl 1126.90057
[38] Kočvara, M.; Stingl, M.; Di Pillo, G.; Murli, A., Pennon—a generalized augmented lagrangian method for semidefinite programming, High performance algorithms and software for nonlinear optimization, 297-315 (2003), Dordrecht: Kluwer Academic Publishers, Dordrecht · Zbl 1037.90003
[39] Kočvara, M.; Stingl, M., PENNON—a code for convex nonlinear and semidefinite programming, Optim Methods Softw, 18, 3, 317-333 (2010) · Zbl 1037.90003
[40] Lasserre, Jb, Moments. Positive polynomials and their applications (2010), London: Imperial College Press, London · Zbl 1211.90007
[41] Laurent, M., Sums of squares, moment matrices and optimization over polynomials, 11-49 (2009), New York: Springer, New York
[42] Löfberg J (2004) Yalmip: A toolbox for modeling and optimization in matlab. In: Proceedings of the CACSD conference, Taipei, Taiwan
[43] Luo, Hz; Wu, Hx; Chen, Gt, On the convergence of augmented lagrangian methods for nonlinear semidefinite programming, J Glob Optim, 54, 3, 599-618 (2012) · Zbl 1261.90035
[44] Martínez, Jm; Svaiter, Bf, A practical optimality condition without constraint qualifications for nonlinear programming, J Optim Theory Appl, 118, 1, 117-133 (2003) · Zbl 1033.90090
[45] Melissen H (1997) Packing and covering with circles. Ph.D. Thesis, University of Utrecht · Zbl 0880.52008
[46] Melissen, Jbm; Schuur, Pc, Improved coverings of a square with six and eight equal circles, Electron J Comb, 3, 1, 32 (1996) · Zbl 0889.52020
[47] Melissen, Jbm; Schuur, Pc, Covering a rectangle with six and seven circles, Discrete Appl Math, 99, 1-3, 149-156 (2000) · Zbl 0951.52017
[48] Minchenko, L.; Stakhovski, S., On relaxed constant rank regularity condition in mathematical programming, Optimization, 60, 4, 429-440 (2011) · Zbl 1250.90093
[49] Mito LM (2018) O problema de cobertura via geometria algébrica convexa. Master’s Thesis, University of São Paulo
[50] Nurmela KJ (1998) Covering a circle by congruent circular disks. Ph.D. Thesis, Helsinki University of Technology
[51] Nurmela KJ, Östergård PRJ (2000) Covering a square with up to 30 equal circles. Technical report, Helsinki University of Technology
[52] Parrilo, Pa, Semidefinite programming relaxations for semialgebraic problems, Math Program Ser B, 96, 293-320 (2003) · Zbl 1043.14018
[53] Putinar, M., Positive polynomials on compact semi-algebraic sets, Indiana Univ Math J, 42, 3, 969-984 (1993) · Zbl 0796.12002
[54] Qi, L.; Wei, Z., On the constant positive linear dependence conditions and its application to SQP methods, SIAM J Optim, 10, 4, 963-981 (2000) · Zbl 0999.90037
[55] Stengle, G., A nullstellensatz and a positivstellensatz in semialgebraic geometry, Math Ann, 207, 2, 87-97 (1974) · Zbl 0253.14001
[56] Sun, J.; Zhang, Lw; Wu, Y., Properties of the augmented Lagrangian in nonlinear semidefinite optimization, J Optim Theory Appl, 12, 3, 437-456 (2006) · Zbl 1278.90305
[57] Sun, D.; Sun, J.; Zhang, L., The rate of convergence of the augmented lagrangian method for nonlinear semidefinite programming, Math Program, 114, 2, 349-391 (2008) · Zbl 1190.90117
[58] Tuyen N V, Yao J, Wen C (2017) A note on approximate Karush-Kuhn-Tucker conditions in locally Lipschitz multiobjective optimization. arXiv:1711.08551 · Zbl 1434.90186
[59] Venceslau, H.; Lubke, D.; Xavier, A., Optimal covering of solid bodies by spheres via the hyperbolic smoothing technique, Optim Methods Softw, 30, 2, 391-403 (2014) · Zbl 1327.90249
[60] Wu, H.; Luo, H.; Ding, X.; Chen, G., Global convergence of modified augmented lagrangian methods for nonlinear semidefinite programmings, Comput Optim Appl, 56, 3, 531-558 (2013) · Zbl 1311.90096
[61] Xavier, Ae; Oliveira, Aaf, Optimum covering of plane domains by circles via hyperbolic smoothing method, J Glob Optim, 31, 493-504 (2005) · Zbl 1093.90023
[62] Yamashita, H.; Yabe, H., A survey of numerical methods for nonlinear semidefinite programming, J Oper Res Soc Jpn, 58, 1, 24-60 (2015) · Zbl 1367.65092
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.