American Institute of Mathematical Sciences

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 & 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. doi: doi:10.1287/moor.24.3.645. [2] D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods,", Academic Press, (1982). [3] I. Griva and R. Polyak, Primal-Dual Nonlinear Rescaling Method with Dynamic Scaling Parameter Update,, Mathematical Programming, 106 (2006), 237. doi: doi:10.1007/s10107-005-0603-6. [4] G. J. Minty, Monotone (nonlinear) Operators in Hilbert Space,, Duke Math Journal, 29 (1962), 341. doi: doi:10.1215/S0012-7094-62-02933-2. [5] B. T. Polyak, "Introduction to Optimization,", Software Inc., (1987). [6] R. Polyak, Modified Barrier Functions (theory and methods),, Mathematical Programming, 54 (1992), 177. doi: doi:10.1007/BF01586050. [7] R. Polyak, Nonlinear Rescaling vs. Smoothing Technique in convex optimization,, Mathematical Programming, 92 (2002), 197. 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. 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. 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. 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. 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. doi: doi:10.1287/moor.1.2.97. [13] R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1996). [14] P. Tseng and D. Bertsekas, On the convergence of exponential multipliers method for convex programming,, Mathematical Programming, 76 (1993), 1. 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. doi: doi:10.1287/moor.24.3.645. [2] D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods,", Academic Press, (1982). [3] I. Griva and R. Polyak, Primal-Dual Nonlinear Rescaling Method with Dynamic Scaling Parameter Update,, Mathematical Programming, 106 (2006), 237. doi: doi:10.1007/s10107-005-0603-6. [4] G. J. Minty, Monotone (nonlinear) Operators in Hilbert Space,, Duke Math Journal, 29 (1962), 341. doi: doi:10.1215/S0012-7094-62-02933-2. [5] B. T. Polyak, "Introduction to Optimization,", Software Inc., (1987). [6] R. Polyak, Modified Barrier Functions (theory and methods),, Mathematical Programming, 54 (1992), 177. doi: doi:10.1007/BF01586050. [7] R. Polyak, Nonlinear Rescaling vs. Smoothing Technique in convex optimization,, Mathematical Programming, 92 (2002), 197. 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. 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. 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. 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. 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. doi: doi:10.1287/moor.1.2.97. [13] R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1996). [14] P. Tseng and D. Bertsekas, On the convergence of exponential multipliers method for convex programming,, Mathematical Programming, 76 (1993), 1. 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 & Management Optimization, 2017, 13 (5) : 1-27. 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 & 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 & 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 & 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 & Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37 [6] Jen-Yen Lin, Hui-Ju Chen, Ruey-Lin Sheu. Augmented Lagrange primal-dual approach for generalized fractional programming problems. Journal of Industrial & Management Optimization, 2013, 9 (4) : 723-741. doi: 10.3934/jimo.2013.9.723 [7] 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 & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 [8] Xiaojing Ye, Haomin Zhou. Fast total variation wavelet inpainting via approximated primal-dual hybrid gradient algorithm. Inverse Problems & Imaging, 2013, 7 (3) : 1031-1050. doi: 10.3934/ipi.2013.7.1031 [9] 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 [10] 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 [11] 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 [12] 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 & Management Optimization, 2013, 9 (1) : 153-169. doi: 10.3934/jimo.2013.9.153 [13] 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 [14] Sandrine Anthoine, Jean-François Aujol, Yannick Boursier, Clothilde Mélot. Some proximal methods for Poisson intensity CBCT and PET. Inverse Problems & Imaging, 2012, 6 (4) : 565-598. doi: 10.3934/ipi.2012.6.565 [15] Mohamed Badreddine, Thomas K. DeLillo, Saman Sahraei. A Comparison of some numerical conformal mapping methods for simply and multiply connected domains. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 55-82. doi: 10.3934/dcdsb.2018100 [16] Chunrong Chen, Shengji Li. Upper Hölder estimates of solutions to parametric primal and dual vector quasi-equilibria. Journal of Industrial & Management Optimization, 2012, 8 (3) : 691-703. doi: 10.3934/jimo.2012.8.691 [17] Pierre Frankel. Alternating proximal algorithm with costs-to-move, dual description and application to PDE's. Discrete & Continuous Dynamical Systems - S, 2012, 5 (3) : 545-557. doi: 10.3934/dcdss.2012.5.545 [18] Hssaine Boualam, Ahmed Roubi. Dual algorithms based on the proximal bundle method for solving convex minimax fractional programs. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-24. doi: 10.3934/jimo.2018128 [19] 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 [20] Jana Kopfová. Nonlinear semigroup methods in problems with hysteresis. Conference Publications, 2007, 2007 (Special) : 580-589. doi: 10.3934/proc.2007.2007.580

Impact Factor: