2011, 1(2): 283-299. doi: 10.3934/naco.2011.1.283

Proximal point nonlinear rescaling method for convex optimization

1. 

Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030, United States

2. 

Departments of Mathematical Sciences and SEOR, George Mason University, Fairfax, VA 22030, United States

Received  November 2010 Revised  April 2011 Published  June 2011

Nonlinear rescaling (NR) methods alternate finding an unconstrained minimizer of the Lagrangian for the equivalent problem in the primal space (which is an infinite procedure) with Lagrange multipliers update.
    We introduce and study a proximal point nonlinear rescaling (PPNR) method that preserves convergence and retains a linear convergence rate of the original NR method and at the same time does not require an infinite procedure at each step.
    The critical component of our analysis is the equivalence of the NR method with dynamic scaling parameter update to the interior quadratic proximal point method for the dual problem in the rescaled from step to step dual space.
    By adding the classical quadratic proximal term to the primal objective function the PPNR step can be viewed as a primal-dual proximal point mapping. This allows analyzing a wide variety of non-quadratic augmented Lagrangian methods from unique and general point of view using tools typical for the classical quadratic proximal-point technique.
    We proved convergence of the primal-dual PPNR sequence under minimum assumptions on the input data and established a $q$-linear rate of convergence under the standard second-order optimality conditions.
Citation: 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
References:
[1]

A. Auslender, M. Teboulle and S. Ben-Tiba, Interior proximal and multipliers methods based on second-order homegeneous kernels, Mathematics of Operations Research, 24 (1999), 645-668. doi: doi:10.1287/moor.24.3.645.

[2]

D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods," Academic Press, New York, 1982.

[3]

I. Griva and R. Polyak, Primal-Dual Nonlinear Rescaling Method with Dynamic Scaling Parameter Update, Mathematical Programming, 106 (2006), 237-259. doi: doi:10.1007/s10107-005-0603-6.

[4]

G. J. Minty, Monotone (nonlinear) Operators in Hilbert Space, Duke Math Journal, 29 (1962), 341-346. doi: doi:10.1215/S0012-7094-62-02933-2.

[5]

B. T. Polyak, "Introduction to Optimization," Software Inc., New York, 1987.

[6]

R. Polyak, Modified Barrier Functions (theory and methods), Mathematical Programming, 54 (1992), 177-222. doi: doi:10.1007/BF01586050.

[7]

R. Polyak, Nonlinear Rescaling vs. Smoothing Technique in convex optimization, Mathematical Programming, 92 (2002), 197-235. doi: doi:10.1007/s101070100293.

[8]

R. Polyak, Nonlinear rescaling as Interior Quadratic Prox method in convex optimization, Computational Optimization and Applications, 35 (2006), 347-373. doi: doi:10.1007/s10589-006-9759-0.

[9]

R. Polyak and M. Teboulle, Nonlinear Rescaling and Proximal-like Methods in convex optimization, Mathematical Programming, 76 (1997), 265-284. doi: doi:10.1007/BF02614440.

[10]

R. Polyak and I. Griva, Primal-Dual Nonlinear Rescaling method for convex optimization, Journal of Optimization Theory and Applications, 122 (2004), 111-156. doi: doi:10.1023/B:JOTA.0000041733.24606.99.

[11]

R. T. Rockafellar, Monotone Operators and The Proximal Point Algorithm, SIAM Journal of Control and Optimization, 14 (1976), 887-898. doi: doi:10.1137/0314056.

[12]

R. T. Rockafellar, Augmented Lagrangians and Applications of the Proximal Point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), 97-116. doi: doi:10.1287/moor.1.2.97.

[13]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1996.

[14]

P. Tseng and D. Bertsekas, On the convergence of exponential multipliers method for convex programming, Mathematical Programming, 76 (1993), 1-19. doi: doi:10.1007/BF01580598.

show all references

References:
[1]

A. Auslender, M. Teboulle and S. Ben-Tiba, Interior proximal and multipliers methods based on second-order homegeneous kernels, Mathematics of Operations Research, 24 (1999), 645-668. doi: doi:10.1287/moor.24.3.645.

[2]

D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods," Academic Press, New York, 1982.

[3]

I. Griva and R. Polyak, Primal-Dual Nonlinear Rescaling Method with Dynamic Scaling Parameter Update, Mathematical Programming, 106 (2006), 237-259. doi: doi:10.1007/s10107-005-0603-6.

[4]

G. J. Minty, Monotone (nonlinear) Operators in Hilbert Space, Duke Math Journal, 29 (1962), 341-346. doi: doi:10.1215/S0012-7094-62-02933-2.

