Support Vector Machine 이해를 위한 Lagrangian Dual Problem 이해해보기
최적화 수업을 듣지 않고 어디까지 이해할 수 있을까...
Optimization with inequality constraints 다음과 같은 최적화 문제를 생각해보자.
$$ \begin{align*} \textbf{Primal Problem:}\quad minimize &\quad f_0(\mathbf{x}) \quad (\mathbf{x} \in \mathbb{R}^n, ;domain;\mathcal{D})\\\
s.t. &\quad f_i(\mathbf{x}) \leq 0, \quad ^\forall i \in [m] \\\
&\quad h_i(\mathbf{x})=0 \quad ^\forall i \in [p] \end{align*} $$
우리가 익숙한 Lagrange Multiplier에서는 제약식이 등호로만 되어있었지만, 이제는 부등식이 추가되었다. 이러한 경우 부등호 조건식 $f_i(\mathbf{x})$를 inequality constraints, 등호 조건식 $h_i(\mathbf{x})$를 equality constraints라고 한다.
부등호 조건이 들어간 최적화 문제를 푸는 것은 참 막막한 일이다.
