• 论文 • 上一篇    下一篇

求解大规模极大极小问题的光滑化三项共轭梯度算法

郭洁1,2, 万中2   

  1. 1. 长沙师范学院数学科学学院, 长沙 410100;
    2. 中南大学数学与统计学院, 长沙 410083
  • 收稿日期:2020-07-24 出版日期:2022-07-14 发布日期:2022-08-03
  • 通讯作者: 万中,Email:wanmath@csu.edu.cn.
  • 基金资助:
    国家社会科学基金项目(21BGL122)和国家自然科学基金项目(71671190)资助.

郭洁, 万中. 求解大规模极大极小问题的光滑化三项共轭梯度算法[J]. 计算数学, 2022, 44(3): 324-338.

Guo Jie, Wan Zhong. A SMOOTHING THREE-TERM CONJUGATE GRADIENT METHOD FOR SOLVING FINITE MINIMAX PROBLEMS[J]. Mathematica Numerica Sinica, 2022, 44(3): 324-338.

A SMOOTHING THREE-TERM CONJUGATE GRADIENT METHOD FOR SOLVING FINITE MINIMAX PROBLEMS

Guo Jie1,2, Wan Zhong2   

  1. 1. School of Mathematical Sciences, ChangSha Normal University, ChangSha 410100, China;
    2. School of Mathematics and Statistics, Central South University, ChangSha, 410083, China
  • Received:2020-07-24 Online:2022-07-14 Published:2022-08-03
基于指数罚函数,对最近提出的一种求解无约束优化问题的三项共轭梯度法进行了修正,并用它求解更复杂的大规模极大极小值问题.证明了该方法生成的搜索方向对每一个光滑子问题是充分下降方向,而且与所用的线搜索规则无关.以此为基础,设计了求解大规模极大极小值问题的算法,并在合理的假设下,证明了算法的全局收敛性.数值实验表明,该算法优于文献中已有的类似算法.
In this paper, by the method of exponential penalty, we modify the recently proposed three-term conjugate gradient method for solving optimization problems such that it is used to solve more complicated large-scale minimax problems. It is proved that the search directions generated by our method are sufficiently descent for the smoothing subproblems, being independent of the used line search rules. With such a property, a new algorithm is developed to solve the large-scale min-max problems, and its global convergence is established under mild assumptions. By numerical experiments, it is shown that this algorithm outperforms the other similar ones available in the literature.

MR(2010)主题分类: 

