Local and Global Optimization Techniques: A Research-Based Coursify Section

Optimization seeks decision variables $x$ that minimize (or maximize) an objective $f(x)$ over a feasible set $\mathcal{X}$. In local optimization, algorithms search for a point that improves the objective in the neighborhood of the current iterate, typically stopping at a local optimum or a stationary point; in global optimization, the goal is to find (or approximate) the best objective value over the entire domain, avoiding suboptimal local traps in nonconvex landscapes. 2

A unifying way to organize techniques is by (i) assumptions (convex vs nonconvex), (ii) information used (gradients/Hessians vs only function values), and (iii) guarantee type (convergence to stationary points vs global optimality or bounds). For example, gradient-based methods provide strong guarantees when the problem is convex, but in nonconvex settings they may converge to a local optimum. 2
For global methods, a common strategy is to maintain bounds (e.g., best-known feasible value and a provable lower/upper bound on the global optimum) and systematically shrink the search region.

Mermaid summary of the landscape and typical behavior:

Key concepts:

• local optimum
• global optimum
• nonconvex optimization
• stationary point

Note: This section focuses on techniques, not only definitions—so each method type is framed by what it assumes and what it can guarantee. 3

Footnotes

1. Optimization: local and global optima (overview) - Background on optimization, local/global optima, and related concepts. ↩ ↩²

2. Gradient descent (convergence in convex vs nonconvex) - Describes gradient descent behavior and convergence context. ↩ ↩² ↩³

3. Newton's method (local convergence ideas) - Explains Newton’s method and convergence characteristics. ↩

4. Branch and bound (global optimization framework) - Core idea of global search using bounds and pruning. ↩

1) Local optimization techniques

Local optimization typically uses first-order (gradients) or second-order (Hessians) information to move downhill/uphill. The classical local methods include gradient descent, Newton’s method, quasi-Newton methods, and constrained variants (projected methods, sequential quadratic programming). In smooth unconstrained settings, local convergence is often tied to conditions like Lipschitz continuity of gradients and (for Newton) nonsingularity of the Hessian near the solution. 2

1.1 Unconstrained local methods

Gradient descent iteratively updates:

$$x_{k+1}=x_k-\alpha_k \nabla f(x_k),$$

where $\alpha_k$ is a step size. When $f$ is convex with appropriate smoothness, gradient descent enjoys convergence guarantees to a global minimizer. In nonconvex settings, standard theory targets convergence to stationary points rather than global optimality. 2

Newton’s method uses second-order curvature:

$$x_{k+1}=x_k - \left[\nabla^2 f(x_k)\right]^{-1}\nabla f(x_k).$$

With appropriate regularity assumptions and starting sufficiently close to a local minimizer (and under conditions like positive definiteness of the Hessian), Newton can exhibit fast local convergence.

Quasi-Newton methods (e.g., BFGS, L-BFGS) approximate Hessian information efficiently, aiming for superlinear/local fast convergence without forming the full Hessian.

Keywords to anchor:

• gradient descent
• Newton’s method
• quasi-Newton method
• step size

1.2 Constrained local methods

For problems with constraints $x\in\mathcal{X}$, local optimization often relies on either:

• Reparameterization/projection (project onto feasible set each step, e.g., projected gradient),
• Sequential approximation (build local models of constraints/constraints linearizations, then solve subproblems, e.g., SQP),
• Penalty/barrier formulations (convert constrained problem into sequence of unconstrained problems).

The key point is: local constrained methods still risk getting stuck at a feasible local optimum or stationary point in nonconvex settings, even if they are effective in practice.

Keywords:

• projected gradient
• sequential quadratic programming (SQP)
• barrier method

Footnotes

1. Gradient descent (convergence in convex vs nonconvex) - Describes gradient descent behavior and convergence context. ↩ ↩²

2. Newton's method (local convergence ideas) - Explains Newton’s method and convergence characteristics. ↩ ↩² ↩³ ↩⁴

2) Global optimization techniques

Global optimization aims to find the best feasible objective value over the full domain. Because global optimality is generally harder than local optimality, global methods often trade more computation for stronger guarantees or improved robustness.

Global techniques commonly fall into categories:

1. Deterministic bounding methods (e.g., branch-and-bound, branch-and-cut; interval/bounding approaches),
2. Stochastic/global heuristics (e.g., simulated annealing, genetic algorithms, particle swarm),
3. Hybrid strategies combining local solvers with global search (multi-start, basin-hopping, memetic algorithms),
4. Convex relaxation / certificates (use relaxations to bound or certify global solutions).

2.1 Branch-and-bound / branch-and-cut (deterministic global optimization)

For certain problem classes (notably mixed-integer programs and some structured nonlinear problems), global solvers can systematically explore the search space while maintaining bounds. The typical logic: partition the feasible region into subregions (“branch”), solve relaxations to obtain bounds (“bound”), and prune subregions that cannot contain a better solution than the best known feasible point.

• branch-and-bound
• branch-and-cut
• mixed-integer programming (MIP)
• cutting plane

2.2 Simulated annealing (stochastic global heuristic)

Simulated annealing is a stochastic search strategy inspired by thermodynamics. It allows occasional uphill moves, helping escape local minima; a cooling schedule gradually reduces the probability of such moves. With carefully designed schedules and assumptions, it can converge in probability to a global optimum, though practical performance depends on parameterization and runtime limits.

• simulated annealing

2.3 Population-based evolutionary methods (GA/PSO)

Genetic algorithms use selection, crossover, and mutation to evolve a population of candidate solutions. Particle swarm optimization updates particles using velocity influenced by personal and global best positions. These methods are often robust in practice for rugged nonconvex landscapes, but theoretical global guarantees depend on specific variants and assumptions.

• genetic algorithm (GA)
• particle swarm optimization (PSO)

2.4 Multi-start and basin-hopping (hybrid global-local)

A pragmatic global approach is multi-start local optimization: run a local solver from many initial points, then keep the best solution found. While it does not provide deterministic global optimality certificates, it often substantially improves practical success probability in nonconvex problems. Hybridization is also common: use a global heuristic to generate promising regions, then use a local solver to refine.

• multi-start
• basin-hopping

Footnotes

1. Branch and bound (global optimization framework) - Core idea of global search using bounds and pruning. ↩

2. Simulated annealing / genetic algorithms (stochastic global heuristics) - Describes stochastic global optimization approach and intuition behind escaping local minima. ↩ ↩²

3) When to use which: decision criteria

A useful decision framework is to match the method to the structure of the problem:

If the problem is convex (or can be made convex)

• Prefer local methods because they often become globally correct under convexity assumptions. In convex optimization, many gradient-based methods converge to the global optimum because local minima are global minima. 2

If the problem is nonconvex

• Local methods are still valuable as solvers for fast improvement (especially as inner loops in hybrids).
• Global methods are needed when you require:
  • stronger robustness to initialization,
  • proof/certificates of global optimality or tight bounds,
  • avoidance of catastrophic local traps.

If you need a certificate (global proof)

• Deterministic global solvers (e.g., MIP branch-and-cut, interval/bounding methods) are more aligned with certification goals.

Keywords:

• convex optimization
• relaxation
• certificate

Footnotes

1. Gradient descent (convergence in convex vs nonconvex) - Describes gradient descent behavior and convergence context. ↩

2. Newton's method (local convergence ideas) - Explains Newton’s method and convergence characteristics. ↩

3. Branch and bound (global optimization framework) - Core idea of global search using bounds and pruning. ↩