Nonlinear rescaling and proximal-like methods in convex optimization. (English) Zbl 0882.90106

Polyak, Roman; Teboulle, Marc

Math. Program. 76, No. 2 (A), 265-284 (1997).

Summary: The nonlinear rescaling principle (NRP) consists of transforming the objective function and/or the constraints of a given constrained optimization problem into another problem which is equivalent to the original one in the sense that their optimal set of solutions coincides. A nonlinear transformation parameterized by a positive scalar parameter and based on a smooth scaling function is used to transform the constraints. The methods based on NRP consist of sequential unconstrained minimization of the classical Lagrangian for the equivalent problem, followed by an explicit formula updating the Lagrange multipliers. We first show that the NRP leads naturally to proximal methods with an entropy-like kernel, which is defined by the conjugate of the scaling function, and establish that the two methods are dually equivalent for convex constrained minimization problems. We then study the convergence properties of the nonlinear rescaling algorithm and the corresponding entropy-like proximal methods for convex constrained optimization problems. Special cases of the nonlinear rescaling algorithm are presented. In particular a new class of exponential penalty-modified barrier functions methods is introduced.

MSC:

90C25

Convex programming

Keywords:

nonlinear rescaling principle; convergence properties; entropy-like proximal methods; convex constrained optimization; exponential penalty-modified barrier functions methods

References:

[1]	D. Bertsekas,Constrained Optimization and Lagrange Multipher Methods (Academic Press, NY, 1982). · Zbl 0572.90067
[2]	A. Ben-Tal, I Yuzefovich and M. Zibulevsky, Penalty/barrier multiplier methods for minimax and constrained smooth convex programs, Research Report 9-92. Optimization Laboratory, Technion, Israel.
[3]	M.G. Breitfeld and D.F. Shanno, Computational experience with modified log-barrier methods for nonlinear programming, Rutcor Research Report 17-93, Rutgers University, New Brunswick, NJ. · Zbl 0811.90093
[4]	R.D. Bruck, Asymptotic behavior of nonexpansive mappings,Contemporary Mathematics 18 (1983) 1–47. · Zbl 0528.47039
[5]	J.H. Cassis, and A. Schmit, On implementation of the extended interior penalty function,International Journal for Numerical Methods in Engineering 10 (1976) 3–23. · Zbl 0338.90064
[6]	J. Eckstein, Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming,Mathematics of Operations Research 18 (1993) 202–226. · Zbl 0807.47036
[7]	A.V. Fiacco, and G.P. McCormick,Nonlinear Programming, Sequential Unconstrained Minimization Techniques, SIAM Classics in Applied Mathematics (SIAM, Philadelphia, PA, 1990).
[8]	R.T. Haftka and J.H. Starnes, Applications of a quadratic extended interior penalty function for structural optimization,AIAA Journal 14 (1976) 718–724. · Zbl 0343.73061
[9]	A.N. Iusem, B. Svaiter, M. Teboulle, Entropy-like proximal methods in convex programming,Mathematics of Operations Research 19 (1994) 790–814. · Zbl 0821.90092
[10]	A. Iusem and M. Teboulle, Convergence rate analysis of nonquadratic proximal methods for convex and linear programming,Mathematics of Operations Research 20 (1995) 657–677. · Zbl 0845.90099
[11]	D.L. Jensen and R.A. Polyak, The convergence of a modified barrier method for convex programming,IBM Journal of Research and Development 38 (1994) 307–321. · Zbl 0820.90083
[12]	B. Martinet, Perturbation des méthodes d’optimisation. Application,R.A.I.R.O. Analyse numérique/Numerical Analysis (1978).
[13]	J.J. Moreau, Proximité et dualité dans un espace Hilbertien,Bulletin de la Societé Mathématique de France 93 (1965) 273–299. · Zbl 0136.12101
[14]	S.G. Nash, R. Polyak and A. Sofer, A numerical comparison of barrier and modified-barrier methods for large scale bound constrained optimization, in: W.W. Hager, D.W. Hearn and P.M. Pardalos, eds.,Large Scale Optimization: State of the Art (Kluwer, Dordrecht, The Netherlands, 1994). · Zbl 0811.90101
[15]	R.A. Polyak, Controlled processes in extremal and equilibrium problems, VINITI, deposited manuscript, Moscow (1986) (in Russian)
[16]	R.A. Polyak, Modified barrier functions (theory and methods),Mathematical Programming 54 (1992) 177–222. · Zbl 0756.90085
[17]	M.J.D. Powell, Some convergence properties of the shifted log barrier method for linear programming, Numerical Analysis Report, DAMTP 1992/NA7, University of Cambridge (1992).
[18]	B. Prasad, and R.T. Haftka, A cubic extended interior penalty function for structural optimization,International Journal for Numerical Methods in Engineering 14 (1979) 1107–1126. · Zbl 0419.73073
[19]	R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[20]	R.T. Rockafellar, A dual approach to solving nonlinear programming problems by unconstrained optimization,Mathematical Programming 5 (1973) 354–373. · Zbl 0279.90035
[21]	R.T. Rockafellar, Monotone operators and the proximal point algorithm.SIAM Journal of Control and Optimization 14 (1976) 877–898. · Zbl 0358.90053
[22]	M. Teboulle, Entropic proximal mappings with application to nonlinear programming,Mathematics of Operations Research 17 (1992) 670–690. · Zbl 0766.90071
[23]	M.J. Todd, Scaling, shifting and weighting in interior-points methods, Technical Report N0. 1067, School of Operations Research and Industrial Engineering, Cornell University (1993).
[24]	P. Tseng, D. Bertsekas, On the convergence of the exponential multiplier method for convex programming,Mathematical Programming 60 (1993) 1–19. · Zbl 0783.90101