Global Optimization

Prerequisites

You should have completed:

• MIP Journey — Branch-and-bound, cutting planes, LP relaxations
• Nonlinear Optimization — Newton's method, interior point, KKT conditions

Or be comfortable with:

• Branch-and-bound trees and bounding
• Nonlinear optimization and KKT conditions
• Why convexity matters for optimization

1. Convex vs. Nonconvex Optimization

The distinction between convex and nonconvex problems is the fundamental divide in optimization.

What is Convexity?

A function $f: \mathbb{R}^n \to \mathbb{R}$ is convex if: $$f(\lambda x + (1-\lambda) y) \leq \lambda f(x) + (1-\lambda) f(y) \quad \forall x, y, ; \lambda \in [0,1]$$

Visually: the line segment between any two points on the graph lies above the graph.

Examples

The Nonconvex Challenge

For nonconvex problems:

• Multiple local minima exist
• Local methods find a local minimum, not the global minimum
• No polynomial-time algorithm is known (NP-hard in general)

2. Introduction to MINLP

Mixed-Integer Nonlinear Programming (MINLP) combines the challenges of MIP and NLP:

$$\min_{x,y} \quad f(x, y)$$ $$\text{s.t.} \quad g(x, y) \leq 0$$ $$\quad\quad h(x, y) = 0$$ $$\quad\quad x \in \mathbb{R}^n, ; y \in \mathbb{Z}^p$$

Where $f$, $g$, and $h$ may be nonlinear.

Why MINLP?

Real problems often have both:

• Discrete decisions: Build a reactor or not, choose among designs
• Nonlinear physics: Chemical equilibria, pressure-flow relations, economies of scale

Applications

• Process design: Chemical plant configuration with physics constraints
• Network design: Routing with nonlinear costs
• Pooling problems: Blending with quality constraints
• Unit commitment: Power generation scheduling

3. Spatial Branch-and-Bound

Standard branch-and-bound branches on integer variables. Spatial branch-and-bound extends this to branch on continuous variables too — enabling global optimization of nonconvex problems.

The Key Idea

For nonconvex problems, LP relaxation isn't enough. Even with integer variables fixed, the nonlinear relaxation may have multiple local optima.

Solution: Branch on continuous variables to partition the domain until the problem becomes "easy enough" to solve globally.

The Algorithm

Initialize:
  - Root node = original problem
  - Global upper bound = +∞ (best solution found)
  - Global lower bound = -∞ (best possible)

While nodes remain:
  1. SELECT a node
  2. SOLVE a convex relaxation (underestimator of the original)
  3. If relaxation infeasible: PRUNE
  4. If relaxation bound ≥ upper bound: PRUNE
  5. If solution is feasible for original problem:
       UPDATE upper bound
       PRUNE
  6. Else:
       Choose variable to BRANCH (integer or continuous)
       Create children with tighter bounds

Continuous Branching

For a continuous variable $x_j$ with bounds $[l_j, u_j]$, branch at some point $\hat{x}_j$:

• Left child: $x_j \in [l_j, \hat{x}_j]$
• Right child: $x_j \in [\hat{x}_j, u_j]$

Why this helps: Tighter bounds → tighter convex relaxations → better lower bounds → more pruning.

Branching Strategies

// Spatial branching considers both integer and continuous variables
// The branching object encodes bounds for the new subproblems

4. Convexification and Relaxations

The quality of spatial B&B depends entirely on the quality of the convex relaxations. Convexification creates convex underestimators of nonconvex functions.

McCormick Envelopes

For a bilinear term $w = x_1 x_2$ with $x_1 \in [l_1, u_1]$ and $x_2 \in [l_2, u_2]$:

The McCormick envelope provides the tightest convex relaxation using four linear inequalities:

$$w \geq l_1 x_2 + l_2 x_1 - l_1 l_2$$ $$w \geq u_1 x_2 + u_2 x_1 - u_1 u_2$$ $$w \leq u_1 x_2 + l_2 x_1 - u_1 l_2$$ $$w \leq l_1 x_2 + u_2 x_1 - l_1 u_2$$

