Previous Articles     Next Articles

A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM

Bothina El-Sobky, Abdallah Abotahoun   

  1. Department of Mathematics, Alexandria University, Alexandria, Egypt
  • Received:2016-08-29 Revised:2017-03-02 Online:2018-11-15 Published:2018-11-15
  • Supported by:

    The authors would like to thank the anonymous referees for their valuable comments and suggestions which have helped to greatly improve this paper.

Bothina El-Sobky, Abdallah Abotahoun. A TRUST-REGION ALGORITHM FOR SOLVING MINI-MAX PROBLEM[J]. Journal of Computational Mathematics, 2018, 36(6): 776-791.

In this paper, we propose an algorithm for solving inequality constrained mini-max optimization problem. In this algorithm, an active set strategy is used together with multiplier method to convert the inequality constrained mini-max optimization problem into unconstrained optimization problem. A trust-region method is a well-accepted technique in constrained optimization to assure global convergence and is more robust when they deal with rounding errors. One of the advantages of trust-region method is that it does not require the objective function of the model to be convex.
A global convergence analysis for the proposed algorithm is presented under some conditions. To show the efficiency of the algorithm numerical results for a number of test problems are reported.

CLC Number: 

[1] V. Dem'yanov and V. Malozemov, Introduction to Minimax, New York, Wiley (1974).

[2] D. Du and P. Pardalos, Minimax and applications, Dordrecht, Kluwer (1995).

[3] C. Charalambous and A. Conn, An eficient method to solve the minimax problem directly, SIAM J. Numer. Anal., 15(1978), 162-187.

[4] G. DiPillo, L. Grippo, and S. Lucidi, A smooth method for the finite minimax problem, Mathematical Programming, 60(1993), 187-214.

[5] J. Jian and M. Chao, A sequential quadratically constrained quadratic programming method for unconstrained minimax problems, J. Math. Anal. Appl., 362(2010), 34-45.

[6] E. Polak, D. Mayne, and J. Higgins, Superlinearly convergent algorithm for minimax problems, Journal of Optimization Theorey and Application, 69(1991), 407-439.

[7] L. Qi and W. Sun, An iterative method for the minimax problem, in minimax and applications, Kulwer Academic Publisher, Boston, 1995, 55-67.

[8] F. Wang and K. Zhang, A hybrid algorithm for nonlinear minimax problems, Ann. Oper. Res., 164(2008), 167-191.

[9] S. Xu, Smoothing method for minimax problems, Comput. Optim. Appl., 20:3(2001), 267-279.

[10] Y. Xue, The sequential quadratic programming method for solving minimax problem, Science and Systems Engineering, 22:3(2002), 355-364.

[11] Yuan. Y, On the superlinear convergence of a trust-region algorithm for nonsmooth optimization, Mathematical Programming, 31(1985), 269-285.

[12] Yi.X, The sequential quadratic programming method for solving minimax problem, Journal of Systems Science and Mathematical Sciences, 22(2002), 355-364.

[13] Yi. X, A Newton like algorithm for solving minimax problem, Journal on Numerical Methods and Computer Applications 2, 108-115(2004).

[14] M. Gaudioso and M. Monaco, A bundle type approach to the unconstrained minimization of convex nonsmooth functions, Mathematical Programming, 23:1(1982), 216-226.

[15] J. Zowe, Nondifferentiable optimziation:a motivation and a short introduction into the subgradient and the bundle concept, Computational Mathematical Programming, Springer, New York (1985).

[16] F. Ye, H. Liu, S. Zhou, and S. Liu, A smoothing trust-region Newton-CG method for minimax problem, Applied Mathematics and Computation, 199:2(2008), 581-589.

[17] A. Fiacco and G. McCormick, Nonlinear Programming:Sequential unconstrained minimization techniques, John Wiley and Sons, New York, (1968).

[18] J. Dennis, M. El-Alem, and K. Williamson, A trust-region approach to nonlinear systems of equalities and inequalities, SIAM J. Optimization, 9(1999), 291-315.

[19] B. El-Sobky, A global convergence theory for an active trust region algorithm for solving the general nonlinear programming problem, Applied Mathematics and Computation, 144:1(2003), 127-157.

[20] B. El-Sobky, A Multiplier active-set trust-region algorithm for solving constrained optimization problem, Applied Mathematics and Computation, 219(2012), 127-157.

[21] B. El-Sobky and Y. Abouel-Naga, Multi-objective economic emission load dispatch problem with trust-region strategy, Electric Power Systems Research, 108(2014), 254-269.

[22] M. Hestenes, Mutiplier and gradient methods, JOTA, 4(1969), 303-320.

[23] T. Coleman and Y. Li, An interior trust region approach for nonlinear minimization subject to bounds, SIAM J. Optimization, 6(1996), 418-445.

[24] J. Dennis, M. El-Alem, and M. Maciel, A global convergence theory for general trust-region-based algorithms for equality constrained optimization, SIAM J. Optimization, 7:1(1997), 177-207.

[25] B. El-Sobky, A new Convergence theory for trust-region algorithm for solving constrained optimization problems, Applied Mathematics Science, 7:110(2013), 5469-5489.

[26] B. El-Sobky, A penalty active-set trust-region algorithm for solving general nonlinear programming problem, Sylwan, 158:9(2014), 273-290.

