\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

Improved Lagrangian-PPA based prediction correction method for linearly constrained convex optimization

  • * Corresponding author: Suhong Jiang

    * Corresponding author: Suhong Jiang

The first author is supported by the NSFC grant 11701048. The second author is supported by the NSFC grant 12101297

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • This paper presents an improved Lagrangian-PPA based prediction correction method to solve linearly constrained convex optimization problem. At each iteration, the predictor is achieved by minimizing the proximal Lagrangian function with respect to the primal and dual variables. These optimization subproblems involved either admit analytical solutions or can be solved by a fast algorithm. The new update is generated by using the information of the current iterate and the predictor, as well as an appropriately chosen stepsize. Compared with the existing PPA based method, the parameters are relaxed. We also establish the convergence and convergence rate of the proposed method. Finally, numerical experiments are conducted to show the efficiency of our Lagrangian-PPA based prediction correction method.

    Mathematics Subject Classification: Primary: 90C25, 90C30; Secondary: 65K05, 65K10.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • Table 1.  Performance of PPA, L-PPA and Our Method

    Size PPA L-PPA Our Method $\tau = 2$ Our Method $\tau = 3$
    $n$ It. CPU It. CPU It. CPU It. CPU
    $500$ 27 2.85 22 2.36 19 2.01 20 2.06
    $1000$ 31 17.01 25 14.42 18 10.23 18 10.28
    $1500$ 36 60.95 29 52.34 19 37.72 17 32.19
    $2000$ 41 178.37 33 152.42 20 88.30 20 89.05
    $3000$ 49 698.51 37 541.60 25 369.14 25 357.59
    $4000$ 59 1917.01 44 2552.53 31 934.66 31 934.66
     | Show Table
    DownLoad: CSV

    Table 2.  Comparison of PPA, L-PPA and Our Method

    Problems PPA L-PPA Our Mthod
    $n$ rank sr fr It. CPU It. CPU It. CPU
    500 10 0.16 0.25 57 1.82 41 1.26 40 0.94
    1000 10 0.12 0.17 70 11.7 52 8.59 41 5.17
    1000 20 0.16 0.25 63 19.17 46 10.25 36 7.51
    2000 10 0.12 0.08 91 95.32 67 50.54 50 46.84
    2000 20 0.16 0.13 82 117.73 61 99.71 46 62.14
     | Show Table
    DownLoad: CSV
  • [1] K. J. Arrow, L. Hurwicz and H. Uzawa, Studies in linear and non-linear programming, In Stanford Mathematical Studies in the Social Sciences, II, Stanford University Press, Stanford, 1958.
    [2] J. F. CaiE. J. Candès and Z. W. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20 (2010), 1956-1982.  doi: 10.1137/080738970.
    [3] E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foud. Comput. Math., 9 (2008), 717-772.  doi: 10.1007/s10208-009-9045-5.
    [4] W. Deng, M. J. Lai and W. Yin, On the $o(1/k)$ convergence and parallelization of the alternating direction method of multipliers, preprint, arXiv: 1312.3040.
    [5] E. EsserX. Q. Zhang and T. F. Chan, A general framework for a class of first order primal- dual algorithms for convex optimization in imaging science, SIAM J. Imaging Sci, 3 (2010), 1015-1046.  doi: 10.1137/09076934X.
    [6] F. Facchinei and J. S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vol. I, Springer Series in Operations Research, Springer Verlag, New York, 2003.
    [7] B. S. He, A class of projection and contraction methods for monotone variational inequalities, Appl. Math. Optim., 35 (1997), 69-76. 
    [8] B. S. He, Inexact implicit methods for monotone general variational inequalities, Math. Program. Ser. A, 86 (1999), 199-217.  doi: 10.1007/s101070050086.
    [9] B. S. He, PPA-like contraction methods for convex optimization: A framework using variational inequality approach, J. Oper. Res. Soc. China, 3 (2015), 391-420.  doi: 10.1007/s40305-015-0108-9.
    [10] B. S. HeX. L. Fu and Z. K. Jiang, Proximal point algorithm using a linear proximal term, J. Optim. Theory Appl., 141 (2009), 299-239.  doi: 10.1007/s10957-008-9493-0.
    [11] B. S. He and Y. Shen, On the convergence rate of customized proximal point algorithm for convex optimization and saddle-point problem (in Chinese), Scientia Sinica Mathematica, 42 (2012), 515-525. 
    [12] B. S. He and M.-H. Xu, A general framework of contraction methods for monotone variational inequalities, Pac. J. Optim., 4 (2008), 195-212. 
    [13] B. S. He and X. M. Yuan, Convergence analysis of primal-dual algorithms for a saddle-point problem: From contraction perspective, SIAM J. Imaging Sci., 5 (2012), 119-149.  doi: 10.1137/100814494.
    [14] B. S. He and X. M. Yuan, A contraction method with implementable proximal regularization for linearly constrained convex programming, Optimization Online, 2010.
    [15] B. JiangZ. Peng and K. Deng, Two new customized proximal point algorithms without relaxation for linearly constrained convex optimization, Bull. Iranian Math. Soc., 46 (2020), 865-892.  doi: 10.1007/s41980-019-00298-0.
    [16] R. M. Larsen, Propack software for large and sparse svd calculation, 2005.
    [17] F. Ma and M. Ni, A class of customized proximal point algorithms for linearly constrained convex optimization, Comput. Appl. Math., 37 (2018), 896-911.  doi: 10.1007/s40314-016-0371-3.
    [18] S. Q. MaD. Goldfarb and L. F. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128 (2011), 321-353.  doi: 10.1007/s10107-009-0306-5.
    [19] B. Martinet, Regularisation d'inéquations variationelles par approximations succesives, Rev. Franqaise Informa. Recherche Opérationalle, 4 (1970), 154-158. 
    [20] B. Martinet, Détermination approchée d'un point fixe d'une application pseudo-contractante. Cas de l'application prox, C. R. Acad. Sci. Paris, 274 (1972), 163-165. 
    [21] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.
    [22] Y. F. YouX. L. Fu and B. S. He, Lagrangian-PPA based contraction methods for linearly constrained convex optimization, Pac. J. Optim., 10 (2014), 199-213. 
    [23] M. Zhu and T. Chan, An efficient primal-dual hybird gradient algorithm for total variation image restoration, UCLA CAM Report, 34 (2008), 8-34. 
  • 加载中

Tables(2)

SHARE

Article Metrics

HTML views(502) PDF downloads(463) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return