Foundation of Nonlinear Optimization-3

Convex Function

Definition : Convex function

$f:\mathbb{R}^n \rightarrow \mathbb{R}$ is said to be convex .
If $\forall x, y \in \mathbb{R}^n, \;\; \lambda \in [0,1]$, then

$$
f(x + \lambda(y-x)) \leq (1-\lambda) f(x) + \lambda f(y)$$

Example

Lyapunov Function $x^T P x$

• 모든 convex function은 Global minima를 쉽게 찾을 수 있다.

Definition : Epi-Graph

$$
E_{pi}(f) \triangleq = \left\{
\begin{bmatrix}
x^o \\
x
\end{bmatrix}
\in \mathbb{R}^{n+1} | x^o \geq f(x)
\right\}$$

Example

Epi-Graph of $f:\mathbb{R} \rightarrow \mathbb{R}$, $f(x) = x^2$.

Lemma C-1

Suppose $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is convex, then Epi($f$) is a convex set

Proof is omitted (or HW)

Definition : Simplex

Simplex $[a_1, \cdots, a_{n+1}]$ : $a_1 \cdots a_n$ 이 꼭지점이 되어 이루어진 도형과 그 내부
It implies that $a \in \textit{int}(A)$, where $\textit{int}(A)$ is interior point of $A$, and $\textit{int}(A)$ is an open set.

Theorem C-1

Let $G$ be a convex set in $\mathbb{R}^n$, If $f : G \rightarrow \mathbb{R}$ is a convex, then f is continuous in $G$.

proof of Theorem C-1

Let $a \in G$, By Caratheodory theorem,

$$
\exists (n+1) \;\textit{simplex} [a_1, \cdots, a_{n+1}], a_i \in G, \;\; \textit{such that} \;\; a \in \textit{int}(A)$$

where $A$ is simplex. It implies that $\exists \delta > 0$ such that $a \in B^o(a, \delta) \subset \textit{int}(A)$ ( Obviously!!)
then $\forall x \in A$, $f(x) \leq \alpha$ . (그림 참조)

Since $A \subset G$, and $G$ is convex, $\exists \mu_i$ for $i=1, \cdots n+1$, such that $\sum_{i=1}^{n+1}\mu_i \alpha_i = x$, $\mu_i \geq 0$, $\sum_{i=1}^{n+1} \mu_i = 1$. Thus,

$$
f(x) = f(\sum_{i=1}^{n+1}\mu_i \alpha_i) \leq \sum_{i=1}^{n+1} \mu_i f(\alpha_i) \leq \alpha \sum_{i=1}^{n+1}\mu_i \tag{1}$$

(Obviolusly, Convex 이므로)

Pick any $x_o \in B^o(a, \delta)$. Let $z = x – x_0$, then $f_z(z) = f(x) – f(x_0)$
Since $B^o(a, \delta)$ is open, $\exists \lambda > 0$ such that $B(x^o, \lambda) \subset B(a, \delta)$ (Open set 이므로 이러한 Open Set 은 당연히 존재한다.)

이 상태에서 다음을 증명해야 한다. (Continuous의 정의에 따라)

$$
\textit{For any}\;\; \varepsilon > 0, \;\; \exists \rho > 0 \;\;\textit{such that}\;\;\left\| z \right\| < \rho \Rightarrow \left\| f_z(z) \right\| \leq \varepsilon$$ for any $\varepsilon > 0$, pick $z$ such that $\left\| \frac{z}{\varepsilon} \right\| < \lambda \Rightarrow \left\| z \right\| < \varepsilon \lambda$ ($\rho = \varepsilon \lambda$)

$$
f_z(z)=f_z\left( (1-\varepsilon) \cdot 0 + \varepsilon \frac{z}{\varepsilon} \right) \leq (1-\varepsilon) f_z(0) + \varepsilon f_z(\frac{z}{\varepsilon}) = \varepsilon f_z(\frac{z}{\varepsilon}) \leq 2 \alpha \varepsilon \tag{2}$$

(Since $f(x) \leq \alpha$, $f_z(z) = f(x) – f(x_0) \leq \left\| f(x) \right\| + \left\| f(x_0) \right\| \leq 2\alpha$ )

