×
Wang, Fusheng; Wang, Yanping

Nonmonotone algorithm for minimax optimization problems. (English) Zbl 1215.65114

Appl. Math. Comput. 217, No. 13, 6296-6308 (2011).
The paper deals with finite minimax optimization problems \[ \min_{x\in\mathbb{R}^n}\;\max_{1\leq i\leq m}\, f_i(x), \] where all functions \(f_i\) are twice continuously differentiable. Equivalently, the function \(\Phi(x)= \max f_i(x)\) is to minimize. The problem is not necessarily differentiable, but it is possible to transform the task to a differentiable programming problem with side conditions (inequalities). The authors introduce a nonmonotone algorithm for the construction of a minimizing sequence. The algorithm takes not only the advantage of nonmonotone strategy and second-order step but also the advantages of trust-region methods and line search methods. The new algorithm is of strongly global convergence and superlinear convergence. Numerical experiments (10 examples) indicate the efficiency.
Reviewer: Werner H. Schmidt (Greifswald)

Cited in 6 Documents

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C47 Minimax problems in mathematical programming

Keywords:

minimax optimization problem; algorithm with nonmonotone strategy; hybrid technique; second-order correction; superlinear convergence
PDF BibTeX XML Cite
\textit{F. Wang} and \textit{Y. Wang}, Appl. Math. Comput. 217, No. 13, 6296--6308 (2011; Zbl 1215.65114)
Full Text: DOI

References:

[1] Overton, Michael L., Algorithms for nonlinear \(l_1\) and \(l_∞\) fitting, (Powell, M. J.D., Nonlinear optimization 1981 (1982), Academic Press: Academic Press London), 213-221
[2] Shen, P. P.; Wang, Y. J., A new pruning test for finding all global minimizers of nonsmooth functions, Applied Mathematics and Computation, 168, 739-755 (2005) · Zbl 1107.65322
[3] Mo, J. T.; Liu, C. Y.; Yan, S. C., A nonmonotone trust region method based on nonincreasing technique of weighted average of the successive function values, Journal of Computational and Applied Mathematics, 209, 97-108 (2007) · Zbl 1142.65049
[4] Zhou, J. L.; Tits, A. L., Nonmonotone line search for minimax problems, Journal of Optimization Theory and Applications, 76, 455-476 (1993) · Zbl 0792.90079
[5] Zhu, Z. B.; Cai, Xiang; Jian, Jinbao, An improved SQP algorithm for solving minimax problems, Applied Mathematics Letters, 22, 464-469 (2009) · Zbl 1189.90193
[6] Jian, J. B.; Ran, Q.; Hu, Q. J., A new superlinearly convergent SQP algorithm for nonlinear minimax problem, Acta Mathematicae Applicatae Sinica (English series), 23, 395-410 (2007) · Zbl 1145.90103
[7] Ploak, E., Basics of minimax algorithms, (Clarke, F. H.; Demyanov, V. F.; Giannessi, F., Nonsmooth Optimization and Related Topics (1989), Plenum: Plenum New York), 343-369 · Zbl 0777.90061
[8] Polak, E.; Mayne, D. H.; Higgins, J. E., Superlinearly convergent algorithm for min-max problems, Journal of Optimization Theory and Applications, 69, 407-439 (1991) · Zbl 0724.90066
[9] Gaudioso, M.; Monaco, M. F., A boundle type approach to the unconstrained minimization of convex nonsmooth functions, Mathematical Programming, 23, 216-226 (1982) · Zbl 0479.90066
[10] Fletcher, R., Second order correction for nondifferentiable optimization problems, (Watson, G. A., Numerical Analysis (1982), Springer: Springer Berlin), 85-114
[11] Fletcher, R., A model algorithm for composite nondifferentiable optimization problems, Mathematical Programming Study, 17, 67-76 (1982) · Zbl 0478.90063
[12] Wang, F. S.; Zhang, K. C., A hybrid algorithm for minimax optimization, Annals of Operations Research, 164, 67-191 (2008)
[13] Xue, Y., The sequential quadratic programming method for solving minimax problem, Journal of Systems Science and Mathematical Sciences, 22, 355-364 (2002) · Zbl 1046.90104
[14] Xue, Y., A Newton like algorithm for solving minimax problem, Journal on Numerical Methods and Computer Applications, 2, 108-115 (2004)
[15] Yuan, Y., On the superlinear convergence of a trust-region algorithm for nonsmooth optimization, Mathematical Programming, 31, 269-285 (1985) · Zbl 0577.90066
[16] Yu, Y. H.; Gao, L., Nonmonotone Line Search for constrained Minimax Problems, Journal of Optimization Theory and Application, 115, 419-446 (2002) · Zbl 1039.90089
[17] Gertz, E. M., A quasi-Newton trust-region method, Mathematical Programming100, 447-470 (2004) · Zbl 1068.90108
[18] Panier, E. R.; Tits, A. L., Avoiding the Maratos effect by means of a nonmonotone line search, Part 1: General constrained problems, SIAM Journal on Numerical Analysis, 28, 1183-1195 (1991) · Zbl 0732.65055
[19] Wang, F. S.; Zhang, K. C.; Tan, X. L., A fractional programming algorithm based on conic quasi-Newton trust region method for unconstrained minimization, Applied Mathematics and Computation, 181, 1061-1067 (2006) · Zbl 1106.65054
[20] Zhang, J. L.; Zhang, X. S., A nonmonotone adaptive trust region method and its convergence, Computers and Mathematics with Applications, 45, 1469-1477 (2003) · Zbl 1065.90071
[21] Zhang, J. L.; Zhang, X. S., A modified SQP method with nonmonotone linesearch technique, Journal of Global Optimization, 21, 201-218 (2001) · Zbl 1068.90616
[22] Nocedal, J.; Wright, S. J., Numerical optimization (2006), Science Press: Science Press Beijing · Zbl 1104.65059
[23] Grippo, L.; Lampariello, F.; Lucidi, S., A nonmonotone line search for Newton’s method, SIAM Journal on Numerical Analysis, 23, 4, 707-716 (1986) · Zbl 0616.65067
[24] Powell, M. J.D., On the global convergence of trust region algorithm for unconstrained minimization, Mathematical Programming, 29, 297-303 (1984) · Zbl 0569.90069
[25] Deng, N. Y.; Xiao, Y.; Zhou, F. J., Nonmonotic trust region algorithm, Journal of Optimization Theory and Application, 76, 2, 259-285 (1993) · Zbl 0797.90088
[26] Toint, P. L., An assessment of non-monotone line search techniques for unconstrained optimization, SIAM Journal on Scientific and Statistical Computing, 17, 3, 725-739 (1996) · Zbl 0849.90113
[27] Sun, W. Y., Nonmonotone trust region method for solving optimization problems, Applied Mathematics and computation, 156, 1, 159-174 (2004) · Zbl 1059.65055
[28] Yuan, Y., On the convergence of a new trust region algorithm, Numerische Mathematik, 70, 515-539 (1995) · Zbl 0828.65062
[29] Yuan, Y.; Sun, W. Y., The theory and methods of optimization (1997), Science Press: Science Press Beijing
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.