From here on out, we will refer to minima entirely. Negation provides an equivalence to the associated definitions for maxima.

Standard Form

Optimization problems in $n$ variables subject to $m$ constraints are written in a standard form.

1. Optimization variables are encoded in a vector $\mathbf{x} \in \R^{n}$.
2. Objective function is encoded as a map $f_0 : \R ^n \rightarrow \R$.
3. Constraints $f_1 (\mathbf{x}) \leq 0 , \dots, f_m (\mathbf{x}) \leq 0$ are represented as a system of $m$ homogeneous inequalities, where each $f_i : \R^n \rightarrow \R$.

$$ \argmin _{\mathbf{x} \in \R^n} f_0(\mathbf{x}) \hspace{15pt} \text{ subject to } \hspace{15pt} \begin{cases} f_1 (\mathbf{x} ) \leq 0 \\ \vdots \\ f_m (\mathbf{x}) \leq 0\end{cases} $$

Feasible Points

A feasible point $\mathbf{x} \in \R^n$ is a point which satisfies the constraints of an optimization problem. Moreover, the feasible set of an optimization problem is the set of all feasible points.

$$ \mathcal{X} = \{ \mathbf{x} \in \R^{n} : f_1(\mathbf{x}) \leq 0 \wedge \dots \wedge f_m (\mathbf{x}) \leq 0 \} $$

With this definition, we can further compact our notation.

$$ \argmin _{\mathbf{x} \in \mathcal{X} } f_0 (\mathbf{x}) $$

Optimization Classification

The notion of feasibility provides a nice way to classify different optimization problems, particularly in terms of the global solution $\mathbf{x}^* \in \mathcal{X}$.

$$ f_0(\mathbf{x}^*) = \begin{cases} +\infty \iff \mathcal{X} = \empty \hspace{43pt} \text{(Infeasible)} \\

\text{Finite} \hspace{91pt} \text{(Feasible, well-behaved)} \\ -\infty \iff \inf f_0 = -\infty \hspace{15pt} \text{(Unbounded from Below)}

\end{cases} $$

Global and Local Minima