📂함수

일반적인 컨벡스 함수의 정의

정의

벡터공간 $V$ 에서 정의된 함수 $f : V \to \mathbb{R}$ 가 모든 $\mathbf{x}, \mathbf{y} \in V$ 와 모든 $t \in [0,1]$ 에 대해 다음을 만족하면 컨벡스 함수^{convex Funciton}라 한다. $$f \left( (1-t) \mathbf{x} + t \mathbf{y} \right) \le (1-t) f \left( \mathbf{x} \right) + t f \left( \mathbf{y} \right)$$

설명

사실 학부수준 이상의 수학을 공부하게 되면 볼록이나 오목이라는 표현은 물론, 컨벡스^convex가 아닌 컨케이브^concave도 사용하지 않게 된다. 어지간하면 모든 개념을 컨벡스로 통일하며, 컨벡스만을 생각한다. 위에서 소개된 컨벡스 함수는 유클리드 공간 $X = \mathbb{R}$ 에서 정의된 볼록함수의 일반화다.

예시

근의 집합이 포물면을 이루는 $f(x,y) := x^{2} + y^{2}$ 은 컨벡스 함수고, 그 값이 최소가 되는 점은 $(x,y) = (0,0)$ 이다.

정리

컨벡스 집합에서의 컨벡스 함수의 최적해

$f : \mathbb{R}^{n} \to \mathbb{R}$ 이 미분가능한 컨벡스 함수고, 컨벡스 집합 $C \subset \mathbb{R}^{n}$ 이 컨벡스 집합이라 하면 다음 둘은 동치다.

• $\mathbf{x}^{\ast} \in C$ 는 $C$ 에서 $f$ 를 최소화하는 최적해다.
• 모든 $\mathbf{x} \in C$ 에 대해 $$\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0$$

증명 ¹

$(\implies)$

$$\mathbf{x}(t) := \mathbf{x}^{\ast} + t \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \in C \qquad , t \in [0,1]$$ $C$ 는 컨벡스 집합이라 가정했으므로, 임의의 $\mathbf{x} \in C$ 와 $\mathbf{x}^{\ast}$ 사이의 어떤 내분점 $\mathbf{x}(t)$ 는 위와 같이 나타낼 수 있다. 한편

• $\mathbf{x}^{\ast} = \argmin_{\mathbf{x} \in C} f$ 이므로 모든 $\mathbf{x} \in C$ 에 대해 $f \left( \mathbf{x}(t) \right) - f \left( \mathbf{x}^{\ast} \right) \ge 0$ 이고
• $f \left( \mathbf{x}(t) \right)$ 의 $t = 0$ 에서의 편미분계수는 연쇄법칙에 따라 $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right)$ 이므로

$$\begin{align*} & \nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \\ =& \left[ {{ \partial } \over { \partial t }} f \left( \mathbf{x} (t) \right) \right]_{t = 0} \\ =& \lim_{t \to 0} {{ f \left( \mathbf{x} (t) \right) - f \left( \mathbf{x}^{\ast} \right) } \over { t }} \\ \ge & 0 \end{align*}$$ 즉 $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0$ 을 얻는다.

---

$(\impliedby)$

$$f \left( (1-t) \mathbf{z} + t \mathbf{y} \right) \le (1-t) f \left( \mathbf{z} \right) + t f \left( \mathbf{y} \right)$$ 의 양변을 $t$ 로 미분해보면 $$\left( - \mathbf{z} + \mathbf{y} \right) \nabla f \left( (1-t) \mathbf{z} + t \mathbf{y} \right) \le - f \left( \mathbf{z} \right) + f \left( \mathbf{y} \right)$$ 이므로, $t = 0$ 일때 다음을 얻는다. $$f \left( \mathbf{z} \right) + \nabla f \left( \mathbf{z} \right) \left( \mathbf{y} - \mathbf{z} \right) \le f \left( \mathbf{y} \right)$$ 가정에서 $\nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \ge 0$ 이므로 $\mathbf{y} = \mathbf{x}$ 와 $\mathbf{z} = \mathbf{x}^{\ast}$ 에 대해 다음을 얻는다. $$\begin{align*} & f \left( \mathbf{x}^{\ast} \right) + 0 \\ \le & f \left( \mathbf{x}^{\ast} \right) + \nabla f \left( \mathbf{x}^{\ast} \right) \left( \mathbf{x} - \mathbf{x}^{\ast} \right) \\ \le & f \left( \mathbf{x} \right) \end{align*}$$ 즉 $f \left( \mathbf{x}^{\ast} \right) \le f \left( \mathbf{x} \right)$ 인데, 이는 모든 $\mathbf{x} \in C$ 에 대해 성립하므로 $\mathbf{x}^{\ast}$ 는 $C$ 에서 $f$ 의 최소해가 된다.

■