摘要
具有线性约束的凸优化问题是数学规划中的一类经典问题。本文将借助对偶理论,研究求解一类具有线性等式约束的凸优化问题的加速算法。由于此类问题的对偶问题是一个具有两块可分离结构的凸优化问题,我们基于Goldstein等人在加速交替方向乘子法方面的重要工作,提出了一种在弱化条件下求解线性等式约束凸优化问题的加速方法。我们的方法与Goldstein等人的加速交替方向乘子法的不同之处为:1)目标函数仅要求具有凸性(而不必强凸);2)罚参数仅要求β>0(而不受目标函数的利普希茨常数、强单调系数的限制)。基于上述弱化的条件,我们证明了所提的加速交替方向乘子法依然具有收敛性和O(1/k^(2))的收敛率。我们将条件弱化后的加速交替方向乘子法用于求解一个图像重建问题。数值实验结果表明,条件弱化后的加速交替方向乘子法依然具有较好的数值效果。
The linearly constrained convex optimization is a class of quintessential problem in optimization community.In this paper,we will devote to the algorithmic study of such problems on the perspective of duality.By introducing auxiliary variables,the dual of this problem can be reformulated into a separable structured optimization.By virtue of the recent advances in accelerated alternating direction method of multiplier,we analyze the convergence and establish the O(1/k^(2))convergence rate of Goldstein et al's accelerated algorithm under some mild conditions.Specifically,1)the objective sufices to be convex instead of strongly convex;2)the penalty parameter merely requiresβ>0 instead of a bounded interval involving Lipschitz constant and strongly convex modulus.Some numerical experiments on image reconstruction problem were conducted to demon-strate the performance of algorithm on solving linearly constrained convex optimization,which is computationally appealing.
作者
孟辛晴
张文星
MENG Xinqing;ZAHNG Wenxing(School of MathematicalSciences,Universityof Electronic Science and Technology of China,Chengdu 611731,Sichuan,China)
出处
《运筹学学报（中英文）》
CSCD
北大核心
2024年第1期1-17,共17页
Operations Research Transactions
基金
国家自然科学基金(No.11971003)
中央高校基本业务费(No.ZYGX2019J090)。
关键词
线性等式约束
对偶
可分离结构凸优化
交替方向乘子法
Nesterov加速技术
linear-equality constraint
duality
separable structured convex opti-mization
alternating direction method of multipliers
Nesterov's acceleration technique