In addition,

$$
0 = f_z(0) = f_z \left( \frac{1}{1 + \varepsilon} z + \frac{\varepsilon}{1+\varepsilon} \cdot – \frac{z}{\varepsilon} \right) \leq \frac{1}{1+\varepsilon}f_z(z) + \frac{\varepsilon}{1+\varepsilon}f_z(-\frac{z}{\varepsilon}) \tag{3}$$

(Equation (1) 에서 당연)

방정식 (3)의 우측항은 결국

$$
0 \leq \frac{1}{1+\varepsilon}f_z(z) + \frac{\varepsilon}{1+\varepsilon}f_z(-\frac{z}{\varepsilon}) \Rightarrow -\varepsilon f_z(-\frac{z}{\varepsilon}) \leq f_z(z)$$

이므로

$$
-2\alpha \varepsilon \leq -\varepsilon f_z(-\frac{z}{\varepsilon}) \leq f_z(z) \tag{4}$$

방정식 (2), (4)에서

$$
-2\alpha \varepsilon \leq f_z(z) \leq 2\alpha \varepsilon \Rightarrow |f_z(z)| \leq 2\alpha \varepsilon$$

Q.E.D of THeorem C-1

Theorem C-2

$f$ is differentiable then $f$ is convex iff $\forall x, y \in \mathbb{R}^n$

$$
f(y) – f(x) \geq \langle \nabla f(x), (y-x) \rangle$$

Remind : Differentiable

$$
f(y) – f(x) = \int_0^1 \frac{\partial f(x+s(y-x))}{\partial x} (y-x) ds$$

Proof of theorem C-1

Proof of Necessity ($\Rightarrow$)

Since $f$ is convex i.e.

$$
f(\lambda x + (1-\lambda)y) \leq \lambda f(x) + (1-\lambda) f(y)$$

and $f$ is differentiable i.e.

$$
f(y) – f(x) = \int_0^1 \langle \nabla f(x + s(y-x)), y-x \rangle ds$$

그러므로 x, y 사이의 한 점 $\lambda x + (1-\lambda) y, \;\; \forall \lambda \in [0,1]$ 에 대하여

$$
\begin{align}
f(\lambda x + (1-\lambda) y) – f(x) &= \int_0^1 \langle \nabla f(x + s(\lambda x + (1-\lambda) y – x))), (1-\lambda)(y-x) \rangle ds \\
&= \int_0^1 \langle \nabla f(x + s(1-\lambda)(y – x)), (1-\lambda)(y-x) \rangle ds \\
&= (1-\lambda)\int_0^1 \langle \nabla f(x + s(1-\lambda)(y – x)), (y-x) \rangle ds
\end{align}$$

따라서 Convex 조건에서

$$
f(\lambda x + (1-\lambda) y) = f(x) + (1-\lambda)\int_0^1 \langle \nabla f(x + s(1-\lambda)(y – x)), (y-x) \rangle ds \leq \lambda f(x) + (1-\lambda) f(y)$$

it implies that

$$
(1-\lambda)\int_0^1 \langle \nabla f(x + s(1-\lambda)(y – x)), (y-x) \rangle ds \leq (1-\lambda) (f(y) – f(x)) \\
\Rightarrow \int_0^1 \langle \nabla f(x + s(1-\lambda)(y – x)), (y-x) \rangle ds \leq f(y) – f(x)$$

Let $\lambda \rightarrow 1$, then

$$
\int_0^1 \langle \nabla f(x), (y-x) \rangle ds \leq f(y) – f(x) \Rightarrow \langle \nabla f(x), (y-x) \rangle \int_0^1 ds \leq f(y) – f(x)$$

Q.E.D of Necessity

Proof of Suffciency ($\Leftarrow$)

$$
f(y) – f(x + \lambda(y-x)) \geq \langle \nabla f(x + \lambda(y-x)), (1-\lambda)(y-x) \rangle \tag{1}$$

$$
f(x) – f(x + \lambda(y-x)) \geq \langle \nabla f(x + \lambda(y-x)), -\lambda(y-x) \rangle \tag{2}$$

