# zbMATH — the first resource for mathematics

##### Examples
 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.

##### Operators
 a & b logic and a | b logic or !ab logic not abc* right wildcard "ab c" phrase (ab c) parentheses
##### Fields
 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)
Primal-relaxed dual global optimization approach. (English) Zbl 0796.90056
Summary: A deterministic global optimization approach is proposed for nonconvex constrained nonlinear programming problems. Partitioning of the variables, along with the introduction of transformation variables, if necessary, converts the original problem into primal and relaxed dual subproblems that provide valid upper and lower bounds respectively on the global optimum. Theoretical properties are presented which allow for a rigorous solution of the relaxed dual problem. Proofs of $\varepsilon$- finite convergence and $\varepsilon$-global optimality are provided. The approach is shown to be particularly suited to (a) quadratic programming problems, (b) quadratically constrained problems, and (c) unconstrained and constrained optimization of polynomial and rational polynomial functions. The theoretical approach is illustrated through a few example problems. Finally, some further developments in the approach are briefly discussed.

##### MSC:
 90C30 Nonlinear programming 90C26 Nonconvex programming, global optimization
Full Text:
##### References:
 [1] Dixon, L. C. W., andSzego, G. P., Editors,Toward Global Optimization, North-Holland, Amsterdam, Holland, 1975. [2] Dixon, L. C. W., andSzego, G. P., Editors,Toward Global Optimization 2, North-Holland, Amsterdam, Holland, 1978. [3] Archetti, F., andSchoen, F.,A Survey on the Global Minimization Problem: General Theory and Computational Approaches, Annals of Operations Research, Vol. 1, pp. 87-110, 1984. · doi:10.1007/BF01876141 [4] Pardalos, P. M., andRosen, J. B.,Methods for Global Concave Minimization: A Bibliographic Survey, SIAM Review, Vol. 28, pp. 367-379, 1986. · Zbl 0602.90105 · doi:10.1137/1028106 [5] Pardalos, P. M., andRosen, J. B.,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, Vol. 268, 1987. · Zbl 0638.90064 [6] Törn, A., andZilinskas, A.,Global Optimization, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, Vol. 350, 1989. [7] Ratschek, H., andRokne, J.,New Computer Methods for Global Optimization, Halsted Press, Chichester, Great Britain, 1988. · Zbl 0648.65049 [8] Mockus, J.,Bayesian Approach to Global Optimization: Theory and Applications, Kluwer Academic Publishers, Amsterdam, Holland, 1989. · Zbl 0693.49001 [9] Horst, R., andTuy, H.,Global Optimization: Deterministic Approaches, Springer-Verlag, Berlin, Germany, 1990. · Zbl 0704.90057 [10] Floudas, C. A., andPardalos, P. M.,A Collection of Test Problems for Constrained Global Optimization Algorithms, Lecture Notes in Computer Science, Springer-Verlag, Berlin, Germany, Vol. 455, 1990. · Zbl 0718.90054 [11] Floudas, C. A., andPardalos, P. M.,Recent Advances in Global Optimization, Princeton University Press, Princeton, New Jersey, 1992. [12] Piyavskii, S. A.,An Algorithm for Finding the Absolute Extremum of a Function, USSR Computational Mathematics and Mathematical Physics, Vol. 12, pp. 57-67, 1972. · Zbl 0282.65052 · doi:10.1016/0041-5553(72)90115-2 [13] Pardalos, P. M., Glick, J. H., andRosen, J. B.,Global Minimization of Indefinite Quadratic Problems, Computing, Vol. 39, pp. 281-291, 1987. · Zbl 0627.65072 · doi:10.1007/BF02239972 [14] Al-Khayyal, F. A.,Jointly Constrained Bilinear Programs and Related Problems: An Overview, Computers in Mathematical Applications, Vol. 19, pp. 53-62, 1990. · Zbl 0706.90074 · doi:10.1016/0898-1221(90)90148-D [15] Hansen, P., Jaumard, B., andLu, S. H.,An Analytical Approach to Global Optimization, Mathematical Programming, Vol. 52, pp. 227-241, 1991. · Zbl 0747.90091 · doi:10.1007/BF01582889 [16] Tuy, H., Thieu, T. V., andThai, N. Q.,A Conical Algorithm for Globally Minimizing a Concave Function over a Closed Convex Set, Mathematics of Operations Research, Vol. 10, pp. 498-514, 1985. · Zbl 0579.90078 · doi:10.1287/moor.10.3.498 [17] Tuy, H.,Global Minimum of a Difference of Two Convex Functions, Mathematical Programming Study, Vol. 30, pp. 150-182, 1987. · Zbl 0619.90061 [18] Tuy, H.,Convex Programs with an Additional Reverse Convex Constraint, Journal of Optimization Theory and Applications, Vol. 52, pp. 463-472, 1987. · Zbl 0585.90071 · doi:10.1007/BF00938217 [19] Tuy, H.,On Outer Approximation Methods for Solving Concave Minimization Problems, Acta Mathematica Vietnamica, Vol. 8, 1983. · Zbl 0574.90074 [20] Horst, R., Thoai, N. V., andDe Vries, J.,A New Simplicial Cover Technique in Constrained Global Optimization, Journal of Global Optimization, Vol. 2, pp. 1-19, 1992. · Zbl 0784.90078 · doi:10.1007/BF00121299 [21] Shor, N. Z.,Dual Quadratic Estimates in Polynomial and Boolean Programming, Annals of Operations Research, Vol. 25, pp. 163-168, 1990. · Zbl 0783.90081 · doi:10.1007/BF02283692 [22] Floudas, C. A., Aggarwal, A., andCiric, A. R.,Global Optimum Search for Nonconvex NLP and MINLP Problems, Computers and Chemical Engineering, Vol. 13, pp. 1117-1132, 1989. · doi:10.1016/0098-1354(89)87016-4 [23] Aggarwal, A., andFloudas, C. A.,A Decomposition Approach for Global Optimum Search in QP, NLP, and MINLP Problems, Annals of Operations Research, Vol. 25, pp. 119-146, 1990. · Zbl 0717.90059 · doi:10.1007/BF02283690 [24] Sherali, H., andTuncbilek, C. H.,A Global Optimization Algorithm for Polynomial Programming Problems Using a Reformulation-Linearization Technique, Journal of Global Optimization, Vol. 2, pp. 101-112, 1992. · Zbl 0787.90088 · doi:10.1007/BF00121304 [25] Hansen, E. R.,Global Optimization Using Interval Analysis: The Multidimensional Case, Numerische Mathematik, Vol. 34, pp. 247-270, 1980. · Zbl 0442.65052 · doi:10.1007/BF01396702 [26] Floudas, C. A., andVisweswaran, V.,A Global Optimization Algorithm for Certain Classes of Nonconvex NLPs, Part 1: Theory, Computers and Chemical Engineering, Vol. 14, pp. 1397-1417, 1990. · doi:10.1016/0098-1354(90)80020-C [27] Visweswaran, V., andFloudas, C. A.,A Global Optimization Algorithm for Certain Classes of Nonconvex NLPs, Part 2: Application of Theory and Test Problems, Computers and Chemical Engineering, Vol. 14, pp. 1419-1434. 1990. · doi:10.1016/0098-1354(90)80021-3 [28] Geoffrion, A. M.,Generalized Benders Decomposition, Journal of Optimization Theory and Applications, Vol. 10, pp. 237-260, 1972. · Zbl 0229.90024 · doi:10.1007/BF00934810 [29] Wolsey, L. A.,A Resource Decomposition Algorithm for General Mathematical Programs, Mathematical Programming Study, Vol. 14, pp. 244-257, 1981. · Zbl 0449.90085 [30] Flippo, O. E.,Stability, Duality and Decomposition in General Mathematical Programming, PhD Thesis, Erasmus University, Rotterdam, Holland, 1990. [31] Hansen, P., andJaumard, B.,Reduction of Indefinite Quadratic Programs to Bilinear Programs, Journal of Global Optimization, Vol. 2, pp. 41-60, 1992. · Zbl 0786.90050 · doi:10.1007/BF00121301 [32] Bazaraa, M. S., andShetty, C. M.,Nonlinear Programming: Theory and Algorithms, John Wiley and Sons, New York, New York, 1979. · Zbl 0476.90035 [33] Visweswaran, V., andFloudas, C. A.,New Properties and Computational Improvement of the GOP Algorithm for Problems with Quadratic Objective Function and Constraints, Journal of Global Optimization, Vol. 3, No. 3, 1993. · Zbl 0795.90070 [34] Meyer, R.,The Validity of a Family of Optimization Methods, SIAM Journal on Control, Vol. 8, pp. 41-54, 1970. · Zbl 0194.20501 · doi:10.1137/0308003 [35] Berge, C.,Topological Spaces, Macmillan Company, New York, New York, 1963. · Zbl 0114.38602 [36] Visweswaran, V., andFloudas, C. A.,Unconstrained and Constrained Global Optimization of Polynomial Functions in One Variable, Journal of Global Optimization, Vol. 2, pp. 73-100, 1992. · Zbl 0781.90084 · doi:10.1007/BF00121303 [37] Floudas, C. A., Jaumard, B., andVisweswaran, V.,Decomposition Techniques for Global Optimization (to appear).