Basic concepts of optimization

Section 30.1 Basic concepts of optimization

Optimization may be naturally stated as search for maximum (for example, maximum profit) or minimum (minimum cost). But since every point of maximum of a function

$f$ is also a point of minimum of

$-f\text{,}$ it is enough to study the minimization problem.

🔗

Suppose

$f\colon E\to \mathbb R$ is a real-valued function on some set

$E\subset \mathbb R^d\text{.}$ The function attains its global minimum at

$p\in E$ if

$f(x)\ge f(p)$ for all

$x\in E\text{.}$ It is possible to have several points of global minimum, for example

$f(x)=\sin x$ on the interval

$[0, 4\pi]$ attains global minimum of

$-1$ at the points

$x=3\pi/2$ and

$x = 7\pi/2\text{.}$

🔗

The Extreme Value Theorem states that if

$f$ is a continuous function and the set

$E$ is closed (includes all its boundary points) and bounded (is contained in some cube), then there is a point

$p\in E$ at which

$f$ attains its global minimum.

🔗

A function

$f$ attains its local minimum at

$p\in E$ if there exists

$r > 0$ such that

$f(x)\ge f(p)$ for all

$x\in E$ such that

$|x-r| \lt r\text{.}$ That is, there exists a neighborhood of point

$p$ such that the smallest value of

$f$ in that neighborhood is

$f(p)\text{.}$

🔗

A major source of difficulty of optimization is searching for global minimum and finding only a local one. There is no universal recipe for avoiding this problem. Consider the function

$f(x) = \sin x + \sin \sqrt{2}x$ on some long interval such as

$[-100, 100]\text{.}$ Where is its global minimum? There is no reliable and efficient way to find it.

🔗

A function that has only one point of local minimum on some set is called unimodal. For example,

$f(x) = x^2 - x$ is unimodal on the interval

$[0, 2]$ but

$f(x) = x - x^2$ is not (according to our definition; when people focus on maximum instead of minimum, the situation is reversed). Working with unimodal functions is much easier because our algorithm is much more likely to find minimum.

🔗

A function is convex (also called “concave up” in calculus) if its graph lies below its secant lines, meaning

$\begin{equation} f( (1-t) a + t b) \le t f(a) + (1-t) f(b), \quad 0 \lt t \lt 1\label{eq-def-convexity}\tag{30.1.1} \end{equation}$

🔗

A function is strictly convex if the inequality (30.1.1) is strict. Such a function is unimodal on any interval. (Can you find a unimodal function that is not convex?)

🔗

Also,

$f$ is called concave (in calculus, “concave down”) if the sign of inequality in (30.1.1) is reversed.