×

Geometric branch-and-bound methods for constrained global optimization problems. (English) Zbl 1286.90118

Summary: Geometric branch-and-bound methods are popular solution algorithms in deterministic global optimization to solve problems in small dimensions. The aim of this paper is to formulate a geometric branch-and-bound method for constrained global optimization problems which allows the use of arbitrary bounding operations. In particular, our main goal is to prove the convergence of the suggested method using the concept of the rate of convergence in geometric branch-and-bound methods as introduced in some recent publications. Furthermore, some efficient further discarding tests using necessary conditions for optimality are derived and illustrated numerically on an obnoxious facility location problem.

MSC:

90C26 Nonconvex programming, global optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

alphaBB
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjiman C.S., Dallwig S., Floudas C.A., Neumaier A.: A global optimization method, αBB, for general twice-differentiable constrained NLPs—I. Theoretical advances. Comput. Chem. Eng. 22, 1137-1158 (1998) · doi:10.1016/S0098-1354(98)00027-1
[2] Androulakis I.P., Maranas C.D., Floudas C.A.: αBB: a global optimization method for general constrained nonconvex problems. J. Glob. Optim. 7, 337-363 (1995) · Zbl 0846.90087 · doi:10.1007/BF01099647
[3] Bazaraa M.S., Sherali H.D., Shetty C.M.: Nonlinear Programming: Theory and Algorithms. 2nd edn. Wiley-Interscience, New York (1993) · Zbl 0774.90075
[4] Blanquero R., Carrizosa E.: Continuous location problems and big triangle small triangle: Constructing better bounds. J. Glob. Optim. 45, 389-402 (2009) · Zbl 1189.90085 · doi:10.1007/s10898-008-9381-z
[5] Craven B.D., Mond B.: Sufficient Fritz John optimality conditions for nondifferentiable convex programming. J. Aust. Math. Soc. 19, 462-468 (1976) · Zbl 0355.90058 · doi:10.1017/S0334270000001326
[6] Drezner Z., Suzuki A.: The big triangle small triangle method for the solution of nonconvex facility location problems. Oper. Res. 52, 128-135 (2004) · Zbl 1165.90552 · doi:10.1287/opre.1030.0077
[7] Floudas C.A.: Deterministic Global Optimization: Theory, Methods and Applications. 1st edn. Springer, New York (1999)
[8] Hansen E.: Global Optimization Using Interval Analysis. 1st edn. Marcel Dekker, New York (1992) · Zbl 0762.90069
[9] Hansen P., Peeters D., Richard D., Thisse J.F.: The minisum and minimax location problems revisited. Oper. Res. 33, 1251-1265 (1985) · Zbl 0582.90027 · doi:10.1287/opre.33.6.1251
[10] Horst R., Pardalos P.M., Thoai N.V.: Introduction to Global Optimization. 2nd edn. Springer, Berlin (2000) · Zbl 0966.90073
[11] Horst R., Tuy H.: Global Optimization: Deterministic Approaches. 3rd edn. Springer, Berlin (1996) · Zbl 0867.90105 · doi:10.1007/978-3-662-03199-5
[12] Kearfott R.B.: An interval branch and bound algorithm for bound constrained optimization problems. J. Glob. Optim. 2, 259-280 (1992) · Zbl 0760.90085 · doi:10.1007/BF00171829
[13] Neumaier A.: Interval Methods for Systems of Equations. 1st edn. Cambridge University Press, New York (1990) · Zbl 0715.65030
[14] Plastria F.: GBSSS: The generalized big square small square method for planar single-facility location. Eur. J. Oper. Res. 62, 163-174 (1992) · Zbl 0760.90067 · doi:10.1016/0377-2217(92)90244-4
[15] Plastria, F.; Drezner, Z. (ed.), Continuous location problems, 225-262 (1995), Berlin · doi:10.1007/978-1-4612-5355-6_12
[16] Ratschek H., Rokne J.: New Computer Methods for Global Optimization. 1st edn. Ellis Horwood, Chichester, England (1988) · Zbl 0648.65049
[17] Ratschek H., Voller R.L: What can interval analysis do for global optimization?. J. Glob. Optim. 1, 111-130 (1991) · Zbl 0752.65054 · doi:10.1007/BF00119986
[18] Schöbel A., Scholz D.: The theoretical and empirical rate of convergence for geometric branch-and-bound methods. J. Glob. Optim. 48, 473-495 (2010) · Zbl 1236.90148 · doi:10.1007/s10898-009-9502-3
[19] Scholz, D.: Theoretical rate of convergence for interval inclusion functions. J. Glob. Optim. (2011). doi:10.1007/s10898-011-9735-9 · Zbl 1259.90104
[20] Scholz D.: Deterministic Global Optimization: Geometric Branch-and-bound Methods and Their Applications. 1st edn. Springer, New York (2012) · Zbl 1237.90002 · doi:10.1007/978-1-4614-1951-8
[21] Sun M., Johnson A.W.: Interval branch and bound with local sampling for constrained global optimization. J. Glob. Optim. 33, 61-82 (2005) · Zbl 1093.90088 · doi:10.1007/s10898-004-6097-6
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.