一种部分非精确求解可分离凸优化问题的渐近点算法（英文）
|
摘要
本文研究了一类具有可分离结构的凸优化问题,在经典的交替方向法的基础上得到了一种部分非精确的渐近点算法.该方法分别求解凸优化问题的两个子问题,其中一个直接求解,另一个通过引入非精确项降低了求解的难度.在合理的假设下,新算法的收敛性得到了证明.数值实验表明新算法是有效的.
In this paper, a new method is proposed for solving a class of separable convex programming problem. The method is referred to as the partial inexact proximal point method. In the method, we take a fresh look at the alternating direction method of multipliers and two subproblems are solved independently. One is solved directly and the other is handled by bring in inexact minimization. Convergence of the method is proved under mild assumptions and its efficiency is also verified by numerical experiments.
In this paper, a new method is proposed for solving a class of separable convex programming problem. The method is referred to as the partial inexact proximal point method. In the method, we take a fresh look at the alternating direction method of multipliers and two subproblems are solved independently. One is solved directly and the other is handled by bring in inexact minimization. Convergence of the method is proved under mild assumptions and its efficiency is also verified by numerical experiments.
引文
[1] Chen S, Saunders M A, Donoho D L. Atomic decomposition by basis pursuit [J]. Siam Rev, 2001, 43: 33.
[2] Candes E J, Tao T. Decoding by linear programming [J].IEEE T Inf Theory, 2005, 51: 4203.
[3] Yang J, Zhang Y, Yin W. An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise [J]. Siam J Sci Comput, 2009, 31: 2842.
[4] Cai J F, Candes E J. A singular value thresholding algorithm for matrix completion [J]. Siam J Optimiz, 2008, 20: 1956.
[5] Boyd S, Vandenberghe L. Convex optimization [M]. Cambridge: Cambridge University Press, 2004.
[6] Glowinski R, Marrocco A. 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 [J]. Revue Fr Autom Inform Rech Opér Anal Numér 1975, 2: 41.
[7] He B S, Liao L Z, Han D R. A new inexact alternating directionsmethod for monotone variational inequalities [J].Math Program, 2002,92: 103.
[8] Ye C H, Yuan X M. A descent method for structured monotone variational inequalities [J]. Optim Method Softw, 2007, 22: 329.
[9] He B S, Tao M,Yuan X M. Alternating direction method with Gaussian back substitution for Separable convex programming [J]. SIAM [J] Optimiz, 2012, 22: 313.
[10] He B S. Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities [J]. Comput Optim Appl, 2009, 42: 195.
[11] Cai X J, Gu G Y,He B S. A proximal point algorithm revisit on the alternating direction method of multipliers [J].Sci China Math, 2013, 56: 2179.
[12] He B S, Liao L Z, Yuan X M. Alternating projection based prediction-correction methods for structuredvariational inequalities [J]. Comput Math, 2006, 24: 693.
[13] Tao M, Yuan X M. An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures [J].Comput Optim Appl, 2012, 52: 439.
[14] Chen Z M, Wan L, Yang Q Z. An inexact direction method for structured variational inequalities [J]. J Optimiz Theory Appl, 2014, 163: 439.
[15] Gu G Y, He B S, Yang J F. Inexact alternating direction-based contraction methods for separable linearly constrained convex optimization [J]. J Optimiz Theory Appl, 2013, 163: 105.
[16] Peng Z, Zhu W X. A partial inexact alternating direction method for structured variational inequalities [J]. Optimization, 2014, 63: 1043.
[17] Peng Z, Wu D H. An inexact proximal alternating directions method for structured variational inequalities [J]. Lect Notes Eng Comput Sci, 2010, 1: 1.
[18] Li H, Kou X P. A new inexact parallel splitting method for monotonevariational inequalities with separable structures [J]. J Sichuan Univ: Nat Sci Ed(四川大学学报:自然科学版), 2016, 53: 503.
[19] Bersekas D P, Tsitsiklis J N. Parallel and distributed computation [M]. Englewood Cliffs: Prentice-Hall, 1997.
[2] Candes E J, Tao T. Decoding by linear programming [J].IEEE T Inf Theory, 2005, 51: 4203.
[3] Yang J, Zhang Y, Yin W. An efficient TVL1 algorithm for deblurring multichannel images corrupted by impulsive noise [J]. Siam J Sci Comput, 2009, 31: 2842.
[4] Cai J F, Candes E J. A singular value thresholding algorithm for matrix completion [J]. Siam J Optimiz, 2008, 20: 1956.
[5] Boyd S, Vandenberghe L. Convex optimization [M]. Cambridge: Cambridge University Press, 2004.
[6] Glowinski R, Marrocco A. 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 [J]. Revue Fr Autom Inform Rech Opér Anal Numér 1975, 2: 41.
[7] He B S, Liao L Z, Han D R. A new inexact alternating directionsmethod for monotone variational inequalities [J].Math Program, 2002,92: 103.
[8] Ye C H, Yuan X M. A descent method for structured monotone variational inequalities [J]. Optim Method Softw, 2007, 22: 329.
[9] He B S, Tao M,Yuan X M. Alternating direction method with Gaussian back substitution for Separable convex programming [J]. SIAM [J] Optimiz, 2012, 22: 313.
[10] He B S. Parallel splitting augmented Lagrangian methods for monotone structured variational inequalities [J]. Comput Optim Appl, 2009, 42: 195.
[11] Cai X J, Gu G Y,He B S. A proximal point algorithm revisit on the alternating direction method of multipliers [J].Sci China Math, 2013, 56: 2179.
[12] He B S, Liao L Z, Yuan X M. Alternating projection based prediction-correction methods for structuredvariational inequalities [J]. Comput Math, 2006, 24: 693.
[13] Tao M, Yuan X M. An inexact parallel splitting augmented Lagrangian method for monotone variational inequalities with separable structures [J].Comput Optim Appl, 2012, 52: 439.
[14] Chen Z M, Wan L, Yang Q Z. An inexact direction method for structured variational inequalities [J]. J Optimiz Theory Appl, 2014, 163: 439.
[15] Gu G Y, He B S, Yang J F. Inexact alternating direction-based contraction methods for separable linearly constrained convex optimization [J]. J Optimiz Theory Appl, 2013, 163: 105.
[16] Peng Z, Zhu W X. A partial inexact alternating direction method for structured variational inequalities [J]. Optimization, 2014, 63: 1043.
[17] Peng Z, Wu D H. An inexact proximal alternating directions method for structured variational inequalities [J]. Lect Notes Eng Comput Sci, 2010, 1: 1.
[18] Li H, Kou X P. A new inexact parallel splitting method for monotonevariational inequalities with separable structures [J]. J Sichuan Univ: Nat Sci Ed(四川大学学报:自然科学版), 2016, 53: 503.
[19] Bersekas D P, Tsitsiklis J N. Parallel and distributed computation [M]. Englewood Cliffs: Prentice-Hall, 1997.