求解极小极大问题的非单调过滤算法

运筹学学报 ›› 2012, Vol. 16 ›› Issue (2): 91-104.

求解极小极大问题的非单调过滤算法

赵奇¹, 张燕¹

1. 江苏科技大学张家港校区基础部, 江苏张家港, 215600

收稿日期:2011-02-28 修回日期:2012-03-29 出版日期:2012-06-15 发布日期:2012-06-15
通讯作者: 赵奇 E-mail:johnzqzq@163.com
基金资助:
1

A Nonmonotoe Filter Method For Minimax Problems

ZHAO Qi¹, ZHANG Yan¹

1. Department of Basic Courses, Jiangsu University of Science and Technology, Jiangsu Zhangjiagang 215600, China

Received:2011-02-28 Revised:2012-03-29 Online:2012-06-15 Published:2012-06-15
Contact: Qi ZHAO E-mail:johnzqzq@163.com

摘要/Abstract

摘要： 提出一种改进的求解极小极大问题的信赖域滤子方法,利用SQP子问题来求一个试探步,尾服用滤子来衡量是否接受试探步,避免了罚函数的使用;并且借用已有文献的思想, 使用了Lagrange函数作为效益函数和非单调技术,在适当的条件下,分析了算法的全局和局部收敛性,并进行了数值实验.

关键词: 极小极大问题, 非单调, 全局收敛性, 滤子算法, 超线性收敛

Abstract: In this paper, we present a modified trust-region filter algorithm to solve the unconstrained minimax problem. The algorithm solves an SQP subproblem to acquire the attempted step. The filter technique is used to weigh the effect of the attempted step so as to avoid the use of a penalty function. Based on the idea of the latest reference, we use the Lagrange function as a merit function, also combine it with the nonmonotone technique to improve the effect of the algorithm. Under some mild conditions, we prove the global convergence and superlinear local convergence. Numerical results show the effectiveness of the algorithm.

Key words: minimax problem, nonmonotone, global convergence, Filter methods, superlinear convergence

赵奇, 张燕. 求解极小极大问题的非单调过滤算法[J]. 运筹学学报, 2012, 16(2): 91-104.

ZHAO Qi, ZHANG Yan. A Nonmonotoe Filter Method For Minimax Problems[J]. Operations Research Transactions, 2012, 16(2): 91-104.

参考文献

Charalambous, Conn A R. An efficient method to solve the Minimax problem directly [J]. SIAM Journal on Numerical Analysis, 1978, 15: 162-187.
Yu Y H, Gao L. Nonmonotone line search algorithm for constrained Minimax problems [J]. Journal of Optimization Theory and Applications, 2002, 115: 419-446.
Zhou J L, Tits A L. Nonmonotone line search method for Minimax problems [J]. Journal of Optimization Theory and Applications, 1993, 76: 455-476.
Vardi A. New Minimax algorithm [J]. Journal of Optimization Theory and Applications, 1992, 75: 612-634.
Conn A R, Gould N I M, Toint P L. Trust-region Methods(MPS-SIAM Series on Optimization), Society for Industrial Mathematics.
黄丽萍. 一类求解极小极大问题的滤子算法[D]. 苏州大学硕士毕业论文, 2009.
薛毅. 求解Minimax问题的SQP方法[J]. 系统科学与数学, 2002, 22: 355-364.
Zhu Z B. An improved SQP algorithm for solving minimax problems [J]. Applied Mathematics Letters, 2009, 22: 464-469.
Polyak R A. Smoothing optimization methods for minimax problems [J]. SIAM Control and Optimization, 1988, 26(6): 1274-1286.
Fletcher R, Leyffer S. Nonlinear programming without a penalty function [J]. Mathematical Programming, 2002, 91(2): 239-269.
Fletcher R, Leyffer S. Global convergence of trust-region SQP-filter algorithms for general nonlinear programming [J]. SIAM Journal on Optimization, 2002, 13(3): 635-659.
Fletcher R, Leyffer S, Toint P L. On the globalconvergence of a filter-SQP algorithm [J]. SIAM Journal on Optimization, 2002, 13(1): 44-59.
Ulbrich S. On the superlinear local convergence of a filter-SQP method [J]. Mathematical Programming, 2004, 100: 217-245.
黄丽萍. 一类求解极小极大问题的滤子算法[D]. 苏州大学硕士毕业论文, 2009.
Su K, Pu D G. A nonmonotone filter trust region method for nonlinear constrained optimization [J]. Journal of Computional and Applied Mathematics, 2009, 223: 230-239.
Fletcher R, Leyffer S, Sheng C G. Nonmonotone filter method for nonlinear optimization. Mathematics and Computer Science Division, 2009, Preprint ANL/MCS-P1679-0909.
Ulbrich M, Ulbrich S. Non-monotone trust-region methods for nonlinear equality constrained optimization without a penalty function [J]. Mathematical Programming, 2003, 95:103-135.
黄丽萍. 一类求解极小极大问题的滤子算法[D]. 苏州大学硕士毕业论文, 2009.

袁亚湘, 孙文渝. 最优化理论和方法[M]. 北京：科学出版社, 1997.

[1]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[2]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[3]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[4]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[5]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[6]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[7]	曾友芳, 唐春明. 二阶锥规划一个超线性收敛的非内部连续化算法[J]. 运筹学学报, 2015, 19(1): 18-30.
[8]	刘元文, 欧宜贵. 求解带界约束的非线性方程组的混合方法[J]. 运筹学学报, 2015, 19(1): 45-56.
[9]	刘媛媛, 欧宜贵. 基于非单调技术的ODE型混合方法[J]. 运筹学学报, 2013, 17(3): 11-22.
[10]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[11]	简金宝, 韦小鹏, 曾汉君, 潘华琴. 一般约束优化基于识别函数的模松弛算法[J]. 运筹学学报, 2011, 15(2): 28-44.
[12]	王华. 解非线性互补问题的非单调可行SQP方法[J]. 运筹学学报, 2011, 15(2): 85-94.