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

[2]

D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods,", Academic Press, (1982).   Google Scholar

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

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

[5]

B. T. Polyak, "Introduction to Optimization,", Software Inc., (1987).   Google Scholar

[6]

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

[7]

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

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

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

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

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

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

[13]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1996).   Google Scholar

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

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

[2]

D. Bertsekas, "Constrained Optimization and Lagrange Multipliers Methods,", Academic Press, (1982).   Google Scholar

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

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

[5]

B. T. Polyak, "Introduction to Optimization,", Software Inc., (1987).   Google Scholar

[6]

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

[7]

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

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

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

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

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

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

[13]

R. T. Rockafellar, "Convex Analysis,", Princeton University Press, (1996).   Google Scholar

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

[1]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[2]

Xuefei He, Kun Wang, Liwei Xu. Efficient finite difference methods for the nonlinear Helmholtz equation in Kerr medium. Electronic Research Archive, 2020, 28 (4) : 1503-1528. doi: 10.3934/era.2020079

[3]

Justin Holmer, Chang Liu. Blow-up for the 1D nonlinear Schrödinger equation with point nonlinearity II: Supercritical blow-up profiles. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020264

[4]

Christian Beck, Lukas Gonon, Martin Hutzenthaler, Arnulf Jentzen. On existence and uniqueness properties for solutions of stochastic fixed point equations. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020320

[5]

Zonghong Cao, Jie Min. Selection and impact of decision mode of encroachment and retail service in a dual-channel supply chain. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020167

[6]

Xin Guo, Lei Shi. Preface of the special issue on analysis in data science: Methods and applications. Mathematical Foundations of Computing, 2020, 3 (4) : i-ii. doi: 10.3934/mfc.2020026

[7]

Shun Zhang, Jianlin Jiang, Su Zhang, Yibing Lv, Yuzhen Guo. ADMM-type methods for generalized multi-facility Weber problem. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020171

[8]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[9]

Gunther Uhlmann, Jian Zhai. Inverse problems for nonlinear hyperbolic equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 455-469. doi: 10.3934/dcds.2020380

[10]

Thomas Bartsch, Tian Xu. Strongly localized semiclassical states for nonlinear Dirac equations. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 29-60. doi: 10.3934/dcds.2020297

[11]

Hua Chen, Yawei Wei. Multiple solutions for nonlinear cone degenerate elliptic equations. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020272

[12]

Abdelghafour Atlas, Mostafa Bendahmane, Fahd Karami, Driss Meskine, Omar Oubbih. A nonlinear fractional reaction-diffusion system applied to image denoising and decomposition. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020321

[13]

Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020448

[14]

Zhiyan Ding, Qin Li, Jianfeng Lu. Ensemble Kalman Inversion for nonlinear problems: Weights, consistency, and variance bounds. Foundations of Data Science, 2020  doi: 10.3934/fods.2020018

[15]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[16]

Scipio Cuccagna, Masaya Maeda. A survey on asymptotic stability of ground states of nonlinear Schrödinger equations II. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020450

[17]

Kihoon Seong. Low regularity a priori estimates for the fourth order cubic nonlinear Schrödinger equation. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5437-5473. doi: 10.3934/cpaa.2020247

[18]

Maoding Zhen, Binlin Zhang, Vicenţiu D. Rădulescu. Normalized solutions for nonlinear coupled fractional systems: Low and high perturbations in the attractive case. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020379

[19]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436

[20]

Claudianor O. Alves, Rodrigo C. M. Nemer, Sergio H. Monari Soares. The use of the Morse theory to estimate the number of nontrivial solutions of a nonlinear Schrödinger equation with a magnetic field. Communications on Pure & Applied Analysis, , () : -. doi: 10.3934/cpaa.2020276

 Impact Factor: 

Metrics

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

Other articles
by authors

[Back to Top]