strong duality

[Math] Duality (쌍대성) 이란 : Optimization에서

요약 optimization에서 Duality 는 primal problem과 dual problem의 관계를 의미함. 이를 이용하여, 원래 최적화(minimization ro maximization)해야 할 문제인 primal problem을 직접 푸는 대신에, duality를 이용하여 이에 해당하는 dual problem을 구하고, 해당 dual problem이 보다 쉽게 풀리는 경우, 이를 풀어서optimal solution 및 optimal value를 구할 수 있다. Duality에는 Weak Duality 관계와 Strong Duality 관계 두가지 경우가 있으며 각각의 경우에 따라 dual program을 활용하는 방식이 조금 차이가 있다. Weak duality relationship의 ..

[Math] Slater's Condition

Slater's condition은 Strong Duality의 Sufficient Condition으로 유명하고, 동시에, Slater's condition을 만족하는 경우에는 KKT가 necessary condition이 되기 위해 선행적으로 요구되는 Regularity Condtion이 성립된다는 성질을 가지고 있는 조건임. Slater's condition은 convex optimization인 경우에만 성립되는 조건인데, KKT conditions가 convex optimization에서는 necessary sufficient condition이 되기 때문에, 결국 Slater's condition을 만족할 경우, KKT conditions를 통해 optimal solution을 찾을 수 있게 ..