一般约束极大极小优化问题一个强收敛的广义梯度投影算法

数学物理学报 ›› 2020, Vol. 40 ›› Issue (3): 641-649.

一般约束极大极小优化问题一个强收敛的广义梯度投影算法

马国栋()

^{玉林师范学院数学与统计学院&广西高校复杂系统优化与大数据处理重点实验室广西玉林 537000}

收稿日期:2019-03-22 出版日期:2020-06-26 发布日期:2020-07-15
作者简介:马国栋, E-mail:mgd2006@163.com
基金资助:
广西自然科学基金(2018GXNSFAA281099);国家自然科学基金(11771383);玉林师范学院科研项目(2019YJKY16);玉林师范学院科研项目(G20150010)

A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints

Guodong Ma()

^{School of Mathematics and Statistics & Guangxi Colleges and Universities Key Laboratory of Complex System Optimization and Big Data Processing, Yulin Normal University, Guangxi Yulin 537000}

Received:2019-03-22 Online:2020-06-26 Published:2020-07-15
Supported by:
the NSF of Guangxi Province(2018GXNSFAA281099);the NSFC(11771383);the Research Projects of Yulin Normal University(2019YJKY16);the Research Projects of Yulin Normal University(G20150010)

摘要/Abstract

摘要：

该文考虑求解带非线性不等式和等式约束的极大极小优化问题，借助半罚函数思想，提出了一个新的广义投影算法.该算法具有以下特点：由一个广义梯度投影显式公式产生的搜索方向是可行下降的；构造了一个新型的最优识别控制函数；在适当的假设条件下具有全局收敛性和强收敛性.最后，通过初步的数值试验验证了算法的有效性.

关键词: 非线性一般约束, 极大极小问题, 广义梯度投影算法, 全局收敛性, 强收敛性

Abstract:

In this paper, minimax optimization problems with inequality and equality constraints is discussed. The original problem is transformed into an associated simple problem with a penalty term and only inequality constraints, then a new generalized gradient projection algorithm is presented. The main characters of the proposed algorithm are as follows:the improved search direction is generated by only one generalized gradient projection explicit formula; the new optimal identification function is introduced; the algorithm is globally and strongly convergent under some mild assumptions. Finally, the numerical results show that the proposed algorithm is promising.

Key words: Nonlinear general constraints, Minimax optimization problems, Generalized gradient projection method, Global convergence, Strong convergence

中图分类号:

O221.2

马国栋. 一般约束极大极小优化问题一个强收敛的广义梯度投影算法[J]. 数学物理学报, 2020, 40(3): 641-649.

Guodong Ma. A Strongly Convergent Generalized Gradient Projection Method for Minimax Optimization with General Constraints[J]. Acta mathematica scientia,Series A, 2020, 40(3): 641-649.

图/表 1

参考文献 16

1	Yu Y H , Gao L . Nonmonotone line search algorithm for constrained minimax problems. J Optimiz Theory App, 2002, 115 (2): 419- 446 doi: 10.1023/A:1020896407415
2	Jian J B , Zhang X L , Quan R , Ma Q . Generalized monotone line search SQP algorithm for constrained minimax problems. Optimization, 2009, 58 (1): 101- 131
3	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 Optimiz Theory App, 2014, 163 (3): 859- 883 doi: 10.1007/s10957-013-0503-5
4	Wang F S , Wang C L . An adaptive nonmonotone trust region method with curvilinear search for minimax problem. Appl Math Comput, 2013, 219, 8033- 8041
5	Ye F , Liu H W , Zhou S S , et al. A smoothing trust region Newton-CG method for minimax problem. Appl Math Comput, 2008, 199, 581- 589
6	Chi X N , Wei H J , Wan Z P , et al. Smoothing Newton algorithm for the circular cone programming with a nonmonotone line search. Acta Math Sci, 2017, 37B (5): 1262- 1280
7	Obasanjo E , Tzallas-Regas G , Rustem B . An interior point algorithm for nonlinear minimax problems. J Optimiz Theory App, 2010, 144 (2): 291- 318 doi: 10.1007/s10957-009-9599-z
8	Mayne D Q , Polak E . Feasible directions algorithms for optimization problems with equality and inequality constraints. Math Program, 1976, 11 (1): 67- 80 doi: 10.1007/BF01580371
9	Jian J B , Xu Q J , Han D L . A strongly convergent norm-relaxed method of strongly sub-feasible direction for optimization with nonlinear equality and inequality constraints. Appl Math Comput, 2006, 182, 854- 870
10	Jian J B , Guo C H , Yang L F . A new generalized projection method of strongly sub-feasible directions for general constrained optimization. Pac J Optim, 2009, 5 (3): 507- 523
11	Rosen J B . The gradient projection method for nonlinear programming. Part I. Linear constraints. J Soc Ind Appl Math, 1960, 8 (1): 181- 217
12	Rosen J B . The gradient projection method for nonlinear programming. Part Ⅱ. Linear constraints. J Soc Ind Appl Math, 1961, 9 (4): 514- 532 doi: 10.1137/0109044
13	朱志斌, 王硕, 简金宝. 非线性优化一个超线性收敛的广义投影型可行方向法. 应用数学学报, 2014, 37 (1): 179- 192
	Zhu Z B , Wang S , Jian J B . A generalized projection feasible method with superlinear convergence for nonlinear optimization. Acta Math Appl Sin, 2014, 37 (1): 179- 192
