American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Parameter-related projection-based iterative algorithm for a kind of generalized positive semidefinite least squares problem
  • NACO Home
  • This Issue
  • Next Article
    A trust region algorithm for computing extreme eigenvalues of tensors
December  2020, 10(4): 487-510. doi: 10.3934/naco.2020047

Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization

Yan Gu 1,, and  Nobuo Yamashita 1,

1. 

Graduate School of Informatics, Kyoto University, Kyoto 606-8501, Japan

* Corresponding author: Yan Gu

This paper is dedicated in honor and to the memory of Professor Wenyu Sun

Received  May 2020 Revised  September 2020 Published  September 2020

Fund Project: This work is supported by JSPS KAKENHI Grant Number 17K00032

This paper studies a proximal alternating direction method of multipliers (ADMM) with variable metric indefinite proximal terms for linearly constrained convex optimization problems. The proximal ADMM plays an important role in many application areas, since the subproblems of the method are easy to solve. Recently, it is reported that the proximal ADMM with a certain fixed indefinite proximal term is faster than that with a positive semidefinite term, and still has the global convergence property. On the other hand, Gu and Yamashita studied a variable metric semidefinite proximal ADMM whose proximal term is generated by the BFGS update. They reported that a slightly indefinite matrix also makes the algorithm work well in their numerical experiments. Motivated by this fact, we consider a variable metric indefinite proximal ADMM, and give sufficient conditions on the proximal terms for the global convergence. Moreover, based on the BFGS update, we propose a new indefinite proximal term which can satisfy the conditions for the global convergence. Experiments on several datasets demonstrated that our proposed variable metric indefinite proximal ADMM outperforms most of the comparison proximal ADMMs.

Keywords: Alternating direction method of multipliers, Variable metric indefinite proximal term, BFGS update, Global convergence, Convex optimization.
Mathematics Subject Classification: Primary: 90C25, 90C53, 65K05.
Citation: Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
References:
[1]

S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine Learning, 3 (2011), 1–122. doi: 10.1561/2200000016.

[2]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145.  doi: 10.1007/s10851-010-0251-1.

[3]

W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, Journal of Scientific Computing, 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.

[4]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods and Software, 4 (1994), 75-83.  doi: 10.1080/10556789408805578.

[5]

J. Eckstein and D. P. Bertsekas, On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318.  doi: 10.1007/BF01581204.

[6]

J. Eckstein and W. Yao, Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM, Mathematical Programming, 170 (2018), 417-444.  doi: 10.1007/s10107-017-1160-5.

[7]

M. Fazel, T. K. Pong, D. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.

[8]

M. Fortin and R. Glowinski, Chapter ⅲ on decomposition-coordination methods using an augmented lagrangian, in Studies in Mathematics and Its Applications, vol. 15, Elsevier, (1983), 97–146. doi: 10.1016/S0168-2024(08)70028-6.

[9]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.

[10]

B. Gao and F. Ma, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, Journal of Optimization Theory and Applications, 176 (2018), 178-204.  doi: 10.1007/s10957-017-1207-z.

[11]

R. Glowinski and A. Marroco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires, ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 9 (1975), 41–76. doi: 10.1051/m2an/197509R200411.

[12]

M. L. N. Gonçalves, M. M. Alves and J. G. Melo, Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers, Journal of Optimization Theory and Applications, 177 (2018), 448-478.  doi: 10.1007/s10957-018-1232-6.

[13]

Y. Gu and N. Yamashita, An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization, preprint, arXiv: 1903.02270.

[14]

Y. Gu and N. Yamashita, A proximal ADMM with the Broyden family for convex optimization problems, Journal of Industrial and Management Optimization, 13 (2020). doi: 10.3934/jimo.2020091.

[15]

D. Harrison Jr and D. L. Rubinfeld, Hedonic housing prices and the demand for clean air, Journal of Environmental Economics and Management, 5 (1978), 81-102.  doi: 10.1016/0095-0696(78)90006-2.

[16]

