Abstract
The nonlinear rescaling principle employs monotone and sufficiently smooth functions to transform the constraints and/or the objective function into an equivalent problem, the classical Lagrangian which has important properties on the primal and the dual spaces.
The application of the nonlinear rescaling principle to constrained optimization problems leads to a class of modified barrier functions (MBF's) and MBF Methods (MBFM's). Being classical Lagrangians (CL's) for an equivalent problem, the MBF's combine the best properties of the CL's and classical barrier functions (CBF's) but at the same time are free of their most essential deficiencies.
Due to the excellent MBF properties, new characteristics of the dual pair convex programming problems have been found and the duality theory for nonconvex constrained optimization has been developed.
The MBFM have up to a superlinear rate of convergence and are to the classical barrier functions (CBF's) method as the Multipliers Method for Augmented Lagrangians is to the Classical Penalty Function Method. Based on the dual theory associated with MBF, the method for the simultaneous solution of the dual pair convex programming problems with up to quadratic rates of convergence have been developed. The application of the MBF to linear (LP) and quadratic (QP) programming leads to a new type of multipliers methods which have a much better rate of convergence under lower computational complexity at each step as compared to the CBF methods.
The numerical realization of the MBFM leads to the Newton Modified Barrier Method (NMBM). The excellent MBF properties allow us to discover that for any nondegenerate constrained optimization problem, there exists a “hot” start, from which the NMBM has a better rate of convergence, a better complexity bound, and is more stable than the interior point methods, which are based on the classical barrier functions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
K. Arrow, L. Hurwicz, H. Uzawa,Studies on Linear and Nonlinear Programming (Stanford University Press, Stanford, CA, 1958).
D. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982).
C.W. Carroll, “The created response surface technique for optimizing nonlinear restrained systems,”Operations Research 9(2) (1961) 169–184.
J.E. Dennis Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NY, 1983).
I.I. Dikin, “Iterative solution of problems of linear and quadratic programming,”Doklady Academii Nauk SSSR 174 (1967) 747–748.
A.V. Fiacco and G.P. McCormick,Nonlinear Programming. Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968).
R. Fletcher, “Recent developments in linear and quadratic programming,” Report NA/94, Numerical Analysis, University of Dundee (Dundee, UK, 1986).
K.R. Firsch, “The logarithmic potential method of convex programming,” Memorandum, University Institute of Economics, Oslo (Oslo, 1955).
P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London, 1981).
P.E. Gill, M. Murray, M.A. Saunders, J.A. Tomlin and M.H. Wright, “On projected Newton barrier methods for linear programming and an equivalence to Karmarkar's projective method,”Mathematical Programming 36 (1986) 183–209.
E.G. Gol'shtein and N.V. Tret'yakov,Modified Lagrangian Functions (Theory and Methods Optimization) (Nauka, Moscow, 1989).
C.C. Gonzaga, “An algorithm for solving Linear Programming problems in O(n 3 L) operations,” to appear in: N. Megiddo, ed.,Research Issues in Linear Programming, Proceedings of the Asilomar Conference (Springer, New York, 1988).
K. Grossman and A.A. Kaplan,Nonlinear Programming Based on Unconstrained Minimization (Nauka, Novosibirsk, 1981). [In Russian.]
M.R. Hestenes, “Multiplier and gradient methods,”Journal of Optimization Theory and Applications 4(5) (1969) 303–320.
N.A. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
K.A. McShane, C.L. Monma and D.F. Shanno, “An implementation of a primal—dual interior point method for Linear Programming,”ORSA Journal on Computing 1 (1989) 70–89.
Ju.E. Nesterov and A.S. Nemirovsky,Self-concordant Functions and Polynomial-Time Methods in Convex Programming (CEMI Academy of Sciences, Moscow, 1989).
E. Polak,Computational Methods im Optimization: A Unified Approach (Academic Press, New York, 1971).
B.T. Polyak,Introduction to Optimization (Nauka, Moscow, 1983). [In Russian.]
B.T. Polyak and N.V. Tret'yakov, “The method of penalty estimates for conditional extremum problems,”Computational Mathematics and Mathematical Physics 13 (1974) 42–58.
R. Polyak, “Smooth optimization methods for solving nonlinear extremal and equilibrium problems with constraints,” Abstracts of the papers ofThe 11th International Symposium on Mathematical Programming (Bonn, 1982).
R. Polyak, “Classical Lagrangians with the properties of the modified ones and estimation of complexity for linear and quadratic programming,” Abstracts of the papers ofThe 12th International Symposium on Mathematical Programming (Boston, 1985).
R. Polyak,Controlled Processes in Extremal and Equilibrium Problems (VINITI, Moscow, 1986), Deposited manuscript. [In Russian.]
R. Polyak, “Smooth optimization methods for minimax problems,”SIAM Journal on Control and Optimization 26(6) (1988) 1274–1286.
R. Polyak, “Modified barrier functions,” IBM Research Report RC14602, IBM T.J. Watson Research Center (Yorktown Heights, NY, 1989).
R. Polyak, “The nonlinear rescaling principle in linear programming,” IBM Research Report RC15030, IBM T.J. Watson Research Center (Yorktown Heights, NY, 1989).
M.J.D. Powell, “A method for nonlinear constraints in minimization problems,” In: R. Fletcher, ed.Optimization (Academic Press, New York, 1969) pp. 283–298.
J. Renegar, “A polynomial-time algorithm, based on Newton's method, for linear programming,”Mathematical Programming 40 (1988) 59–93.
J. Renegar and M. Shub, “Simplified complexity analysis for Newton LP methods,” Technical Report No. 807, School of Operation Research and Industrial Engineering, College of Engineering, Cornell University (Ithaca, NY, 1988).
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970).
R.T. Rockafellar, “Augmented Lagrange multiplier functions and duality in nonconvex programming,”SIAM Journal on Control and Optimization 12(2) (1974) 268–285.
S. Smale, “Newton's method estimates from data at one point,” in: R.E. Ewing et al., eds.The Merging of Disciplines in Pure, Applied, and Computational Mathematics (Springer, New York—Berlin, 1986) pp. 185–196.
S. Smale, “Algorithms for solving equations,” in:Proceedings of the International Congress of Mathematicians (Berkeley, CA, 1986) pp. 172–195.
M.J. Todd, “Recent developments and new directions in linear programming,” Technical Report No. 827, School of Operation Research and Industrial Engineering, Cornell University (Ithaca, NY, 1988).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Polyak, R. Modified barrier functions (theory and methods). Mathematical Programming 54, 177–222 (1992). https://doi.org/10.1007/BF01586050
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01586050