求解一类线性等式约束凸优化问题的加速方法

doi:10.15960/j.cnki.issn.1007-6093.2024.01.001

摘要/Abstract

摘要：

具有线性约束的凸优化问题是数学规划中的一类经典问题。本文将借助对偶理论, 研究求解一类具有线性等式约束的凸优化问题的加速算法。由于此类问题的对偶问题是一个具有两块可分离结构的凸优化问题, 我们基于Goldstein等人在加速交替方向乘子法方面的重要工作, 提出了一种在弱化条件下求解线性等式约束凸优化问题的加速方法。我们的方法与Goldstein等人的加速交替方向乘子法的不同之处为：1) 目标函数仅要求具有凸性(而不必强凸)；2) 罚参数仅要求$\beta>0$(而不受目标函数的利普希茨常数、强单调系数的限制)。基于上述弱化的条件, 我们证明了所提的加速交替方向乘子法依然具有收敛性和O(1/k²)的收敛率。我们将条件弱化后的加速交替方向乘子法用于求解一个图像重建问题。数值实验结果表明, 条件弱化后的加速交替方向乘子法依然具有较好的数值效果。

关键词: 线性等式约束, 对偶, 可分离结构凸优化, 交替方向乘子法, Nesterov加速技术

Abstract:

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 suffices to be convex instead of strongly convex; 2) the penalty parameter merely requires $\beta>0$ instead of a bounded interval involving Lipschitz constant and strongly convex modulus. Some numerical experiments on image reconstruction problem were conducted to demonstrate the performance of algorithm on solving linearly constrained convex optimization, which is computationally appealing.

Key words: linear-equality constraint, duality, separable structured convex optimization, alternating direction method of multipliers, Nesterov's acceleration technique

中图分类号:

O221.2

孟辛晴, 张文星. 求解一类线性等式约束凸优化问题的加速方法[J]. 运筹学学报, 2024, 28(1): 1-17.

Xinqing MENG, Wenxing ZAHNG. An accelerated method for solving a class of linear equality constrained convex optimization[J]. Operations Research Transactions, 2024, 28(1): 1-17.

图/表 5

图1

图2

图3

图4

图5

参考文献 33

1	Bruckstein A , Donoho D , Elad M .From sparse solutions of systems of equations to sparse modeling of signals and images[J].SIAM Review,2009,51,34-81. doi: 10.1137/060657704
2	Chan T , Shen J .Image Processing and Analysis: Variational, PDE, Wavelet, and Stochastic Methods[M].Philadelphia: SIAM,2005.
3	Hastie T , Tibshirani R , Friedman J .The Elements of Statistical Learning: Data Mining, Inference, and Prediction[M].New York: Springer,2008.
4	Wets R .Stochastic Systems: Modeling, Identification and Optimization[M].Amsterdam: The Mathematical Programming Study,1976.
5	Glowinski R , Marrocco A .Analyse numérique du champ magnétique d'un alternateur par élèments finis et sur-relaxation ponctuelle non linèaire[J].Computer Methods in Applied Mechanics and Engineering,1974,3(1):55-85. doi: 10.1016/0045-7825(74)90042-5
6	Gabay D , Mercier B .A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J].Computers & Mathematics with Applications,1976,2(1):17-40.
7	He B , Liao L , Han D , et al.A new inexact alternating directions method for monotone variational inequalities[J].Mathematical Programming,2002,92(1):103-118. doi: 10.1007/s101070100280
8	Eckstein J, Fukushima M. Some reformulations and applications of the alternating direction method of multipliers[M]//Large Scale Optimization, Boston: Springer, 1994, 115-134.
9	Glowinski R. On alternating direction methods of multipliers: A historical perspective[M]//Modeling, Simulation and Optimization for Science and Technology, Netherlands: Springer, 2014, 59-82.
10	Boyd S , Parikh N , Chu E , et al.Distributed optimization and statistical learning via the alternating direction method of multipliers[J].Foundations and Trends in Machine Learning,2011,3,1-122.
11	Eckstein J, Yao W. Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results[R]. New Brunswick: Rutgers University, 2012.
12	Gabay D. Applications of the method of multipliers to variational inequalities[M]//Studies in Mathematics and its Applications, Amsterdam: Elsevier, 1983, 299-331.
13	He B , Yuan X .On the ${O}(1/n)$ convergence rate of the Douglas-Rachford alternating direction method[J].SIAM Journal on Numerical Analysis,2012,50(2):700-709. doi: 10.1137/110836936
14	Nesterov Y .A method for solving the convex programming problem with convergence rate $o(1/k^2)$[J].Nauk SSSR,1983,269(3):543-547.
15	Zhang R , White J .GMRES-accelerated ADMM for quadratic objectives[J].SIAM Journal on Optimization,2018,28(4):3025-3056. doi: 10.1137/16M1059941
16	Zhang J , Peng Y , Ouyang W , et al.Accelerating ADMM for efficient simulation and optimization[J].ACM Transactions on Graphics,2019,38(6):1-21.
17	Ouyang Y , Chen Y , Lan H , et al.An accelerated linearized alternating direction method of multipliers[J].SIAM Journal on Imaging Sciences,2015,8(1):644-681. doi: 10.1137/14095697X
18	Goldstein T , O'Donoghue B , Setzer S , et al.Fast alternating direction optimization methods[J].SIAM Journal on Imaging Sciences,2014,7(3):1588-1623. doi: 10.1137/120896219
19	Bai J , Li J , Xu F , et al.A novel method for a class of structured low-rank minimizations with equality constraint[J].Journal of Computational and Applied Mathematics,2018,330,475-487. doi: 10.1016/j.cam.2017.09.021
20	He B, Yuan X. On the acceleration of augmented Lagrangian method for linearly constrained optimization[EB/OL]. (2010-10-11)[2021-06-20]. http://www.optimization-online.org/DB_FILE/2010/10/2760.pdf.
21	Luo G , Yang Q .A fast symmetric alternating direction method of multipliers[J].Numerical Mathematics: Theory, Methods and Applications,2020,13(1):200-219. doi: 10.4208/nmtma.OA-2018-0108
22	Lei Y , Xie J .A symmetric alternating minimization algorithm for total variation minimization[J].Signal Processing,2020,176,107673. doi: 10.1016/j.sigpro.2020.107673
23	Bauschke H , Combettes P .Convex Analysis and Monotone Operator Theory in Hilbert Spaces[M].New York: Springer,2011.
24	Combettes P , Wajs V .Signal recovery by proximal forward-backward splitting[J].Multiscale Modeling and Simulation,2005,4(4):1168-1200. doi: 10.1137/050626090
25	Ng M , Yuan X , Zhang W .Coupled variational image decomposition and restoration model for blurred cartoon-plus-texture images with missing pixels[J].IEEE Transactions on Image Processing,2013,22(6):2233-2246. doi: 10.1109/TIP.2013.2246520
26	Xu H , Feng C , Li B .Temperature aware workload managementin geo-distributed data centers[J].IEEE Transactions on Parallel and Distributed Systems,2014,26(6):1743-1753.
27	Ruszczyński A .Parallel decomposition of multistage stochastic programming problems[J].Mathematical Programming,1993,58(1):201-228.
28	Tao M , Yuan X .Recovering low-rank and sparse components of matrices from incomplete and noisy observations[J].SIAM Journal on Optimization,2011,21(1):57-81. doi: 10.1137/100781894
29	Starck J , Murtagh F , Fadili J .Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity[M].Cambridge: Cambridge University Press,2010.
30	Hansen P , Nagy J , O'leary D .Deblurring Images: Matrices, Spectra, and Filtering[M].Philadelphia: SIAM,2006.
31	Scherzer O , Grasmair M , Grossauer H , et al.Variational Methods in Imaging[M].New York: Springer,2009.
32	Huber P .Robust regression: Asymptotics, conjectures and Monte Carlo[J].Annals of Statistics,1973,1,799-821.
33	Nesterov Y .Smooth minimization of non-smooth functions[J].Mathematical Programming,2005,103,127-152.

