## Definition An **optimisation problem** is the task of finding the best element $x^* \in S$ from some set $S$ according to a criterion — typically minimising or maximising a function. The foundational abstraction underlying ML, OR, scientific computing, engineering design. ## Standard Form $ \min_x \, f(x) \quad \text{subject to} \quad g_i(x) \leq 0, \quad h_j(x) = 0 $ - $f$ — **objective function**. - $g_i$ — **inequality constraints**. - $h_j$ — **equality constraints**. - Domain may be continuous ($x \in \mathbb{R}^n$) or discrete ($x \in \mathbb{Z}^n$). Maximisation is just minimisation of $-f$. ## Major Classes By problem structure: | Class | Continuous? | Convex? | Solvable? | |---|---|---|---| | Linear Programming | Yes | Yes | Polynomial (Simplex / interior-point) | | Convex Optimization | Yes | Yes | Polynomial (in problem dimensions) | | Quadratic Programming | Yes | If $Q \succeq 0$ | Polynomial when convex | | Non-linear (smooth) | Yes | Not necessarily | Local optima only | | Integer Programming | No | Discrete | NP-hard in general | | Combinatorial | No | Discrete | NP-hard for many problems | ## Key Concepts - **Feasibility region** — the set of $x$ satisfying all constraints. See [[Feasibility Region]]. - **Objective value** — $f(x)$ at a particular $x$. See [[Objective Function]]. - **Local vs global optimum.** See [[Local vs Global Optimum]]. - **Duality** — every problem has a dual; relates to bounds and sensitivity analysis. See [[Duality]]. ## Solution Approaches - **Closed-form** — rare, but exists for some problems (least squares, eigenvalue). - **Iterative** — gradient descent, Newton, simplex, branch-and-bound. - **Approximation** — when exact is intractable; metaheuristics, relaxation. - **Stochastic** — when objective is noisy or expensive to evaluate. ## What Makes It Hard - **Non-convexity** — many local optima. - **Constraints** — feasibility may be hard to maintain. - **High dimensions** — curse of dimensionality. - **Discrete decisions** — combinatorial blow-up. - **Black-box / non-differentiable** objectives. ## Why This Matters Across AI/ML ML *is* optimisation: minimise loss over parameters. Different ML algorithms differ mostly in the objective and the feasibility constraints. Understanding optimisation = understanding the engine driving most of ML. ## Related - [[Objective Function]] - [[Feasibility Region]] - [[Convex vs Non-Convex Optimization]] - [[Gradient Descent]] - [[10 - Optimization Notes Hub]]