×

A relaxation method for nonconvex quadratically constrained quadratic programs. (English) Zbl 0835.90060

Summary: We present an algorithm for finding approximate global solutions to quadratically constrained quadratic programming problems. The method is based on outer approximation (linearization) and branch-and-bound with linear programming subproblems. When the feasible set is non-convex, the infinite process can be terminated with an approximate (possibly infeasible) optimal solution. We provide error bounds that can be used to ensure stopping within a prespecified feasibility tolerance. A numerical example illustrates the procedure. Computational experiments with an implementation of the procedure are reported on bilinearly constrained test problems with up to sixteen decision variables and eight constraints.

MSC:

90C20 Quadratic programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Al-Khayyal, F. A. (1990), Jointly Constrained Bilinear Programs and Related Problems: An Overview,Computers and Mathematics with Applications 19, 53-62. · Zbl 0706.90074 · doi:10.1016/0898-1221(90)90148-D
[2] Al-Khayyal, F. A. (1992), Generalized Bilinear Programming, Part I: Models, Applications and Linear Programming Relaxation,European Journal of Operational Research 60, 306-314. · Zbl 0784.90051 · doi:10.1016/0377-2217(92)90082-K
[3] Al-Khayyal, F. A. and Falk, J. E. (1983), Jointly Constrained Biconvex Programming,Mathematics of Operations Research 8, 273-286. · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[4] Al-Khayyal, F. A. and Larsen, C. (1990), Global Optimization 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
[5] Al-Khayyal, F. A. and Pardalos, P. M. (1991), Global Optimization Algorithms for VLSI Compaction Problems,Arabian Journal for Science and Engineering 16, 335-339. · Zbl 0793.68081
[6] Baron, D. P. (1972), Quadratic Programming with Quadratic Constraints,Naval Research Logistics Quarterly 17, 253-260. · Zbl 0249.90057 · doi:10.1002/nav.3800190204
[7] Eben Chaime, M. (1990), The Physical Design of Printed Circuit Boards: A Mathematical Programming Approach, Ph.D. Dissertation, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia.
[8] Erenguc, S. S. and Benson, H. P. (1991), An Algorithm for Indefinite Integer Quadratic Programming,Computers & Mathematics with Applications 21, 99-106. · Zbl 0721.90056 · doi:10.1016/0898-1221(91)90164-Y
[9] Evans, D. H. (1963), Modular Design ? A Special Case in Nonlinear Programming,Operations Research 11, 637-647. · Zbl 0113.35801 · doi:10.1287/opre.11.4.637
[10] Filar, J. A. and Schultz, T. A. (1995), Bilinear Programming and Structured Stochastic Games,Journal of Optimization Theory and Applications (forthcoming). · Zbl 0593.90091
[11] Floudas, C. A. and Aggarwal, A. (1990), A Decomposition Strategy for Global Optimum Search in the Pooling Problem,ORSA Journal on Computing 2, 225-235. · Zbl 0755.90091
[12] Floudas, C. A. and Visweswaran, V. (1993), A Primal-Relaxed Dual Global Optimization Approach,Journal of Optimization Theory and Its Applications 78, 187-225. · Zbl 0796.90056 · doi:10.1007/BF00939667
[13] Foulds, L. R., Haughland, D., and Johnston, K. (1992), A Bilinear Approach to the Pooling Problem,Optimization 24, 165-180. · Zbl 0817.90073 · doi:10.1080/02331939208843786
[14] Goldberg, J. B. (1984), The Modular Design Problem with Linear Separable Side Constraints: Heuristics and Applications, Ph.D. Dissertation, Industrial and Operations Engineering Department, University of Michigan, Ann Arbor, Michigan.
[15] Hansen, P. (1979), Methods of Nonlinear 0-1 Programming,Annals of Discrete Mathematics 5, 53-70. · Zbl 0426.90063 · doi:10.1016/S0167-5060(08)70343-1
[16] Hansen, P. and Jaumard, B. (1992), Reduction of Indefinite Quadratic Programs to Bilinear Programs,Journal of Global Optimization 2, 41-60. · Zbl 0786.90050 · doi:10.1007/BF00121301
[17] Hao, E. P. (1982), Quadratically Constrained Quadratic Programming: Some Applications and a Method for Solution,ZOR 26, 105-119. · Zbl 0479.90065 · doi:10.1007/BF01917102
[18] Horst, R. (1986), A General Class of Branch and Bound Methods in Global Optimization with Some New Approaches to Concave Minimization,Journal of Optimization Theory and Applications 51, 271-291. · Zbl 0581.90073 · doi:10.1007/BF00939825
[19] Horst, R. and Tuy, H. (1993),Global Optimization: Deterministic Approaches, Second Edition, Springer-Verlag, Berlin. · Zbl 0704.90057
[20] Pardalos, P. M. and Rosen, J. B. (1987),Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science 268. Springer-Verlag, Berlin. · Zbl 0638.90064
[21] Press, W. H., Teukolsky, S. A., Vetterling, W. T., and Flannery, B. P. (1988),Numerical Recipes in C, Cambridge University Press, Cambridge. · Zbl 0661.65001
[22] Rutenberg, D. P. and Shaftel, T. L. (1971), Product Design: Sub-Assemblies for Multiple Markets,Management Science 18, B220-B231. · doi:10.1287/mnsc.18.4.B220
[23] Sherali, H. D. and Tuncbilek, C. H. (1992), A Global Optimization Algorithm for Polynomial Programming Problems Using a Reformulation-Linearization Technique,Journal of Global Optimization 2, 101-112. · Zbl 0787.90088 · doi:10.1007/BF00121304
[24] Shor, N. Z. (1990), Dual Quadratic Estimates in Polynomial and Boolean Programming,Annals of Operations Research 25, 163-168. · Zbl 0783.90081 · doi:10.1007/BF02283692
[25] Van de Panne, C. (1966), Programming with a Quadratic Constraint,Management Science 12, 748-815. · Zbl 0141.17504
[26] Visweswaran, V. and Floudas, C. A. (1993), New Properties and Computational Improvement of the GOP Algorithm for Problems with Quadratic Objective Functions and Constraints,Journal of Global Optimization 3, 439-462. · Zbl 0795.90070 · doi:10.1007/BF01096414
[27] Visweswaran, V. and Floudas, C. A. (1990), A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLP’s: II. Applications of Theory and Test Problems,Computers and Chemical Engineering 14, 1417-1434.
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.