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

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.

### MSC:

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

### References:

  Overton, Michael L., Algorithms for nonlinear l_{1} and l∞ Fitting, (), 213-221  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  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  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  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  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  Ploak, E., Basics of minimax algorithms, (), 343-369 · Zbl 0777.90061  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  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  Fletcher, R., Second order correction for nondifferentiable optimization problems, (), 85-114  Fletcher, R., A model algorithm for composite nondifferentiable optimization problems, Mathematical programming study, 17, 67-76, (1982) · Zbl 0478.90063  Wang, F.S.; Zhang, K.C., A hybrid algorithm for minimax optimization, Annals of operations research, 164, 67-191, (2008)  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  Xue, Y., A Newton like algorithm for solving minimax problem, Journal on numerical methods and computer applications, 2, 108-115, (2004)  Yuan, Y., On the superlinear convergence of a trust-region algorithm for nonsmooth optimization, Mathematical programming, 31, 269-285, (1985) · Zbl 0577.90066  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  Gertz, E.M., A quasi-Newton trust-region method, Mathematical programming100, 447-470, (2004) · Zbl 1068.90108  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  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  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  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  Nocedal, J.; Wright, S.J., Numerical optimization, (2006), Science Press Beijing · Zbl 1104.65059  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  Powell, M.J.D., On the global convergence of trust region algorithm for unconstrained minimization, Mathematical programming, 29, 297-303, (1984) · Zbl 0569.90069  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  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  Sun, W.Y., Nonmonotone trust region method for solving optimization problems, Applied mathematics and computation, 156, 1, 159-174, (2004) · Zbl 1059.65055  Yuan, Y., On the convergence of a new trust region algorithm, Numerische Mathematik, 70, 515-539, (1995) · Zbl 0828.65062  Yuan, Y.; Sun, W.Y., The theory and methods of optimization, (1997), 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.