04-04 Partial optimization

Reminder: $C$가 convex set이고 $f$가 $(x,y)$에 대해 convex일때, $g(x)=\underset{y\in C}{min}f(x,y)$는 x에 대해 convex이다.

즉, 위의 성질에 의해 다변수 함수로 구성된 convex problem에서의 partial optimization이 가능하며 이 과정에서 convexity가 유지된다.

Example: hinge form of SVMs

Non-separable set에 대한 SVM 문제는 다음과 같이 정의된다.

$$\begin{array}{rlrl}& \underset{\beta ,{\beta }_0,\xi }{min}& & \frac{1}{2}\Vert \beta {\Vert }_2^2+C\sum _{i=1}^n{\xi }_i\\ & \text{subject to}& & {\xi }_i\ge 0,\\ & & & y_i(x_i^T\beta +{\beta }_0)\ge 1-{\xi }_i,\\ & & & i=1,..,n\end{array}$$

위의 제약조건들은 아래의 제약조건 하나로 표현될 수 있다.

$$\begin{array}{r}{\xi }_i\ge max\{0,1-y_i(x_i^T\beta +{\beta }_0)\}\end{array}$$

이때, $max\{0,1-y_i(x_i^T\beta +{\beta }_0)\}$는 ${\xi }_i$의 하한임을 이용하여 $\tilde{f}$를 얻을 수 있다.

$$\begin{array}{rl}\frac{1}{2}\Vert \beta {\Vert }_2^2+C\sum _{i=1}^n{\xi }_i& \ge \frac{1}{2}\Vert \beta {\Vert }_2^2+C\sum _{i=1}^{n}max(0,1-y_i(x_i^T\beta +{\beta }_0))\\ & =min\{\frac{1}{2}\Vert \beta {\Vert }_2^2+C\sum _{i=1}^n{\xi }_i|{\xi }_i\ge 0,y_i(x_i^T\beta +{\beta }_0)\ge 1-{\xi }_i,i=1,..,n\}\\ & =\tilde{f}(\beta ,{\beta }_0)\end{array}$$

그리고 아래와 같이 $\tilde{f}$를 objective function으로 사용함으로써 좀 더 간단한 형태로 solution을 얻을 수 있다. 주어진 문제에서 $\xi$가 제거되었고, 또한 constrained problem에서 unconstrained problem으로 변환되었다.

$$\begin{array}{r}\underset{\beta ,{\beta }_0}{min}\frac{1}{2}\Vert \beta {\Vert }_2^2+C\sum _{i=1}^{n}max\{0,1-y_i(x_i^T\beta +{\beta }_0)\}\end{array}$$