Optimization Theory (Convex Sets)

Optimization Problem

이번 학기에 최적화 이론이라는 수업을 듣게 되었는데, 중간고사 시험공부를 위해 리뷰 대신 남기려고 합니다. 최적화 이론 수업 내용은 굉장히 어렵지만, 그래도 배우는 게 많아 다른 연구원들도 관심이 있다면 다른 학기에 수강해보시는 것을 추천드립니다. 

이 글은 수업에서 배운 내용을 정리겸 제가 복습하는 식으로 작성하도록 하겠습니다. 글은 아마도 중간고사 범위를 다 커버하기 전까지는 계속해서 작성할 것 같습니다. 최대한 저의 이해도를 바탕으로 깊이 있게 작성해보려고 노력하였지만, 내용 자체가 워낙 어려워서 설명이 부족해 보이는 부분은 양해 부탁드리겠습니다.

일단 최적화 이론 자체는 응용분야가 상당히 많습니다. 신호처리나 제어공학, 통신 시스템 등 다양한 분야에서 사용이 될 수 있지만, 머신러닝/딥러닝에서도 최적화는 많이 사용이 되죠. 다양한 Optimization problem들이 있지만 이 수업에서 집중적으로 다루는 문제는 Convex Optimization입니다. 우선 벤 다이어그램을 하나 보도록 하겠습니다.

우리가 일반적으로 머신러닝/딥러닝에서 마주하게 되는 최적화 문제는 NonConvex 문제에 해당합니다. 신경망 내부에는 다양한 연산들이 존재하고 그로 인해 만들어지는 Loss Landscape는 Convexity를 가지기 힘듭니다. 그럼에도 불구하고 Convex Optimization을 배워야 하는 이유는 우리가 잘 알고 있는 Convex Optimization을 조금 변형하여 우리가 풀고 싶은 문제로 동일하게 만들 수 있고(Equivalent problem) 몇몇 Non-Convex Problem을 Convex Problem으로 근사할 수 있기 때문입니다.

Convexity가 보장되면 최적화 관점에서 무엇이 좋을까요? Local Minima = Global Minima라는 것을 무조건 보장할 수 있기 때문입니다. 이것에 대한 증명은 이번 글이 아니라 추후에 작성되는 글에서 다뤄질 것 같습니다. 아무튼 최적화 입장에서 Convexity가 보장되면 문제를 쉽게 풀 수 있기 때문에 Convex Optimization이 최적화 이론에서 중요하게 다뤄지는 것 같습니다.

그럼 이제 본격적으로 시작해보도록 하겠습니다. 이번글에서 다룰 내용은 Convex Set에 대한 이야기로 최적화에 대한 내용은 아닙니다. 본격적인 최적화 내용을 이해하기 위한 준비 운동이라 보면 될 것 같네요.

Lecture 2 : Convex Sets

Affine and Convex Sets

우선 Line과 Line segment가 무엇인지부터 알아보도록 하겠습니다.

• Line : y=\theta x_{1}+(1-\theta )x_{2},\theta \in R
• Line Segment : y=\theta x_{1}+(1-\theta )x_{2},\theta \in [0,1]

Line은 두 Point를 지나면서 무한하게 펼쳐지는 직선입니다. Line Segment는 두 Point를 이어주는 선분이죠. \theta 값을 조정하면서 직선이나 선분의 모든 값을 만들 수 있기 때문에 정의는 저렇게 선형 결합 꼴로 나와있습니다. 여기서부터 Affine Set과 Convex Set의 정의가 출발하게 됩니다.

Affine Sets

• 어떤 집합 C가 있다고 가정할 때 임의의 두 point 간 line 역시 집합 C에 포함된다면 그 집합은 affine set이라 부릅니다.

• x_{1},x_{2}\in C,\theta \in R, \theta x_{1}+(1-\theta )x_{2}를 만족하면 affine Set이라 볼 수 있습니다.

