不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法

doi:10.12286/jssx.2018.1.49

计算数学 ›› 2018, Vol. 40 ›› Issue (1): 49-62.DOI: 10.12286/jssx.2018.1.49

不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法

王福胜, 张瑞

太原师范学院数学系, 晋中 030619

收稿日期:2017-01-20 出版日期:2018-03-15 发布日期:2018-02-03
基金资助:
国家自然科学基金（11171250）；山西省回国留学人员科研资助项目（2017-104）资助.

PDF ( 584 ) 引用

王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.

Wang Fusheng, Zhang Rui. A STRONGLY SUB-FEASIBLE NORM-RELAXED SQCQP ALGORITHM FOR THE INEQUALITY CONSTRAINED MINIMAX PROBLEMS[J]. Mathematica Numerica Sinica, 2018, 40(1): 49-62.

A STRONGLY SUB-FEASIBLE NORM-RELAXED SQCQP ALGORITHM FOR THE INEQUALITY CONSTRAINED MINIMAX PROBLEMS

Wang Fusheng, Zhang Rui

Department of Mathematics, Taiyuan Normal University, Jinzhong 030619, China

Received:2017-01-20 Online:2018-03-15 Published:2018-02-03

针对带不等式约束的极大极小问题，借鉴一般约束优化问题的模松弛强次可行SQP算法思想，提出了求解不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法.首先，通过在QCQP子问题中选取合适的罚函数，保证了算法的可行性以及目标函数F（x）的下降性，同时简化QCQP子问题二次约束项参数α_k的选取，可保证算法的可行性和收敛性.其次，算法步长的选取合理简单.最后，在适当的假设条件下证明了算法具有全局收敛性及强收敛性.初步的数值试验结果表明算法是可行有效的.

关键词： 极大极小问题, 模松弛, 强次可行, SQCQP算法, 全局收敛性

In this paper, the minimax problems with inequality constraints are discussed, and a new strongly sub-feasible norm-relaxed SQCQP algorithm for the inequality constrained minimax problems is proposed. First, the penalty function $a_k$ in the QCQP subproblem can ensure the feasibility of the algorithm and the descent property of the objective function F(x), and the parameter α_k of quadratic constraints can guarantee the feasibility and convergence of the algorithm. Second, the determination of stepsize is reasonable and simple. Finally,the proposed algorithm possesses global convergence under suitable assumptions. The preliminary numerical experiments show that the algorithm is feasible and effective.

Key words: minimax problem, Norm-relaxed, Strongly sub-feasible, SQCQP algorithm, Global convergence

MR(2010)主题分类:

90C30
65K05

分享此文:

[1] Rustem B, Nguyen Q. An algorithm for the inequality-constrained discrete minimax problem[J]. SIAM Journal on Optimization, 1998, 8:265-283.

[2] Polak E, Royset J O and Womersley R S. Algorithms with Adaptive Smoothing for Finite minimax Problems[J]. Journal of Optimization Theory and Applications, 2003, 119(3):459-484.

[3] Di Pillo G, Grippo L, Lucidi S. A smooth method for the finite minimax problem[J]. Math Program, 1993, 60:187-214.

[4] Vardi A. New minimax algorithm[J]. J Optim Theory Appl, 1992, 75:613-634

[5] Jian J B, Li J,Zheng H Y, Li J L. A superlinearly convergent norm-relaxed method of quasistrongly sub-feasible direction for inequality constrained minimax problems[J]. Applied Mathematics and Computation, 2014, 226:673-690.

[6] He S X, Liu X F, Wang C M. A Nonlinear Lagrange Algorithm for minimax Problems with General Constraints[J]. Numerical Functional Analysis and Optimization, 2016, 37(6):680-698.

[7] Zhu Z B, Cai X, Jian J B. An improved SQP algorithm for solving minimax problems[J]. Applied Mathematics Letters, 2009, 22(4):464-469.

[8] 薛毅. 求解minimax优化问题的SQP方法[J].系统科学与数学, 2002, 22(3):355-364.

[9] Wang F S. A hybrid algorithm for linearly constrained minimax Problems[J]. Annals of Operations Research, 2013, 206(1):501-525.

[10] Wang F S, Wang C L, Wang L. A new trust-region algorithm for finite minimax problem[J]. Journal of Computational Mathematics, 2012, 30(3):262-278.