Other Convexifications

Factorable Functions

A key insight: Most nonlinear functions can be factored into elementary operations: $$f(x) = x_1^2 + \sin(x_2) + x_1 x_3$$

Introduce auxiliary variables:

• $w_1 = x_1^2$ (convex, no relaxation)
• $w_2 = \sin(x_2)$ (bounded relaxation)
• $w_3 = x_1 x_3$ (McCormick)
• $f = w_1 + w_2 + w_3$ (linear)

This systematic approach enables automatic convexification.

// CouenneExprMul.cpp handles multiplication
// exprMul::generateCuts() creates McCormick cuts

5. Outer Approximation

For convex MINLP, there's a more efficient approach than spatial B&B: Outer Approximation (OA) alternates between an MILP master problem and NLP subproblems.

The Idea

Instead of branching on continuous variables, use linear cuts to approximate the nonlinear feasible region from outside.

The Algorithm

Initialize: Set of linearizations L = {}

Repeat:
  1. MILP MASTER: Solve
       min  c^T x + d^T y
       s.t. linearizations in L
            y ∈ Z^p
     Get solution (x*, y*)

  2. NLP SUBPROBLEM: Fix integers y = y*, solve
       min  c^T x + d^T y*
       s.t. g(x, y*) ≤ 0, h(x, y*) = 0
     Get solution x̂ (or infeasibility certificate)

  3. ADD LINEARIZATIONS:
     - At x̂: g(x̂) + ∇g(x̂)^T (x - x̂) ≤ 0
     - If infeasible: feasibility cuts

Until: MILP and NLP solutions match

Why It Works (for Convex Problems)

Bonmin's Modes

Bonmin implements several OA variants:

The hybrid mode is often fastest — it uses OA for quick bounds and B&B for difficult nodes.

// BonOaDecBase.cpp implements the OA decomposition
// Each NLP solve generates cuts added to the MILP

6. Bonmin and Couenne in Practice

COIN-OR provides two MINLP solvers that build on the foundation libraries:

Bonmin (Basic Open-source Nonlinear Mixed INteger programming)

For: Convex MINLP

Architecture:

• Uses Cbc for MILP (master problem, branch-and-bound)
• Uses Ipopt for NLP (subproblems)
• Uses Cgl for cutting planes

Strengths:

• Efficient for convex problems
• Multiple algorithm modes
• Warm-starting between solves

Limitations:

• May find local (not global) optima for nonconvex problems
• Assumes constraint qualification holds

Couenne (Convex Over and Under ENvelopes for Nonlinear Estimation)

For: Nonconvex MINLP (global optimization)

Architecture:

• Uses Cbc for the branch-and-bound tree
• Uses Ipopt for local NLP solves (upper bounds)
• Implements spatial branching and automatic convexification

Key Features:

• Expression decomposition: Breaks complex functions into simple operations
• Bound tightening: FBBT and OBBT to tighten variable domains
• Cut generation: McCormick, disjunctive cuts, and more
• Branching strategies: On both integer and continuous variables

Global Optimality Guarantee: Couenne proves a solution is globally optimal when the gap between upper and lower bounds closes.

When to Use Which

Practical Tips

1. Provide good bounds: Tighter variable bounds = faster convergence
2. Good starting point: Help local solvers find good upper bounds
3. Reformulate if possible: Convex formulations are much faster
4. Monitor gap: The optimality gap shows progress
5. Use presolve: Can dramatically reduce problem size

// Set up OsiSolverInterface with the MINLP
CouenneProblem problem;
problem.readNl("myProblem.nl");

// Solve globally
CouenneSolver solver(&problem);
solver.solve();

// Get gap
double gap = solver.getOptimumBound() - solver.getBestFeasible();

Summary

Global optimization is computationally expensive but sometimes necessary — when local optima aren't good enough and you need a guarantee of global optimality.

Next Steps

• Explore Couenne source in the browser
• Try the derivation of branch-and-bound correctness
• Read about McCormick envelopes in detail