×

zbMATH — the first resource for mathematics

An extension of Karmarkar’s projective algorithm for convex quadratic programming. (English) Zbl 0674.90077
The paper uses Karmarkar’s polynomial-time LP algorithm as a base on which to develop a polynomial-time algorithm for convex quadratic programs. Using the interior ellipsoid method, the following sub- optimization problem is solved: \[ \min f(\hat x)=\hat x[n]^ T\hat Q\hat x[n]/2\hat x_{n+1}-\hat c\hat x[n] \] subject to: \(\hat A\hat x=\hat b\), \(\| \hat x-e\| \leq \beta <1\), where \[ \hat Q=DQD\quad (D=diag(x^ k)),\quad \hat c=cD,\quad \hat A=\left( \begin{matrix} AD-b\\ e^ T\end{matrix} \right),\quad \hat b=\left( \begin{matrix} 0\\ n+1\end{matrix} \right),\quad and \] \^x[n] is the vector of the first n components of \(\hat x\in R^{n+1}\). The authors show that this problem can be solved in \(O(Ln^ 3)\) operations and that \(O(Ln)\) iterates are required. While no computational results are presented, the authors claim an efficient implementation is possible and cite a Ph.D. thesis as a source of some such testing.
Reviewer: J.J.Dinkel

MSC:
90C25 Convex programming
90C20 Quadratic programming
68Q25 Analysis of algorithms and problem complexity
90C05 Linear programming
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. M. Anstreicher, ”A monotonic projective algorithm for fractional linear programming,”Algorith-mica 1 (1986) 483–498. · Zbl 0625.90088
[2] E.R. Barnes, ”A variation on Karmarkar’s algorithm for solving linear programming,”Mathematical Programming 36 (1986) 174–182. · Zbl 0626.90052
[3] E.M.L. Beale, ”On quadratic programming,”Naval Research Logistics Quarterly 6 (1959) 227–243.
[4] A.R. Conn and J. W. Sinclair, ”Quadratic programming via a non-differentiable penalty function,” Report 75/15, Department of Combinatorics and Optimization, University of Waterloo (Waterloo, Canada, 1975).
[5] R.W. Cottle and G.B. Dantzig, ”Complementary pivot theory of mathematical programming,”Linear Algebra and Its Applications 1 (1968) 103–125. · Zbl 0155.28403
[6] G.B. Dantzig,Linear Programming and Extensions (Princeton University Press, Princeton, 1963).
[7] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematics Doklady 8 (1967) 674–675. · Zbl 0189.19504
[8] B.C. Eaves, ”On the basic theorem of complementarity,”Mathematical Programming 1 (1971) 68–75. · Zbl 0227.90044
[9] P.E. Gill and W. Murray, ”Newton type methods for unconstrained and linearly constrained optimization,”Mathematical Programming 7 (1974) 311–350. · Zbl 0297.90082
[10] M. Grötschel, L. Lovász and A. Schrijver, ”The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197. · Zbl 0492.90056
[11] C. Hildreth, ”A quadratic programming procedure,”Naval Research Logistics Quarterly 4 (1957) 79–85.
[12] 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.
[13] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[14] L.G. Khachiyan, ”A polynomial algorithm for linear programming,”Soviet Mathematics Doklady 20 (1979) 191–194. · Zbl 0414.90086
[15] K.O. Kortanek and M. Shi, ”Convergence results and numerical experiments on a linear programming hybrid algorithm,” to appear in the EuropeanJournal of Operational Research, Dept. of Mathematics, Carnegie Mellon University (PA, 1985).
[16] M.K. Kozlov, S.P. Tarasov and L.G. Khachiyan, ”Polynomial solvability of convex quadratic programming,”Soviet Mathematics Doklady 20 (1979) 1108–1111. · Zbl 0434.90071
[17] C.E. Lemke, ”Bimatrix equilibrium points and mathematical programming,”Management Science 11 (1965) 681–689. · Zbl 0139.13103
[18] D.G. Luenberger,Linear and Nonlinear Programming (2nd Edition, Addison-Wesley, Menlo Park, 1984). · Zbl 0571.90051
[19] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, 1982). · Zbl 0503.90060
[20] J. Rosen, ”The gradient projection method for nonlinear programming, I. Linear constraints,”SIAM Journal on Applied Mathematics 12 (1964) 74–92. · Zbl 0156.16205
[21] D.C. Sorensen, ”Trust region methods for unconstrained minimization,” in: M.J.D. Powell, ed.,Nonlinear Optimization (Academic Press, New York, 1981). · Zbl 0571.90081
[22] M.J. Todd and B.P. Burrell, ”An extension of Karmarkar’s algorithm for linear programming using dual variables,”Algorithmica 1 (1986) 409–424. · Zbl 0621.90048
[23] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”On a modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056
[24] P. Wolfe, ”The simplex algorithm for quadratic programming,”Econometrica 27 (1959) 382–398. · Zbl 0103.37603
[25] Y. Ye and M. Kojima, ”Recovering optimal dual solutions in Karmarkar’s algorithm for linear programming,”Mathematical Programming 39 (1987) 305–317. · Zbl 0639.90062
[26] Y. Ye, ”Interior algorithms for linear, quadratic, and linearly constrained convex programming,” Ph.D. Thesis, Dept. of Engineering-Economic Systems, Stanford University (CA, 1987).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.