[27] Y. Pei and D. Zhu, A trust-region algorithm combining line search filter technique for nonlinear constrained optimization. International Journal of Computer Mathematics, 91:8(2014), 1817?839.

[28] Y. Yuan, Recent advances in trust region algorithms, Math. Program. Ser. B, 151(2015), 249-281.

[29] J. Dennis and R. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall, Englewood N.J. Cliffs, (1983).

[30] J. Moré and D. Sorensen, Computing a trust-region step, SIAM J. Sci. Stats. Comput., 4(1983), 553-572.

[31] T. Steihaug, The conjugate gradient method and trust-region in large scale optimization, SIAM J. Numer. Anal., 20(1983), 3.

[32] Y. Yuan, On the convergence of a new trust region algorithm, Numer. Math. 70(1995), 515-539.

[33] O. Mangasarian, Nonlinear Programming, McGraw-Hill Book Company, New York, (1969).

[34] M. El-Alem, M. Abdel-Aziz, and A. El-Bakry, A projected Hessian Gauss-Newton algorithm for solving systems of nonlinear equations and inequalities, Inter.J. of Math. and Math. Sc., 25:6(2001), 397-409.

[35] B. Rustem and Q. Nguyen, An algorithm for the inequality-constrained discrete min-max problem, SIAM J. Optim., 8:1(1998), 265-283.
[1] Xiaoyu Wang, Ya-xiang Yuan. STOCHASTIC TRUST-REGION METHODS WITH TRUST-REGION RADIUS DEPENDING ON PROBABILISTIC MODELS [J]. Journal of Computational Mathematics, 2022, 40(2): 294-334.
[2] Yuting Chen, Mingyuan Cao, Yueting Yang, Qingdao Huang. AN ADAPTIVE TRUST-REGION METHOD FOR GENERALIZED EIGENVALUES OF SYMMETRIC TENSORS [J]. Journal of Computational Mathematics, 2021, 39(3): 358-374.
[3] Keke Zhang, Hongwei Liu, Zexian Liu. A NEW ADAPTIVE SUBSPACE MINIMIZATION THREE-TERM CONJUGATE GRADIENT ALGORITHM FOR UNCONSTRAINED OPTIMIZATION [J]. Journal of Computational Mathematics, 2021, 39(2): 159-177.
[4] Wenjuan Xue, Weiai Liu. A MULTIDIMENSIONAL FILTER SQP ALGORITHM FOR NONLINEAR PROGRAMMING [J]. Journal of Computational Mathematics, 2020, 38(5): 683-704.
[5] Liqiang Song, Wei Hong Yang. A BLOCK LANCZOS METHOD FOR THE CDT SUBPROBLEM [J]. Journal of Computational Mathematics, 2019, 37(2): 240-260.
[6] Fan Jiang, Deren Han, Xiaofei Zhang. A TRUST-REGION-BASED ALTERNATING LEAST-SQUARES ALGORITHM FOR TENSOR DECOMPOSITIONS [J]. Journal of Computational Mathematics, 2018, 36(3): 351-373.
[7] Caixia Kou, Zhongwen Chen, Yuhong Dai, Haifei Han. AN AUGMENTED LAGRANGIAN TRUST REGION METHOD WITH A BI-OBJECT STRATEGY [J]. Journal of Computational Mathematics, 2018, 36(3): 331-350.
[8] Yangyang Xu. FAST ALGORITHMS FOR HIGHER-ORDER SINGULAR VALUE DECOMPOSITION FROM INCOMPLETE DATA [J]. Journal of Computational Mathematics, 2017, 35(4): 397-422.
[9] Jinkui Liu, Shengjie Li. SPECTRAL DY-TYPE PROJECTION METHOD FOR NONLINEAR MONOTONE SYSTEM OF EQUATIONS [J]. Journal of Computational Mathematics, 2015, 33(4): 341-355.
[10] Jinghui Liu, Changfeng Ma. A NEW NONMONOTONE TRUST REGION ALGORITHM FOR SOLVING UNCONSTRAINED OPTIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2014, 32(4): 476-490.
[11] 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.
[12] Xuebin Wang, Changfeng Ma, Meiyan Li. A SMOOTHING TRUST REGION METHOD FOR NCPS BASED ON THE SMOOTHING GENERALIZED FISCHER-BURMEISTER FUNCTION [J]. Journal of Computational Mathematics, 2011, 29(3): 261-286.
[13] Duoquan Li. A NEW SQP-FILTER METHOD FOR SOLVING NONLINEAR PROGRAMMING PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 609-634.
[14] Chang-yin Zhou,Guo-ping He,Yong-li Wang . A NEW CONSTRAINTS IDENTIFICATION TECHNIQUE-BASED QP-FREE ALGORITHM FOR THE SOLUTION OF INEQUALITY CONSTRAINED MINIMIZATION PROBLEMS [J]. Journal of Computational Mathematics, 2006, 24(5): 591-608.
[15] Xin-long Luo. Singly Diagonally Implicit Runge-Kutta Methods Combining Line Search Techniques for Unconstrained Optimization [J]. Journal of Computational Mathematics, 2005, 23(2): 153-164.
Viewed
Full text


Abstract