B. He, L.-Z. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities, Mathematical Programming, 92 (2002), 103-118.  doi: 10.1007/s101070100280.

[17]

B. He, H. Liu, Z. Wang and X. Yuan, A strictly contractive Peaceman–Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1011-1040.  doi: 10.1137/13090849X.

[18]

B. He and X. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709.  doi: 10.1137/110836936.

[19]

B. He and X. Yuan, Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI Journal of Computational Mathematics, 1 (2015), 145-174.  doi: 10.5802/smai-jcm.6.

[20]

B. He, F. Ma and X. Yuan, Optimally linearizing the alternating direction method of multipliers for convex programming, Computational Optimization and Applications, (2019), 1–28. doi: 10.1007/s10589-019-00152-3.

[21]

K. Koh, S.-J. Kim and S. Boyd, An interior-point method for large-scale l1-regularized logistic regression, Journal of Machine Learning Research, 8 (2007), 1519-1555.  doi: 10.1109/JSTSP.2007.910971.

[22]

M. Li, D. Sun and K.-C. Toh, A majorized admm with indefinite proximal terms for linearly constrained convex composite optimization, SIAM Journal on Optimization, 26 (2016), 922-950.  doi: 10.1137/140999025.

[23]

P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979.  doi: 10.1137/0716071.

[24]

P. A. Lotito, L. A. Parente and M. Solodov, A class of variable metric decomposition methods for monotone variational inclusions, Journal of Convex Analysis, 16 (2009), 857-880. 

[25]

Y. Nesterov, Gradient methods for minimizing composite functions, Mathematical Programming, 140 (2013), 125-161.  doi: 10.1007/s10107-012-0629-5.

[26]

R. K. Pace and R. Barry, Sparse spatial autoregressions, Statistics and Probability Letters, 33 (1997), 291-297.  doi: 10.1016/S0167-7152(96)00140-X.

[27]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.

[28]

H. Trevor, T. Robert and F. JH, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer Science and Business Media, 2009.

[29]

P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 117 (2009), 387-423.  doi: 10.1007/s10107-007-0170-0.

[30]

M. Xu, Proximal alternating directions method for structured variational inequalities, Journal of Optimization Theory and Applications, 134 (2007), 107-117.  doi: 10.1007/s10957-007-9192-2.

[31]

M. Xu and T. Wu, A class of linearized proximal alternating direction methods, Journal of Optimization Theory and Applications, 151 (2011), 321-337.  doi: 10.1007/s10957-011-9876-5.

[32]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1 (2008), 143-168.  doi: 10.1137/070703983.

show all references

References:
[1]

S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine Learning, 3 (2011), 1–122. doi: 10.1561/2200000016.

[2]

A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, Journal of Mathematical Imaging and Vision, 40 (2011), 120-145.  doi: 10.1007/s10851-010-0251-1.

[3]

W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, Journal of Scientific Computing, 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.

[4]

J. Eckstein, Some saddle-function splitting methods for convex programming, Optimization Methods and Software, 4 (1994), 75-83.  doi: 10.1080/10556789408805578.

[5]

J. Eckstein and D. P. Bertsekas, On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators, Mathematical Programming, 55 (1992), 293-318.  doi: 10.1007/BF01581204.

[6]

J. Eckstein and W. Yao, Relative-error approximate versions of Douglas–Rachford splitting and special cases of the ADMM, Mathematical Programming, 170 (2018), 417-444.  doi: 10.1007/s10107-017-1160-5.

[7]

M. Fazel, T. K. Pong, D. Sun and P. Tseng, Hankel matrix rank minimization with applications to system identification and realization, SIAM Journal on Matrix Analysis and Applications, 34 (2013), 946-977.  doi: 10.1137/110853996.

[8]

M. Fortin and R. Glowinski, Chapter ⅲ on decomposition-coordination methods using an augmented lagrangian, in Studies in Mathematics and Its Applications, vol. 15, Elsevier, (1983), 97–146. doi: 10.1016/S0168-2024(08)70028-6.

[9]

