02-06-01 Dual cones

Dual cones

Dual cone은 cone과 쌍을 이뤄서 정의되며, 표기는 cone은 \(K\)로 dual cone은 \(K^∗\)로 한다. Dual cone도 cone이며 \(K\)의 convex 여부와 상관없이 \(K^∗\)은 항상 convex이다. 다음 식과 같이 dual cone은 set의 점 \(x\)와 내적을 했을 때 0보다 큰 점인 \(y\)의 집합으로 정의된다.

\[K^∗ = \{y \mid x^T y \ge 0 \text{ for all } x \in K\}\]

점 \(x\)와 점 \(y\)의 내적이 0보다 크려면 두 벡터 사이의 각도가 \(cos\theta \ge 0\)인 구간인 \(0 \le \theta \le 90\)과 \(270 \le \theta \le 360\)이 된다. 따라서, dual cone의 boundary는 cone의 boundary에서 supporting hyperplane을 만들었을 때 -normal vector의 방향으로 생성된다. 아래 그림을 보면 dual cone이 정의되는 구간을 확인할 수 있다. 결론적으로 dual cone의 구간은 cone의 원점에서 정의되는 모든 supporting hyperplane들의 -normal vector 방향의 구간임을 알 수 있다.

기하학적으로 \(y \in K^∗\)일 때 \(-y\)는 원점에서 \(K\)를 support하는 hyperplane의 normal이다. 다음 그림을 보면 왼쪽은 inward normal \(y\)를 갖는 halfspace가 cone \(K\)를 포함하므로 \(y \in K^∗\)이다. 오른쪽은 inward normal \(z\)를 갖는 halfspace가 cone \(K\)를 포함하지 않으므로 \(y \notin K^∗\)이다.

Dual cones examples

다음은 cone과 dual cone의 예들이다. 이 중 처음 세 개는 self-dual로 cone과 dual cone이 동일하다. 마지막 예는 \(l_\infty\) cone의 dual cone이 \(l_1\) cone임을 말하고 있다 반대로 \(l_1\) cone의 dual cone이 \(l_\infty\) cone이다.

• \[K = R^n_+, K^* = R^n_+\]
• \[K = S^n_+, K^* = S^n_+\]
• \[K = \{(x, t) \mid \left \Vert x \right \|_2 \le t \}, K^* = \{(x, t)\mid \left \Vert x \right \|_2 \le t \}\]
• \[K = \{(x, t) \mid \left \Vert x \right \|_1 \le t \}, K^* = \{(x, t) \mid \{\left \Vert x \right \| \} {\infty} \le t \}\]

\(l_2\) cone은 self-dual

아래 그림은 \(l_2\) cone이 self-dual임을 보여주고 있다. 즉, \(x \in K\)가 boundary 점일 때 \(x\)의 supporting hyperplane의 normal인 \(-y\)는 \(K\)의 경계와 정확히 일치하며, \(y\)는 dual cone \(K^∗\)의 경계가 되므로 cone \(K\)와 dual cone \(K^*\)는 일치한다.

\(l_\infty\) cone의 dual cone은 \(l_1\) cone

아래 그림은 \(l_\infty\) cone의 dual cone이 \(l_1\) cone임을 보여주고 있다. 즉, \(x \in K\)가 boundary 점일 때 \(x\)의 supporting hyperplane의 normal인 \(-y\)는 \(K\)의 내부로 들어가서 \(l_1\) cone의 경계와 일치하게 된다.