×

A reformulation-convexification approach for solving nonconvex quadratic programming problems. (English) Zbl 0844.90064

Summary: We consider the class of linearly constrained nonconvex quadratic programming problems, and present a new approach based on a novel Reformulation-Linearization/Convexification Technique. In this approach, a tight linear (or convex) programming relaxation, or outer-approximation to the convex envelope of the objective function over the constrained region, is constructed for the problem by generating new constraints through the process of employing suitable products of constraints and using variable redefinitions. Various such relaxations are considered and analyzed, including ones that retain some useful nonlinear relationships. Efficient solution techniques are then explored for solving these relaxations in order to derive lower and upper bounds on the problem, and appropriate branching/partitioning strategies are used in concert with these bounding techniques to derive a convergent algorithm. Computational results are presented on a set of test problems from the literature to demonstrate the efficiency of the approach. (One of these test problems had not previously been solved to optimality.) It is shown that for many problems, the initial relaxation itself produces an optimal solution.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization

Software:

MINOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Khayyal, F. A. and J. E. Falk (1983), Jointly Constrained Biconvex Programming,Math, of Oper. Res. 8, 273-286. · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[2] Al-Khayyal, F. A. and C. Larson (1990), Global Minimization of a Quadratic Function Subject to a Bounded Mixed Integer Constraint Set,Annals of Operations Research 25, 169-180. · Zbl 0719.90050 · doi:10.1007/BF02283693
[3] Balas, E. (1975), Nonconvex Quadratic Programming via Generalized Polars,SIAM Journal on Applied Math. 28, 335-349. · Zbl 0294.90066 · doi:10.1137/0128029
[4] Benacer, R. and PhamDinh, Tao (1986), Global Maximization of a Nondefinite Quadratic Function over a Convex Polyhedron, pp. 65-76, inFermat Days 85: Mathematics for Optimization, J. B. Hiriart-Urruty (ed.), North-Holland, Amsterdam. · Zbl 0626.90064
[5] Bomze, I. M. (1992), Copositivity Conditions for Global Optimality Indefinite Quadratic Programming Problems,Czechoslovak Journal for Operations Research 1, 1-19. · Zbl 0972.90051
[6] Fisher, M. L. (1981), The Lagrangian Relaxation Methods for Solving Integer Programming Problems,Management Science 27, 1-18. · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[7] Floudas, C. A. and P. M. Parsalos (1990),A Collection of Test Problems for Constrained Global Optimization Algorithms, Springer-Verlag, Berlin.
[8] Floudas, C. A. and V. Visweswaran (1990), A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLP’s-1. Theory,Computers and Chemical Engineering 14, 1419. · doi:10.1016/0098-1354(90)80020-C
[9] Floudas, C. A. and V. Visweswaran (1993), A Primal-Relaxed Dual Global Optimization Approach: Theory,JOTA 78, 187-225. · Zbl 0796.90056 · doi:10.1007/BF00939667
[10] Golub, G. H. and C. F. Van Loan (1989),Matrix Computations, Second Edition, The Johns Hopkins University Press, Baltimore. · Zbl 0733.65016
[11] Guignard, M. and S. Kim (1987), Lagrangian Decomposition: A Model Yielding Stronger Lagrangian Bounds,Mathematical Programming 39, 215-228. · Zbl 0638.90074 · doi:10.1007/BF02592954
[12] Hansen, P., B. Jaumard, and S. Lu (1991), An Analytical Approach to Global Optimization,Math. Programming 52, 227-254. · Zbl 0747.90091 · doi:10.1007/BF01582889
[13] Kough, P. F., The Indefinite Quadratic Programming Problem,Operations Research 27(3), 516-533. · Zbl 0409.90070
[14] Larsson, T. and Z. Liu (1989), A Primal Convergence Result for Dual Subgradient Optimization with Applications to Multicommunity Network Flows, Research Report, Department of Mathematics, Linkoping Institute of Technology, S-581 83, Linkoping, Sweden.
[15] Manas, M. (1968), An Algorithm for a Nonconvex Programming Problem,Econ Math Obzor Acad. Nad. Ceskoslov 4(2), 202-212.
[16] Meyer, G. G. (1988), Convergence of Relaxation Algorithms by Averaging,Mathematical Programming 40, 205-212. · Zbl 0648.90069 · doi:10.1007/BF01580731
[17] Mueller, R. K. (1970), A Method for Solving the Indefinite Quadratic Programming Problem,Management Science 16(5), 333-339. · Zbl 0191.48605 · doi:10.1287/mnsc.16.5.333
[18] Murtagh, B. A. and M. A. Saunders (1987), MINOS 5.1 User’s Guide, Technical Report Sol 83-20R, Systems Optimization Laboratory, Department of Operations Research, Stanford University, Stanford, California.
[19] Muu, L. D. and W. Oettli (1991), An Algorithm for Indefinite Quadratic Programming with Convex Constraints,Operations Research Letters 10, 323-327. · Zbl 0748.90049 · doi:10.1016/0167-6377(91)90004-9
[20] Pardalos, P. M. (1991), Global Optimization Algorithms for Linearly Constrained Indefinite Quadratic Programs,Computers Math. Applic. 21, 87-97. · Zbl 0733.90051 · doi:10.1016/0898-1221(91)90163-X
[21] Pardalos, P. M., J. H. Glick, and J. B., Rosen (1987), Global Minimization of Indefinite Quadratic Problems,Computing 39, 281-291. · Zbl 0627.65072 · doi:10.1007/BF02239972
[22] Pardalos, P. M. and J. B. Rosen (1987),Constrained Global Optimization: Algorithms and Applications, Springer-Verlag, Berlin. · Zbl 0638.90064
[23] Pardalos, P. M. and S. A. Vavasis (1991), Quadratic Programming with One Negative Eigenvalue Is NP-Hard,Journal of Global Optimization 1, 15-22. · Zbl 0755.90065 · doi:10.1007/BF00120662
[24] Phillips, A. T. and J. B. Rosen (1990), Guaranteed?-Approximate Solution for Indefinite Quadratic Global Minimization,Naval Research Logistics 37, 499-514. · Zbl 0708.90063 · doi:10.1002/1520-6750(199008)37:4<499::AID-NAV3220370405>3.0.CO;2-9
[25] Ritter, K. (1966), A Method for Solving Maximum Problems with a Nonconcave Quadratic Objective Function,Z. Wahrscheinlichkeitstheorie,4, 340-351. · Zbl 0139.13105 · doi:10.1007/BF00539118
[26] Sherali, H. D. and A. R. Alameddine (1992), A New Reformulation-Linearization Technique for Bilinear Programming Problems,Journal of Global Optimization 2(3), 379-410. · Zbl 0791.90056 · doi:10.1007/BF00122429
[27] Sherali, H. D. and D. C. Myers (1985/6), The Design of Branch and Bound Algorithms for a Class of Nonlinear Integer Programs,Annals of Oper. Res. 5, 463-484.
[28] Sherali, H. D. and C. H. Tuncbilek (1992), A Global Optimization Algorithm for Polynomial Programming Problems Using a Reformulation-Linearization Technique,The Journal of Global Optimization 2, 101-112. · Zbl 0787.90088 · doi:10.1007/BF00121304
[29] Sherali, H. D. and O. Ulular (1989), A Primal-Dual Conjugate Subgradient Algorithm for Specially Structured Linear and Convex Programming Problems,Appl. Math. Optim. 20, 193-221. · Zbl 0675.90069 · doi:10.1007/BF01447654
[30] Tuncbilek, C. H. (1994),Polynomial and Indefinite Quadratic Programming Problems: Algorithms and Applications, PhD Dissertation, Industrial and Systems Engineering, Virginia Polytechnic Institute and State University.
[31] Tuy, H. (1987), Global Minimization of a Difference of Two Convex Functions,Mathematical Programming Study 30, 150-182. · Zbl 0619.90061
[32] Vavasis, S. A. (1992), Approximation Algorithms for Indefinite Quadratic Programming,Mathematical Programming 57, 279-311. · Zbl 0845.90095 · doi:10.1007/BF01581085
[33] Visweswaran, V. and C. A. Floudas, (1993), New Properties and Computational Improvement of the GOP Algorithm for Problems with Quadratic Objective Function and Constraints,Journal of Global Optimization 3, 439-462. · Zbl 0795.90070 · doi:10.1007/BF01096414
[34] Zwart, P. B. (1973), Nonlinear Programming: Counterexamples to Two Global Optimization Algorithms,Operations Research 21(6), 1260-1266. · Zbl 0274.90049 · doi:10.1287/opre.21.6.1260
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.