混合约束Minimax问题的基于序列线性方程组的模松弛SQP算法
|
摘要
本文针对带等式与不等式的混合约束Minimax问题,提出了基于序列线性方程组的模松弛SQP算法.在新算法中,我们首先引入了ε-积极约束集,在此基础上构造了—个模松弛QP子问题和序列线性方程组,以获得可行下降方向.另外,新算法采取了一种既无罚函数又无滤子的弧搜索步长策略,以避免罚参数的选取·新算法既克服了Maratos效应,又大大地减少了算法的计算工作量和储存量.在适当的假设条件下,证明了算法的全局收敛性.初步数值实验验证了该算法的有效性与优越性.
Many problems of interest in real world applications can be modeled as a socalled minimax problem, it is of great value to study its theory and solving method. In this paper, a new SQP algorithm with a system of linear equations is proposed to solve minimax problems with equality and inequality constraints. First,based on the ε-active constraint set,a norm-relaxed quadratic programming subproblem and a system of linear equations are established to get the feasible direction of descent,which can overcome the Maratos effect,and greatly reduce the computational complexity of the algorithm; Second, a new curve search step-size strategy without the penalty factors or filters is introduced. The method not only avoids the choice of penalty factors, but also reduces the storage capacity of the computer. Finally, it is proved that,under appropriate assumptions, the new algorithm is globally convergent. Some preliminary numerical experiments are reported to show the effectiveness and competitiveness of the algorithm.
Many problems of interest in real world applications can be modeled as a socalled minimax problem, it is of great value to study its theory and solving method. In this paper, a new SQP algorithm with a system of linear equations is proposed to solve minimax problems with equality and inequality constraints. First,based on the ε-active constraint set,a norm-relaxed quadratic programming subproblem and a system of linear equations are established to get the feasible direction of descent,which can overcome the Maratos effect,and greatly reduce the computational complexity of the algorithm; Second, a new curve search step-size strategy without the penalty factors or filters is introduced. The method not only avoids the choice of penalty factors, but also reduces the storage capacity of the computer. Finally, it is proved that,under appropriate assumptions, the new algorithm is globally convergent. Some preliminary numerical experiments are reported to show the effectiveness and competitiveness of the algorithm.
引文
[1]Rustem B,Nguyen Q. An algorithm for the inequality-constrained discrete minimax problem. SIAM Journal on Optimization, 1998, 8:265-283
[2]Yu Y H, Gao L. Nonmonotone line search for constrained minimax problems. Journal of Optimization Theory and Applications, 2002, 115:419-446
[3]Coleman T F. A note on new algorithms for constrained minimax optimization. Mathematical Programmmming, 1978, 15:239-242
[4]Polak E, Royset J O, and Womersley R S. Algorithms with Adaptive Smoothing for Finite Minimax Problems. Journal of Optimization Theory and Applications, 2003, 119(3):459-484
[5]Di Pillo G, Grippo L, Lucidi S. A smooth method for the finite minimax problem. Mathematical Programmmming,1993, 60:187-214
[6]简金宝.光滑约束优化快速算法-理论分析与数值试验.北京:科学出版社,2010(Jian, J B. Fast Algorithms for Smooth Constrained Optimization—Theoretical Analysis and Numerical Experiments. Beijing:Science Press, 2010)
[7]Tang C M, Jian J B. Sequential Quadratically Constrained Quadratic Programming Method with an Augmented Lagrangian Line Search Function. Journal of Computational and Applied Mathematics,2008, 220(1-2):525-547
[8]薛毅.求解Minimax优化问题的SQP方法,系统科学与数学,2002, 22(3):355-364(Xue Y. The Sequential Quadratic Programming Method for Solving Minimax Problem. Journal of Systems Science and Mathematical Sciences, 2002, 22(3):355-364)
[9]Wang F S. A hybrid algorithm for linearly constrained minimax Problems. Annals of Operations Research, 2013, 206(1):501-525
[10]He S X,Liu X F, Wang C M. A Nonlinear Lagrange Algorithm for Minimax Problems with General Constraints. Numerical Functional Analysis and Optimization, 2016, 37(6):680-698
[11]刘美杏,唐春明,简金宝.不等式约束优化基于新型积极识别集的SQCQP算法,应用数学学报,2015, 38(2):222-234(Liu M X, Tang C M, Jian J B. An SQCQP Algorithm with new active identification set for inequality constrained optimization. Acta Mathematicae Applicatae Sinica, 2015, 38(2):222-234)
[12]Panier E R, Tits A L, Herskovits J N. A QP-free globally convergent locally superlinearly convergent algorithm for inequality constrained optimization. SIAM Journal on Control and Optimization, 1988,26(4):788-811
[13]Zhu Z B, Cai X, Jian J B. An improved SQP algorithm for solving minimax problems. Applied Mathematics Letter, 2009, 22:464-469
[14]Jian J B, Ma R Q, Zhang X L. Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints. Journal of Computational and Applied Mathematics,2007, 205:406-429
[15]Jian J B, Li J, Zheng H Y, Li J L. A superlinearly convergent norm-relaxed method of quasi-strongly sub-feasible direction for inequality constrained minimax problems. Applied Mathe-matics and Computation, 2014, 226:673-690
[16]Jian J B, Zhang X L, Ma R Q. Generalized monotone line search SQP algorithm for constrained minimax problems. Optimization, 2009, 58(1):101-131
[17]Wang L R, Luo Z J. A Simple SQP Algorithm for Constrained Finite Minimax Problems. The Science World Journal,2014(2014),Article ID 159754, 9 pages.
[18]谢亚军,马昌凤.约束Minimax问题的SQP-Filter算法及收敛性.西华大学学报,2011,30(6):62-64(Xie Y J, Ma C F. SQP-Filter Algorithm for Constrained Minimax Problem and Its Convergence.Journal of Xihua University(Natural Science Edition), 2011, 30(6):62-64)
[19]Luo Z J, Wang L R. Improved Filter-SQP Algorithm with Active Set for Constrained Minimax Problems. Journal of Applied Mathematics, 2014(2014), Article ID 293475, 7 pages.
[20]Liu X W, Yuan Y X. A Sequential Quadratic Programming Method Without A Penalty Function Or A Filter For Nonlinear Equality Constrained Optimization. SIAM Journal On Optimization, 2011,21(2):545-571
[2]Yu Y H, Gao L. Nonmonotone line search for constrained minimax problems. Journal of Optimization Theory and Applications, 2002, 115:419-446
[3]Coleman T F. A note on new algorithms for constrained minimax optimization. Mathematical Programmmming, 1978, 15:239-242
[4]Polak E, Royset J O, and Womersley R S. Algorithms with Adaptive Smoothing for Finite Minimax Problems. Journal of Optimization Theory and Applications, 2003, 119(3):459-484
[5]Di Pillo G, Grippo L, Lucidi S. A smooth method for the finite minimax problem. Mathematical Programmmming,1993, 60:187-214
[6]简金宝.光滑约束优化快速算法-理论分析与数值试验.北京:科学出版社,2010(Jian, J B. Fast Algorithms for Smooth Constrained Optimization—Theoretical Analysis and Numerical Experiments. Beijing:Science Press, 2010)
[7]Tang C M, Jian J B. Sequential Quadratically Constrained Quadratic Programming Method with an Augmented Lagrangian Line Search Function. Journal of Computational and Applied Mathematics,2008, 220(1-2):525-547
[8]薛毅.求解Minimax优化问题的SQP方法,系统科学与数学,2002, 22(3):355-364(Xue Y. The Sequential Quadratic Programming Method for Solving Minimax Problem. Journal of Systems Science and Mathematical Sciences, 2002, 22(3):355-364)
[9]Wang F S. A hybrid algorithm for linearly constrained minimax Problems. Annals of Operations Research, 2013, 206(1):501-525
[10]He S X,Liu X F, Wang C M. A Nonlinear Lagrange Algorithm for Minimax Problems with General Constraints. Numerical Functional Analysis and Optimization, 2016, 37(6):680-698
[11]刘美杏,唐春明,简金宝.不等式约束优化基于新型积极识别集的SQCQP算法,应用数学学报,2015, 38(2):222-234(Liu M X, Tang C M, Jian J B. An SQCQP Algorithm with new active identification set for inequality constrained optimization. Acta Mathematicae Applicatae Sinica, 2015, 38(2):222-234)
[12]Panier E R, Tits A L, Herskovits J N. A QP-free globally convergent locally superlinearly convergent algorithm for inequality constrained optimization. SIAM Journal on Control and Optimization, 1988,26(4):788-811
[13]Zhu Z B, Cai X, Jian J B. An improved SQP algorithm for solving minimax problems. Applied Mathematics Letter, 2009, 22:464-469
[14]Jian J B, Ma R Q, Zhang X L. Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints. Journal of Computational and Applied Mathematics,2007, 205:406-429
[15]Jian J B, Li J, Zheng H Y, Li J L. A superlinearly convergent norm-relaxed method of quasi-strongly sub-feasible direction for inequality constrained minimax problems. Applied Mathe-matics and Computation, 2014, 226:673-690
[16]Jian J B, Zhang X L, Ma R Q. Generalized monotone line search SQP algorithm for constrained minimax problems. Optimization, 2009, 58(1):101-131
[17]Wang L R, Luo Z J. A Simple SQP Algorithm for Constrained Finite Minimax Problems. The Science World Journal,2014(2014),Article ID 159754, 9 pages.
[18]谢亚军,马昌凤.约束Minimax问题的SQP-Filter算法及收敛性.西华大学学报,2011,30(6):62-64(Xie Y J, Ma C F. SQP-Filter Algorithm for Constrained Minimax Problem and Its Convergence.Journal of Xihua University(Natural Science Edition), 2011, 30(6):62-64)
[19]Luo Z J, Wang L R. Improved Filter-SQP Algorithm with Active Set for Constrained Minimax Problems. Journal of Applied Mathematics, 2014(2014), Article ID 293475, 7 pages.
[20]Liu X W, Yuan Y X. A Sequential Quadratic Programming Method Without A Penalty Function Or A Filter For Nonlinear Equality Constrained Optimization. SIAM Journal On Optimization, 2011,21(2):545-571