()
[1] Brusco M J, Jacobs L W. Personnel tour scheduling when starting-time restrictions are present[J]. Management Science, 1998, 44(4):534-547.
[2] Auke P, Sandjai B, Ger K. A simple staffing method for multiskill call centers[J]. Manufacturing and Service Operations Management, 2008, 10(3):421-428.
[3] Xu S. Smoothing method for minimax problems[J]. Computational Optimization&Applications, 2001, 20(3):267-279.
[4] Polak E. Optimization Algorithms and Consistent Approximations[M]. New York:SpringerVerlag, 1997.
[5] Vardi A. New minimax algorithm[J]. Journal of Optimization Theory&Applications, 1992, 75(3):613-634.
[6] Polak E, Royset J O, Womersley R S. Algorithms with adaptive smoothing for finite minimax problems[J]. Journal of Optimization Theory and Applications, 2003, 119(3):459-484.
[7] Li J, Huo J. Inexact smoothing method for large scale minimax optimization[J]. Applied Mathematics&Computation, 2011, 218(6):2750-2760.
[8] Liu J K, Zheng L. A smoothing iterative method for the finite minimax problem[J]. Journal of Computational and Applied Mathematics, 2020, 374(1):1-11.
[9] Kort B W, Bertsekas D P. A new penalty function method for constrained minimization[C]. IEEE Conference on Decision&Control. IEEE, 1972.
[10] Pang D Y, Du S Q, Ju J J. The smoothing Fletcher-Reeves conjugate gradient method for solving finite minimax problems[J]. Scienceasia, 2016, 42(1):40-45.
[11] Lv J, Deng S H, Wan Z. An efficient single-parameter scaling memoryless Broyden-FletcherGoldfarb-Shanno algorithm for solving large scale unconstrained optimization problems[J]. IEEE Access, 2020, 8(1):85664-85674.
[12] Peng J M, Lin Z. A non-interior continuation method for generalized linear complementarity problems[J]. Mathematical Programming, 1999, 86(3):533-563.
[13] Demyanov V F, Molozemov V N. Introduction to Minimax[M]. New York:Wiley, 1974.
[14] Charalambous C, Conn A R. An efficient method to solve the minimax problem directly[J]. SIAM Journal on Numerical Analysis, 1978, 15(1):162-187.
[15] Makela M M, Neittaanmaki P. Nonsmooth Optimization[M]. Singapore:World Scientific, 1992.
[16] Chen X. Smoothing methods for nonsmooth, nonconvex minimization[J]. Mathematical Programming, 2012, 134(1):71-91.
[17] Dolan E D, Moré J J. Benchmarking optimization software with performance profiles[J]. Mathematical Programming, 2002, 91(2):201-213.
[1] 马玉敏, 蔡邢菊. 求解带线性约束的凸优化的一类自适应不定线性化增广拉格朗日方法[J]. 计算数学, 2022, 44(2): 272-288.
[2] 刘金魁, 孙悦, 赵永祥. 凸约束伪单调方程组的无导数投影算法[J]. 计算数学, 2021, 43(3): 388-400.
[3] 尹江华, 简金宝, 江羡珍. 凸约束非光滑方程组一个新的谱梯度投影算法[J]. 计算数学, 2020, 42(4): 457-471.
[4] 吴敏华, 李郴良. 求解带Toeplitz矩阵的线性互补问题的一类预处理模系矩阵分裂迭代法[J]. 计算数学, 2020, 42(2): 223-236.
[5] 张纯, 贾泽慧, 蔡邢菊. 广义鞍点问题的改进的类SOR算法[J]. 计算数学, 2020, 42(1): 39-50.
[6] 王福胜, 张瑞. 不等式约束极大极小问题的一个新型模松弛强次可行SQCQP算法[J]. 计算数学, 2018, 40(1): 49-62.
[7] 刘金魁. 解凸约束非线性单调方程组的无导数谱PRP投影算法[J]. 计算数学, 2016, 38(2): 113-124.
[8] 刘亚君, 刘新为. 无约束最优化的信赖域BB法[J]. 计算数学, 2016, 38(1): 96-112.
[9] 简金宝, 尹江华, 江羡珍. 一个充分下降的有效共轭梯度法[J]. 计算数学, 2015, 37(4): 415-424.
[10] 张凯院, 牛婷婷, 聂玉峰. 一类非线性矩阵方程对称解的双迭代算法[J]. 计算数学, 2014, 36(1): 75-84.
[11] 袁敏, 万中. 求解非线性P0互补问题的非单调磨光算法[J]. 计算数学, 2014, 36(1): 35-50.
[12] 简金宝, 唐菲, 黎健玲, 唐春明. 无约束极大极小问题的广义梯度投影算法[J]. 计算数学, 2013, 35(4): 385-392.
[13] 刘金魁. 两种有效的非线性共轭梯度算法[J]. 计算数学, 2013, 35(3): 286-296.
[14] 范斌, 马昌凤, 谢亚君. 求解非线性互补问题的一类光滑Broyden-like方法[J]. 计算数学, 2013, 35(2): 181-194.
[15] 简金宝, 马鹏飞, 徐庆娟. 不等式约束优化一个基于滤子思想的广义梯度投影算法[J]. 计算数学, 2013, 35(2): 205-214.
阅读次数
全文


摘要