Although QP-free algorithms have good theoretical convergence and are effective in practice, their applications to minimax optimization have not yet been investigated. In this article, on the basis of the stationary conditions, without the exponential smooth function or constrained smooth transformation, we propose a QP-free algorithm for the nonlinear minimax optimization with inequality constraints. By means of a new and much tighter working set, we develop a new technique for constructing the sub-matrix in the lower right corner of the coefficient matrix. At each iteration, to obtain the search direction, two reduced systems of linear equations with the same coefficient are solved. Under mild conditions, the proposed algorithm is globally convergent. Finally, some preliminary numerical experiments are reported, and these show that the algorithm is promising.
Jinbao JIAN
,
Guodong MA
. A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION[J]. Acta mathematica scientia, Series B, 2020
, 40(6)
: 1723
-1738
.
DOI: 10.1007/s10473-020-0608-5
[1] Polak E. On the mathematical foundations of nondifferentiable optimization in engineering design. SIAM Rev, 1987, 29:21-89
[2] Polak E, Salcudean S E, Mayne D Q. Adaptive control of ARMA plants using worst case design by semiinfinite optimization. IEEE T Automat Contr, 1987, 32:388-396
[3] Panier E R, Tits A L. A globally convergent algorithm with adaptively refined discretization for semi-infinite optimization problems arising in engineering design. IEEE T Automat Contr, 1989, 34:903-908
[4] Cai X Q, Teo K L, Yang X Q, et al. Portfolio optimization under a minimax rule. Manage Sci, 2000, 46:957-972
[5] Polak E. Optimization:Algorithms and Consistent Approximations. New York:Springer, 1997
[6] Polak E, Royset J O, Womersley R S. Algorithms with adaptive smoothing for finite min-max problems. J Optim Theory Appl, 2003, 119:459-484
[7] Pee E Y, Royset J O. On solving large-scale finite Minimax problems using exponential smoothing. J Optim Theory Appl, 2011, 148:390-421
[8] Jian J B, Quan R, Zhang X L. Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints. J Comput Appl Math, 2007, 205:406-429
[9] Jian J B, Hu Q J, Tang C M. Superlinearly convergent Norm-Relaxed SQP method based on active set identification and new line search for constrained Minimax problems. J Optim Theory Appl, 2014, 163:859-883
[10] Ye F, Liu H W, Zhou S S, et al. A smoothing trust-region Newton-CG method for minimax problems. Appl Math Comput, 2008, 199:581-589
[11] Hare W, Nutini J. A derivative-free approximate gradient sampling algorithm for finite minimax problems. Comput Optim Appl, 2013, 56:1-38
[12] Jian J B, Mo X D, Qiu L J, et al. Simple sequential quadratically constrained quadratic programming feasible algorithm with active identification sets for constrained Minimax problems. J Optim Theory Appl, 2014, 160:158-188
[13] Panier E R, Tits A L, Herskovits J N. A QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization. SIAM J Control Optim, 1988, 26:788-811
[14] Gao Z Y, He G P, Wu F. Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints. J Optim Theory Appl, 1997, 95:371-397
[15] Yang Y F, Li D H, Qi L Q. A feasible sequnetial system of linear equations method for inequality constrained optimization. SIAM J Optim, 2003, 13:1222-1244
[16] Chen L F, Wang Y L, He G P. A feasible active set QP-free method for nonlinear programming. SIAM J Optim, 2006, 17:401-429
[17] Zhu Z B. An interior point type QP-free algorithm with superlinear convergence for inequality constrained optimization. Appl Math Model, 2007, 31:1201-1212
[18] Ma G D, Jian J B. A QP-free algorithm of quasi-strongly sub-feasible directions for inequality constrained optimization. J Ind Manag Optim, 2015, 11:307-328
[19] Li J L, Yang Z P. A QP-free algorithm without a penalty function or a filter for nonlinear general-constrained optimization. Appl Math Comput, 2018, 316:52-72
[20] Jian J B, Cheng W X. A superlinearly convergent strongly sub-feasible SSLE-type algorithm with working set for nonlinearly constrained optimization. J Comput Appl Math, 2009, 225:172-186
[21] Jian J B, Han D L, Xu Q J. A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization. Acta Math Sin, 2010, 26:2399-2420
[22] Karmitsa N. Test problems for large-scale nonsmooth minimization. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing, No B, 2007
