一类凸优化的加速混合下降算法

doi:10.12286/jssx.2017.2.200

计算数学 ›› 2017, Vol. 39 ›› Issue (2): 200-212.DOI: 10.12286/jssx.2017.2.200

一类凸优化的加速混合下降算法

徐海文¹, 孙黎明²

1. 中国民用航空飞行学院计算机学院, 广汉 618307;
2. 南京审计大学理学院, 南京 211815

收稿日期:2016-06-28 出版日期:2017-05-15 发布日期:2017-07-18
基金资助:
国家自然科学基金（U1233105）资助项目.

PDF ( 606 ) 引用被引次数 ( 2 )

徐海文, 孙黎明. 一类凸优化的加速混合下降算法[J]. 计算数学, 2017, 39(2): 200-212.

Xu Haiwen, Sun Liming. A ACCELERATED HYBRID DESCENT ALGORITHM FOR CONVEX MINIMIZATION[J]. Mathematica Numerica Sinica, 2017, 39(2): 200-212.

A ACCELERATED HYBRID DESCENT ALGORITHM FOR CONVEX MINIMIZATION

Xu Haiwen¹, Sun Liming²

1. College of Computer Science and Technology, Civil Aviation Flight University of China, Guanghan 618307, China;
2. College of Science, Nanjing Audit University, Nanjing 211815, China

Received:2016-06-28 Online:2017-05-15 Published:2017-07-18

凸优化问题的混合下降算法利用近似条件的已知信息和随机数扩张预测校正步得到了一组下降方向.而前向加速收缩算法利用高斯赛德尔迭代算法的技术，结合邻近点算法和近似邻近点算法的思想，构造了富有扩张性的下降方向.本文借鉴混合下降算法和前向加速收缩算法的思想，利用已有近似规则信息改善了混合下降算法的下降方向，得到了一类凸优化问题的加速混合下降算法.随后利用\Markov不等式、凸函数性质和投影的基本性质等，实现了算法的依概率收敛证明.一系列数值试验表明了加速混合下降算法的有效性和效率性.

关键词： 凸优化问题, 混合下降算法, 邻近点算法, 前向加速收缩算法, 依概率收敛

The set of descent directions of hybrid descent method (HD Method) for convex minimization is obtained by the known information of approximate conditions and random number expansion prediction correction step.While the rich expansion descent directions of forward accelerated contraction method is constructed by the technology of Gauss-Seidel iterative algorithm and the thoughts of proximal point algorithm (PPA) and approximate proximal point algorithm.Inspired by the idea of the hybrid descent algorithm and the forward acceleration algorithm,the accelerated hybrid descent algorithm for convex minimization is obtained by using the history approximate rule information to improve the iterative step of hybrid descent algorithm.Subsequetly,the probability convergence of accelerated hybrid descent algorithm is introduced by the basic properties of Markov's inequality,the convex function and the projection.Some numerical experiments show the effectiveness and efficiency of the accelerated hybrid descent algorithm.

Key words: Convex minimization, hybrid descent algorithm, proximal point algorithm, forward accelerated contraction algorithm, probability convergence

MR(2010)主题分类:

分享此文:

[1] Nesterov Y E. A method for solving the convex programming problem with convergence rate O(1/k²)[J]. Dokl. Akad. Nauk SSSR, 1983, 269:543-547.

[2] Patrick T H, Pang J S. Finite-Dimensional Variational Inequality and Nonlinear Complementartity problems:A survey of theory, algorithms and applications[J]. Mathematical Programming, 1998, 48:162-220.

[3] Rockafellar R T. Augmented Lagrangians and applications of the proximal point algorithm in convex programming[J]. Mathematics of Operations Research, 1976, 1:97-116.

[4] Rockafellar R T. Monotone operators and the proximal point algorithm[J]. SIAM Journal on Control and Optimization, 1976, 14:877-898.

[5] Eckstein J. Approximate iterations in Bregman-function-based proximal algorithms[J]. Mathematical Programming, 1998, 83:113-123.

[6] He B S, Yuan X M. An accelerated inexact proximal point algorithm for convex minimization[J]. Journal of Optimization Theory and Applications, 2012, 154(2):536-548.

[7] He B S, Liao L Z, Wang X. Proximal-like contraction methods for monotone variational inequalities in a unified framework I:Effective quadruplet and primary methods[J]. Computational Optimization and Applications, 2012, 51(2):681-708.

[8] He B S, Liao L Z, Yang Z H. A new approximate proximal point algorithm for maximal monotone operator[J]. Science in China, Series A, 2003, 46:200-206.

[9] He B S, Liao L Z. Improvements of some projection methods for monotone nonlinear variational inequalities[J]. Journal of Optimization Theory and Applications, 2002, 112:111-128.

[10] Korpelevich G M. The extragradient method for finding saddle points and other problems[J]. Ekonomika i Matematicheskie Metody, 1976, 12:747-756.

[11] Khobotov E N. Modification of the extragradient method for solving variational inequalities and certain optimization problems[J]. USSR Computational Mathematics and Mathematical Physics, 1987, 27:120-127.

[12] 徐海文. 一类凸优化的混合下降算法[J]. 计算数学, 2012, 34(1):93-102.

[13] 徐海文. 一类单调非线性变分不等式的前向加速收缩算法[J]. 数值计算与计算机应用, 2011, 32(4):259-266.

[14] 徐海文. 一类变分不等式的随机步长收缩算法[J]. 工程数学学报, 2011, 8(4):461-469.

[1]	郦旭东. 复合凸优化的快速邻近点算法[J]. 计算数学, 2020, 42(4): 385-404.
[2]	申远, 李倩倩, 吴坚. 一种基于邻近点算法的变步长原始-对偶算法[J]. 计算数学, 2018, 40(1): 85-95.
[3]	徐海文. 一类凸优化的混合下降算法[J]. 计算数学, 2012, 34(1): 93-102.

阅读次数

全文

摘要

一类凸优化的加速混合下降算法

A ACCELERATED HYBRID DESCENT ALGORITHM FOR CONVEX MINIMIZATION

扫码分享