직선이나 평면 전체는 affine set이라 볼 수 있습니다. 하지만 원이나 타원, 삼각형 등은 affine 하다고 볼 수 없습니다. 기본적으로 affine set은 무한한 domain을 가져야만 성립이 될 수 있다고 보면 됩니다. 직선이 affine 한 이유는 직선 상 두 점을 어떻게 선택해도 만들어지는 line은 그 직선 자체가 되기 때문에 집합에 포함된다고 볼 수 있습니다. 평면이 affine 한 이유는 평면 상 어느 두 점을 선택해도 만들어지는 그 line은 평면 내에 존재하기 때문입니다.

우리가 보통 Convex 하다고 알고 있는 원이 affine 하지 않은 이유는 원 내부에 어떠한 두 점을 선택했을 때 만들어지는 line은 원 밖을 벗어나기 때문입니다. 아마 이 정도면 다들 affine set에 대해서 감을 잡을 수 있을 것 같습니다.

Affine combination

• \theta_{1} x_{1}+\cdots +\theta_{k} x_{k},\sum^{k}_{i=1} \theta_{k} =1를 affine combination이라 부릅니다. 단순한 선형결합과 조금 다른 점은 앞의 계수들의 총 합이 1이 되어야 한다는 constraint가 붙는다는 점 입니다.

• 따라서 affine set은 그 set 안에 있는 모든 point들 간의 affine combination을 포함하게 됩니다. 그 set 안에서 어떤 point를 잡고 affine combination을 해도 그 set안에 포함될 수 밖에 없다는 구조라 보면 됩니다.

Affine hull

• 예를 들어 affine set이 아닌 그냥 특정한 집합 C 있다고 가정해보겠습니다. 그 Set 안에 있는 모든 affine combination들의 합집합을 우리는 affine hull이라 부르고 Set C를 포함하는 가장 최소의 affine set 입니다.

• 수식으로는 affC=\{ \theta_{1} x_{1}+\ldots +\theta_{k} x_{k}|x_{1},\ldots x_{k}\in C,\theta_{1} +\ldots +\theta_{k} =1\} 이렇게 정의가 됩니다.

이따 바로 뒤에서 Convex hull이 무엇인지 알아볼 것인데 그때 그림을 통해서 본다면 더욱 이해가 쉽기 때문에 여기서는 이 정도로 서술하고 다음으로 넘어가겠습니다.

Convex Sets

• 어떤 집합 C가 있다고 가정할 때 임의의 두 point 간 line segment 역시 집합 C에 포함된다면 그 집합은 affine set이라 부릅니다.

• x_{1},x_{2}\in C,\theta \in R, \theta x_{1}+(1-\theta )x_{2}를 만족하면 Convex Set이라 볼 수 있습니다.

• 따라서 모든 Affine Set은 Convex Set에 해당합니다. Affine Set에서 두 Point간 Line segment는 무조건 포함되기 때문입니다. 하지만 역은 성립하지 않습니다. 모든 Convex Set이 Affine 한 것은 아니죠.

몇 가지 Convex set과 Non-Convex set을 한번 그림으로 보도록 하겠습니다.

그냥 집합 안에 두 점을 임의로 잡아보고 두 점을 이어주는 선분을 그려봤을 때 그 선분 전체가 원래 집합 안에 포함된다면 Convex set 아니면 Non-Convex set입니다. 마지막 그림은 Closed Set이 아니라 line segment가 포함이 안 되는 부분이 있어서 Non-Convex라 보면 됩니다.

Convex Combination

• \theta_{1} x_{1}+\cdots +\theta_{k} x_{k},\sum^{k}_{i=1} \theta_{k} =1를 convex combination이라 부릅니다. affine combination과 조금 다른 점은 모든 계수들이 0 이상이 되어야 한다는 constraint가 추가로 붙는다는 점 입니다.

• 동일하게 Convex set은 그 set 안에 있는 모든 point들 간의 convex combination을 포함하게 됩니다. 그 set 안에서 어떤 point를 잡고 convex combination을 해도 그 set안에 포함될 수 밖에 없다는 구조라 보면 됩니다.

Convex hull