D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Computers and Mathematics with Applications, 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.

[10]

B. Gao and F. Ma, Symmetric alternating direction method with indefinite proximal regularization for linearly constrained convex optimization, Journal of Optimization Theory and Applications, 176 (2018), 178-204.  doi: 10.1007/s10957-017-1207-z.

[11]

R. Glowinski and A. Marroco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de dirichlet non linéaires, ESAIM: Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique, 9 (1975), 41–76. doi: 10.1051/m2an/197509R200411.

[12]

M. L. N. Gonçalves, M. M. Alves and J. G. Melo, Pointwise and ergodic convergence rates of a variable metric proximal alternating direction method of multipliers, Journal of Optimization Theory and Applications, 177 (2018), 448-478.  doi: 10.1007/s10957-018-1232-6.

[13]

Y. Gu and N. Yamashita, An alternating direction method of multipliers with the BFGS update for structured convex quadratic optimization, preprint, arXiv: 1903.02270.

[14]

Y. Gu and N. Yamashita, A proximal ADMM with the Broyden family for convex optimization problems, Journal of Industrial and Management Optimization, 13 (2020). doi: 10.3934/jimo.2020091.

[15]

D. Harrison Jr and D. L. Rubinfeld, Hedonic housing prices and the demand for clean air, Journal of Environmental Economics and Management, 5 (1978), 81-102.  doi: 10.1016/0095-0696(78)90006-2.

[16]

B. He, L.-Z. Liao, D. Han and H. Yang, A new inexact alternating directions method for monotone variational inequalities, Mathematical Programming, 92 (2002), 103-118.  doi: 10.1007/s101070100280.

[17]

B. He, H. Liu, Z. Wang and X. Yuan, A strictly contractive Peaceman–Rachford splitting method for convex programming, SIAM Journal on Optimization, 24 (2014), 1011-1040.  doi: 10.1137/13090849X.

[18]

B. He and X. Yuan, On the $O(1/n)$ convergence rate of the Douglas-Rachford alternating direction method, SIAM Journal on Numerical Analysis, 50 (2012), 700-709.  doi: 10.1137/110836936.

[19]

B. He and X. Yuan, Block-wise alternating direction method of multipliers for multiple-block convex programming and beyond, SMAI Journal of Computational Mathematics, 1 (2015), 145-174.  doi: 10.5802/smai-jcm.6.

[20]

B. He, F. Ma and X. Yuan, Optimally linearizing the alternating direction method of multipliers for convex programming, Computational Optimization and Applications, (2019), 1–28. doi: 10.1007/s10589-019-00152-3.

[21]

K. Koh, S.-J. Kim and S. Boyd, An interior-point method for large-scale l1-regularized logistic regression, Journal of Machine Learning Research, 8 (2007), 1519-1555.  doi: 10.1109/JSTSP.2007.910971.

[22]

M. Li, D. Sun and K.-C. Toh, A majorized admm with indefinite proximal terms for linearly constrained convex composite optimization, SIAM Journal on Optimization, 26 (2016), 922-950.  doi: 10.1137/140999025.

[23]

P.-L. Lions and B. Mercier, Splitting algorithms for the sum of two nonlinear operators, SIAM Journal on Numerical Analysis, 16 (1979), 964-979.  doi: 10.1137/0716071.

[24]

P. A. Lotito, L. A. Parente and M. Solodov, A class of variable metric decomposition methods for monotone variational inclusions, Journal of Convex Analysis, 16 (2009), 857-880. 

[25]

Y. Nesterov, Gradient methods for minimizing composite functions, Mathematical Programming, 140 (2013), 125-161.  doi: 10.1007/s10107-012-0629-5.

[26]

R. K. Pace and R. Barry, Sparse spatial autoregressions, Statistics and Probability Letters, 33 (1997), 291-297.  doi: 10.1016/S0167-7152(96)00140-X.

[27]

L. I. Rudin, S. Osher and E. Fatemi, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena, 60 (1992), 259-268.  doi: 10.1016/0167-2789(92)90242-F.