[5]

B. T. Polyak, "Introduction to Optimization," Software Inc., New York, 1987.

[6]

R. Polyak, Modified Barrier Functions (theory and methods), Mathematical Programming, 54 (1992), 177-222. doi: doi:10.1007/BF01586050.

[7]

R. Polyak, Nonlinear Rescaling vs. Smoothing Technique in convex optimization, Mathematical Programming, 92 (2002), 197-235. doi: doi:10.1007/s101070100293.

[8]

R. Polyak, Nonlinear rescaling as Interior Quadratic Prox method in convex optimization, Computational Optimization and Applications, 35 (2006), 347-373. doi: doi:10.1007/s10589-006-9759-0.

[9]

R. Polyak and M. Teboulle, Nonlinear Rescaling and Proximal-like Methods in convex optimization, Mathematical Programming, 76 (1997), 265-284. doi: doi:10.1007/BF02614440.

[10]

R. Polyak and I. Griva, Primal-Dual Nonlinear Rescaling method for convex optimization, Journal of Optimization Theory and Applications, 122 (2004), 111-156. doi: doi:10.1023/B:JOTA.0000041733.24606.99.

[11]

R. T. Rockafellar, Monotone Operators and The Proximal Point Algorithm, SIAM Journal of Control and Optimization, 14 (1976), 887-898. doi: doi:10.1137/0314056.

[12]

R. T. Rockafellar, Augmented Lagrangians and Applications of the Proximal Point algorithm in convex programming, Mathematics of Operations Research, 1 (1976), 97-116. doi: doi:10.1287/moor.1.2.97.

[13]

R. T. Rockafellar, "Convex Analysis," Princeton University Press, Princeton, 1996.

[14]

P. Tseng and D. Bertsekas, On the convergence of exponential multipliers method for convex programming, Mathematical Programming, 76 (1993), 1-19. doi: doi:10.1007/BF01580598.

[1]

Yu-Hong Dai, Xin-Wei Liu, Jie Sun. A primal-dual interior-point method capable of rapidly detecting infeasibility for nonlinear programs. Journal of Industrial and Management Optimization, 2020, 16 (2) : 1009-1035. doi: 10.3934/jimo.2018190

[2]

Guoqiang Wang, Zhongchen Wu, Zhongtuan Zheng, Xinzhong Cai. Complexity analysis of primal-dual interior-point methods for semidefinite optimization based on a parametric kernel function with a trigonometric barrier term. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 101-113. doi: 10.3934/naco.2015.5.101

[3]

Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

[4]

Yanqin Bai, Xuerui Gao, Guoqiang Wang. Primal-dual interior-point algorithms for convex quadratic circular cone optimization. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 211-231. doi: 10.3934/naco.2015.5.211

[5]

Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37

[6]

Xiayang Zhang, Yuqian Kong, Shanshan Liu, Yuan Shen. A relaxed parameter condition for the primal-dual hybrid gradient method for saddle-point problem. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022008

[7]

Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial and Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723

[8]

Kai Wang, Deren Han. On the linear convergence of the general first order primal-dual algorithm. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021134

[9]

Nadia Hazzam, Zakia Kebbiche. A primal-dual interior point method for $ P_{\ast }\left( \kappa \right) $-HLCP based on a class of parametric kernel functions. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 513-531. doi: 10.3934/naco.2020053

[10]

Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91

[11]

Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems and Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031

[12]

Yixuan Yang, Yuchao Tang, Meng Wen, Tieyong Zeng. Preconditioned Douglas-Rachford type primal-dual method for solving composite monotone inclusion problems with applications. Inverse Problems and Imaging, 2021, 15 (4) : 787-825. doi: 10.3934/ipi.2021014

[13]

Yu-Hong Dai, Zhouhong Wang, Fengmin Xu. A Primal-dual algorithm for unfolding neutron energy spectrum from multiple activation foils. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2367-2387. doi: 10.3934/jimo.2020073

[14]

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

[15]

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

[16]

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

[17]

Yu-Lin Chang, Jein-Shan Chen, Jia Wu. Proximal point algorithm for nonlinear complementarity problem based on the generalized Fischer-Burmeister merit function. Journal of Industrial and Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153

[18]

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

[19]

Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems and Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565

[20]

Samira Shahsavari, Saeed Ketabchi. The proximal methods for solving absolute value equation. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 449-460. doi: 10.3934/naco.2020037

 Impact Factor: 

Metrics

  • PDF downloads (79)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]