Mono-objective optimization

The mono-objective optimization is the standard optimization problem, and is widely treated in literature (see [13] for an introduction). With this preliminary statement, here are reported some results, useful to find a solution for the problems 4.2, 4.3.

The existence of the minimum (at least one) is granted by the Weierstrass Theorem⁷, but these minimums can be local or global:

Definition 5.7 (Local Minimum)   The point $\mathbf{x^\star} \in X$ is a local (or relative) minimum of the function $f$ iff
$\exists\epsilon > 0\colon f(\mathbf{x}) \geq f(\mathbf{x^\star}) \wedge \forall \mathbf{x}\in X \quad \lvert\mathbf{x} - \mathbf{x^\star}\rvert < \epsilon$.

Definition 5.8 (Global Minimum)   The point $\mathbf{x^\star} \in X$ is a global (or absolute) minimum of the function $f$ iff $f(\mathbf{x}) \geq f(\mathbf{x^\star}) \;\forall \mathbf{x}\in X$.

Definition 5.9 (Feasible direction)   $\mathbf{d}\in\mathbb{R}^n$ is a feasible direction if $\exists\alpha^\star > 0\colon \mathbf{x}+\alpha\mathbf{d}\in X,\, \forall\alpha\colon 0 \leq \alpha \leq\alpha^\star$

In an intuitive manner the concept of feasible direction is useful to solve the problem of minimization: we search all the direction in which the function $f$ is decreasing.

Lemma 5.10 (First order necessary condition)   If $\,\mathbf{x}^\star\in X$ is a minimum of $f\in C^1$ then $\forall\mathbf{d}\in\mathbb{R}^n$, where $\mathbf{d}$ is an feasible direction, $\mathbf{d}^T\cdot\nabla f(\mathbf{x}^\star) \geq 0$, where $(\cdot)$ has the usual definition of scalar product in the space $\mathbb{R}^n$.

Corollary 5.10.1   If $\,\mathbf{x}^\star\in X$ is an internal point of $X$, then $\mathbf{d}^T\cdot\nabla f(\mathbf{x}^\star) = 0$

Lemma 5.11 (Second order necessary condition)   If $\,\mathbf{x}^\star\in X$ is a minimum of $f\in C^2$ then $\forall\mathbf{d}\in\mathbb{R}^n$, where $\mathbf{d}$ is an feasible direction,

i)

$\mathbf{d}^T\cdot\nabla f(\mathbf{x}^\star) \geq 0$;

ii)

if $\,\mathbf{d}^T\cdot\nabla f(\mathbf{x}^\star) = 0$ then $\mathbf{d}^T\cdot\nabla^2f(\mathbf{x}^\star)\cdot\mathbf{d}\geq 0$

Corollary 5.11.1   If $\mathbf{x}^\star\in X$ is an internal point of $X$, then

i)

$\mathbf{d}^T\cdot\nabla f(\mathbf{x}^\star) = 0$

ii)

$\mathbf{d}^T\cdot\nabla^2f(\mathbf{x}^\star)\cdot\mathbf{d}\geq 0$

The conditions of the corollary 4.1.1 are necessary and sufficient conditions for the existence of the minimum (local). In order to have some information about the existence of a global minimum, the theory of convex functions must be very briefly reported.

Definition 5.12 (Convex function)   The function $f\colon X \rightarrow Y$, where $X$ is a convex set⁸, is convex if $\forall\mathbf{x}_1,\mathbf{x}_2\in X \wedge \forall\alpha\colon 0 \leq \alpha\leq 1$

$$f(\alpha\mathbf{x}_1 + (1-\alpha)\mathbf{x}_2) \leq \alpha f(\mathbf{x}_1)+ (1-\alpha)f\mathbf{x}_2)$$ (5.17)

If in the equation (4.1) the sign $<$ applies, then the function is said to be strictly convex.

Another way to write the equation (4.1) is:

Lemma 5.13   The function $f\in C^1\colon X\rightarrow Y$ is convex over a convex set $X$ if

$$f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x}) f(\mathbf{y}-\mathbf{x}),\, \forall \mathbf{y},\mathbf{x}\in X$$

or, if $f$ is twice derivable,

Lemma 5.14   The function $f\in C^2\colon X\rightarrow Y$ is convex over a convex set $X$ if

$$\nabla^2 f(\mathbf{x}) \geq 0,\, \forall \mathbf{x}\in X$$

The convex functions are a very useful mathematical tool in the class of optimization problem, mainly for the next two results:

Theorem 5.15   If $f\colon X \rightarrow Y$ is convex over a convex set $X$, the set $A$ of the minimum of the function is convex, and every local minimum is also a global minimum.

Theorem 5.16   If $f\in C^1\colon X\rightarrow Y$ is convex over a convex set $X$, and if $\exists \mathbf{x}^\star\in X\colon \forall \mathbf{x}\in X \nabla f(\mathbf{x}^\star)(\mathbf{x}-\mathbf{x}^\star)\geq 0$, then $\mathbf{x}^\star$ is a global minimum of $f$ over $X$.

The theorem 4.16 also implies that the conditions of the lemma 4.10 and corollary 4.10.1 (first order conditions) are both necessary and sufficient conditions for the existence of a global minimum.