[28]

H. Trevor, T. Robert and F. JH, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Springer Science and Business Media, 2009.

[29]

P. Tseng and S. Yun, A coordinate gradient descent method for nonsmooth separable minimization, Mathematical Programming, 117 (2009), 387-423.  doi: 10.1007/s10107-007-0170-0.

[30]

M. Xu, Proximal alternating directions method for structured variational inequalities, Journal of Optimization Theory and Applications, 134 (2007), 107-117.  doi: 10.1007/s10957-007-9192-2.

[31]

M. Xu and T. Wu, A class of linearized proximal alternating direction methods, Journal of Optimization Theory and Applications, 151 (2011), 321-337.  doi: 10.1007/s10957-011-9876-5.

[32]

W. Yin, S. Osher, D. Goldfarb and J. Darbon, Bregman iterative algorithms for $l_1$-minimization with applications to compressed sensing, SIAM Journal on Imaging Sciences, 1 (2008), 143-168.  doi: 10.1137/070703983.

Figure 1.  Evolution of the objective function values with respect to iterations on real datasets
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Evolution of the objective function values with respect to iterations on synthetic datasets
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  Comparison on the CPU time
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  Comparisons among existing methods
method $ S, T $ $ \alpha $ $ \tau $
Classical ADMM [9,11] $ S=T=0 $ $ (0, (1+\sqrt 5)/2) $ -
Semi-proximal ADMM [7] fixed positive semidefinite matrices $ (0, (1+\sqrt 5)/2) $ $ (1, +\infty) $
Variable semi-proximal ADMM [13,14] variable positive semidefinite matrices 1 $ (1, +\infty) $
Indefinite proximal ADMM [20] fixed indefinite matrices 1 $ (0.75,1) $
Proposed method variable indefinite matrices 1 $ (0.75,1) $
Table Options

Download as excel

method $ S, T $ $ \alpha $ $ \tau $
Classical ADMM [9,11] $ S=T=0 $ $ (0, (1+\sqrt 5)/2) $ -
Semi-proximal ADMM [7] fixed positive semidefinite matrices $ (0, (1+\sqrt 5)/2) $ $ (1, +\infty) $
Variable semi-proximal ADMM [13,14] variable positive semidefinite matrices 1 $ (1, +\infty) $
Indefinite proximal ADMM [20] fixed indefinite matrices 1 $ (0.75,1) $
Proposed method variable indefinite matrices 1 $ (0.75,1) $
Table201 
Construction of $ T_k $ via the BFGS update
1 Let $ \delta \in (0, \infty) $, $ \tau \in (\frac3 4, 1) $ and $ B_0 \succeq \tau M $;
2 Let $ c_k $ be a sequence such that $ c_k \in [0,1] $ and $ \sum\limits_{k=0}^{\infty} c_k < \infty $;
3 If $ s_k \neq 0 $, then set $ \tilde{l}_k = M^{\delta} s_k $ and update $ B_{k+1} $ via
$\begin{equation*} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ B_{k+1} = B_{k}+ c_k \left(\frac {{\tilde{l}}_{k}{\tilde{l}}_{k}^\top}{{\tilde{l}}_{k}^\top {s}_{k}} -{\frac {B_{k}{s}_{k}{s}_{k}^\top B_{k}^\top}{{s}_{k}^\top B_{k}{s}_{k}}} \right); \end{equation*} $
4 Otherwise
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ B_{k+1} = B_k;$
5 Construct $ T_{k+1} $ as
$\begin{equation*} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T_{k+1} = B_{k+1} - M. \end{equation*} $
Table Options

Download as excel

