zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Reduction of indefinite quadratic programs to bilinear programs. (English) Zbl 0786.90050
The authors consider the problem of reducing indefinite quadratic programs (Q) to bilinear programs (B) based on a duplication of variables. They propose optimal reduction methods for two criteria: (i) the number of additional variables and (ii) the number of complicating variables (i.e., the number of variables which yield, after fixation, an easy-to-solve problem). These two problems are shown to be equivalent to a maximum bipartite subgraph and a maximum stable set problem respectively in a graph associated with the quadratic program. Finally the reduction of more general global optimization problem than quadratic programs (as example, polynomial programs, hyperbolic programs, problems with variables having fractional exponents, trigonometric and transcendental functions) is discussed.

90C20Quadratic programming
90-08Computational methods (optimization)
Full Text: DOI
[1] Al-Khayyal, F. A. (1990), Generalized Bilinear Programming: Part I. Models, Applications, and Linear Programming Relaxation, Research Report, Georgia Institute of Technology. · Zbl 0784.90051
[2] Al-Khayyal, F. A. and J. E., Falk (1983), Jointly Constrained Biconvex Programming, Mathematics of Operations Research 8 (2), 273-286. · Zbl 0521.90087 · doi:10.1287/moor.8.2.273
[3] Al-Khayyal, F., R. Horst, and P. Pardalos (1991), Global Optimization of Concave Functions Subject to Separable Quadratic Constraints and of All-Quadratic Separable Problems, Annals of Operations Research.
[4] Avriel, M., W. E., Diernert, S., Schaible, and I., Zang (1988), Generalized Concavity, New York: Plenum Press. · Zbl 0679.90029
[5] Avriel, M. and A. C., Williams (1971), An Extension of Geometric Programming with Applications in Engineering Optimization, Journal of Engineering Mathematics 5 (3), 187-194. · doi:10.1007/BF01535411
[6] Balas, E. and C. S., Yu (1986), Finding a Maximum Clique in an Arbitrary Graph, SIAM Journal on Computing 15, 1054-1068. · Zbl 0604.05024 · doi:10.1137/0215075
[7] Baron, D. P. (1972), Quadratic Programming with Quadratic Constraints, Naval Research Logistics Quarterly 19, 253-260. · Zbl 0249.90057 · doi:10.1002/nav.3800190204
[8] Bartholomew-Biggs, M. C. (1976), A Numerical Comparison between Two Approaches to Nonlinear Programming Problems, Technical Report #77, Numerical Optimization Center, Hatfield, England. · Zbl 0395.90070
[9] Benacer, R. and T., Pham Dinh (1986), Global Maximization of a Nondefinite Quardatic Function over a Convex Polyhedron, pp. 65-76 in J.-B., Hirriart-Urruty (ed.), Fermat Days 1985: Mathematics for Optimization, Amsterdam: North-Holland. · Zbl 0626.90064
[10] Berge, C. (1983), Graphes, 3rd ed., Paris: Gauthier-Villars. · Zbl 0531.05031
[11] Berge, C. (1987), Hypergraphes, Paris, Gauthier-Villars.
[12] Bernard, J. C. and J. A., Ferland (1989), Convergence of Interval-Type Algorithms for Generalized Fractional Programming, Mathematical Programming 43, 349-363. · Zbl 0677.90074 · doi:10.1007/BF01582298
[13] Carraghan, R. and P. M., Pardalos (1990), An Exact Algorithm for the Maximum Clique Problem, Operations Research Letters 9, 375-382. · Zbl 0711.90080 · doi:10.1016/0167-6377(90)90057-C
[14] Colville, A. R. (1986), A Comparative Study on Nonlinear Programming Codes, IBM Scientific Center Report 320-2949, New York.
[15] Dembo, R. S. (1972), Solution of Complementary Geometric Programming Problems, M.Sc. Thesis, Technion, Haifa.
[16] Dembo, R. S. (1976), A Set of Geometric Programming Test Problems and Their Solutions, Mathematical Programming 10, 192-213. · Zbl 0349.90066 · doi:10.1007/BF01580667
[17] Duffin, R. J., E. L., Peterson, and C., Zener (1967), Geometric Programming: Theory and Applications, New York: Wiley. · Zbl 0171.17601
[18] Ecker, J. G. and R. D., Niemi (1975), A Dual Method for Quadratic Programs with Quadratic Constraints, SIAM Journal on Applied Mathematics 28, 568-576. · Zbl 0296.90035 · doi:10.1137/0128046
[19] 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
[20] Flippo, O. E. (1989), Stability, Duality and Decomposition in General Mathematical Programming, Rotterdam: Erasmus University Press. · Zbl 0742.90076
[21] Floudas, C. A., A., Aggarwal, and A. R., Ciric (1989), Global Optimum Search for Nonconvex NLP and MINLP Problems, Computers and Chemical Engineering 13 (10), 1117-1132. · doi:10.1016/0098-1354(89)87016-4
[22] Floudas, C. A. and P., Pardalos (1990), A Collection of Test Problems for Constrained Global Optimization, Lecture Notes in Computer Science, 455, Berlin: Springer-Verlag. · Zbl 0718.90054
[23] Floudas, C. A. and V., Visweswaran (1990), A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs?I. Theory, Computers and Chemical Engineering 14 (12), 1397-1417. · doi:10.1016/0098-1354(90)80020-C
[24] Friden, C., A., Hertz, and D.de, Werra (1990), Tabaris: An Exact Algorithm Based on Tabu Search for Finding a Maximum Independent Set in a Graph, Computers and Operations Research 17 (5), 437-445. · Zbl 0713.90087 · doi:10.1016/0305-0548(90)90048-C
[25] Garey, M. R., D. S., Johnson, and L., Stockmeyer (1976), Some Simplified NP-Complete Graph Problems, Theoretical Computer Science 1, 237-267. · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[26] Geoffrion, A. M. (1972), Generalized Benders Decomposition, Journal of Optimization Theory and Its Applications 10, 237-260. · Zbl 0229.90024 · doi:10.1007/BF00934810
[27] Gochet, W. and Y., Smeers (1979), A Branch and Bound Method for Reversed Geometric Programming, Operations Research 27, 982-996. · Zbl 0427.90077 · doi:10.1287/opre.27.5.982
[28] Hock, W. and K., Schittkowski (1981), Test Examples for Nonlinear Programming Codes, Lecture Notes in Economics and Mathematical Systems #187, Berlin: Springer-Verlag. · Zbl 0452.90038
[29] Horst, R. and H., Tuy (1990), Global Optimization, Deterministic Approaches, Berlin: Springer-Verlag. · Zbl 0704.90057
[30] Konno, H. (1976), Maximizing a Convex Quadratic Function Subject to Linear Constraints Mathematical Programming 11, 117-127. · Zbl 0355.90052 · doi:10.1007/BF01580380
[31] Konno, H. and T. Kuno (1989), Linear Multiplicative Programming, Preprint IHSS 89-13, Tokyo Institute of Technology. · Zbl 0761.90080
[32] Kough, P. F. (1979), The Indefinite Quadratic Programming Problem, Operations Research 27, 516-533. · Zbl 0409.90070 · doi:10.1287/opre.27.3.516
[33] Mladineo, R. H. (1986), An Algorithm for Finding the Global Maximum of a Multimodal, Multivariate Function, Mathematical Programming 34, 188-200. · Zbl 0598.90075 · doi:10.1007/BF01580583
[34] 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
[35] Pardalos, P. M. and J. B., Rosen (1986), Methods for Global Concave Minimization: A Bibliographic Survey, SIAM Review 28 (3), 367-379. · Zbl 0602.90105 · doi:10.1137/1028106
[36] Pardalos, P. M. and J. B., Rosen (1987), Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science #268, Berlin: Springer Verlag. · Zbl 0638.90064
[37] Pham Dinh, T. and S.El, Bernoussi (1989), Numerical Methods for Solving a Class of Global Nonconvex Optimization Problems, International Series of Numerical Mathematics 87, 97-132. · Zbl 0683.90077
[38] Phan, H. (1982), Quadratically Constrained Quadratic Programming: Some Applications and a Method of Solution, Zeitschrift für Operations Research 26, 105-119. · Zbl 0479.90065 · doi:10.1007/BF01917102
[39] Phillips, A. T. and J. B., Rosen, (1990), Guaranteed ?-Approximate Solution to Indefinite Global Optimization, 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
[40] Ragavachari, M. (1989), On Connections between Zero-One Integer Programming and Concave Programming under Linear Constraints, Operations Research 17, 680-684. · Zbl 0176.49805 · doi:10.1287/opre.17.4.680
[41] Reeves, G. R. (1975), Global Minimization in Nonconvex All-Quadratic Programming, Management Science 22, 76-86. · Zbl 0315.90059 · doi:10.1287/mnsc.22.1.76
[42] Sherali, H. and A. Alameddine (1990), A New Reformulation-Linearization Technique for Bilinear Programming Problems, Research Report, Department of Industrial and Systems Engineering, Virginia Polytechnic Institute. · Zbl 0791.90056
[43] Stephanopoulos, G. and A. W., Westerberg (1975), The Use of Hestenes’ Method of Multipliers to Resolve Dual Gaps in Engineering System Optimization, Journal of Optimization Theory and Applications 15, 285-309. · Zbl 0278.49040 · doi:10.1007/BF00933339
[44] Simões, L. M. C. (1987), Search for the Global Optimum of Least Volume Trusses, Engineering Optimization 11, 49-67. · doi:10.1080/03052158708941036
[45] Thoai, N. V. (1990), Application of Decomposition Techniques in Global Optimization to the Convex Multiplicative Programming Problem, Paper presented at the Second Workshop on Global Optimization, Sopron, Hungary.
[46] Tuy, H. (1986), A General Deterministic Approach to Global Optimization via d.-c. Programming, pp. 137-162, in J. B., Hirriart-Urruty (ed.), Fermat Days 1985: Mathematics for Optimization, Amsterdam: North-Holland.
[47] Visweswaran, V. and C. A., Floudas (1990), A Global Optimization Algorithm (GOP) for Certain Classes of Nonconvex NLPs?II. Application of Theory and Test Problems, Computers and Chemical Engineering 14 (12), 1419-1434. · doi:10.1016/0098-1354(90)80021-3
[48] Wolsey, L. A. (1981), A Resource Decomposition Algorithm for General Mathematical Programs, Mathematical Programming Study 14, 244-257. · Zbl 0449.90085