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
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.