中文

Operations Research Transactions >

2024 , Vol. 28 >Issue 1: 1 - 17

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2024.01.001

An accelerated method for solving a class of linear equality constrained convex optimization

Expand
  • 1. School of Mathematical Sciences, University of Electronic Science and Technology of China, Chengdu 611731, Sichuan, China

Received date: 2021-07-25

  Online published: 2024-03-16

Copyright

, 2024, All rights reserved, without authorization
Fold

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

Cite this article

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 . DOI: 10.15960/j.cnki.issn.1007-6093.2024.01.001

References

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.
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.
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.
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.
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.
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.
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.
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.
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.
22 Lei Y , Xie J .A symmetric alternating minimization algorithm for total variation minimization[J].Signal Processing,2020,176,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.
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.
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.
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.
Options
Outlines

/

〈 〉