• 예를 들어 convex set이 아닌 그냥 특정한 집합 C 있다고 가정해보겠습니다. 그 Set 안에 있는 모든 convex combination들의 합집합을 우리는 convex hull이라 부르고 Set C를 포함하는 가장 최소의 convex set 입니다.

Convex hull이 무엇인지 간단하게 그림을 통해서 알아보도록 하겠습니다.

왼쪽 그림을 봤을 때 원래 집합 C가 점들로 구성된 집합이라 가정했을 때 집합 C를 포함하는 가장 작은 Convex Set은 왼쪽 오각형과 같습니다. 오른쪽 그림을 봤을 때 원래 집합 C는 움푹 파인 형태를 가진 집합이라 했을 때 C를 포함하는 가장 작은 Convex Set은 오른쪽 도형과 같습니다. Convex hull을 보면 알겠지만 Convex Set이라는 것은 직관적으로 파악할 수 있을 것 같습니다. Affine hull도 이러한 개념으로 생각하면 될 것 같습니다.

Cones

• 어떤 Cone이라는 것은 임의의 point를 가지고 양의 스칼라 실수배를 취해도 여전히 그 집합에 포함되었을 때 Cone이라 정의 됩니다.

• 여기서 Convex Cone은 한발 더 나아가 양의 스칼라 실수배와 덧셈에 닫혀있는 집합이라 보면 됩니다. 수식으로는 다음과 같습니다. \theta_{1} x_{1}+\theta_{2} x_{2}\in C,0\leq \theta_{1} ,\theta_{2} 

• Convex Set과 비교했을 때, 모든 계수들의 합이 1이어야 한다는 constraint가 사라졌다고 보면 됩니다. 따라서 이 집합은 무한한 영역을 가지게 됩니다.

• 원점으로 뻗어나가는 직선들이 만들어내는 영역이라 보면 됩니다. 그래서 항상 원점을 포함해야 합니다. 그림을 통해 알아보도록 하겠습니다.

\theta_{1} x_{1}+\theta_{2} x_{2}\in C,0\leq \theta_{1} ,\theta_{2}  이것을 이해해보면 결국 저러한 집합이 나올 수밖에 없다는 것을 알 수 있습니다. \theta_{2}가 0이라면 원점으로부터 x_{1}을 관통하는 무한한 직선을 만들 수 있습니다. 반대로 \theta_{1}가 0이라면 원점으로부터 x_{2}을 관통하는 무한한 직선을 만들 수 있습니다.

이 두 집합을 combination 한다면 그 사이에 포함되는 모든 값들을 적절히 만들어낼 수가 있겠죠. 그렇기 때문에 저러한 콘(?) 형태의 모습이 나오게 됩니다.

Conic Combination

• \theta_{1} x_{1}+\cdots +\theta_{k} x_{k},\sum^{k}_{i=1} \theta_{k} =1를 convex combination이라 부릅니다. convex combination과 조금 다른 점은 모든 계수들의 합이 1이어야 한다는 constraint가 사라졌다는 점 입니다.

• 동일하게 Convex cone set은 그 set 안에 있는 모든 point들 간의 conic combination을 포함하게 됩니다. 그 set 안에서 어떤 point를 잡고 conic combination을 해도 그 set안에 포함될 수 밖에 없다는 구조라 보면 됩니다.

Conic hull

• 예를 들어 conic set이 아닌 그냥 특정한 집합 C 있다고 가정해보겠습니다. 그 Set 안에 있는 모든 conic combination들의 합집합을 우리는 conic hull이라 부르고 Set C를 포함하는 가장 최소의 convex cone set 입니다.

마지막으로 Conic hull이 무엇인지 간단하게 그림을 통해서 알아보도록 하겠습니다.

Convex Cone set을 잘 이해했다면 conic hull이 왜 저런 모양을 가지게 되는지는 바로 이해하실 수 있으리라 생각이 듭니다. 자 그렇다면 기본이 되는 구조에 대해서는 이제 알아보았고 조금 더 응용된 예시를 한번 살펴보도록 하겠습니다.

Convex Set Examples

Examples of convex sets

• empty set, any single point, whole space R^{n}등은 모두 affine set 입니다. 따라서 convex set 입니다. 직관적으로 받아들일 수 있을 것 같네요.

