×

An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming. (English) Zbl 0717.90055

Summary: We present a primal interior point method for convex quadratic programming which is based upon a logarithmic barrier function approach. This approach generates a sequence of problems, each of which is approximately solved by taking a single Newton step. It is shown that the method requires O(\(\sqrt{n}L)\) iterations and \(O(n^{3.5}L)\) arithmetic operations. By using modified Newton steps the number of arithmetic operations required by the algorithm can be reduced to \(O(n^ 3L)\).

MSC:

90C25 Convex programming
90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C60 Abstract computational complexity for mathematical programming problems
49M15 Newton-type methods
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming problems,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052 · doi:10.1007/BF02592024
[2] D.A. Bayer and J.C. Lagarias, ”The nonlinear geometry of linear programming,” Preprints, AT&T Bell Laboratories (Murray Hill, NJ, 1986). · Zbl 0671.90045
[3] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[4] A.V. Fiacco and G.P. McCormick,Nonlinear programming: Sequential unconstrained minimization techniques (John Wiley and Sons, New York, 1968). · Zbl 0193.18805
[5] K.R. Frisch, ”The logarithmic potential method of convex programming,” Unpublished manuscript, University Institute of Economics (Oslo, Norway, 1955).
[6] P.E. Gill, G.H. Golub, W. Murray and M.A. Saunders, ”Methods for modifying matrix factorizations,”Mathematics of Computation 28 (1974) 505–535. · Zbl 0289.65021 · doi:10.1090/S0025-5718-1974-0343558-6
[7] P.E. Gill, W. 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
[8] D. Goldfarb, ”Matrix factorizations in optimization of nonlinear functions subject to linear constraints,”Mathematical Programming 10 (1975) 1–31. · Zbl 0374.90060 · doi:10.1007/BF01580651
[9] D. Goldfarb and A. Idnani, ”A numerically stable dual method for solving strictly convex quadratic programs,”Mathematical Programming 27 (1983) 1–33. · Zbl 0537.90081 · doi:10.1007/BF02591962
[10] 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
[11] A.S. Householder,The Theory of Matrices in Numerical Analysis (Bleisdel, Waltham, MA, 1964). · Zbl 0161.12101
[12] P. Huard, ”Resolution of mathematical programming with nonlinear constraints by the method of centres,” in: J. Abadic, ed.,Nonlinear Programming (North-Holland, Amsterdam, 1967). · Zbl 0157.49701
[13] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[14] S. Kapoor and P. Vaidya, ”Fast algorithms for convex quadratic programming and multicommodity flows,”Proceedings of the 18th Annual ACM Symposium on the Theory of Computing (1986) 147–159.
[15] M. Kojima, S. Mizuno and A. Yoshise, ”A primal-dual interior point algorithm for linear programming,” in: N. Meggido, ed.,Progress in Mathematical Programming (Springer, Berlin) pp. 29–97. · Zbl 0708.90049
[16] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087 · doi:10.1007/BF01587074
[17] M.K. Kozlov, S.P. Tarasov and L.G. Khachiyan, ”Polynomial solvability of convex quadratic programming,”Doklady Akademiia Nauk SSSR 248 (1979). [Translated inSoviet Mathematics Doklady 20 (1979) 1108–1111.] · Zbl 0434.90071
[18] N. Meggido, ”Pathways to the optimal set in linear programming,” in: N. Meggaddo, ed.,Progress in Mathematical Programming (Springer, Berlin, 1988) pp. 131–158.
[19] S. Mehrotra and J. Sun, ”An algorithm for convex quadratic programming that requires O(n 3.5 L) arithmetic operations,”Mathematics of Operations Research 15 (1990) 342–363. · Zbl 0714.90075 · doi:10.1287/moor.15.2.342
[20] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part I: Linear programming,”Mathematical Programming 44 (1989) 27–41. · Zbl 0676.90038 · doi:10.1007/BF01587075
[21] R.D.C. Monteiro and I. Adler, ”Interior path following primal–dual algorithms. Part II: Convex quadratic programming,”Mathematical Programming 44 (1989) 43–66. · Zbl 0676.90039 · doi:10.1007/BF01587076
[22] 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
[23] N.Z. Shor, ”Utilization of the operation of space dilatation in the minimization of convex functions,”Kibernetika 6, 6–12. [Translated inCybernetics 13 (1970) 94–96.] · Zbl 0243.90037
[24] P.M. Vaidya, ”An algorithm for linear programming which requires O(((m+n)n 2+(m+n) 1.5 n)L) arithmetic operations,”Mathematical Programming 47 (1990) 175–201. · Zbl 0708.90047 · doi:10.1007/BF01580859
[25] Y. Ye, ”Interior algorithms for linear quadratic and linearly constrained convex programming,” Ph.D. Dissertation, Dept. of Engineering-Economic Systems, Stanford University (Stanford, CA, 1987).
[26] Y. Ye, ”Further development on the interior algorithm for convex quadratic programming,” Manuscript, Dept. of Engineering-Economic Systems, Stanford University (Stanford, CA, 1987).
[27] Y. Ye and M. Kojima, ”Recovering optimal dual solutions in Karmarkar’s polynomial algorithm for linear programming,”Mathematical Programming 39 (1985) 305–318. · Zbl 0639.90062
[28] Y. Ye and E. Tse, ”An extension of Karmarkar’s projective algorithm for convex quadratic programming,”Mathematical Programming 44 (1989) 157–179. · Zbl 0674.90077 · doi:10.1007/BF01587086
[29] D.B. Yudin and A.S. Nemirovski, ”Informational complexity and effective methods of solution for convex extremal problems,”Ekonomika i Matematicheskie Metody 12 (1976) 357–369. [Translated inMatekon: Translations of Russian and East European Math. Economics, 13 (Spring 1977) 25–45.] · Zbl 0329.90054
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.