# American Institute of Mathematical Sciences

• Previous Article
The optimization of a multi-period multi-product closed-loop supply chain network with cross-docking delivery strategy
• JIMO Home
• This Issue
• Next Article
A unified derivative-free projection method model for large-scale nonlinear equations with convex constraints
doi: 10.3934/jimo.2021174
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

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

 1 Aliyun School of Big Data, Changzhou University, Jiangsu, China 2 School of Accounting, Nanjing University of Finance and Economics, Jiangsu, China

* Corresponding author: Suhong Jiang

Received  November 2020 Revised  July 2021 Early access October 2021

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

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.

Citation: Yanfei You, Suhong Jiang. Improved Lagrangian-PPA based prediction correction method for linearly constrained convex optimization. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021174
##### References:
 [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. Cai, E. 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. Esser, X. 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. He, X. 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. Jiang, Z. 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. Ma, D. 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. You, X. 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.

show all references

##### References:
 [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. Cai, E. 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. Esser, X. 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. He, X. 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. Jiang, Z. 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. Ma, D. 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. You, X. 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.
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
 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
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
 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

2020 Impact Factor: 1.801