• 임의의 line은 모두 affine set입니다. 특히 원점을 지나는 직선은 vector space라 볼 수 있고 따라서 convex cone 입니다. vector space로 정의 되기 위해서는 원점을 꼭 포함해야한다는 것은 아마 선형대수학때 배웠으리라 생각이 들고 원점을 포함해서 무한한 영역을 가로지르기 때문에 Convex cone 입니다.

• 임의의 line segment는 convex 하지만 affine이 될 수는 없습니다.

• 임의의 subspace는 affine 하면서 동시에 convex cone 입니다. subspace의 정의 자체가 Linear combination에 갇혀 있는 집합이기 때문에 subspace의 정의만 잘 알고 있다면 이해할 수 있을 것 같습니다.

Hyperplane and Halfspaces

Hyperplane은 초평면으로 우리가 상상할 수 없는 초공간 내에서 정의되는 Linear 한 space라 보면 됩니다. 2차원 평면에서 정의가 된다면 직선, 3차원 공간에서 정의가 된다면 평면… 이런 식으로 말이죠. 정의 자체는 간단합니다.

• \{ x|a^{T}x=b\} ,a\in R^{n},a!=0,b\in R

여기서 a는 Hyperplane의 법선벡터로 평면 내부에 존재하는 모든 벡터와 수직의 관계를 이루는 중요한 벡터입니다. 평면의 방향을 결정한다고 볼 수도 있죠. 그 다음으로 b는 원점으로부터 평면이 어느 정도 offset을 가지는 지 결정해주는 상수 값입니다.

Hyperplane을 2차원으로 단면화를 했을 때는 저렇게 보이겠죠. hyperplane은 affine set입니다. 고로 convex set이지요. 그리고 hyperplane은 전체 공간을 이등분으로 나누는 어떠한 경계 역할을 수행합니다. 평면 아래와 위로 나뉘겠죠? 이때 나눠지는 공간들을 우리는 Halfspace라 정의합니다.

• \{ x|a^{T}x\leq b\} ,\{ x|b\leq a^{T}x\} 

등호가 성립하면 Closed half space이고 성립하지 않으면 open half space라 볼 수 있습니다. half space는 분명 무한한 집합이지만 affine set은 아닙니다. (affine set은 infinite set 이지만 모든 infinite set이 affine set인 것은 아닙니다.)

 a^{T}x\leq b 부근에서 half space를 벗어나는 line은 존재하기 때문에 affine set이 될 수 없습니다. 다만 convex set 인 것은 맞습니다.

Euclidean balls and Ellipsoids(타원)

Euclidean balls는 공이라 생각하면 되는데, 2차원 평면에서는 원, 3차원 공간에서는 구, 고차원 공간에서는 ball 이렇게 부르는 것 같습니다. 정의 자체는 친숙합니다. ball에 해당하는 중심이 있고 그 중심과의 거리가 r 이하에 해당하는 point들의 집합이라 보면 됩니다.

• B(x_{c},r)=\{ x|\parallel x-x_{c}\parallel \leq r\} =\{ x|(x-x_{c})^{T}(x-x_{c})\leq r^{2}\} 

x_{c}가 ball의 중심점이고 r의 ball의 반경이라 보면 됩니다. ball은 생긴 것부터 자명하게 Convex Set 인 것 같지만 책에 간단한 증명이 나와있어 한번 같이 풀어보도록 하겠습니다.

가장 간단하게 어떤 임의의 집합이 Convex Set임을 보이고 싶다면 \theta x_{1}+(1-\theta )x_{2} 이 그 Set에 포함된다는 것을 보이면 됩니다.

• \parallel x_{1}-x_{c}\parallel \leq r,\parallel x_{2}-x_{c}\parallel \leq r : 일단 Ball 내부에 존재하는 두 Point x_{1},x_{2}를 정의하겠습니다.

• \parallel \theta x_{1}+(1-\theta )x_{2}-x_{c}\parallel_{2} ,0\leq \theta \leq 1 : 이제 이 녀석이 r 보다 작다는 것을 보이면 Euclidean ball은 Convex Set입니다.

