6-3. Quadratic Optimization Problem

---

< 목차 >

1. 용어정의
2. Quadratic optimization problem
   1. Solving a constrained optimization using Lagrange multipliers
   2. Comparison between the primal and dual problems

---

1. 용어정의

• Lagrange multiplier : 라그랑주 승수법, 제한조건이 있는 최적화 문제를 풀기 위한 방법으로 제한조건 내에서 주어진 함수의 극댓값과 극솟값을 찾는 것이다.

---

2. Quadratic optimization problem

2-1. Solving a constrained optimization using Lagrange multipliers

||w||에 관한 2차 최적화 문제는 위에서 주어진 constraint를 이용해서 Lagrange multipliers 로 다음과 같이 전개하여 풀어낼 수 있다.

 

 

이후,  maximum likelihood 과 같은 방식으로 w와 b에 관해 편미분하고, 두 항을 위의 식에 대입한다.

 

그러면 초기에 세웠던 L(w,b,a)를 아래와 같이 a에 관한 수식으로 표현할 수 있으며, 파란박스 영역에 존재하는 Mapping 간의 내적은 Kernel function으로 둘 사이의 유사성을 의미하는 것이다. 이를 'Dual problem' 이라고 정의한다.

 

전개된 L(a)는 "a_n ≥ 0" 라는 constraint을 만족해야하며, 이를 inequality constraint라고 하고 해당 조건을 만족하는 Optimization의 순서는 아래와 같다.

 

 

이때, (3) 과정에서 'S'는 support vector를 말하며, 최적화과정에서 (5) 에서 주어진 세 가지의 KKT 조건을 만족해야 하는데, 이는 모든 입력데이터에 대해 오직 support vector만 model 에 영향을 줄 수 있다는 것을 의미한다. 

2-2. Comparison between the primal and dual problems 

앞서 설명한 내용을 종합해보면, Primal problem 과 Dual problem은 동일한 문제의 Optimization에 대해 다른 표현을 가진다. Primal problem은 Non-linear mapping function의 차원인 M개의 미지수가 존재하며, Dual problem은 N개 데이터의 수에 따라 N개의 미지수가 필요하다.

 

 

즉, 일반적인 경우에 데이터의 크기는 M < N 이기때문에, Dual problem 이 계산적으로 더 복잡하다.

---