The global convergence of augmented Lagrangian methods based on NCP function in constrained nonconvex optimization. (English) Zbl 1160.65031
The authors study the global convergence properties for modified augmented Lagrangian methods using a class of augmented Lagrangian functions based on nonlinear complementarity problem (NCP) function for inequality constrained optimization problems. They show that under weaker conditions, the augmented Lagrangian method using safeguarding strategy converges to a Karush-Kuhn-Tucker point or a degenerate point of the original problem. The convergence properties of the augmented Lagrangian method using conditional multiplier updating rule is presented. The use of penalty parameter updating criteria and normalization of the multipliers in augmented Lagrangian methods is investigated. Some preliminary numerical results on the four proposed modified augmented algorithms are presented.
Reviewer: Hang Lau (Montréal)
MSC:
| 65K05 | Numerical mathematical programming methods |
| 90C26 | Nonconvex programming, global optimization |
| 90C33 | Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) |
Keywords:
nonconvex optimization; constrained optimization; augmented Lagrangian methods; convergence to KKT point; degenerate point; nonlinear complementarity problem; Karush-Kuhn-Tucker point; numerical results; algorithmsReferences:
| [1] | 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) · Zbl 1151.49027 |
| [2] | 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., 111, 5-32 (2008) · Zbl 1163.90041 |
| [3] | Bartholomew-Biggs, M. C., Recursive quadratic programming methods based on the augmented Lagrangian function, Math. Program. Study, 31, 21-41 (1987) · Zbl 0636.90079 |
| [4] | Bertsekas, D. P., Constrained Optimization and Lagrangian Multiplier Methods (1982), Academic Press: Academic Press New York · Zbl 0453.65045 |
| [5] | Birgin, E. G.; Castillo, R. A.; Martínez, J. M., Numerical comparison of augmented Lagrangian algorithms for nonconvex problems, Comput. Optim. Appl., 31, 31-55 (2005) · Zbl 1101.90066 |
| [6] | Coleman, T. F.; Li, Y., On the convergence of reflective Newton methods for large-scale nonlinear minimization subject to bounds, Math. Program., 67, 189-224 (1994) · Zbl 0842.90106 |
| [7] | Coleman, T. F.; Li, Y., An interior trust region approach for nonlinear minimization subject to bounds, SIAM J. Optim., 6, 418-445 (1996) · Zbl 0855.65063 |
| [8] | Conn, A. R.; Gould, N. I.M.; Sartenaer, A.; Toint, P. L., Convergence properties of an augmented Lagrangian algorithm for optimization with a combination of general equality and linear constraints, SIAM J. Optim., 6, 674-703 (1996) · Zbl 0856.90098 |
| [9] | Conn, A. R.; Gould, N. I.M.; Toint, P. L., A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds, SIAM J. Numer. Anal., 28, 545-572 (1991) · Zbl 0724.65067 |
| [10] | Contesse-Becker, L., Extended convergence results for the method of multipliers for nonstrictly binding inequality constraints, J. Optim. Theory Appl., 79, 273-310 (1993) · Zbl 0797.90087 |
| [11] | Floudas, C. A.; Pardalos, P. M.; Adjiman, C. S.; Esposito, W. R.; Gumus, Z. H.; Harding, S. T.; Klepeis, J. L.; Meyer, C. A.; Schweiger, C. A., Handbook of Test Problems in Local and Global Optimization (1999), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 0943.90001 |
| [12] | Griva, I.; Polyak, R., A primal-dual nonlinear rescaling method with dynamic scaling parameter update, Math. Program., 106, 237-259 (2006) · Zbl 1134.90494 |
| [13] | Hager, W. W., Dual techniques for constrained optimization, J. Optim. Theory Appl., 55, 37-71 (1987) · Zbl 0622.90075 |
| [14] | Hestenes, M. R., Multiplier and gradient methods, J. Optim. Theory Appl., 4, 303-320 (1969) · Zbl 0174.20705 |
| [15] | Huang, X. X.; Yang, X. Q., A unified augmented Lagrangian approach to duality and exact penalization, Math. Oper. Res., 28, 524-532 (2003) · Zbl 1082.90135 |
| [16] | Kiwiel, K. C., On the twice differentiable cubic augmented Lagrangian, J. Optim. Theory Appl., 88, 233-236 (1996) · Zbl 0842.90093 |
| [17] | B.W. Kort, D.P. Bertsekas, A new penalty method for constrained minimization, in: Proceedings of the 1972 IEEE Conference on Decision and Control, New Orleans, 1972, pp. 162-166.; B.W. Kort, D.P. Bertsekas, A new penalty method for constrained minimization, in: Proceedings of the 1972 IEEE Conference on Decision and Control, New Orleans, 1972, pp. 162-166. |
| [18] | Kort, B. W.; Bertsekas, D. P., Combined primal-dual and penalty methods for convex programming, SIAM J. Control Optim., 14, 268-294 (1976) · Zbl 0332.90035 |
| [19] | Lewis, R. M.; Torczon, V., A globally convergent augmented Lagrangian pattern search algorithm for optimization with general constraints and simple bounds, SIAM J. Optim., 12, 1075-1089 (2002) · Zbl 1011.65030 |
| [20] | Li, D., Zero duality gap for a class of nonconvex optimization problems, J. Optim. Theory Appl., 85, 309-324 (1995) · Zbl 0829.90109 |
| [21] | Li, D.; Sun, X. L., Convexification and existence of saddle point in a \(p\) th-power reformulation for nonconvex constrained optimization, Nonlinear Anal., 47, 5611-5622 (2001) · Zbl 1042.90643 |
| [22] | Li, D.; Sun, X. L., Existence of a saddle point in nonconvex constrained optimization, J. Global Optim., 21, 39-50 (2001) · Zbl 1099.90590 |
| [23] | H.Z. Luo, Studies on the augmented Lagrangian methods and convexification methods for constrained global optimization, Ph.D. Thesis, Department of Mathematics, Shanghai University, 2007.; H.Z. Luo, Studies on the augmented Lagrangian methods and convexification methods for constrained global optimization, Ph.D. Thesis, Department of Mathematics, Shanghai University, 2007. |
| [24] | Luo, H. Z.; Sun, X. L.; Li, D., On the convergence of augmented Lagrangian methods for constrained global optimization, SIAM J. Optim., 18, 1209-1230 (2007) · Zbl 1162.90019 |
| [25] | Luo, H. Z.; Sun, X. L.; Wu, H. X., Convergence properties of augmented Lagrangian methods for constrained global optimization, Optim. Methods Softw., 23, 763-778 (2008) · Zbl 1154.90575 |
| [26] | Mangasarian, O. L., Unconstrained Lagrangians in nonlinear programming, SIAM J. Control Optim., 13, 772-791 (1975) · Zbl 0269.90045 |
| [27] | Nguyen, V. H.; Strodiot, J. J., On the convergence rate of a penalty function method of exponential type, J. Optim. Theory Appl., 27, 495-508 (1979) · Zbl 0378.90087 |
| [28] | Di Pillo, G.; Lucidi, S., An augmented Lagrangian function with improved exactness properties, SIAM J. Optim., 12, 376-406 (2001) · Zbl 0996.65064 |
| [29] | Polak, E.; Tits, A. L., A globally convergent implementable multiplier method with automatic penalty limitation, Appl. Math. Optim., 6, 335-360 (1980) · Zbl 0445.90070 |
| [30] | Polyak, R., Modified barrier functions: theory and methods, Math. Program., 54, 177-222 (1992) · Zbl 0756.90085 |
| [31] | Polyak, R., Nonlinear rescaling vs. smoothing technique in convex optimization, Math. Program., 92, 197-235 (2002) · Zbl 1022.90014 |
| [32] | Powell, M. J.D., A method for nonlinear constraints in minimization problems, (Fletcher, R., Optimization (1969), Academic Press: Academic Press New York), 283-298 · Zbl 0881.65003 |
| [33] | Ren, Y. H.; Zhang, L. W.; Xiao, X. T., A nonlinear Lagrangian based on Fischer-Burmeister NCP function, Appl. Math. Comput., 188, 1344-1363 (2007) · Zbl 1119.65054 |
| [34] | Rockafellar, R. T., The multiplier method of Hestenes and Powell applied to convex programming, J. Optim. Theory Appl., 12, 555-562 (1973) · Zbl 0254.90045 |
| [35] | Rockafellar, R. T., Augmented Lagrange multiplier functions and duality in nonconvex programming, SIAM J. Control Optim., 12, 268-285 (1974) · Zbl 0257.90046 |
| [36] | Rockafellar, R. T., Lagrange multipliers and optimality, SIAM Rev., 35, 183-238 (1993) · Zbl 0779.49024 |
| [37] | Rubinov, A. M.; Huang, X. X.; Yang, X. Q., The zero duality gap property and lower semicontinuity of the perturbation function, Math. Oper. Res., 27, 775-791 (2002) · Zbl 1082.90567 |
| [38] | Rubinov, A. M.; Yang, X. Q., Lagrange-type Functions in Constrained Non-Convex Optimization (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht · Zbl 1136.90503 |
| [39] | Sun, X. L.; Li, D.; McKinnon, K. I.M., On saddle points of augmented Lagrangians for constrained nonconvex optimization, SIAM J. Optim., 15, 1128-1146 (2005) · Zbl 1114.90099 |
| [40] | Tseng, P.; Bertsekas, D. P., On the convergence of the exponential multiplier method for convex programming, Math. Program., 60, 1-19 (1993) · Zbl 0783.90101 |
| [41] | Xu, Z. K., Local saddle points and convexification for nonconvex optimization problems, J. Optim. Theory Appl., 94, 739-746 (1997) · Zbl 0899.90136 |
| [42] | Yamashita, H., A globally convergent constrained quasi-Newton method with an augmented Lagrangian type penalty function, Math. Program., 23, 75-86 (1982) · Zbl 0477.90056 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