• x_{c}=\theta x_{c}+(1-\theta )x_{c} : 간단한 트릭을 사용해서 대입 해주도록 합시다.

• \parallel \theta x_{1}+(1-\theta )x_{2}-x_{c}\parallel_{2} =\parallel \theta (x_{1}-x_{c})+(1-\theta )(x_{2}-x_{c})\parallel_{2}  : 동일한 수식이지만 형태만 조금 변경한 것 입니다.

• \parallel \theta (x_{1}-x_{c})+(1-\theta )(x_{2}-x_{c})\parallel_{2} \leq \parallel \theta (x_{1}-x_{c})\parallel +\parallel (1-\theta )(x_{2}-x_{c})\parallel  : Euclidean norm의 삼각 부등식에 의해서 성립 합니다. \parallel A+B\parallel \leq \parallel A\parallel +\parallel B\parallel

• \parallel \theta (x_{1}-x_{c})\parallel +\parallel (1-\theta )(x_{2}-x_{c})\parallel =\theta \parallel x_{1}-x_{c}\parallel +(1-\theta )\parallel x_{2}-x_{c}\parallel  : 마지막으로 Euclidean norm의 homogeneity에 의해 성립합니다.

• \theta \parallel x_{1}-x_{c}\parallel +(1-\theta )\parallel x_{2}-x_{c}\parallel \leq r : \parallel x_{1}-x_{c}\parallel \leq r,\parallel x_{2}-x_{c}\parallel \leq r이기 때문에 결국 r 보다 작다는 것이 증명이 됩니다.

따라서 Euclidean ball은 Convex Set입니다. 삼각 부등식과 동차성을 이용하여 증명을 하는 것이 핵심이라 볼 수 있습니다.

다음으로는 타원입니다. 저는 타원의 정의 자체가 수식으로는 아직 이해가 안 돼서 일단 받아들이기만 했습니다. 이해를 하기 위해서는 선형대수학의 공부가 조금 더 필요한 모양입니다.

• \{ x|(x-x_{c})^{T}P^{-1}(x-x_{c})\leq 1\}  : 이때 P는 symmetric 하며 positive definite 입니다.

• 행렬 P의 고유값이 타원의 각 차원을 이루는 축이라 보면 됩니다. 2차원이면 단축,장축 이렇게 구성이 되겠죠?

생긴 건만 보면 역시 Convex Set 인 듯하네요. 증명에 관심 있는 분들은 직접 해보시길 바랍니다.

Norm Cone

Norm Cone이라 불리는 녀석도 있습니다. 다변수 미적분학을 공부했다면 한 번쯤은 봤을 수 있지만, 그렇지 않다면 상상이 잘 안 갈 수도 있습니다. 정의는 간단합니다.

• C=\{ (x,t)|\parallel x\parallel \leq t\} \subseteq R^{n+1}

시각화를 해보면 이해가 쉽기 때문에 n=2 인 경우를 보여드리겠습니다.

수식 자체는 \sqrt{x^{2}_{1}+x^{2}_{2}} \leq t입니다.

t=0이라면 그냥 x_{1}=0,x_{2}=0 원점이 되겠네요.

t=1이라면 \sqrt{x^{2}_{1}+x^{2}_{2}} \leq 1  반지름이 1인 원이 됩니다.

t=k이라면 \sqrt{x^{2}_{1}+x^{2}_{2}} \leq k  반지름이 k인 원이 됩니다.

이러한 구조를 표현하려면 R^2에서는 표현할 수 없겠죠? t에 대한 새로운 축이 존재해야 하기 때문에 R^3에서 정의가 됩니다. 시각화를 해보면 아래와 같습니다.

이제야 정말로 콘의 모양을 보여주고 있습니다. 증명은 Euclidean ball과 비슷합니다. 이 역시 Convex Set입니다. 하지만 Affine set은 아닙니다.

Polyhedron(다면체)

다면체는 유한한 개수의 선형 방정식과 부등식의 해집합입니다. 더 쉽게 말하면 유한한 개수의 hyperplane과 halfspace들의 교집합이라 보면 됩니다. 수식은 아래와 같습니다.

