Optimization — Advanced
Mathematical Optimization - Advanced
Graduate levelGoals of this series
- Understand the theory and solution methods of integer programming (branch and bound, cutting planes).
- Learn the computational complexity and NP-hardness of combinatorial optimization problems.
- Master decomposition methods and efficient algorithms for large-scale optimization.
- Understand the theory of distributed optimization and ADMM.
- Learn optimization under uncertainty (robust optimization).
- Understand the basics of the calculus of variations and optimal control.
Prerequisites
- The intermediate material (convex optimization, duality theory, KKT conditions)
- Basics of functional analysis (normed spaces, functionals)
- Basics of combinatorics (graph theory, computational complexity)
Chapters
Chapter 1: Integer Programming
Formulation of integer programs, branch and bound, and cutting-plane methods.
Chapter 2: Combinatorial Optimization
Examples of combinatorial optimization, NP-hardness, and approximation algorithms.
Chapter 3: Large-Scale Optimization
Exploiting sparsity, decomposition methods, coordinate descent, and the proximal gradient method.
Chapter 4: Distributed Optimization
ADMM, consensus optimization, and federated learning.
Chapter 5: Robust Optimization
Handling uncertainty, robust linear programming, and distributionally robust optimization.
Chapter 6: Calculus of Variations and Optimal Control
Optimization of functionals, the Euler–Lagrange equation, and the maximum principle.
Chapter 7: Numerical Optimization — Convergence Rates and Acceleration
Lipschitz smoothness and strong convexity, Nesterov's accelerated gradient method with its $O(1/k^2)$ rate, the Nemirovski-Yudin lower bound, FISTA, and the local convergence rates of Newton/BFGS.
Chapter 8: Proximal Operator
Definition and uniqueness of $\text{prox}_{\lambda g}$, the relation to projection, the resolvent (implicit gradient step), closed forms such as soft thresholding, the Moreau envelope, and the bridge to proximal gradient methods.
Chapter 9: Proximal Gradient Method and FISTA
The proximal gradient method (ISTA) via forward-backward splitting and its accelerated version FISTA, convergence rates, backtracking and restart, and applications to Lasso, total variation, and compressed sensing.
Chapter 10: Bayesian Optimization
Surrogate models via Gaussian processes, acquisition functions (EI, PI, UCB), and sequential surrogate optimization.
Chapter 11: Simulated Annealing
The Metropolis criterion, cooling schedules, and stochastic methods for global optimization.
Chapter 12: Genetic Algorithms
Evolutionary optimization via selection, crossover, and mutation; the schema theorem.
Chapter 13: Dynamic Programming
Optimal substructure, overlapping subproblems, the knapsack problem, and the Bellman equation.
Chapter 14: Particle Swarm Optimization and Swarm Intelligence
The PSO velocity update, ant colony optimization, cuckoo search, and the firefly algorithm.
Chapter 15: Multi-Objective Optimization
Pareto optimality, scalarization, NSGA-II, MOEA/D, and performance indicators.
Chapter 16: Differential Evolution and Evolution Strategies
DE/rand/1/bin, CMA-ES, natural evolution strategies, and the natural gradient.
Chapter 17: Genetic Programming and Grammatical Evolution
Tree crossover and mutation, STGP, grammatical evolution based on context-free grammars, and parsimony pressure.
Chapter 18: Common Concepts in Evolutionary Computation
Exploration and exploitation, memetic algorithms, the Baldwin effect, and the cross-entropy method.
Chapter 19: Optimization under Uncertainty
VaR and CVaR, the minimax principle, info-gap decision theory, and polynomial chaos expansion.
Chapter 20: Multidisciplinary Design Optimization (MDO)
Collaborative optimization, the SAND, IDF, and MDF architectures, coupling variables, and sensitivity analysis.
Chapter 21: Design of Experiments and Space-Filling
Full factorial designs, Latin hypercube sampling, space-filling metrics, and the Morris-Mitchell criterion.
Exercises
A problem set to check your understanding at the advanced level.
Overview
The advanced material goes beyond the framework of continuous optimization to treat a broader range of optimization problems.
Integer programming treats optimization problems in which the variables are constrained to integer values. One learns systematic solution methods that combine continuous relaxation with branch and bound, as well as the polyhedral approach of cutting-plane methods.
Combinatorial optimization introduces the concept of NP-hardness through classical problems such as the traveling salesman problem and the knapsack problem, along with the approximation algorithms and metaheuristics used to cope with it.
Large-scale optimization covers the methods needed in modern data science and machine learning to handle large amounts of data and variables efficiently:
- Exploiting sparse matrix structure
- Problem decomposition (Dantzig–Wolfe decomposition, Benders decomposition)
- Coordinate descent and the proximal gradient method
Distributed optimization treats optimization methods for the case in which the data is spread across several nodes. ADMM (the alternating direction method of multipliers) is a powerful framework for solving constrained optimization problems in a distributed manner.
Robust optimization seeks solutions that guarantee worst-case performance when the parameters are uncertain. One learns how it differs from stochastic approaches and which computable relaxations are available.
The calculus of variations and optimal control treats optimization over function spaces. The Euler–Lagrange equation and Pontryagin's maximum principle are the fundamental theorems in the optimal control of dynamical systems.
Frequently Asked Questions
What topics does advanced optimization cover?
Integer programming, combinatorial optimization (NP-hardness and approximation algorithms), large-scale optimization (decomposition, coordinate descent, the proximal gradient method), distributed optimization (ADMM), robust optimization, and the calculus of variations and optimal control, together with metaheuristics such as simulated annealing, genetic algorithms, particle swarm optimization, and evolution strategies, and the convergence theory of numerical optimization (Nesterov acceleration, the proximal operator).
How does one cope with the NP-hardness of combinatorial optimization?
When an exact solution cannot be found in practical time, one combines several strategies: narrowing the search space with branch and bound or cutting-plane methods, obtaining approximate solutions with approximation algorithms that carry performance guarantees, and searching for practical solutions with metaheuristics such as simulated annealing, genetic algorithms, and particle swarm optimization.
What methods are used in large-scale optimization?
One uses the exploitation of sparse matrix structure, problem decomposition (Dantzig–Wolfe decomposition, Benders decomposition), coordinate descent, the proximal gradient method (ISTA/FISTA), and ADMM (the alternating direction method of multipliers) in a distributed setting. The key is to handle large numbers of variables and data while keeping the per-iteration cost low.
Reading
The Wall of Combinatorial ExplosionReading
The combinatorial explosion that shatters the idea that "trying everything yields the optimum." A relaxed look at how we live with NP-hardness and reach practical solutions through relaxation, branch and bound, and metaheuristics — the way practitioners actually think.
Betting on an Uncertain WorldReading
Real data fluctuates and the future is unreadable. Why does a solution that looked optimal on paper break down in production? A relaxed look at robust optimization, which prepares for the worst, and stochastic optimization, which plays the average — how professionals face uncertainty.