🗂️ Convex Optimization Problem

❓ Convex Optimization Problem

\[f(wx_1 + (1-w)x_2)≤ wf(x_1) + (1-w)f(x_2),\ \ w \in [0,1] \\ f''(x) ≥ 0\]

Convex Problem 이란, 목적 함수 $f(x)$가 Convex Function 이면서 Feasible Set 역시 Convex Set 이 되는 문제 상황을 일컫는다. Convex Problem 는 수학적 최적화에서 매우 중요한 개념인데, 그 이유는 해당 조건을 만족하면 국소 최적해가 전역 최적해와 동치가 되어 최적화 난이도가 급격히 낮아지기 때문이다. 또한 Convex Problem을 해결해 국소 최적해를 구하는 알고리즘은 이미 많이 개발 되어 있기 때문에 주어진 최적화 문제를 Convex Problem으로 치환해 해결하는게 가장 효율적이다. 한편, 여기서 Feasible Set 이란, 함수의 실행 가능 영역•정의역이라고 생각하면 된다. 아래 그림, 빨간 직선의 영역에 해당한다. 세트라는 명칭은 무한한 직선이 아닌 유한한 선분을 표현하는 용어라고 생각하면 된다.

위에 서술한 두개의 수식은 어떤 문제 상황이 Convex Problem 인지 아닌지 구분해주는 판별식의 역할을 한다. 왜 두 수식을 만족하면 Convex Problem이 되는지 살펴보고 마지막에는 Convex Problem 에서 왜 국소 최적해가 전역 최적해와 동치가 되는지 그 증명을 해보려 한다.

Convex Function

﹤ Jensen’s Inequality

첫번째 수식을 보자. 우리는 이것을 얀센 부등식이라고 부른다. 얀센 부등식 은 어떤 함수 $f(x)$의 Convex Function 여부를 판정 하는데 사용된다. 좌변은 Feasible Set 에 해당되는 데이터 포인트의 함수값을 의미하며 그림 상에서 초록색 곡선으로 표현된다. 한편, 우변은 Feasible Set의 평균변화율을 기울기로 하면서 구간 양쪽 끝을 지나는 선분을 일컫는다. 그림에서 파란색 직선이 바로 부등식의 우변이다.

그렇다면 위 부등식을 항상 만족하려면 함수 $f(x)$는 어떤 형태를 가져야 할까?? 먼저 오목 함수인 Concave Function부터 생각해보자. 위 그림을 뒤집어서 생각해보면 되는데, 함수가 정의되는 전체 정의역에서 위 부등식을 만족하는 구간(파란색 직선이 초록색 곡선보다 위에 있는)을 전혀 찾아볼 수 없다. 따라서 얀센 부등식을 만족하려면 Feasible Set 의 구간이 반드시 Convex Set 이어야 하고, 해당 구간에서 목적함수는 반드시 Convex Function의 형태를 띄고 있어야 한다.

그렇다면 목적함수가 Convex인지는 어떻게 판별할 수 있을까?? 주어진 모든 상황에서 위 그림처럼 쉽게 함수의 그래프를 그릴 수는 없을 것이다. 그래서 수식으로 어떤 목적함수가 Convex인지 판별할 수 있어야 한다. 드디어 제시된 두번째 수식을 활용할 차례다.

📈 Second Derivative

두번째 수식을 흔히 이계도함수라고 부른다. 아마 수능 수학에서 21, 30번과 같은 킬러 문제를 풀 때 가끔씩 사용하던 기억이 날 것이다. 이계도함수는 도함수를 한 번 더 미분한 것으로 원함수의 곡선이 얼마나 빠르게 변하는지 혹은 곡선의 곡률에 대한 정보를 알려준다. 이를 통해 원함수의 극대, 극소는 물론 변곡점의 위치를 알아낼 수 있다. 그래서 어떤 이차함수를 예시로 들어보자. 2차항의 부호가 양수라면 이계도함수의 값은 항상 양수가 될 것이고, 음수라면 항상 음수가 될 것이다. 그런데 우리는 이미 직관적으로 2차함수에서 최고차항의 부호가 양수면 아래로 볼록한 함수, 반대의 경우 위로 오목한 오목함수가 된다는 것을 알고 있다. 따라서 이계도 함수의 값이 항상 양수라면 해당 함수는 Convex Function이 된다.

