Algorithms for the solution of quadratic knapsack problems. (English) Zbl 0729.65047
Let Q be an \(n\times n\) real matrix and let e denote the n-vector of ones. The authors present and analyze three algorithms for minimizing the quadratic form (x,Qx) subject to \((e,x)=1\), \(x\geq 0.\)
The first algorithm is an extension of the potential reduction algorithm for linear complementarity problems developed recently by M. Kojima, S. Mizuno, and A. Yoshise [An O(\(\sqrt{n}L)\) iteration potential reduction algorithm for linear complementary problems. Math. Program., Ser. A, No.3, 331-342 (1991)] to the problems with arbitrary positive semidefinite matrices Q.
The second algorithm deals with the problem of computing a stationary point for the indefinite case and the knapsack constraint of the form \((e,x)=n\), \(x\geq 0\). The algorithm is a variation of the affine scaling method and interior trust region method.
The third algorithm is based on simplicial partitioning and convex underestimating functions. It is guaranteed to converge to the global minimum of indefinite problems.
For the first two algorithms, computational results on a variety of test problems are presented.
The first algorithm is an extension of the potential reduction algorithm for linear complementarity problems developed recently by M. Kojima, S. Mizuno, and A. Yoshise [An O(\(\sqrt{n}L)\) iteration potential reduction algorithm for linear complementary problems. Math. Program., Ser. A, No.3, 331-342 (1991)] to the problems with arbitrary positive semidefinite matrices Q.
The second algorithm deals with the problem of computing a stationary point for the indefinite case and the knapsack constraint of the form \((e,x)=n\), \(x\geq 0\). The algorithm is a variation of the affine scaling method and interior trust region method.
The third algorithm is based on simplicial partitioning and convex underestimating functions. It is guaranteed to converge to the global minimum of indefinite problems.
For the first two algorithms, computational results on a variety of test problems are presented.
Reviewer: M.Vlach (Praha)
Keywords:
quadratic programming; convergence; potential reduction algorithm; linear complementarity problems; knapsack constraint; affine scaling method; interior trust region method; simplicial partitioning; convex underestimating functions; computational results; test problemsSoftware:
GQTPARReferences:
| [1] | Ben Daya, M.; Shetty, C. M., Polynomial Barrier Function Algorithms for Convex Quadratic Programming, (Report J 88-5 (1988), School of ISE, Georgia Inst. of Technology: School of ISE, Georgia Inst. of Technology Atlanta) · Zbl 0723.90061 |
| [2] | Brucker, P., An \(O(n)\) algorithm for quadratic knapsack problems, Oper. Res. Lett., 3, 163-166 (1984) · Zbl 0544.90086 |
| [3] | Calamai, P. H.; Moré, J. J., Quasi-Newton updates with bounds, SIAM J. Numer. Anal., 24, 1434-1441 (1987) · Zbl 0644.65033 |
| [4] | Dorn, W. S., Duality in quadratic programming, Quart. Appl. Math., 18, 155-162 (1960) · Zbl 0101.37003 |
| [5] | Dussault, J.; Ferland, J. A.; Lemaire, B., Convex quadratic programming with one constraint and bounded variables, Math. Programming, 36, 90-104 (1986) · Zbl 0633.90057 |
| [6] | Eaves, B. C.; Freund, R. M., Optimal scaling of balls and polyhedra, Math. Programming, 23, 138-147 (1982) · Zbl 0479.90064 |
| [7] | Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman San Francisco · Zbl 0411.68039 |
| [8] | D. Goldfarb and S. Liu, An \(On^3L Math. Programming \); D. Goldfarb and S. Liu, An \(On^3L Math. Programming \) · Zbl 0717.90055 |
| [9] | Golub, G. H.; Van Loan, C. F., Matrix Computations (1989), John Hopkins U.P: John Hopkins U.P Baltimore · Zbl 0733.65016 |
| [10] | Horst, R., An Algorithm for nonconvex programming problems, Math. Programming, 10, 312-321 (1976) · Zbl 0337.90062 |
| [11] | Kapoor, S.; Vaidya, P., Fast algorithms for convex quadratic programming and multicommodity flows, Proceedings of the 18th Annual ACM Symposium on the Theory of Computation, 147-159 (1986) |
| [12] | Karmarkar, N., A new polynomial-time algorithm for linear programming, Combinatorica, 4, 373-395 (1984) · Zbl 0557.90065 |
| [13] | Kojima, M.; Mizuno, S.; Yoshise, A., An \(O(nL)\) Iteration Potential Reduction Algorithm for Linear Complementarity Problems, (Research Report (1988), Dept. of Information Science, Tokyo Inst. of Technology: Dept. of Information Science, Tokyo Inst. of Technology Tokyo) · Zbl 0738.90077 |
| [14] | Kojima, M.; Mizuno, S.; Yoshise, A., A polynomial-time algorithm for a class of linear complementarity problems, Math. Programming, 44, 1-26 (1989) · Zbl 0676.90087 |
| [15] | Kozlov, M. K.; Tarasov, S. P.; Khachiyan, L. G., Polynomial solvability of convex quadratic programming, Soviet Math. Doklady, 20, 1108-1111 (1979) · Zbl 0434.90071 |
| [16] | S. Mehrota and J. Sun, An algorithm for convex quadratic programming that requires \(On^{3.5}L\)Math. Oper. Res.; S. Mehrota and J. Sun, An algorithm for convex quadratic programming that requires \(On^{3.5}L\)Math. Oper. Res. |
| [17] | Monteiro, R. C.; Adler, I., Interior path following primal-dual algorithms, part I: Linear programming, Math. Programming, 44, 27-41 (1989) · Zbl 0676.90038 |
| [18] | Moré, J. J.; Sorensen, D. C., Computing a trust region step, SIAM J. Sci. Statist. Comput., 4, 553-572 (1983) · Zbl 0551.65042 |
| [19] | J. J. Moré and S. A. Vavasis, On the solution of concave knapsack problems, Math. Programming; J. J. Moré and S. A. Vavasis, On the solution of concave knapsack problems, Math. Programming |
| [20] | Motzkin, T. S.; Straus, E. G., Maxima for graphs and a new proof of a theorem of Turan, Canad. J. Math., 17, 533-540 (1965) · Zbl 0129.39902 |
| [21] | Pardalos, P. M., Quadratic problems defined on a convex hull of points, BIT, 28, 323-328 (1988) · Zbl 0644.65036 |
| [22] | Pardalos, P. M.; Kovoor, N., An Algorithm for singly constrained quadratic problems, Math. Programming, 46, 321-328 (1990) · Zbl 0711.90061 |
| [23] | Pardalos, P. M.; Rosen, J. B., Methods of global concave minimization: A bibliographic survey, SIAM Rev., 28, 367-379 (1986) · Zbl 0602.90105 |
| [24] | Pardalos, P. M.; Rosen, J. B., Constrained Global Optimization: Algorithms and Applications, (Lecture Notes in Comput. Sci., 268 (1987), Springer-Verlag) · Zbl 0638.90064 |
| [25] | Pardalos, P. M.; Schnitger, G., Checking local optimality in constrained quadratic programming is NP-hard, Oper. Res. Lett., 7, 33-35 (1988) · Zbl 0644.90067 |
| [26] | Sorensen, D. C., Newton’s method with a model trust region modification, SIAM J. Numer. Anal., 19, 409-426 (1982) · Zbl 0483.65039 |
| [27] | M. J. Todd and Y. Ye, A centered projective algorithm for linear programming, Math. Oper. Res.; M. J. Todd and Y. Ye, A centered projective algorithm for linear programming, Math. Oper. Res. · Zbl 0722.90044 |
| [28] | Vavasis, S. A., Local Minima for Indefinite Quadratic Knapsack Problems, (Technical Paper (1989), Dept. of Computer Science, Cornell Univ: Dept. of Computer Science, Cornell Univ Ithaca, N.Y) · Zbl 0751.90058 |
| [29] | Wolfe, P., Algorithm for a least-distance programming problem, Math. Programming Study, 1, 190-205 (1974) · Zbl 0359.90062 |
| [30] | Y. Ye, An \(On^3L Math. Programming \); Y. Ye, An \(On^3L Math. Programming \) |
| [31] | Ye, Y., On the Interior Algorithm for Nonconvex Quadratic Programming (1988), Dept. of Management Sciences. Univ. of Iowa: Dept. of Management Sciences. Univ. of Iowa Iowa City, Manuscript |
| [32] | Ye, Y., Interior Algorithms for Linear, Quadratic, and Linearly Constrained Convex Programming, (Ph.D. Thesis (1987), Dept. of Engineering-Economic Systems, Stanford Univ: Dept. of Engineering-Economic Systems, Stanford Univ Stanford, Calif) |
| [33] | Ye, Y.; Tse, E., An extension of Karmarkar’s projective algorithm for convex quadratic programming, Math. Programming, 44, 157-179 (1989) · Zbl 0674.90077 |
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.
