[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을 찾을 수 있게 된다.

 

쉽게 말하면, Slater's condition을 만족하는 경우,

• dual problem으로도 optimal solution을 찾을 수 있으며,
• KKT conditions를 통해서도 optimal solution을 찾을 수 있다.

 

즉, Slater's condition을 만족하면 최적해를 구하기 위한 다양한 방법이 가능해진다.

 

Definition

우선 Standard form of Optimization이 다음과 같이 주어진다.

Equailty constraints와 Ineqaulity contraints를 가지고 있는 optimization problem (minimization의 경우)은 다음과 같이 표현된다.

$$\begin{aligned}&\text{minimize }f(\textbf{x}) \\ & \text{s.t:} \\ & g_i(\textbf{x}) \le 0, i=1,\dots,m \\ & h_j(\textbf{x})=0,j=1,\dots,k \end{aligned}$$

이같은 Optimization problem이 Slater's condition을 만족하려면, 다음을 만족시키는 $\textbf{x}^*$가 존재해야함.

1. 우선 Convex Optimization Problem이어야 함.
   • $f(\textbf{x})$는 $f:\mathbb{R}^n\to\mathbb{R}$이면서 convex function이어야 함.
   • 모든 $\forall i$에 대해서 $g_i(\textbf{x})$는 convex function이어야함.
   • 모든 $\forall j$에 대해서 $h_i(\textbf{x})$는 affine function이어야 함 : $h_i(\textbf{x})=A\textbf{x}+\textbf{b},\quad\text{ where } A \text{ is matrix and }\textbf{b}\text{ is a vector}$
2. 모든 $\forall i$에 대해서 $g_i(\textbf{x}^*) < 0$이 성립해야함. (등호가 없음.)
   • 만약 $g_i(\textbf{x})=A\textbf{x}+\textbf{b}$와 같은 affine function이라면, $g_i(\textbf{x}^*) \le 0$여도 됨.

 

Slater's condition 에 해당하는 convex optimization problem에서는 equality constraints와 inequality constraints를 만족하는 input $\textbf{x}$를 하나만 찾아도 strong duality가 성립하게 된다.