지금까지는 단변수 함수에 대한 케이스만 살펴보았다. 그렇다면 이것을 다변수로 확장할 수는 없을까?? 물론 가능하다. 어떤 다변수 함수가 Convex인지 판정하는 것도 위와 동일한 조건을 통해 판별한다. 이 때 등장하는게 바로 헤시안 행렬이다. 헤시안 행렬이란, 어떤 다변수 함수의 이계도함수값을 행렬로 나타낸 것이다. 단변수 함수의 이계도함수 역할과 동일하다. 그래서 어떤 다변수 함수가 컨백스 함수이려면, 헤시안 행렬이 Positive Semi-Define 조건을 만족해야 한다. 헤시안 행렬과 Positive Semi-Define에 대해서는 다른 포스트에서 자세히 다루도록 하겠다.

🪪 Proof: local minimum same as global minimum in Convex

이제 드디어 목적함수가 컨백스 함수일 때, 국소 최적해가 전역 최적해와 동치가 되는지를 증명해보려 한다. 먼저 증명은 귀류법을 사용한다. 귀류법이란, 수학, 논리학, 철학 등에서 주장이 부정됨을 보이기 위해 모순 또는 부정된 가정을 유도하는 논증 기법으로, 특정 주장이 참임을 증명하기보다는 그 반대인 부정된 주장이 거짓임을 보이는 데 사용한다. 그래서 귀류법을 활용해 다음과 같은 명제가 거짓임을 증명해보려 한다.

어떤 함수 $f(x)$는 Convex면서 Feasible Set이 Convex Set임을 만족하는 동시에 아래 수식을 만족한다고 한다.

\[f(x^@) < f(x^!)\]

부등식의 우변은 국소 최적해를 의미하고, 좌변은 국소 최적해보다 작은 함수값이 존재한다고 가정한 것이다. 이제 이 명제가 틀림을 증명하면 우리는 자연스럽게 국소 최적해가 전역 최적해와 동치가 된다는 것을 확인할 수 있게 된다.

우리는 함수 $f(x)$가 Convex면서 Feasible Set이 Convex Set이라고 가정했기 때문에, $\alpha x^! + (1-\alpha)x^@$ 역시 Feasible Set이 될 것이다. 이러한 사실을 활용해 두 점($x^!, x^@$)을 얀센 부등식에 넣어보자.

\[f(wx^! + (1-w)x^@)≤ wf(x^!) + f(x^!) - f(x^!) + (1-w)f(x^@) \\ f(wx^! + (1-w)x^@)≤ f(x^!) +(1-w)(f(x^@) -f(x^!))\]

우변부터 함께 살펴보자. $(1-w)$는 반드시 양수가 된다. 얀센 부등식 정의상 $w \in [0,1]$을 만족하기 때문이다. 한편, $f(x^@) -f(x^!)$는 음수가 된다. 증명을 시작하면서 $f(x^@)$가 $f(x^!)$보다 작다고 가정했기 때문이다. 따라서 우변은 $f(x^!)$보다 아주 조금 작은 값(w→1)이 될 것이다. 이제 좌변을 살펴보자. 마찬가지로 w→1을 해주면 좌변은 $f(x^!)$의 매우 근접한 위치의 함수값을 보자는 의미가 된다. 좌변을 $\alpha$, 우변을 $\beta$로 치환해 지금까지 증명 과정을 다시 부등식으로 표현하면 다음과 같다.

\[\alpha ≤ \beta < f(x^!)\]

우리는 $f(x^!)$가 지역 최소값이라고 정의한 바 있다. 지역 최소값이라는 것은 그 주변에서 가장 작은값이라는 의미를 갖는다. 그런데 $f(x^!)$의 주변값인 $\alpha$가 지역 최소값보다 작다고 부등식은 말하고 있기 때문에, 지역 최소값 정의에 위배되어 위 명제는 거짓이 된다.

정리하자면, 어떤 함수 $f(x)$가 컨백스 성질을 만족하면서, Feasible Set 역시 Convex Set인 경우에 국소 최소값이 전역 최소값이 아닐 경우, 국소 최적이 국소 최적이 아닌 경우가 발생하기 떄문에 반드시 위 조건에서 국소 최적값은 전역 최적값이 되어야 한다.