Seonglae ChoKKT Contition
Optimal Solution을 찾기 위한 Necessary Condition
- Primal feasibility: 모든 제한 조건(constraints)을 만족하는 변수 값(w*)을 찾아야 합니다.
- Dual feasibility: Lagrange multiplier인 알파와 베타는 모두 0 이상이어야 합니다.
- Complementary slackness: 알파와 각 제한 조건의 곱은 0이어야 합니다.
- Stationarity: 목적 함수(objective function)를 w로 미분한 값이 0이어야 합니다.
알파와 베타가 KKT 조건을 만족하면 Primal problem에서도 KKT 조건을 만족한다는 것이 보장
For the convex problem
- f, g all convex, h Affinity
- constraints are all strictly feasible
- Dual complementarity condition - alphas are all bigger than 0
- complementary slackness -
- Stationarity - w derivation is 0 at that point
then
Complementary slackness 때문에 부등호를 의미없게 하기 위해 g(w*)가 0이 된다