Karush-Kuhn-Tucker Condition
[Convex Optimization](https://texonom.com/convex-optimization-d3bdaf9012a34af18743ac995ca00366) [Lagrange Duality](https://texonom.com/lagrange-duality-8de2c3f1399e4765ba2543d4e8360eeb) 


### KKT Contition
Optimal Solution을 찾기 위한 [Necessary Condition](https://texonom.com/necessary-condition-b1f022e558bc41fc9136493dd6aff1a1) 
1. Primal feasibility: 모든 제한 조건(constraints)을 만족하는 변수 값(w*)을 찾아야 합니다.
2. Dual feasibility: Lagrange multiplier인 알파와 베타는 모두 0 이상이어야 합니다.
3. Complementary slackness: 알파와 각 제한 조건의 곱은 0이어야 합니다.
4. Stationarity: 목적 함수(objective function)를 w로 미분한 값이 0이어야 합니다.
알파와 베타가 KKT 조건을 만족하면 Primal problem에서도 KKT 조건을 만족한다는 것이 보장

### For the convex problem
5. f, g all convex, h [Affinity](https://texonom.com/affinity-6bba36af687f4be5adc4276ebc5a3d9a) 
6. constraints are all strictly feasible
7. **Dual complementarity condition** - alphas are all bigger than 0
8. **complementary slackness** - $\alpha^* g(w^*) = 0$
9. Stationarity - w derivation is 0 at that point 
10.  $p^* = d^* = L(w^*, \alpha^*, \beta^*)$
then
![](https://www.notion.so/image/https%3A%2F%2Fs3-us-west-2.amazonaws.com%2Fsecure.notion-static.com%2Fa2ab5119-aa49-40dc-ade6-e06257f51d3b%2FUntitled.png?table=block&id=ce29ebf7-9cca-4bd8-86f9-5cf6a17356c6&cache=v2)
Complementary slackness 때문에 부등호를 의미없게 하기 위해 g(w*)가 0이 된다





