• 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. 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. 

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

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 and 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 and 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 and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[4]

Guoyong Gu, Junfeng Yang. A unified and tight linear convergence analysis of the relaxed proximal point algorithm. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022107

[5]

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

[6]

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

[7]

Yuan Shen, Chang Liu, Yannian Zuo, Xingying Zhang. A modified self-adaptive dual ascent method with relaxed stepsize condition for linearly constrained quadratic convex optimization. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022101

[8]

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 and Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389

[9]

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 and Management Optimization, 2018, 14 (3) : 1143-1155. doi: 10.3934/jimo.2018003

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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

[18]

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

[19]

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

[20]

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

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (305)
  • HTML views (268)
  • Cited by (0)

Other articles
by authors

[Back to Top]