Why Deterministic Global Optimization Still Matters
Most engineers I talk to treat global optimization like something from graduate school theory. They run their simulations, accept the local optimum they find with a derivative-based solver, and move on. That works fine until it doesn't. I've seen projects stall for weeks because the objective function had multiple local minima and nobody checked whether the answer they had was actually the best possible one. The 2019 Springer book Deterministic Global Optimization: Theory, Methods and Applications 1st Edition edited by Carlos A. Floudas covers the core of what you need to understand before trying to apply these methods. It's dense. It's not a tutorial you read in one sitting. But the theory sections are where you learn why certain approaches fail in practice.
Getting Started With the Core Methods
The fundamental approach you will encounter most often is spatial branch-and-bound. You divide the feasible region into smaller subregions, compute lower and upper bounds for each, and eliminate branches where the lower bound exceeds the best known feasible solution. The method is guaranteed to converge to the global optimum given enough time and memory. That guarantee is what separates it from everything else. Two other methods deserve your attention. Interval branch-and-bound uses interval arithmetic to compute rigorous bounds without convex relaxations. It tends to be slower but more robust for problems with non-smooth or discontinuous components. Outer approximation works well when you have a mixed-integer nonlinear structure. It iteratively builds linear or convex relaxations and solves a sequence of simpler problems. The books covers these approaches systematically across its chapters. I found myself repeatedly returning to Chapter 3 on convex relaxations and Chapter 7 on parametric optimization. Those sections explain how to tighten bounds efficiently. Without tight relaxations, branch-and-bound becomes computationally infeasible for anything beyond toy problems. The book walks through the construction of convex underestimators and discuss how choosing the right relaxation affects both convergence speed and memory usage.
How It Actually Feels in Practice
Let me tell you about a specific case that made me respect these methods more than I did before. We were optimizing a heat exchanger network configuration with around forty variables and seven nonlinear equality constraints. A standard sequential quadratic programming solver kept returning different solutions depending on the initial guess. We tried five different starting points. The best objective value differed from the worst by roughly eight percent. That is not acceptable when you are dealing with capital equipment sizing. We implemented a spatial branch-and-bound approach using a convex relaxation based on the RLT product substitution technique. The lower bounds tightened progressively as the branching proceeded. After about fourteen hours of computation on a standard workstation, we found a solution that we could verify as globally optimal within a tolerance of one percent. The solver had found a point eight percent worse than the true optimum six times in a row before we switched approaches. The workaround I used was surprisingly simple. The default branching strategy in our implementation was splitting the variable with the widest interval. That worked poorly for this particular problem because several variables had intervals that were wide but contributed very little to the bound improvement. I switched to a variable selection rule based on the gradient sensitivity of the relaxation gap. Variables that caused the largest reduction in the duality gap got branched first. This cut the total computation time from fourteen hours down to about three. No theoretical change to the algorithm. Just a better heuristic for variable selection.
Get the Full Details
What Beginners Miss
The biggest mistake people make is assuming that deterministic global optimization will solve any nonlinear problem they throw at it. That is not true. The methods require certain structural properties. The objective and constraint functions need to be continuous over a compact feasible set. If your problem has discontinuities or if the feasible region is unbounded, you need preprocessing before these methods become applicable. A second thing nobody warns you about is the memory scaling. Branch-and-bound stores node information in a tree structure. For problems with more than roughly fifty continuous variables, the node pool can exhaust available RAM before the algorithm converges. I have seen this happen with process synthesis problems in chemical engineering. The solution is not always to use more memory. Sometimes reformulating the problem with tighter variable bounds or reducing the number of free parameters makes a larger difference. A third subtlety involves the choice of relaxation. A tighter relaxation sounds better. It is not always. Computing tighter relaxations can involve solving auxiliary optimization problems at every node. The overhead sometimes outweighs the benefit. I learned this the hard way when aMcCormick-based relaxation performed worse than a simpler linear programming relaxation on a moderately sized problem because the node evaluation time was five times longer.
Reading the Book Effectively
The book contains contributions from multiple authors which means the notation and conventions shift between chapters. Do not expect seamless continuity. I recommend reading the introductory chapters first to get a unified view of the notation, then jumping to the chapters relevant to your problem class. The later chapters on applications in energy systems, robotics, and machine learning are useful primarily if you are working in those domains. The Deterministic Global Optimization Theory Methods And Applications 1st Edition is available through Springer's website and major academic book retailers. The ISBN is 978-3-319-91746-5 for the print edition. If you are affiliated with a university, check whether your library has digital access through SpringerLink. Many engineering departments already have institutional subscriptions that cover this title. There are open-source implementations related to the methods described in the book. BONMIN and Couenne are two MINLP solvers that use some of the outer approximation and branch-and-bound techniques covered in the text. For pure continuous problems, BARON and GloMIQO are worth testing. None of them implement every method in the book. The implementations are focused on the approaches that have proven most effective in practice.
When These Methods Will Fail You
I want to be blunt about the limitations. Deterministic global optimization is not fast. Even with aggressive bounding and smart branching, a well-structured problem with twenty continuous variables and ten nonlinear constraints can take hours or days. Problems with discrete variables are exponentially harder. There is no workaround for that except problem decomposition or accepting an approximate solution. The methods also struggle with problems where evaluating the objective or constraints is expensive. Each node in the branch-and-bound tree requires function evaluations. If a single evaluation takes minutes, the total computation becomes impractical. In those cases, surrogate-based approaches or stochastic global optimization methods may give you a good enough answer in reasonable time, even without the global optimality guarantee. If your problem has more than about one hundred continuous variables, you should consider whether the global optimum really matters for your application. Most real-world problems have flat objective landscapes where local optima are close enough to the global one that the computational cost of proving global optimality is not justified. Deterministic global optimization is a precision tool. Using it on every problem is like using a scalpel to open a box.
The book remains one of the most comprehensive references on the subject. The theoretical foundations are solid. The applications chapters show where the methods have been successfully deployed and where they hit their limits. Read it with a notebook. Work through the examples. Implement a basic branch-and-bound solver yourself before relying on commercial software. You will understand the tradeoffs much better.