[11] Fukushima M, Luo Z Q, Tseng P. A Sequential Quadratically Constrained Quadratic Programming Methods for Differentialable Convex minimization[J]. SIAM Journal on Optimization, 2003, 13(4):1098-1119.

[12] Solodov M V. On the Sequential Quadratically Constrained Quadratic Programming Methods[J]. Mathematics of Operations Research, 2004, 29(1):64-79.

[13] Yuan Y X, Sun W Y. Optimization Theory and Methods[M]. Beijing:Science Press, 1997.

[14] Tang C M, Jian J B. Sequential Quadratically Constrained Quadratic Programming Method with an Augmented Lagrangian Line Search Function[J]. Journal of Computational and Applied Mathematics, 2008, 220(1-2):525-547.

[15] 晁绵涛.非线性minimax问题的二次约束二次算法模型[J]. 广西大学硕士学位论文, 2007.

[16] 刘美杏,唐春明,简金宝.不等式约束优化基于新型积极识别集的SQCQP算法[J]. 应用数学学报, 2015, 38(2):222-234.

[17] Chao M T, Wang Z X, Liang Y M, Hu Q J. Quadratically Constraint Quadratical Algorithm Model for Nonlinear minimax Problems[J]. Applied Mathmatics and Computation, 2008, 205:247-262.

[18] Jian J B, Chao M T. A sequential quadratically constrained quadratic programming method for uncostrained minimax problems[J]. Journal of Mathematical Analysis and Applications, 2010, 362:34-45.

[19] Jian J B, Zheng H Y, Hu Q J,Tang C M. A new norn-relaxed method of strongly sub-feasible direction for inequality constrained optimization[J]. Applied Mathematics and Computation, 2005, 168:1-28.

[20] Chen, X., Kostreva, M.M. A generalization of the norm-relaxed method of feasible directions[J]. Applied Mathematics and Computation, 1999, 102:257-273.

[21] 简金宝.光滑约束优化快速算法-理论分析与数值试验[M].北京:科学出版社, 2010.

[22] Jian J B, Quan R,Zhang X L. Feasible generalized monotone line search SQP algorithm for nonlinear minimax problems with inequality constraints[J]. Journal of Computational and Applied Mathematics, 2007, 205:406-429.

[23] Napsu Karmitsa. Test problems for large-scale nonsmooth minimization[J]. Reports of the Department of Mathematical Information Technology, Series B. Scientific Computing, 2007, B4:1-12.

[1]	尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[2]	张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[3]	刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[4]	刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.
[5]	简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.
[6]	袁敏, 万中. 求解非线性P₀互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50.
[7]	简金宝, 唐菲, 黎健玲, 唐春明. 无约束极大极小问题的广义梯度投影算法[J]. 计算数学, 2013, 35(4): 385-392.
[8]	刘金魁. 两种有效的非线性共轭梯度算法[J]. 计算数学, 2013, 35(3): 286-296.
[9]	范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.
[10]	简金宝, 马鹏飞, 徐庆娟. 不等式约束优化一个基于滤子思想的广义梯度投影算法[J]. 计算数学, 2013, 35(2): 205-214.
[11]	刘景辉, 马昌凤, 陈争. 解无约束优化问题的一个新的带线搜索的信赖域算法[J]. 计算数学, 2012, 34(3): 275-284.
[12]	王开荣, 刘奔. 建立在修正BFGS公式基础上的新的共轭梯度法[J]. 计算数学, 2012, 34(1): 81-92.
[13]	江羡珍, 韩麟, 简金宝. Wolfe线搜索下一个全局收敛的混合共轭梯度法[J]. 计算数学, 2012, 34(1): 103-112.
[14]	万中, 冯冬冬. 一类非单调保守BFGS算法研究[J]. 计算数学, 2011, 33(4): 387-396.
[15]	杨柳, 陈艳萍. 求解非线性方程组的一种新的全局收敛的Levenberg-Marquardt算法[J]. 计算数学, 2008, 30(4): 388-396.

阅读次数

全文

摘要

不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法

A STRONGLY SUB-FEASIBLE NORM-RELAXED SQCQP ALGORITHM FOR THE INEQUALITY CONSTRAINED MINIMAX PROBLEMS

扫码分享