Problem statement

Course completion
11%
$
\DeclareMathOperator*{\argmax}{arg\,max}
\DeclareMathOperator*{\argmin}{arg\,min}
\DeclareMathOperator{\dom}{dom}
\DeclareMathOperator{\sigm}{sigm}
\DeclareMathOperator{\softmax}{softmax}
\DeclareMathOperator{\sign}{sign}
$

When faced with an optimization problem, the goal can be:

  • to find optimal parameters $\mathbf{x}^{*}$ for which $f(\mathbf{x}^{*})$ has the least possible value (in which case we refer to it as a minimization problem), or
  • to find optimal parameters $\mathbf{x}^{*}$ for which $f(\mathbf{x}^{*})$ has the greatest possible value –in which case we refer to it as a maximization problem.to find optimal parameters $\mathbf{x}^{*}$ for which $f(\mathbf{x}^{*})$ has the greatest possible value –in which case we refer to it as a maximization problem.

The space of values of $\mathbf{x}$ considered as possible solutions is called the domain of f and is noted $\dom f$. We now give a formal definition.

Definition 1.1 (global optimization problem)
Let us consider the problem of minimizing a function f over it’s domain $\dom f$ which we note $$\min_{\mathbf{x}\in\dom f}f(\mathbf{x}).$$ Let $\mathbf{x}^{*}$ be a solution to the above minimization problem which we note $$\mathbf{x}^{*}=\argmin_{\mathbf{x}\in\dom f}f(\mathbf{x}),$$ then $\mathbf{x}^{*}$ is called a global minimum and satisfies $$\forall\mathbf{x}\in\dom f,f(\mathbf{x}^{*})\leq f(\mathbf{x}).$$ A global maximization problem and a global maximum are defined analogously using the notations $\max$ and $\argmax$. The terms optimum and global optimum can be used indiscriminately to refer to maxima or minima.

It is often very hard to find a global optimum because it is defined as being better than all possible values of $\mathbf{x}$ in the available domain. Therefore it is sometimes necessary to consider only the simpler problem of local optimization.

Definition 1.2 (local optimum)
$\mathbf{x}^{*}$ is a local minimum of f iff $$\exists\boldsymbol{\epsilon}>0,\forall\mathbf{x}\in\dom f,\left\Vert \mathbf{x}-\mathbf{x}^{*}\right\Vert <\boldsymbol{\epsilon}\Rightarrow f(\mathbf{x}^{*})\leq f(\mathbf{x}).$$
The definition of a local maximum is analogous with $f(\mathbf{x}^{*})\geq f(\mathbf{x})$.

In other words, $\mathbf{x}^{*}$ is a local minimum if it is possible to find a small neighborhood of $\mathbf{x}^{*}$ such that $\mathbf{x}^{*}$ is a global minimum of the restriction of $f$ to this neighborhood. See Figure “Global and local optima” for a visual representation of global and local optima of a simple function. In particular, any global optimum is also a local optimum for which any choice of neighborhood is acceptable.


global-local-optima
Figure 1: A visualisation of Global and local optima

Next: The curse of dimensionality