• P=\{ x|a^{T}_{j}x\leq b_{j},j=1,\ldots ,m,c^{T}_{j}x=d_{j},j=1,\ldots ,p\}  : 유한한 선형 방정식과 부등식의 해집합입니다.

Polyhedra(다면체)는 Convex set입니다.

Simplexes(단체)

단체를 이해하기 위해서는 affinely independent를 이해해야 합니다. affinely indepdent란 모든 point 간의 line이 independent 해야 한다는 점입니다.

예를 들어 2-simplex는 세 개의 Point로 구성이 되어 있습니다. 세 개의 point 중 임의로 두 point를 잡았을 때 만들어지는 line 들은 모두 다른 방향을 가지고 있으므로 독립입니다. 그래서 결국 R^{n} 공간에서는 n+1개의 affinely indepent point만 존재할 수 있습니다. Simplexes(단체)의 수식은 아래와 같습니다.

• C=\{ \theta_{0} v_{0}+\ldots +\theta_{k} v_{k}|0\preceq \theta ,1^{T}\theta =1\} 

Simplexes 역시 Convex Set입니다.

Operations that Preserve Convexity

마지막으로 Convex Set의 Convexity를 보존하는 몇 가지 연산들을 살펴보고 이번 글을 마무리하도록 하겠습니다. Convexity를 보존하는 것은 왜 중요할까요? 우리가 잘 알고 있는 Convex Set을 이용해서 새로운 Convex Set을 정의하는 데 유용하기 때문입니다. 

즉, 어떠한 Set은 이게 Convex Set인지 아닌지 판가름하기 어려워서 돌아가는 방법을 취한다고 보면 됩니다. 우리가 잘 알고 쉬운 Convext Set을 가지고 Convexity가 보존되는 연산만을 이용해서 복잡하고 어려운 Set에 도달할 수 있다면 이 Set의 Convexity가 보장되기 때문이죠.

4가지 정도 예시를 살펴보도록 하겠습니다.

InterSection

예를 들어 A라는 Convex Set과 B라는 Convex Set의 교집합은 마찬가지로 Convex Set입니다. Polyhedron(다면체) 역시 Hyperplane(Convex)와 HalfSpace(Convex) 간의 교집합인 것처럼 교집합 연산은 Convexity를 보존해주게 됩니다.

증명을 어떻게 해야 하는지는 책에 나와있지 않아 잘 모르겠지만 직관적으로 봤을 때는 이해하는 데 큰 어려움을 없을 것 같습니다.

Affine Function

affine 함수는 Linear function이라 보면 됩니다. f(x)=Ax+b 이런 형태인 것이지요. 이때 임의의 Convex Set에 affine function을 가해도 그 image는 여전히 convex 합니다. 즉, Linear 연산은 Convexity를 보존하는 것입니다. 데이터가 Convex Set이라는 가정이 있을 때, 우리가 신경망에서 활성화 함수를 사용하지 않고 Linear Layer만 거치게 되면 사실 Convex function을 얻을 수는 있습니다. 형태가 선형 회귀 꼴이라 성능이 좋지는 않겠지만요.

실제로 타원은 unit ball의 affine function이 가해진 꼴이라고 하더군요. 그 자세한 내막은 모르겠지만 어찌 됐든 Linear 연산은 convexity를 보존시켜줍니다. Linear 연산은 scaling과 translation이 있죠? 아마 선형성에 대해서 이해를 하고 있다면 linear 연산이 convexity를 보존시켜준다는 것은 직관적으로 받아들일 수 있을 것 같습니다.

• 즉, Convex set의 affine function이 만들어내는 image는 동일하게 convex 합니다.
• convex set의 affine inverse function이 만들어내는 inverse image 역시 동일하게 convex 합니다.

(참고로 image는 치역이라 생각하면 됩니다.)

Perspective functions

Perspective function은 카메라에 상이 맺히는 것과 같이 멀리 있는 물체는 작게 가까이 있는 물체는 크게 원근에 따라 상을 만드는 함수입니다.