Construction of $ T_k $ via the BFGS update
1 Let $ \delta \in (0, \infty) $, $ \tau \in (\frac3 4, 1) $ and $ B_0 \succeq \tau M $;
2 Let $ c_k $ be a sequence such that $ c_k \in [0,1] $ and $ \sum\limits_{k=0}^{\infty} c_k < \infty $;
3 If $ s_k \neq 0 $, then set $ \tilde{l}_k = M^{\delta} s_k $ and update $ B_{k+1} $ via
$\begin{equation*} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ B_{k+1} = B_{k}+ c_k \left(\frac {{\tilde{l}}_{k}{\tilde{l}}_{k}^\top}{{\tilde{l}}_{k}^\top {s}_{k}} -{\frac {B_{k}{s}_{k}{s}_{k}^\top B_{k}^\top}{{s}_{k}^\top B_{k}{s}_{k}}} \right); \end{equation*} $
4 Otherwise
$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ B_{k+1} = B_k;$
5 Construct $ T_{k+1} $ as
$\begin{equation*} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ T_{k+1} = B_{k+1} - M. \end{equation*} $
Table 2.  Results for real datasets
Datasets Tolerance $ \beta $ ADMM SPADM IPADM IADMB IADML
Iter. T-A Iter. T-A Iter. T-A Iter. T-A Iter. T-A
Boston-house
$ m=506 $
$ n=13 $		 $ \epsilon^ \mathrm{rel} = 10^{-2} $ 100 22.0 0.0010 70.0 0.0015 48.0 0.0013 26.0 0.0015 25.0 0.0018
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 300 9.0 0.0010 37.0 0.0013 32.0 0.0012 20.0 0.0015 21.0 0.0016
500 11.0 0.0010 29.0 0.0012 26.0 0.0011 20.0 0.0012 19.0 0.0014
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 300 16.0 0.0010 69.0 0.0014 60.0 0.0013 29.0 0.0014 {34.0} 0.0017
$ \epsilon ^ \mathrm{abs} = 10^{-4} $ 500 18.0 0.0011 75.0 0.0015 65.0 0.0014 28.0 0.0015 30.0 0.0016
700 25.0 0.0010 86.0 0.0017 75.0 0.0015 36.0 0.0017 36.0 0.0017
California-housing
$ m=20640 $
$ n=8 $		 $ \epsilon^ \mathrm{rel} = 10^{-2} $ 1000 36.0 0.0014 89.0 0.0069 77.0 0.0064 38.0 0.0022 38.0 0.0054
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 1500 24.0 0.0012 73.0 0.0057 64.0 0.0056 26.0 0.0022 27.0 0.0050
1700 21.0 0.0013 67.0 0.0056 59.0 0.0049 24.0 0.0018 24.0 0.0041
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 5000 23.0 0.0013 55.0 0.0046 49.0 0.0044 28.0 0.0020 28.0 0.0048
$ \epsilon ^ \mathrm{abs} = 10^{-4} $ 5300 22.0 0.0014 53.0 0.0045 47.0 0.0043 27.0 0.0023 27.0 0.0042
5500 22.0 0.0012 52.0 0.0041 47.0 0.0042 26.0 0.0018 26.0 0.0036
Table Options

Download as excel

