[수학] Convex function

Convex function의 정의

convex function의 정의는 다음과 같다.

 

$\text{A function }J:D\rightarrow \mathbb{R}\text{ is convex if }D \text{ is a convex set and for any two points }z_{1},z_{2}\in D$

$J(\lambda z_{1}+(1-\lambda) z_{2}) \leq \lambda J(z_{1})+(1-\lambda) J(z_{2})\; \forall \lambda \in [0,1]$

 

여기서 중요한 점은 convex function은 반드시 domain($D$)이 convex set이어야 한다는 것이다.

 

Convex function의 example

 

1. $J(z)=a^{\top}z+b$

 

affine mapping은 convex이자 concave function이다.

convex임을 증명하려면 정의가 성립하는지 따지면 되는데

 

$$J(z) = {a^T}(\lambda {z_1} + (1 - \lambda ){z_2}) + b$$

$$=\lambda {a^T}{z_1} + \lambda b + (1 - \lambda ){a^T}{z_2} + (1 - \lambda )b=\lambda J(z_1)+(1-\lambda)J(z_2)$$

 

2. $J(z)=\|z\|$

 

이 함수는 norm의 성질을 이용하여 증명할 수 있다.

 

$\| \lambda z_{1} + (1-\lambda) z_{2}\| \leq \lambda\|z_{1}\| + (1-\lambda) \|z_{2}\|$

$\because \|a+b\| \leq \|a\|+\|b\|$

 

3. $J(z)=z^{\top} Q z \; \text{ where }Q\geqslant 0$

 

$J(z) = ( \lambda z_{1} + (1-\lambda)z_{2})^{\top} Q ( \lambda z_{1} + (1-\lambda)z_{2}) \leq \lambda z_{1}^{\top}Qz_{1} + (1-\lambda) z_{2}^{\top}Qz_{2}$인지 확인해야 한다.

 

$$\begin{array}{l}{\lambda ^2}z_1^Q{z_1} + (1 - {\lambda ^2})z_2^Q{z_2} + 2\lambda (1 - \lambda )z_1^Q{z_2} \le \lambda z_1^Q{z_1} + (1 - \lambda )z_2^Q{z_2}\\  - \lambda (1 - \lambda )(z_1^Q{z_1} + {z_2}Q{z_2} + 2z_1^Q{z_2}) \le 0\\  - \lambda (1 - \lambda ){({z_1} - {z_2})^}Q({z_1} - {z_2}) \le 0 \end{array}$$

 

Q가 semi-positive definite이므로 마지막 식이 성립한다. 즉, convex function 정의를 만족한다.

 

Convex function의 중요한 성질

 

Local minimum of convex function is a global minimum.

 

이에 대한 증명은 proof by contradiction으로 증명가능하다고 알려져있다.

 

$\text{optimal solution :}z^* \Rightarrow J(z^*)$

$J(z^*)$는 optimal value가 된다.

 

위의 명제에 대한 모순을 만들기 위해

$J(x) < J(z^*)$를 만족하는 $x$가 있다고 하자. 즉, 이 $x$ 역시 또다른 local minimum인 셈이다.

이러한 $x$가 존재하는 것이 모순임을 밝히면 증명이 가능해진다.

 

그러면 $y = \lambda x +(1-\lambda)z^* \; \lambda \in [0,1]$인 점이 있을 때

convex function 정의에 의해

$J(y) \leq \lambda J(x)+(1-\lambda) J(z^*) < \lambda J(z^*)+(1-\lambda) J(z^*)=J(z^*)$가 성립한다.

 

그런데 $\| y-z^*\|<r \; r\ll 1$라는 특정 ball 안에서 local minimum인 $z^*$는 $J(y)\geq J(z)$를 만족해야하므로

위의 결론($J(y) < J(z^*)$)와 모순이 된다.

 

따라서 $x$는 존재하지 않고, convex의 local minimum은 global minimum이다.

 

그런데 이러한 global minimum이 unique한가? => 유일성은 보장되지 않는다.