따라서, 피사체는 R^{n+1} 차원의 공간에 있고 상은 R^{n}차원의 평면에 맺히게 됩니다.

우리가 동차 좌표계에서 마지막 원소를 1로 정규화시키고 제거하는 식으로 여기서도 동일하게 사용이 됩니다.

그림을 통해서 한번 예시를 들어보겠습니다. 구를 평면에 투영을 시키면 그림자 같은 것이 생길 것입니다. 그렇다면 그 그림자는 어떻게 생겼을까요? 원이나 타원처럼 생겼겠죠? 역시나 Convex set으로 보존이 됩니다.

그림자가 검은색 타원으로 Convex Set으로 정의가 되었네요.

따라서 어떤 Convex Set이 있을 때 그것의 Perspective image 역시 Convex 하며 그 Inverse도 성립합니다. 여기서 Inverse가 성립한다는 것이 이해가 안될 수 있습니다. 그렇기 때문에 한번 수학적으로 증명을 해보도록 하겠습니다.

Q. If C\subseteq R^{n} is convex, then the inverse image of a convex set under the perspective function is also convex

• P^{-1}(C)=\{ (x,t)\in R^{n+1}|x/t\in C,t>0\} 

일단 원래 Convex Set에 두 point \frac{x}{t} ,\frac{y}{s} 가 있을 때, 각각의 inverse image를 (x,t) (y,s)라 정의하겠습니다.

• (x,t)\in P^{-1}(C),(y,s)\in P^{-1}(C)

이때 0\leq \theta \leq 1에 대해서 우리는 아래의 관계를 증명해야 합니다.

• \theta (x,t)+(1-\theta )(y,s)\theta \in P^{-1}(C)

이것을 증명하는 것은 아래를 증명하는 것과 동치입니다.

• \frac{\theta x+(1-\theta )y}{\theta t+(1-\theta )s} \in C

동치인 이유를 아는 것이 중요한데요, \theta (x,t)+(1-\theta )(y,s)\theta = \left( \theta x+\left( 1-\theta \right)  y\right)  ,\left( \theta t+(1-\theta \right)  s)\in P^{-1}(C)를 만족하기 위해서는 \frac{\theta x+(1-\theta )y}{\theta t+(1-\theta )s} \in C가 만족되어야 합니다. P^{-1}(C)의 정의를 살펴보시길 바랍니다.

즉, 이러한 상황에서 우리는 아래와 같이 표현할 수 있는 0\leq \alpha \leq 1만 찾을 수 있다면 증명은 완료됩니다.

• \frac{\theta x+(1-\theta )y}{\theta t+(1-\theta )s} =\alpha (\frac{x}{t} )+(1-\alpha )\left( \frac{y}{s} \right)  

• \alpha =\frac{\theta t}{\theta t+(1-\theta )s} \in [0,1]로 설정한다면 가능합니다. 어떻게 찾았는지는 잘 모르겠네요.

아무튼 C가 convex set이니, persective function의 inverse image인 P^{-1}(C)는 역시 convex set 입니다.

Linear-fraction functions

마지막 연산입니다. 사실 여기는 제대로 이해를 못 해서 그냥 받아들이기만 하고, 추후에 이해가 명확해지면 그때 내용을 보충하도록 하겠습니다. Linear-fraction function은 perspective function과 affine function을 같이 하는 것입니다. 둘 다 convexity를 보존하기 때문에 마찬가지로 Linear-fraction function 역시 convexity를 보존하게 됩니다.

• 임의의 Convex Set에 대해서 Linear-fraction function의 image는 여전히 convex set 입니다.
• 임의의 Convex Set에 대해서 inverse Linear-fraction function의 image는 여전히 convex set 입니다.

일단 이 정도로 Convex Set에 대해서 살펴보았습니다. 글을 전반적으로 보면 알겠지만 선형대수의 중요함이 보이는 부분들이 있습니다. 개인적으로 필요한 부분들은 따로 공부하려고 합니다.

다음번 글은 Convex Function에 대해서 알아보도록 하겠습니다.