Convex 최적화(1): Convex Function, Set

어떤 주어진 조건에 대해 목적함수를 최대/최소화하는 문제를 Optimization 문제(Optimization Programming)이라고 부른다. 주어진 Optimization 문제의 특성에 따라서 Linear Program Optimization, Integer Program Optimization, Convex Optimization 등의 하위 분류로 나뉘어진다.

• 이 중 Convex Optimization은 목적함수 및 제약 조건 함수가 Convex Function에 속하며, 동시에 문제의 범위에 해당하는 Domain이 Convex Set으로 정의된 경우에 해당한다.

Convex Function

• 흔히들 Convex에 대한 이야기를 꺼낼 때, 가장 먼저 떠올리게 되는 개념이 Convex function이다. 흔히들 볼록 함수라고 말하는 함수인데, 아래 그래프를 보면 아래로 볼록한 형태를 띄고 있는 것을 확인할 수 있다. 위로 볼록인 경우도 Convex 아니냐?라고 반문할 수 있겠으나, 정의가 그러하다. 위로 볼록한 함수는 아래로는 ‘오목’한 함수이고, 그에 따라 Concave function이라 정의되어 있다. Concave function의 경우 함수 값에 부호만 바꿔 취해준 형태에 해당하므로, 쉽게 Convex function으로 바꾸어 활용 가능하다.

wikipedia; 변수 x에 대한 간단한 Convex function 예시

• 함수의 범위를 x1에서 x2 사이로 한정지어 살펴본다고 할 때, f(x1)과 f(x2)를 이은 직선을 우선 상정해보자(l이라 부르겠다). 위 그림에서 볼 수 있듯 x1과 x2사이의 모든 값에 대해 f(x)가 l보다 작은 값을 갖게 된다.
• 수식으로 표현하면, 아래와 같다.

• (우변의 f 안에 들어간 함수 형태는 Convex combination이라는 형태로 자주 보게될 형태다.)
• 정의 자체는 꽤나 간단한 편이다. 앞으로 Optimization 문제 내에서 사용되는 함수의 모양이 위와 같은 특성을 갖게 될 경우, Convex Optimization 문제의 특성을 갖게 될 가능성이 높다. 추가로 필요한 조건은 아래에서 살펴볼 Convex set에 대한 조건이다.

Convex Set

• Convex set은 흔히 말하는 ‘볼록’ 개념은 없다고 볼 수 있다.( Set이 바깥으로 볼록하다던가…라는 식의 주장은 펼 수 있겠으나.)
• Convex Set의 정의는 Set 내에 포함된 두 점을 이었을 때, 그 선분 내에 모든 점이 해당 Set 내에 포함된다는 것이다.

wikipedia

• 그림으로 예시를 들여다보면, Set에 음푹 패인 부분이 없다고 한다면, Convex Set에 해당한다고 쉽게 판단할 수 있다.

• Convex function과의 연결점도 존재하는데, 만일 함수가 Convex function이라면, 그 epigraph(함수 위에 해당하는 area)는 항상 Convex set의 성질을 갖게 된다.

Optimization 문제 내에 포함된 모든 함수(목적 함수 및 제약조건 식)가 convex function이고, 그 함수들이 정의되는 Domain이 Convex set의성질을 만족한다면, 해당 문제는 Convex Optimization 문제가 된다.