×

Modified barrier functions (theory and methods). (English) Zbl 0756.90085

Summary: 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.

MSC:

90C30 Nonlinear programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] K. Arrow, L. Hurwicz, H. Uzawa,Studies on Linear and Nonlinear Programming (Stanford University Press, Stanford, CA, 1958). · Zbl 0091.16002
[2] D. Bertsekas,Constrained Optimization and Lagrange Multiplier Methods (Academic Press, New York, 1982). · Zbl 0572.90067
[3] C.W. Carroll, ”The created response surface technique for optimizing nonlinear restrained systems,”Operations Research 9(2) (1961) 169–184. · Zbl 0111.17004 · doi:10.1287/opre.9.2.169
[4] J.E. Dennis Jr. and R.B. Schnabel,Numerical Methods for Unconstrained Optimization and Nonlinear Equations (Prentice-Hall, Englewood Cliffs, NY, 1983).
[5] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Doklady Academii Nauk SSSR 174 (1967) 747–748. · Zbl 0189.19504
[6] A.V. Fiacco and G.P. McCormick,Nonlinear Programming. Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968). · Zbl 0193.18805
[7] R. Fletcher, ”Recent developments in linear and quadratic programming,” Report NA/94, Numerical Analysis, University of Dundee (Dundee, UK, 1986). · Zbl 0615.65063
[8] K.R. Firsch, ”The logarithmic potential method of convex programming,” Memorandum, University Institute of Economics, Oslo (Oslo, 1955).
[9] P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London, 1981).
[10] 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. · Zbl 0624.90062 · doi:10.1007/BF02592025
[11] E.G. Gol’shtein and N.V. Tret’yakov,Modified Lagrangian Functions (Theory and Methods Optimization) (Nauka, Moscow, 1989).
[12] 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).
[13] K. Grossman and A.A. Kaplan,Nonlinear Programming Based on Unconstrained Minimization (Nauka, Novosibirsk, 1981). [In Russian.]
[14] M.R. Hestenes, ”Multiplier and gradient methods,”Journal of Optimization Theory and Applications 4(5) (1969) 303–320. · Zbl 0174.20705 · doi:10.1007/BF00927673
[15] N.A. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[16] 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. · Zbl 0752.90047
[17] Ju.E. Nesterov and A.S. Nemirovsky,Self-concordant Functions and Polynomial-Time Methods in Convex Programming (CEMI Academy of Sciences, Moscow, 1989).
[18] E. Polak,Computational Methods im Optimization: A Unified Approach (Academic Press, New York, 1971). · Zbl 0257.90055
[19] B.T. Polyak,Introduction to Optimization (Nauka, Moscow, 1983). [In Russian.]
[20] 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. · Zbl 0273.90055 · doi:10.1016/0041-5553(74)90004-4
[21] 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).
[22] 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).
[23] R. Polyak,Controlled Processes in Extremal and Equilibrium Problems (VINITI, Moscow, 1986), Deposited manuscript. [In Russian.]
[24] R. Polyak, ”Smooth optimization methods for minimax problems,”SIAM Journal on Control and Optimization 26(6) (1988) 1274–1286. · Zbl 0657.90075 · doi:10.1137/0326071
[25] R. Polyak, ”Modified barrier functions,” IBM Research Report RC14602, IBM T.J. Watson Research Center (Yorktown Heights, NY, 1989). · Zbl 0756.90085
[26] R. Polyak, ”The nonlinear rescaling principle in linear programming,” IBM Research Report RC15030, IBM T.J. Watson Research Center (Yorktown Heights, NY, 1989).
[27] 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. · Zbl 0194.47701
[28] J. Renegar, ”A polynomial-time algorithm, based on Newton’s method, for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050 · doi:10.1007/BF01580724
[29] 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). · Zbl 0751.90048
[30] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[31] R.T. Rockafellar, ”Augmented Lagrange multiplier functions and duality in nonconvex programming,”SIAM Journal on Control and Optimization 12(2) (1974) 268–285. · Zbl 0285.90063 · doi:10.1137/0312021
[32] 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. · Zbl 0613.65058
[33] S. Smale, ”Algorithms for solving equations,” in:Proceedings of the International Congress of Mathematicians (Berkeley, CA, 1986) pp. 172–195.
[34] 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).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.