[1]	彭建文, 雷宏旺. 非凸两分块优化问题的一类惯性对称正则化交替方向乘子法[J]. 运筹学学报, 2023, 27(3): 37-52.
[2]	王茂然, 蔡邢菊, 吴中明, 韩德仁. 多模式交通均衡问题的一阶分裂算法[J]. 运筹学学报, 2023, 27(2): 63-78.
[3]	王海军, 王辉辉. 带消失约束的区间值优化问题的最优性条件与对偶定理[J]. 运筹学学报, 2023, 27(1): 87-102.
[4]	谢文蕙, 凌晨, 潘晨健. 一个基于张量火车分解的张量填充方法及在图像恢复中的应用[J]. 运筹学学报, 2022, 26(3): 31-43.
[5]	吕袈豪, 罗洪林, 杨泽华, 彭建文. 随机Bregman ADMM及其在训练具有离散结构的支持向量机中的应用[J]. 运筹学学报, 2022, 26(2): 16-30.
[6]	张立卫. 浅谈增广Lagrange方法中的二阶分析[J]. 运筹学学报, 2021, 25(3): 1-14.
[7]	王双月, 罗自炎. 一类基于L_0/1软间隔损失函数的低秩支持张量机[J]. 运筹学学报, 2021, 25(3): 160-172.
[8]	任建峰, 田晓云. 带有异常点的平方度量设施选址问题[J]. 运筹学学报, 2021, 25(1): 114-122.
[9]	仲维亚, 施益媚. 不确定彩排时长下节目调度的鲁棒优化[J]. 运筹学学报, 2020, 24(3): 77-86.
[10]	陈彩华. 多块交替方向乘子法不收敛反例的几点注记[J]. 运筹学学报, 2019, 23(3): 135-140.
[11]	高雷阜, 闫婷婷. 均衡约束数学规划问题的一类广义Mond-Weir型对偶理论[J]. 运筹学学报, 2019, 23(2): 95-103.
[12]	王硕, 朱志斌, 张本鑫. 最小化三个凸函数之和的一个简单原始-对偶算法[J]. 运筹学学报, 2018, 22(2): 127-138.
[13]	杨俊锋. 图像处理中全变差正则化数据拟合问题算法回顾[J]. 运筹学学报, 2017, 21(4): 69-83.
[14]	康志林, 李仲飞. CVaR鲁棒均值-CVaR投资组合模型与求解[J]. 运筹学学报, 2017, 21(1): 1-12.
[15]	田朝薇, 张立卫. 从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性[J]. 运筹学学报, 2017, 21(1): 111-117.