Proximal point nonlinear rescaling method for convex optimization

Igor Griva; Roman A. Polyak

doi:10.3934/naco.2011.1.283

Article Contents

2011, Volume 1, Issue 2: 283-299. Doi: 10.3934/naco.2011.1.283

This issue Previous Article An optimal impulsive control regulator for linear systems Next Article Multiplicative perturbation analysis for QR factorizations

Proximal point nonlinear rescaling method for convex optimization

Igor Griva^1, and
Roman A. Polyak^2,

1.
Department of Mathematical Sciences, George Mason University, Fairfax, VA 22030
2.
Departments of Mathematical Sciences and SEOR, George Mason University, Fairfax, VA 22030

Received: November 2010

Revised: April 2011

Published: June 2011

Abstract / Introduction Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: 90C25; 90C30.

Citation:

Related Papers

Cited by

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.