(식 (2)의 경우 방향이 반대이므로 $\lambda$에 마이너스가 붙었다.)

(1) $\times \lambda +$ (2)$\times (1-\lambda)$

$$
\lambda f(y) + (1 – \lambda) f(x) – \lambda f(x + \lambda(y-x)) – (1 – \lambda) f(x + \lambda(y-x)) \geq 0 \\
\Rightarrow \lambda f(y) + (1 – \lambda) f(x) \geq f(x + \lambda(y-x))$$

Convex 증명, 자동적으로 continuous 증명 그러므로 Differentiable 까지 증명
Q.E.D of Sufficiency

Theorem C-3

$f$ is twice continuosly differentiable, then $f$ is convex iff

$$
\frac{\partial^2 f(x)}{\partial x^2} \geq 0, \forall x \in \mathbb{R}^n$$

Definition : Semipositive definite

$f:\mathbb{R}^n \rightarrow \mathbb{R}$ 에 대하여

$$
\frac{\partial^2 f(x)}{\partial x^2} \geq 0, \forall x \in \mathbb{R}^n$$

이면 Semipositive definite이라 하며, 이는 $\forall x \in \mathbb{R}^n$ 에 대하여

$$
\langle x, \frac{\partial^2 f(x)}{\partial x^2} x \rangle \geq 0$$

을 의미한다.

Proof of theorem C-2

Proof of Necessity ($\Rightarrow$)

Since $f:\mathbb{R}^n \rightarrow \mathbb{R}$ is twice differentiable i.e.

$$
f(y) -f(x) = \langle \nabla f(x), y-x \rangle + \int_0^1 (1-s)\langle y-x, \frac{\partial^2 f}{\partial x^2}(x+s(y-x)) \left( y-x\right) \rangle ds$$

By Theorem C-2,

$$
0 \leq f(y) – f(x) – \langle \nabla f(x), y-x \rangle$$

Hence,

$$
\frac{f(y) – f(x) – \langle \nabla f(x), y-x \rangle}{\left\| y-x \right\|^2} \geq 0$$

Accordingly,

$$
\frac{f(y) – f(x) – \langle \nabla f(x), y-x \rangle}{\left\| y-x \right\|^2} = \int_0^1 (1-s) \langle \frac{y-x}{\left\| y-x \right\|}, \frac{1}{\left\| y-x \right\|} \langle y-x, \frac{\partial^2 f}{\partial x^2}(x+s(y-x)) \left( y-x\right) \rangle ds \geq 0$$

Let $ y \rightarrow x$, then $\frac{y-x}{\left\| y-x \right\|} = z$ is a normal vector. Therefore,

$$
\langle z, \frac{\partial^2 f(x)}{\partial x^2} z \rangle \int_0^1 (1-s) ds \geq 0 \;\;\Leftrightarrow \;\; \frac{1}{2} \langle z, \frac{\partial^2 f(x)}{\partial x^2} z \rangle \geq 0$$

Consequently, $\frac{\partial^2 f(x)}{\partial x^2}$ is Positive SemiDefinite.
Q.E.D of Necessity

Proof of Sufficiency ($\Leftarrow$)

Rewrite the twice differential as

$$
f(y) -f(x) – \langle \nabla f(x), y-x \rangle = \int_0^1 (1-s)\langle y-x, \frac{\partial^2 f}{\partial x^2}(x+s(y-x)) \left( y-x\right) \rangle ds$$

By Assunption, $\frac{\partial^2 f}{\partial x^2}(x+s(y-x)) \geq 0\;\; \forall \lambda \in [0,1]$. Thus,

$$
0 \leq \int_0^1 (1-s)\langle y-x, \frac{\partial^2 f}{\partial x^2}(x+s(y-x)) \left( y-x\right) \rangle ds = f(y) -f(x) – \langle \nabla f(x), y-x \rangle$$

It implis that

<

p class=”mathjax”>$$
f(y) -f(x) \geq \langle \nabla f(x), y-x \rangle$$

By Theorem C-2, If the above condifition is satisfied, then the function $f$ is convex.
Q.E.D of Sufficiency