• 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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

B. S. He, A class of projection and contraction methods for monotone variational inequalities, Appl. Math. Optim., 35 (1997), 69-76.   Google Scholar

[8]

B. S. He, Inexact implicit methods for monotone general variational inequalities, Math. Program. Ser. A, 86 (1999), 199-217.  doi: 10.1007/s101070050086.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[14]

B. S. He and X. M. Yuan, A contraction method with implementable proximal regularization for linearly constrained convex programming, Optimization Online, 2010. Google Scholar

[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.  Google Scholar

[16]

R. M. Larsen, Propack software for large and sparse svd calculation, 2005. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

B. Martinet, Regularisation d'inéquations variationelles par approximations succesives, Rev. Franqaise Informa. Recherche Opérationalle, 4 (1970), 154-158.   Google Scholar

[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.   Google Scholar

[21]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

B. S. He, A class of projection and contraction methods for monotone variational inequalities, Appl. Math. Optim., 35 (1997), 69-76.   Google Scholar

[8]

B. S. He, Inexact implicit methods for monotone general variational inequalities, Math. Program. Ser. A, 86 (1999), 199-217.  doi: 10.1007/s101070050086.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[14]

B. S. He and X. M. Yuan, A contraction method with implementable proximal regularization for linearly constrained convex programming, Optimization Online, 2010. Google Scholar

[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.  Google Scholar

[16]

R. M. Larsen, Propack software for large and sparse svd calculation, 2005. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[19]

B. Martinet, Regularisation d'inéquations variationelles par approximations succesives, Rev. Franqaise Informa. Recherche Opérationalle, 4 (1970), 154-158.   Google Scholar

[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.   Google Scholar

[21]

R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim., 14 (1976), 877-898.  doi: 10.1137/0314056.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

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
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
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
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
[1]

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

[2]

Yuan Shen, Wenxing Zhang, Bingsheng He. Relaxed augmented Lagrangian-based proximal point algorithms for convex optimization with linear constraints. Journal of Industrial & Management Optimization, 2014, 10 (3) : 743-759. doi: 10.3934/jimo.2014.10.743

[3]

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

[4]

Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control & Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027

[5]

Giuseppe Marino, Hong-Kun Xu. Convergence of generalized proximal point algorithms. Communications on Pure & Applied Analysis, 2004, 3 (4) : 791-808. doi: 10.3934/cpaa.2004.3.791

[6]

Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389

[7]

Jie Shen, Jian Lv, Fang-Fang Guo, Ya-Li Gao, Rui Zhao. A new proximal chebychev center cutting plane algorithm for nonsmooth optimization and its convergence. Journal of Industrial & Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003

[8]

Ram U. Verma. On the generalized proximal point algorithm with applications to inclusion problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 381-390. doi: 10.3934/jimo.2009.5.381

[9]

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

[10]

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

[11]

Yanqin Bai, Lipu Zhang. A full-Newton step interior-point algorithm for symmetric cone convex quadratic optimization. Journal of Industrial & Management Optimization, 2011, 7 (4) : 891-906. doi: 10.3934/jimo.2011.7.891

[12]

Tim Hoheisel, Maxime Laborde, Adam Oberman. A regularization interpretation of the proximal point method for weakly convex functions. Journal of Dynamics & Games, 2020, 7 (1) : 79-96. doi: 10.3934/jdg.2020005

[13]

Sanming Liu, Zhijie Wang, Chongyang Liu. Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems. Numerical Algebra, Control & Optimization, 2015, 5 (1) : 79-89. doi: 10.3934/naco.2015.5.79

[14]

A. M. Bagirov, Moumita Ghosh, Dean Webb. A derivative-free method for linearly constrained nonsmooth optimization. Journal of Industrial & Management Optimization, 2006, 2 (3) : 319-338. doi: 10.3934/jimo.2006.2.319

[15]

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

[16]

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

[17]

Adil Bagirov, Sona Taheri, Soodabeh Asadi. A difference of convex optimization algorithm for piecewise linear regression. Journal of Industrial & Management Optimization, 2019, 15 (2) : 909-932. doi: 10.3934/jimo.2018077

[18]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134

[19]

Cristian Barbarosie, Anca-Maria Toader, Sérgio Lopes. A gradient-type algorithm for constrained optimization with application to microstructure optimization. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1729-1755. doi: 10.3934/dcdsb.2019249

[20]

Jinyan Fan. On the Levenberg-Marquardt methods for convex constrained nonlinear equations. Journal of Industrial & Management Optimization, 2013, 9 (1) : 227-241. doi: 10.3934/jimo.2013.9.227

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (65)
  • HTML views (68)
  • Cited by (0)

Other articles
by authors

[Back to Top]