04-02 Convex solution sets

Convex solution set의 성질에 대해 알아보자.
\(X_{opt}\)를 다음과 같이 어떤 convex problem에 대한 solution의 집합이라고 하겠다.

\[\begin{aligned} X_{opt} = &\text{arg}\min_x &&f(x) \\ &\text{subject to} &&g_{i}(x) \leq 0, i = 1, .., m \\ &&&h_{j}(x) = 0, j = 1, .., r \\\\ \end{aligned}\]

Key property1

\(X_{opt}\)는 convex set이다.

Proof

\(x\), \(y\)가 solution일때,

1. Domain set \(D\)는 convex set이므로,
   \(0 \le t \le 1\)에 대해 \(tx+ (1-t)y \in D\)를 만족한다.
   
   
2. \(g_i, i=1,\dotsc,m\)와 \(h_j, j=1, \dotsc,r\)은 각각 convex, affine function이므로 아래 제약조건을 만족한다.
   
   \(\begin{aligned} g_{i}(tx + (1-t)y) \leq tg_i(x) + (1-t)g_i(y) \leq 0, \\ h_{j}(tx + (1-t)y) = th_j(x) + (1-t)h_j(y) = 0 \\ \end{aligned}\)
   
   
3. \(f\)는 convex function이므로 아래를 만족한다.
   
   \(\begin{aligned} f(tx+(1-t)y) &\leq tf(x) + (1-t)f(y) \\ &= tf^{\star} + (1-t) f^{\star} \\ &= f^{\star} \end{aligned}\)
   즉, \(tx + (1-t)y\) 또한 solution이다.

Geometric interpretation

Convex function에서의 local optimum은 곧 global optimum이기 때문에
복수의 element를 가진 solution set이 있다면 이는 아래와 같은 모양일 수 밖에 없다.

Key property2

\(f\)가 strictly convex이라면 solution은 unique하다. 즉, \(X_{opt}\)는 하나의 element만을 갖는다.

\(f\)가 strictly convex라는 것은 \(f\)가 다음과 같은 성질을 항상 만족한다는 것과 같다.

\[f(tx + (1-t)y) < tf(x) + (1-t)f(y),\] \[\text{where } 0 < t < 1, x \neq y, \text{ and } x, y \in \text{dom } f.\]

즉, \(f\)는 평평한 구간이 없는 아래로 볼록한 형태이며 \(f\)의 solution은 오직 하나이다.