14	简金宝. 光滑约束优化快速算法-理论分析与数值试验. 北京: 科学出版社, 2010
	Jian J B . Fast Algorithms for Smooth Constrained Optimization-Theoretical Analysis and Numerical Experiments. Beijing: Science Press, 2010
15	Ma G D , Jian J B . An ε-generalized gradient projection method for nonlinear minimax problems. Nonlinear Dynam, 2014, 75 (4): 693- 700 doi: 10.1007/s11071-013-1095-1
16	Ma G D , Zhang Y F , Liu M X . A generalized gradient projection method based on a new working set for minimax optimization problems with inequality constraints. J Inequal Appl, 2017, 2017, 51 doi: 10.1186/s13660-017-1321-3

问题	$n/l$/$m'$$/m$	$x^0$	算法	Ni	$F(x^*)$
问题1	$2/3/0/1$	$(-1, 3)^T$	算法A	$14$	$2.1266e-10$
			算法JZQM	$12$	$2.0079e-10$
			算法YG	$13$	$0$
问题2	$2/3/0/1$	$(-1, 1)^T$	算法A	$8$	$-1$
			算法JZQM	$15$	$-1$
			算法YG	$11$	$-1$
问题3	$2/6/2/0$	$(1, 3)^T$	算法A	$20$	$0.6256$
			算法JZQM	$15$	$0.5832$
			算法YG	$18$	$0.6164$
问题5	$2/2/0/1$	$(-1, 4)^T$	算法A	$20$	$-5.8714$
			算法JZQM	$12$	$-5.8754$
问题6	$3/3/1/2$	$(2, 3, 2)^T$	算法A	$8$	$-3.8621$
			算法JZQM	$5$	$-3.9345$
问题7	$10/8/0/3$	$(0, 1, 1, 1, 0, 0, 1, 1, 1, 0)^T$	算法A	$74$	$2.3521e+003$
			算法JZQM	$52$	$2.3339e+003$

[1]	万成高. 随机环境中马氏链函数加权和的极限定理[J]. 数学物理学报, 2015, 35(1): 163-171.
[2]	陈加伟, 万仲平, 赵烈济. 可数族弱Bregman相对非扩展映像的收敛性分析[J]. 数学物理学报, 2014, 34(1): 70-79.
[3]	胡慧英, 曾六川. 两个平衡问题和可数无穷多非扩张映像公共不动点问题的新的迭代算法[J]. 数学物理学报, 2013, 33(5): 860-881.
[4]	胡朝明, 万中, 王旭. 一种新的非单调谱共轭梯度算法[J]. 数学物理学报, 2013, 33(1): 78-88.
[5]	周长银; 贺国平; 王永丽. 基于有效约束识别技术的一个SSLE算法及其收敛性分析[J]. 数学物理学报, 2007, 27(3): 535-540.
[6]	高自友, 任华玲, 贺国平. 无严格互补松驰条件的序列线性方程组新算法[J]. 数学物理学报, 2004, 24(3): 275-284.
[7]	简金宝. 不等式约束最优化超线性与二次收敛的强次可行SQP算法[J]. 数学物理学报, 2001, 21(2): 268-277.
[8]	刘法胜傅白白夏尊铨. 参变极值问题的信息凝聚分布与Boltzmann极大熵函数[J]. 数学物理学报, 1999, 19(5): 531-536.
[9]	施保昌, 陈珽, 祝世京. 多目标决策的中心方法之统一探讨[J]. 数学物理学报, 1997, 17(S1): 15-22.