×

Nonmonotone line search for minimax problems. (English) Zbl 0792.90079

Summary: It was recently shown [see E. R. Panier and the second author, SIAM J. Numer. Anal. 28, No. 4, 1183-1195 (1991; Zbl 0732.65055)] that, in the solution of smooth constrained optimization problems by sequential quadratic programming (SQP), the Maratos effect can be prevented by means of a certain nonmonotone (more precisely, three-step or four-step monotone) line search. Using a well-known transformation, this scheme can be readily extended to the case of minimax problems. It turns out however that, due to the structure of these problems, one can use a simpler scheme. Such a scheme is proposed and analyzed in this paper. Numerical experiments indicate a significant advantage of the proposed line search over the Armijo search.

MSC:

90C30 Nonlinear programming
49J35 Existence of solutions for minimax problems

Citations:

Zbl 0732.65055
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Polyak, R. A.,Smooth Optimization Methods for Minimax Problems, SIAM Journal on Control and Optimization, Vol. 26, pp. 1274-1286, 1988. · Zbl 0657.90075 · doi:10.1137/0326071
[2] Polak, E., Mayne, D. Q., andHiggins, J. E.,A Superlinearly Convergent Algorithm for Minmax Problems, Proceedings of the 28th IEEE Conference on Decision and Control, Tampa, Florida, Vol. 1, pp. 894-898, 1989. · doi:10.1109/CDC.1989.70250
[3] Conn, A. R., andLi, Y.,An Efficient Algorithm for Nonlinear Minimax Problems, Report CS-88-41, University of Waterloo, Waterloo, Ontario, Canada, 1989.
[4] Han, S. P.,Superlinear Convergence of a Minimax Method, Report TR-78-336, Department of Computer Science, Cornell University, Ithaca, New York, 1978.
[5] Han, S. P.,Variable Metric Methods for Minimizing a Class of Nondifferentiable Functions, Mathematical Programming, Vol. 20, pp. 1-13, 1981. · Zbl 0441.90095 · doi:10.1007/BF01589328
[6] Conn, A. R.,An Efficient Second-Order Method to Solve the Constrained Minimax Problem, Report CORR-79-5, Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Ontario, Canada, 1979.
[7] Murray, A. W., andOverton, M. L.,A Projected Lagrangian Algorithm for Nonlinear Minimax Optimization, SIAM Journal on Scientific and Statistical Computing, Vol. 1, pp. 345-370, 1980. · Zbl 0461.65052 · doi:10.1137/0901025
[8] Overton, M. L., Algorithms for Nonlinear l1 and475-1, Nonlinear Optimization 1981, Edited by M. J. D. Powell, Academic Press, London, England, pp. 213-221, 1982.
[9] Womersley, R. S., andFletcher, R.,An Algorithm for Composite Nonsmooth Optimization Problems, Journal of Optimization Theory and Applications, Vol. 48, pp. 493-523, 1986. · Zbl 0562.90077 · doi:10.1007/BF00940574
[10] Chamberlain, R. M., Powell, M. J. D., Lemarechal, C., andPedersen, H. C.,The Watchdog Technique for Forcing Convergence in Algorithms for Constrained Optimization, Mathematical Programming Study, Vol. 16, pp. 1-17, 1982. · Zbl 0477.90072 · doi:10.1007/BFb0120945
[11] Fletcher, R.,Second-Order Corrections for Nondifferentiable Optimization, Lecture Notes in Mathematics, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, Vol. 912, pp. 85-114, 1981.
[12] Mayne, D. Q., andPolak, E.,A Superlinearly Convergent Algorithm for Constrained Optimization Problems, Mathematical Programming Study, Vol. 16, pp. 45-61, 1982. · Zbl 0477.90071 · doi:10.1007/BFb0120947
[13] Grippo, L., Lampariello, F., andLucidi, S.,A Nonmonotone Line Search Technique for Newton’s Method, SIAM Journal on Numerical Analysis, Vol. 23, pp. 707-716, 1986. · Zbl 0616.65067 · doi:10.1137/0723046
[14] Panier, E. R., andTits, A. L.,Avoiding the Maratos Effect by Means of a Nonmonotone Line Search, Part 1: General Constrained Problems, SIAM Journal on Numerical Analysis, Vol. 28, pp. 1183-1195, 1991. · Zbl 0732.65055 · doi:10.1137/0728063
[15] Bonnans, J. F., Panier, E. R., Tits, A. L., andZhou, J. L.,Avoiding the Maratos Effect by Means of a Nonmonotone Line Search, Part 2: Inequality Constrained Problems?Feasible Iterates, SIAM Journal on Numerical Analysis, Vol. 29, pp. 1187-1202, 1992. · Zbl 0763.65042 · doi:10.1137/0729072
[16] Panier, E. R., andTits, A. L.,A Superlinearly Convergent Method of Feasible Directions for Optimization Problems Arising in the Design of Engineering Systems, Lecture Notes in Control and Information Sciences, Edited by A. Bensoussan and J. L. Lions, Springer-Verlag, Berlin, Germany, Vol. 83, pp. 65-73, 1986. · Zbl 0605.90094
[17] Powell, M. J. D.,A Fast Algorithm for Nonlinearly Constrained Optimization Calculations, Lecture Notes in Mathematics, Edited by G. A. Watson, Springer-Verlag, Berlin, Germany, Vol. 630, pp. 144-157, 1978. · Zbl 0374.65032
[18] Powell, M. J. D.,The Convergence of Variable Metric Methods for Nonlinearly Constrained Optimization Calculations, Nonlinear Programming 3, Edited by O. L. Mangasarian, R. R. Meyer, S. M. Robinson, Academic Press, New York, New York, pp. 27-63, 1978.
[19] Stoer, J.,The Convergence of Sequential Quadratic Programming Methods for Solving Nonlinear Programs, Recent Advances in Communication and Control Theory, Edited by R. E. Kalman, G. I. Marchuk, A. E. Ruberti, and A. J. Viterbi, Optimization Software, New York, New York, pp. 412-421, 1987.
[20] Zhou, J. L., andTits, A. L.,User’s Guide for FSQP Version 2.4?A Fortran Code for Solving Optimization Problems, Possibly Minimax, with General Inequality Constraints and Linear Equality Constraints, Generating Feasible Iterates, Report TR-90-60, Systems Research Center, University of Maryland, College Park, Maryland, 1991.
[21] Watson, G. A.,The Minimax Solution of an Overdetermined System of Nonlinear Equations, Journal of the Institute for Mathematics and Its Applications, Vol. 23, pp. 167-180, 1979. · Zbl 0406.65025 · doi:10.1093/imamat/23.2.167
[22] Charalambous, C., andConn, A. R.,An Efficient Method to Solve the Minimax problem Directly, SIAM Journal on Numerical Analysis, Vol. 15, pp. 162-187, 1978. · Zbl 0384.65032 · doi:10.1137/0715011
[23] Madsen, K., andSchjaer-Jacobsen, H.,Linearly Constrained Minimax Optimization, Mathematical Programming, Vol. 14, pp. 208-223, 1978. · Zbl 0375.65034 · doi:10.1007/BF01588966
[24] Hock, W., andSchittkowski, K.,Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems, Springer-Verlag, Berlin, Germany, Vol. 187, 1981. · Zbl 0452.90038
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.