Datasets Tolerance $ \beta $ ADMM SPADM IPADM IADMB IADML
Iter. T-A Iter. T-A Iter. T-A Iter. T-A Iter. T-A
Boston-house
$ m=506 $
$ n=13 $		 $ \epsilon^ \mathrm{rel} = 10^{-2} $ 100 22.0 0.0010 70.0 0.0015 48.0 0.0013 26.0 0.0015 25.0 0.0018
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 300 9.0 0.0010 37.0 0.0013 32.0 0.0012 20.0 0.0015 21.0 0.0016
500 11.0 0.0010 29.0 0.0012 26.0 0.0011 20.0 0.0012 19.0 0.0014
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 300 16.0 0.0010 69.0 0.0014 60.0 0.0013 29.0 0.0014 {34.0} 0.0017
$ \epsilon ^ \mathrm{abs} = 10^{-4} $ 500 18.0 0.0011 75.0 0.0015 65.0 0.0014 28.0 0.0015 30.0 0.0016
700 25.0 0.0010 86.0 0.0017 75.0 0.0015 36.0 0.0017 36.0 0.0017
California-housing
$ m=20640 $
$ n=8 $		 $ \epsilon^ \mathrm{rel} = 10^{-2} $ 1000 36.0 0.0014 89.0 0.0069 77.0 0.0064 38.0 0.0022 38.0 0.0054
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 1500 24.0 0.0012 73.0 0.0057 64.0 0.0056 26.0 0.0022 27.0 0.0050
1700 21.0 0.0013 67.0 0.0056 59.0 0.0049 24.0 0.0018 24.0 0.0041
$ \epsilon ^ \mathrm{abs} = 10^{-3} $ 5000 23.0 0.0013 55.0 0.0046 49.0 0.0044 28.0 0.0020 28.0 0.0048
$ \epsilon ^ \mathrm{abs} = 10^{-4} $ 5300 22.0 0.0014 53.0 0.0045 47.0 0.0043 27.0 0.0023 27.0 0.0042
5500 22.0 0.0012 52.0 0.0041 47.0 0.0042 26.0 0.0018 26.0 0.0036
Table 3.  Results for Synthetic datasets ($ \epsilon^ \mathrm{rel} = 10^{-2} $, $ \epsilon ^ \mathrm{abs} = 10^{-3} $)
Data T-LU/ME $ \beta $ ADMM SPADM IPADM PADML IADML
Iter. T-A Iter. T-A Iter. T-A Iter. T-A Iter. T-A
$ m=2664 $ T-LU$ =10.315 $ 300 30.7 0.5069 75.2 0.5898 66.9 0.5286 36.3 0.2987 34.1 0.2784
$ n=2778 $ T-ME$ =1.980 $ 500 17.9 0.3010 49.9 0.4102 42.5 0.3555 26.5 0.2260 24.5 0.2034
800 11.5 0.1888 36.0 0.2854 31.7 0.2539 20.1 0.1695 18.3 0.1507
1000 10.3 0.1716 31.6 0.2537 27.3 0.2232 18.4 0.1578 17.1 0.1437
$ m=3580 $ T-LU$ =28.516 $ 300 44.9 1.4417 111.5 1.9481 95.9 1.6807 50.2 0.9149 47.8 0.8656
$ n=4620 $ T-ME$ =5.378 $ 500 27.9 0.9129 73.1 1.2882 62.1 1.0911 36.0 0.6608 33.7 0.6198
800 17.9 0.5888 53.2 0.9468 42.5 0.7578 27.9 0.5178 25.4 0.4786
1000 14.3 0.4787 41.1 0.7307 35.1 0.6266 24.6 0.4576 22.9 0.4221
$ m=7498 $ T-LU=118.826 500 46.8 1.7680 86.9 4.0866 67.2 3.1514 47.2 2.2569 47.0 2.2453
$ n=5633 $ T-ME=16.141 1000 24.3 0.9105 51.0 2.3636 45.0 2.0981 27.6 1.3902 26.1 1.2590
1500 16.1 0.6303 40.9 1.9333 36.0 1.6943 20.7 0.9949 19.5 0.9493
2000 12.1 0.4829 28.9 1.3641 25.9 1.2279 18.8 0.9107 17.0 0.8338
$ m=4774 $ T-LU=158.214 500 48.0 4.7976 134.3 8.7370 116.7 7.6785 61.6 4.1815 59.7 3.9039
$ n=10368 $ T-ME=24.249 1000 23.4 2.3597 80.7 5.3301 70.8 5.7369 41.6 3.6014 38.1 2.6846
1500 17.4 1.4561 55.7 3.0283 49.0 2.6745 31.4 1.7645 29.1 1.6197
2000 13.7 1.1631 47.0 2.6077 41.2 2.2898 29.1 1.6362 26.3 1.4693
Table Options

Download as excel

