• Original Articles •

### A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM

Fusheng Wang1, Chuanlong Wang1, Li Wang2

1. 1. Department of Mathematics, Taiyuan Normal University, Taiyuan 030012, China;
2. Department of Mathematics, University of California, San Diego, USA
• Received:2010-10-30 Revised:2011-07-29 Online:2012-05-15 Published:2012-05-07

Fusheng Wang, Chuanlong Wang, Li Wang. A NEW TRUST-REGION ALGORITHM FOR FINITE MINIMAX PROBLEM[J]. Journal of Computational Mathematics, 2012, 30(3): 262-278.

In this paper, a new trust region algorithm for minimax optimization problems is proposed, which solves only one quadratic subproblem based on a new approximation model at each iteration. The approach is different with the traditional algorithms that usually require to solve two quadratic subproblems. Moreover, to avoid Maratos effect, the nonmonotone strategy is employed. The analysis shows that, under standard conditions, the algorithm has global and superlinear convergence. Preliminary numerical experiments are conducted to show the effiency of the new method.

CLC Number:

 [1] G.A. Watson, The minimax solution of an overdetermined systemof nonlinear equations, Journalof the Institute for Mathematics and its Applications, 23 (1979), 167-180.[2] M.L. Overton, Algorithms for nonlinear l1 and l∞ fitting, Nonlinear optimization, 1981, Editedby M. J. D. Powell, Academic Press, London, England, 1982, 213-221.[3] M. Gaudioso, M.F. Monaco, A boundle type approach to the unconstrained minimization of convexnonsmooth functions, Math. Program., 23 (1982), 216-226.[4] X. Chen, Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations,J. Comput. Appl. Math., 80 (1997), 105-126.[5] X. Chen, Smoothing methods for complementarity problems and their applications: a survey,Journal of the Operations Research Society of Japan, 43 (2000), 32-47.[6] P.P. Shen, Y.J.Wang, A new pruning test for finding all global minimizers of nonsmooth functions,Appl. Math. Comput., 168 (2005), 739-755.[7] G. Di Pillo, L. Grippo, S. Lucidi, A smooth method for the finite minimax problem, Math.Program., 60 (1993), 187-214.[8] Y. Xue, The sequential quadratic programming method for solving minimax problem, Journal ofSystems Science and Mathematical Sciences, 22 (2002), 355-364.[9] Y. Xue, A Newton like algorithm for solving minimax problem, Journal on Numerical Methodsand Computer Applications, 2 (2004), 108-115.[10] J.B. Jian, R. Quan, Q.J. Hu, A new superlinearly convergent SQP algorithm for nonlinear minimaxproblem, Acta Mathematicae Applicatae Sinica, English series, 23 (2007), 395-410.[11] Z.B. Zhu, X. Cai, J.B. Jian, An improved SQP algorithm for solving minimax problems, Appl.Math. Lett., 22 (2009), 464-469.[12] E. Polak, D.H. Mayne, J.E. Higgins, Superlinearly convergent algorithm for min-max problems,J. Optimiz. Theorey Appl., 69 (1991), 407-439.[13] A. Vardi, New minimax algorithm, J. Optimiz. Theorey Appl., 75 (1992), 613-634.[14] S.P. Han, Variable metric methods for minimizing a class of nondifferentiable functions, Math.Program., 20 (1981), 1-13.[15] J.L. Zhou, A.L. Tits, Nonmonotone line search for minimax problems, J. Optimiz. Theorey Appl.,76 (1993), 455-476.[16] W.Y. Sun, On the convergence of an iterative method for the minimax problem, J. Aust. Math.Soc., Ser. B, 39 (1997), 280-292.[17] A.R. Conn, N.I. M. Gould, P.L. Toint, Trust-Region Methods, MPS/SIAM, Philadeiphia, 2000.[18] R. Fletcher, Second order correction for nondifferentiable optimization problems, in: G.A.Watson,ed., Numerical Analysis, (1982), 85-114.[19] R. Fletcher, A model algorithm for composite nondifferentiable optimization problems, MathematicalProgramming Study, 17 (1982), 67-76.[20] Y. Yuan, On the superlinear convergence of a trust-region algorithm for nonsmooth optimization,Math. Program., 31 (1985), 269-285.[21] E.R. Panier, A.L. Tits, Avoiding the Maratos effect by means of a nonmonotone line search, Part1: General constrained problems, SIAM J. Numer. Anal., 28 (1991), 1183-1195.[22] J.Y. Fan, W.B. Ai, Q.Y. Zhang, A line search and trust region algorithm with trust region radiusconverging to zero, J. Comput. Math., 22:6 (2004), 865-873.[23] Q.Y. Zhou, W.Y. Sun, An adaptive nonmonotonic trust region method with curvilinear searches,J. Comput. Math., 6 (2006), 761-771.[24] J.T. Mo, K.C. Zhang, Z.X. Wei, A nonmonotone trust region method for unconstrained optimization,Appl. Math. Comput., 171 (2005), 371-384.[25] F.S. Wang, K.C. Zhang, A hybrid algorithm for nonlinear minimax problems, Ann. Oper. Res.,164 (2008), 167-191.[26] M.J.D. Powell, On the global convergence of trust region algorithm for unconstrained minimization,Math. Program., 29 (1984), 297-303.[27] Y.X. Yuan, W.Y. Sun, Optimization Theory and Methods, Science Press, Beijing, China, 1997.[28] L. Luksan, A compact variable metric algorithm for nonlinear minimax approximation, Computing,36 (1986), 355-373.
 No related articles found!
Viewed
Full text

Abstract