[최적화] (1) Convex Optimization Problem

용어정리를 간단히하면 min / max / argmin / argmax 등의 경우 그 대상이 되는 f(x)를 objective function이라 부른다. 그리고 이 objective function은 대게 constraints(제약조건)에 종속(subject to)된다. 

특정 inequaility constraints가 존재하여 f(x)의 정의역 중 일부분으로 solution이 한정된다면 이 부분집합을 feasible solution set이라 부른다. 이 feasible solution set 중 목표함수의 값을 최적화하는 solution을 optimal solution이라 부르고, 보통 x*으로 표기한다.

 

local min/max와 관련한 오해가 있는듯하여 간단한 예시를 통해 개념을 명료화한다.

local min/max는 미분가능과는 무관하다. 따라서 특정값 x=a에서 미분값이 정의되지 않아도 local min이 될 수 있다. 

 

그럼 Convex Optimization Problem은 무엇인가? 정의에 따르면 f(x)가 convex하고, feasible set이 convex한 경우다. 

우선 모든 x1, x2가 S(feasible solution set)에 속하는 경우 a∈[0,1]에 대해 ax1+(1-a)x2 ∈S 가 성립한다면 feasible solution set이 convex하다고 말할 수 있다. 단순히 생각해보면 x1, x2가 S에 속한다면 그 둘 사이의 어떠한 x도 S에 속한한다는 뜻이며 이는 곧 feasible solution set의 정의다. 

이러한 feasible solution set의 원소 x3(=ax1+(1-a)x2)에 대해 af(x1)+(1-a)f(x2)가 이보다 크다면 f(x)는 convex하다. 후자는 f(x1)과 f(x2)를 linear하게 잇는 선분인데 이보다는 x1<=x3<=x2의 관계에 놓인 x3의 함수값이 작아야한다는 것이다. 그림과 함께 이해하면 convex에 대한 개념은 쉽다. 

 

그럼 좀더 수학적인 정의를 살펴보자. 

f(x)가 만약 모든 x에 대해 미분가능한 함수이고, f''(x) >= 0이라면 f(x)는 convex function이다. 가령 f(x) = x^2는 그 모양만 생각해봤을 때도 convex이지만 수학적 정의를 따져봐도 f"(x) = 2 이기 때문에 convex funtion인 것이다. 

조금 더 나아가서 f(x)가 vector field 위에 정의된 함수라 가정해보자. 

이 경우 f"(x)인 hessian mtx가 p.s.d를 충족한다면 f(x)는 convex function이다. p.s.d는 f"(x)인 H가 모든 vector Z에 대해 (Z^T)(H)(Z) >= 0 을 만족하는 경우를 말한다. 

 

convex optimization을 다룰 때는 lcoal minimum이 global minimum이 된다. 이는 매우 강력한 명제로 기능한다.

 

이를 증명해보자. x*이 convex optimization problem에서 구한 local minimum일 때 f(x') < f(x*)인 x'가 있다고 가정해보자. 과연 이 local minimum x*가 존재하는 상황 속에서 그보다 더 작은 f(x')가 존재할 수 있는것인가?가 핵심이다. 

우선 x*와 x' 사이에 놓인 x3을 구한다. 이 때 f(x3) <= a(f*) + (f(x*) - f(x*)) + (1-a)f(x')을 만족해야만한다. 그런데 우변의 식은 f(x*) + (1-a)(f(x')-f(x*))으로 유도할 수 있고, f(x') < f(x*), (1-a) > 0 이기 때문에 둘째항은 항상 음수가 된다. 그럼 f(x3) < f(x*) + 음수 < f(x*)이 되니까 local min인 x*의 함수값보다 작은 x3이 존재한다는 결론에 이르게 된다.  

 

그러나 f(x') < f(x*) 전제에서 f(x3) < f(x*)가 도출되었음에도 불구하고, 이는 x*가 그 근방에서 극소값이란 local minimum 의 정의에 배치되기 때문에 전제 자체가 틀렸다는 결론으로 귀결된다. 따라서 local minimum은 convex optimization problem을 다룰 때 global minimum이다. 

 

ax* + (1-a)x' ∈ S 또한 매우 중요한 역할을 한다. 

가령 f(x) = x^2, feasible solution set S : x>=1이라면 x*=1이 된다. x' = 0이면 x3이 [0,1] 사이에 놓인다. 그러면 f(x3) <= af(x*) + (1-a)f(x')은 성립을 하게 된다. 그러면 x'이 local min이 되지만 이는 feasible solution set에서 벗어나있기 때문에 이 특정 convex optimization problem의 optimal solution은 아니다.