A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

doi:10.1007/s10473-020-0608-5

数学物理学报(英文版) ›› 2020, Vol. 40 ›› Issue (6): 1723-1738.doi: 10.1007/s10473-020-0608-5

A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

简金宝¹, 马国栋²

1. College of Mathematics and Physics, Guangxi University for Nationalities, Nanning 530006, China;
2. School of Mathematics and Statistics, Yulin Normal University, Yulin 537000, China

收稿日期:2019-08-02 修回日期:2020-07-15 出版日期:2020-12-25 发布日期:2020-12-30
通讯作者: Guodong MA,E-mail:mgd2006@163.com E-mail:mgd2006@163.com
作者简介:Jinbao JIAN,E-mail:jianjb@gxu.edu.cn
基金资助:
This work was supported by the Natural Science Foundation of Guangxi Province (2018GXNSFAA281099), the National Natural Science Foundation of China (11771383) and the Yulin Normal University Research Grant (2019YJKY16).

A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

Jinbao JIAN¹, Guodong MA²

1. College of Mathematics and Physics, Guangxi University for Nationalities, Nanning 530006, China;
2. School of Mathematics and Statistics, Yulin Normal University, Yulin 537000, China

Received:2019-08-02 Revised:2020-07-15 Online:2020-12-25 Published:2020-12-30
Contact: Guodong MA,E-mail:mgd2006@163.com E-mail:mgd2006@163.com
Supported by:
This work was supported by the Natural Science Foundation of Guangxi Province (2018GXNSFAA281099), the National Natural Science Foundation of China (11771383) and the Yulin Normal University Research Grant (2019YJKY16).

摘要/Abstract

摘要： 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.

关键词: minimax optimization, inequality constraints, QP-free algorithm, global convergence

Abstract: 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.

Key words: minimax optimization, inequality constraints, QP-free algorithm, global convergence

中图分类号:

49K35

简金宝, 马国栋. A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION[J]. 数学物理学报(英文版), 2020, 40(6): 1723-1738.

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.

参考文献

[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

A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

A GLOBALLY CONVERGENT QP-FREE ALGORITHM FOR INEQUALITY CONSTRAINED MINIMAX OPTIMIZATION

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 6

Metrics

本文评价

推荐阅读 0

[1]	盛洲, 袁功林, 崔曾如. A NEW ADAPTIVE TRUST REGION ALGORITHM FOR OPTIMIZATION PROBLEMS[J]. 数学物理学报(英文版), 2018, 38(2): 479-496.
[2]	迟晓妮; 刘三阳. AN INFEASIBLE-INTERIOR-POINT PREDICTOR-CORRECTOR ALGORITHM FOR THE SECOND-ORDER CONE PROGRAM[J]. 数学物理学报(英文版), 2008, 28(3): 551-559.
[3]	张立平. A GLOBAL LINEAR AND LOCAL QUADRATIC SINGLE--STEP NONINTERIOR#br# CONTINUATION METHOD FOR MONOTONE SEMIDEFINITE COMPLEMENTARITY PROBLEMS[J]. 数学物理学报(英文版), 2007, 27(2): 243-253.
[4]	张立平, 高自友, 赖炎连. MERIT FUNCTION AND GLOBAL ALGORITHM FOR BOX CONSTRAINED VARIATIONAL INEQUALITIES[J]. 数学物理学报(英文版), 2002, 22(1): 63-71.
[5]	童小娇, 周叔子. GLOBAL CONVERGENCE OF A TRUST REGION ALGORITHM USING INEXACT GRADIENT FOR EQUALITY-CONSTRAINED OPTIMIZATION[J]. 数学物理学报(英文版), 2000, 20(3): 365-373.
[6]	刘光辉, 韩继业, 戚厚铎, 徐中玲. CONVERGENCE ANALYSIS ON A CLASS OF CONJUGATE GRADIENT METHODS WITHOUT SUFFICIENT DECREASE CONDITION[J]. 数学物理学报(英文版), 1998, 18(1): 11-16.