Supplements 살펴보기
convex set의 예제와 특징, convexity를 보존하는 연산, convex function에 대해서 배워본다.
Convex sets
Linear combination에 계수가 양수이면서 계수의 합이 1이되도록 하는 것이 Convex combination이다. 그 결과는 Convex hull이 된다.
Examples
Polyhedron은 Affine space의 부등식형태인데 A의 모든 row에 대해 \(a_i^T x \le b_i\)라는 것이다.
이는 Halfspace의 intersection을 의미한다.
\(Ax \le b,Cx=d\) 도 polyhedron인데 \(Cx=d\)를 \(Cx \le d, Cx \ge d\)로 나타낼 수 있기 때문이다. 두번째 부등식은 \(-Cx \le -d\)가 된다.
Simplex는 점들이 affinely independent할 때의 점들 \(\{ x_0, ... x_k \}\)의 convex combination이다. 이는 polyhedra의 special case이다. (affinely inedependent는 각 point의 차가 linearly independent한것. 어떤 두 점을 잇는 직선 상에 다른 점이 존재해선 안됨.)
고전적인 예제는 probability simplex이다.
\[convex\{e_1,...e_n\}=\{w : w \ge 0, 1^T w = 1\}\]Norm cone은 원뿔모양이다.
Normal cone은 매우 중요한데 sub-gradient나 KKT 등을 얘기할 때 필요하다. 정의가 살짝 어렵지만, C상의 어떤 점 x에 대해 다른 어떤 C상의 점 y보다 내적을 했을 때 같거나 더 큰 경우는 C의 곡면상의 normal vector일 때이다. C는 non-convex해도 되고, 어떠한 형태라도 normal cone은 convex하다.
positive semi definite: all eigenvalues are >=0, \(a^T X a \ge 0\)
2 by 2 symmetric matrix를 예로 들어보면 element가 3개인데, positive semi definite한 symmetric matrix를 그려보면 원뿔 모양이다.
Key properties
Separating hyperplane theorem
Supporting hyperplane theorem
Operations preserving convexity
Intersection
Scaling and translation
Affine images
Affine preimages
Same, for convex functions
Strongly convex -> quadratic 부분을 제거해도 convex하다는것. 최소한 2차만큼은 굽어있다는 것이다.