Data T-LU/ME $ \beta $ ADMM SPADM IPADM PADML IADML
Iter. T-A Iter. T-A Iter. T-A Iter. T-A Iter. T-A
$ m=2664 $ T-LU$ =10.315 $ 300 30.7 0.5069 75.2 0.5898 66.9 0.5286 36.3 0.2987 34.1 0.2784
$ n=2778 $ T-ME$ =1.980 $ 500 17.9 0.3010 49.9 0.4102 42.5 0.3555 26.5 0.2260 24.5 0.2034
800 11.5 0.1888 36.0 0.2854 31.7 0.2539 20.1 0.1695 18.3 0.1507
1000 10.3 0.1716 31.6 0.2537 27.3 0.2232 18.4 0.1578 17.1 0.1437
$ m=3580 $ T-LU$ =28.516 $ 300 44.9 1.4417 111.5 1.9481 95.9 1.6807 50.2 0.9149 47.8 0.8656
$ n=4620 $ T-ME$ =5.378 $ 500 27.9 0.9129 73.1 1.2882 62.1 1.0911 36.0 0.6608 33.7 0.6198
800 17.9 0.5888 53.2 0.9468 42.5 0.7578 27.9 0.5178 25.4 0.4786
1000 14.3 0.4787 41.1 0.7307 35.1 0.6266 24.6 0.4576 22.9 0.4221
$ m=7498 $ T-LU=118.826 500 46.8 1.7680 86.9 4.0866 67.2 3.1514 47.2 2.2569 47.0 2.2453
$ n=5633 $ T-ME=16.141 1000 24.3 0.9105 51.0 2.3636 45.0 2.0981 27.6 1.3902 26.1 1.2590
1500 16.1 0.6303 40.9 1.9333 36.0 1.6943 20.7 0.9949 19.5 0.9493
2000 12.1 0.4829 28.9 1.3641 25.9 1.2279 18.8 0.9107 17.0 0.8338
$ m=4774 $ T-LU=158.214 500 48.0 4.7976 134.3 8.7370 116.7 7.6785 61.6 4.1815 59.7 3.9039
$ n=10368 $ T-ME=24.249 1000 23.4 2.3597 80.7 5.3301 70.8 5.7369 41.6 3.6014 38.1 2.6846
1500 17.4 1.4561 55.7 3.0283 49.0 2.6745 31.4 1.7645 29.1 1.6197
2000 13.7 1.1631 47.0 2.6077 41.2 2.2898 29.1 1.6362 26.3 1.4693
[1]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[2]

Fan Jiang, Zhongming Wu, Xingju Cai. Generalized ADMM with optimal indefinite proximal term for linearly constrained convex optimization. Journal of Industrial and Management Optimization, 2020, 16 (2) : 835-856. doi: 10.3934/jimo.2018181
[3]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
[4]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247
[5]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
[6]

Sohana Jahan. Supervised distance preserving projection using alternating direction method of multipliers. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1783-1799. doi: 10.3934/jimo.2019029
[7]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[8]

Saman Babaie–Kafaki, Reza Ghanbari. A class of descent four–term extension of the Dai–Liao conjugate gradient method based on the scaled memoryless BFGS update. Journal of Industrial and Management Optimization, 2017, 13 (2) : 649-658. doi: 10.3934/jimo.2016038
[9]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[10]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283
[11]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[12]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859
[13]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057
[14]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control and Optimization, 2021  doi: 10.3934/naco.2021028
[15]

Tengteng Yu, Xin-Wei Liu, Yu-Hong Dai, Jie Sun. Variable metric proximal stochastic variance reduced gradient methods for nonconvex nonsmooth optimization. Journal of Industrial and Management Optimization, 2022, 18 (4) : 2611-2631. doi: 10.3934/jimo.2021084
[16]

Regina S. Burachik, C. Yalçın Kaya. An update rule and a convergence result for a penalty function method. Journal of Industrial and Management Optimization, 2007, 3 (2) : 381-398. doi: 10.3934/jimo.2007.3.381
[17]

Yan Gu, Nobuo Yamashita. A proximal ADMM with the Broyden family for convex optimization problems. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2715-2732. doi: 10.3934/jimo.2020091
[18]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial and Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[19]

Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
[20]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial and Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069

 Impact Factor: 

Tools

Metrics

  • PDF downloads (182)
  • HTML views (198)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy