×

zbMATH — the first resource for mathematics

\(\alpha BB\): A global optimization method for general constrained nonconvex problems. (English) Zbl 0846.90087
Summary: A branch-and-bound global optimization method, \(\alpha BB\), for general continuous optimization problems involving nonconvexities in the objective function and/or constraints is presented. The nonconvexities are categorized as being either of special structure or generic. A convex relaxation of the original nonconvex problem is obtained by (i) replacing all nonconvex terms of special structure (i.e., bilinear, fractional, signomial) with customized tight convex lower bounding functions and (ii) by utilizing the \(\alpha\) parameter as defined by the second and the third author [J. Global Optim. 4, No. 2, 135-170 (1994; Zbl 0797.90114)] to underestimate nonconvex terms of generic structure. The proposed branch-and-bound type algorithm attains finite \(\varepsilon\)-convergence to the global minimum through the successive subdivision of the original region and the subsequent solution of a series of nonlinear convex minimization problems. The global optimization method, \(\alpha BB\), is implemented in \(C\) and tested on a variety of example problems.

MSC:
90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
PDF BibTeX Cite
Full Text: DOI
References:
[1] F.A. Al-Khayyal. Jointly Constrained Bilinear Programs and Related Problems.Int. J. Comp. Math., 19(11):53, 1990. · Zbl 0706.90074
[2] F.A. Al-Khayyal and J.E. Falk. Jointly constrained biconvex programming.Math. Opers. Res., 8:523, 1983. · Zbl 0521.90087
[3] I.P. Androulakis and V. Venkatasubramanian. A Genetic Algorithmic Framework for Process Design and Optimization.Comp. chem. engng., 15(4):217, 1991.
[4] A. Ben-Tal, G. Eiger, and V. Gershovitz. Global Optimization by Reducing the Duality Gap.in press, Math. Prog., 1994. · Zbl 0807.90101
[5] C.A. Floudas and P.M. Pardalos.Recent advances in global optimization Princeton Series in Computer Science. Princeton University Press, Princeton, New Jersey, 1992.
[6] C.A. Floudas and V. Visweswaran. A global optimization algorithm (GOP) for certain classes of nonconvex NLPs: I. Theory.Comput. chem. Engng., 14(12):1397, 1990.
[7] C.A. Floudas and V. Visweswaran. A primal-relaxed dual global optimization approach.J. Opt. Th. Appl., 78(2):187, 1993. · Zbl 0796.90056
[8] E.R. Hansen.Global Optimization Using Interval Analysis. Marcel Dekkar, New York, NY, 1992. · Zbl 0762.90069
[9] C.A. Haverly. Studies of the Behavior of Recursion for the Pooling Problem.SIGMAP Bulletin, 25:19, 1978.
[10] D.E. Goldberg.Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, New York, NY, 1989. · Zbl 0721.68056
[11] R. Horst and P.M. Pardalos.Handbook of Global Optimization: Nonconvex Optimization and Its Applications. Kluwer Academic Publishers, 1994.
[12] P. Hansen, B. Jaumard, and S. Lu. Global Optimization of Univariate Lipschitz Functions: I. Survey and Properties.Math. Prog., 55:251, 1992a. · Zbl 0825.90755
[13] P. Hansen, B. Jaumard, and S. Lu. Global Optimization of Univariate Lipschitz Functions: II. New Algorithms and Computational Comparison.Math. Prog., 55:273, 1992b. · Zbl 0825.90756
[14] R. Horst, N.V. Thoai, and J. De Vries. A New Simplicial Cover Technique in Constrained Global Optimization.J. Global Opt., 2:1, 1992. · Zbl 0784.90078
[15] R. Horst and H. Tuy. On the Convergence of Global Methods in Multiextremal Optimization.Opt. Th. Appl., 54:283, 1987. · Zbl 0595.90079
[16] R. Horst and H. Tuy.Global Optimization. Springer-Verlag, Berlin, Germany, 1990. · Zbl 0704.90057
[17] C.D. Maranas and C.A. Floudas. Global Minimum Potential Energy Conformations of Small Molecules.J. Glob. Opt., 4:135, 1994a. · Zbl 0797.90114
[18] C.D. Maranas and C.A. Floudas. Global Optimization in Generalized Geometric Porgramming.submitted to Comp. chem. Engnr., 1994c. · Zbl 0811.90057
[19] C.D. Maranas and C.A. Floudas. Finding All Solutions of Nonlinearly Constrained Systems of Equations.submitted to J. Global Opt., 1995a. · Zbl 0841.90115
[20] C.M. McDonald and C.A. Floudas. Decomposition Based and Branch and Bound Global Optimization Approaches for the Phase Equilibrium Problem.J. Global Opt., 5:205, 1994. · Zbl 0820.90100
[21] R. Moore, E. Hansen and A. Leclerc. Rigorous Methods for Global Optimization. InRecent advances in global optimization Princeton Series in Computer Science. Princeton University Press, Princeton, New Jersey, 1992.
[22] B.A. Murtagh and M.A. Saunders.MINOS5.0 Users Guide. Systems Optimization Laboratory, Dept. of Operations Research, Stanford University, CA., 1983. Appendix A: MINOS5.0, Technical Report SOL 83-20.
[23] P.M. Pardalos and J.B. Rosen.Constrained global optimization: Algorithms and applications, volume 268of Lecture Notes in Computer Science. Springer Verlag, Berlin, Germany, 1987.
[24] H. Ratschek and J. Rokne.New Computer Methods for Global Optimization. Halsted Press, Chichester, Great Britain, 1988. · Zbl 0648.65049
[25] A.H.G. Rinnoy-Kan and G.T. Timmer. Stochastic Global Optimization Methods. Part I: Clustering Methods.Math. Prog., 39:27, 1987. · Zbl 0634.90066
[26] C.D. Gelatt, S. Kirkpatrick and M.P. Vecchi.Science, 220:671, 1983. · Zbl 1225.90162
[27] H.D. Sherali and A. Alameddine. A New Reformulation Linearization Technique for Bilinear Programming Problems.J. Global Opt., 2(4):379, 1992. · Zbl 0791.90056
[28] H.D. Sherali and C.H. Tuncbilek. A Global Optimization Algorithm for Polynomial Programming Using a Reformulation-Linearization Technique.J. Global Opt., 2:101, 1992. · Zbl 0787.90088
[29] N.Z. Shor. Dual Quadratic Estimates in Polynomial and Boolean Programming.Annals of Operations Research, 25:163, 1990. · Zbl 0783.90081
[30] A. Torn and A. Zilinskas.Global Optimization, volume 350 ofLecture Notes in Computer Science. Springer-Verlag, Berlin, Germany, 1989.
[31] H. Tuy. Global Minimum of the Difference of Two Convex Functions.Mathematical Programming Study, 30:150, 1987. · Zbl 0619.90061
[32] H. Tuy, T.V. Thieu, and N.Q. Thai. A Conical Algorithm for Globally Minimizing A Concave Function over a Closed Convex Set.Mathematics of Operations Research, 10:498, 1985. · Zbl 0579.90078
[33] V. Visweswaran and C.A. Floudas. New properties and computational improvement of the GOP algorithm for problems with quadratic objective function and constraints.J. Global Opt., 3(3):439, 1993. · Zbl 0795.90070
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.