Introduction to Optimization Techniques
Course‑level overview – concise, structured, and easy to read
1. What Is Optimization?
| Aspect |
Description |
| Goal |
Find the “best” solution among all feasible alternatives. |
| Best |
Defined by a objective function (e.g., minimize cost, maximize profit, reduce error). |
| Feasibility |
Solutions must satisfy a set of constraints (equalities, inequalities, logical conditions). |
| Domain |
Variables may be continuous, discrete, integer, binary, or a mix. |
Typical formulation
[
\begin{aligned}
\text{minimize / maximize} \quad & f(\mathbf{x}) \
\text{subject to} \quad & g_i(\mathbf{x}) \le 0,; i=1,\dots,m\
& h_j(\mathbf{x}) = 0,; j=1,\dots,p\
& \mathbf{x}\in\mathcal{X}
\end{aligned}
]
2. Classification of Optimization Problems
| Class |
Variable Type |
Objective |
Typical Methods |
| Linear Programming (LP) |
Continuous |
Linear |
Simplex, interior‑point |
| Integer Programming (IP) |
Integer / binary |
Linear |
Branch‑and‑bound, cutting planes |
| Mixed‑Integer Linear Programming (MILP) |
Mix of continuous & integer |
Linear |
Branch‑and‑cut, Benders |
| Nonlinear Programming (NLP) |
Continuous |
Non‑linear |
Gradient‑based (SQP, interior‑point), trust‑region |
| Mixed‑Integer Nonlinear Programming (MINLP) |
Mix |
Non‑linear |
Outer‑approximation, ECP, heuristic hybrids |
| Convex Optimization |
Continuous |
Convex objective & convex constraints |
Interior‑point, proximal methods |
| Combinatorial Optimization |
Discrete (graphs, sets) |
Often linear |
Dynamic programming, greedy, approximation algorithms |
| Stochastic / Robust Optimization |
Continuous or discrete |
Expectation or worst‑case |
Sample‑average approximation, scenario trees |
| Metaheuristics |
Any |
Black‑box |
Genetic algorithms, simulated annealing, particle swarm, ant colony |
3. Core Concepts & Terminology
| Term |
Meaning |
| Feasible region |
Set of all (\mathbf{x}) that satisfy constraints. |
| Optimal solution |
Feasible point that yields the best objective value. |
| Local vs. global optimum |
Local: best in a neighbourhood; Global: best overall. |
| Convexity |
If feasible region and objective are convex → any local optimum is global. |
| Duality |
Every primal problem has a dual; dual solutions give bounds and sensitivity information. |
| Sensitivity / Shadow price |
Change in optimal value per unit change in a constraint RHS. |
| KKT conditions |
Necessary (and under convexity, sufficient) conditions for optimality in NLP. |
| Relaxation |
Removing/integrating constraints (e.g., integer → continuous) to obtain a bound. |
| Branch‑and‑bound |
Systematically explore sub‑problems, pruning by bounds. |
| Cutting plane |
Add linear constraints that cut off infeasible integer points without removing feasible ones. |
4. Solution Approaches
4.1 Exact Algorithms
| Technique |
When to use |
Key idea |
| Simplex |
|
|