Abstract
This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor ofε with\(O(\sqrt m \left| {ln \varepsilon } \right|)\) iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of\(O(\sqrt m \left| {ln \varepsilon } \right|)\) Newton iterations to guarantee an error reduction by a factor ofε in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D.A. Bayer and J.C. Lagarias, “The nonlinear geometry of linear programming,” Preprints, AT&T Bell Laboratories (Murray Hills, NJ, 1986).
M.B. Daya and C.M. Shetty, “Polynomial barrier function algorithm for linear programming,” Technical report J 88-4, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, GA, 1987).
M.B. Daya and C.M. Shetty, “Polynomial barrier function algorithm for convex quadratic programming,” Technical report J 88-5, School of Industrial and Systems Engineering, Georgia Institute of Technology (Atlanta, GA, 1988).
A.V. Fiacco and G.P. McCormick, “The sequential unconstrained minimization technique (SUMT) for nonlinear programming, a primal—dual method,”Management Science 10 (1964) 601–617.
R.M. Freund, “Projective transformations for interior point methods, Part I: Basic theory and linear programming,” Working paper OR 179-88, Massachusetts Institute of Technology (Boston, MA, 1988).
R.M. Freund, “Projective transformations for interior point methods, Part II: Analysis of an algorithm for finding the weighted center of a polyhedral system,” Working paper OR 180-88, Massachusetts Institute of Technology (Boston, MA, 1988).
K.R. Frisch, “The logarithmic potential method of convex programming,” Technical report, University Institute of Economics (Oslo, Norway, 1955).
J.L. Goffin, “Affine methods in nondifferentiable optimization,”CORE Discussion Paper No 8744 (Center of Operations Research & Econometrics, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 1987).
D. Goldfarb and S. Liu, “An O(n 3 L) primal interior point algorithm for convex quadratic programming,” Technical report, Dept. of IEOR, Columbia University (New York, NY, 1988).
C.C. Gonzaga, “An algorithm for solving linear programming problems in O(n 3 L) operations,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, Berlin, 1988) pp. 1–28.
P. Huard and B.T. Liêu, “La méthode des centres dans un espace topologique,” Numerische Mathematik 8 (1966) 56–67.
F. Jarre, “On the convergence of the method of analytic centers when applied to convex quadratic programs,” Report No. 35, Schwerpunktprogramm der DFG Anwendungsbezogene Optimierung und Steuerung, Institut für Angewandte Mathematik und Statistik, Universität Würzburg (1987).
F. Jarre, “On the method of analytic centers for solving smooth convex programs,” in: S. Dolecki, ed.,Optimization. Lecture Notes in Mathematics, No. 1405 (Springer, Berlin, 1989) pp. 69–85.
F. Jarre, G. Sonnevend, J. Stoer, “An implementation of the method of analytic centers,” in: A. Benoussan, J.L. Lions, eds.,Lecture Notes in Control and Information Sciences, No. 111 (Springer, Berlin, 1988) pp. 297–307.
N. Karmarkar, “A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395.
S. Kapoor and P.M. Vaidya, “Fast algorithms for convex quadratic programming and multicommodity flows,”Journal of the ACM (1986) 147–159.
M. Kojima, S. Mizuno and T. Noma, “A new continuation method for complementarity problems with uniformP-functions,”Mathematical Programming 43 (1989) 107–113.
G.P. McCormick, “Miscellaneous results concerning Karmarkar's projective method and SUMT,” Manuscript GWU/IMSE/Serial T-519/87, Institute for Management Science and Engineering, The George Washington University (1987).
N. Megiddo, “Pathways to the optimal set in linear programming,” in: N. Megiddo, ed.Progress in Mathematical Programming (Springer, Berlin, 1988) pp. 131–158.
S. Mehrotra and J. Sun, “An algorithm for convex quadratic programming that requires O(n 3.5 L) arithmetic operations,” Technical report 87-24, Dept. of IE/MS, Northwestern University (Evaston IL, 1987).
S. Mehrotra and J. Sun, “A method of analytic centers for quadratically constrained quadratic programs,” Technical report 88-01, Dept. of IE/MS, Northwestern University (Evanston, IL, 1988).
S. Mehrotra and J. Sun, “An interior point algorithm for solving smooth convex programs based on Newton's method,” Technical report 88-08, Dept of IE/MS, Northwestern University (Evanston, IL, 1988).
R.C. Monteiro and I. Adler, “An O(n 3) primal—dual interior point algorithm for linear programming,” Report ORC 87-4 Operations Research Center, Dept. of Operations Research, University of California (Berkeley, CA, 1987).
R.C. Monteiro and I. Adler, “An O(n 3) primal-dual interior point algorithm for convex quadratic programming,” Report ORC 87-15 Operations Research Center, Dept. of Operations Research, University of California (Berkeley, CA, 1987).
J.E. Nesterov and A.S. Nemirovsky, “A general approach to polynomial-time algorithms design for convex programming,” Report, Central Economical and Mathematical Institute, USSR Academy of Sciences (Moscow, USSR, 1988).
J. Renegar, “A polynomial-time algorithm based on Newton's method for linear programming,”Mathematical Programming 40 (1988) 59–93.
C. Roos and J.Ph. Vial, “A polynomial method of approximate centers for linear programming,” Report 88-68, Delft University of Technology (Delft, The Netherlands, 1988).
G. Sonnevend, “An analytical centre for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,”Lecture Notes in Control and Information Sciences, No.84 (1985) pp. 866–876.
G. Sonnevend and J. Stoer, “Global ellipsoidal approximations and homotopy methods for solving convex analytic programs,” to appear inApplied Mathematics and Optimization (1988).
P.M. Vaidya, “An algorithm for solving linear programming which requires O(((m+n)n 2+(m+n) 1.5 n)L) arithmetic operations,” preprint AT&T Bell Laboratories (Murray Hills, NJ, 1987).
C. Witzgall, P.T. Boggs and P.D. Domich, “On center trajectories and their relatives in linear programming,” Technical report, National Bureau of Standards (1988).
Y. Ye, “Further development on the interior algorithm for convex quadratic programming,” Manuscript, Dept. of Engineering-Economic Systems, Stanford University (Stanford, CA, 1987).
Y. Ye and M. Todd, “Containing and shrinking ellipsoids in the path — following algorithm,” Report, Dept. of Engineering-Economic Systems, Stanford University, and Dept. of OR and Industrial Engineering, Cornell University (Ithaca, NY, 1987).
Y. Ye and E. Tse, “A polynomial-time algorithm for convex quadratic programming,” Report, Dept. of Engineering-Economic Systems, Stanford University (Stanford, CA, 1986).
U. Zimmermann, “On recent developments in linear programming,” in:International Series of Numerical Mathematics, No. 84 (Birkhäuser Verlag, Basel, 1988).
Author information
Authors and Affiliations
Additional information
This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.
Rights and permissions
About this article
Cite this article
Jarre, F. On the convergence of the method of analytic centers when applied to convex quadratic programs. Mathematical Programming 49, 341–358 (1990). https://doi.org/10.1007/BF01588796
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01588796