볼록 최적화 — 개념, 방법, 활용

볼록 최적화란 볼록한 실행 가능 집합 위에서 볼록 함수를 최소화하는 것을 뜻합니다. 이것이 중요한 가장 큰 이유는 간단합니다. 이런 볼록성 조건이 성립하면 어떤 국소 최소값도 전역 최소값이 되기 때문입니다.

이 보장 덕분에 이런 문제는 일반적인 최적화 문제보다 훨씬 더 믿을 만합니다. 물론 문제를 올바르게 모델링해야 하지만, 일단 모델이 볼록이면 작은 주변에서만 최선처럼 보이는 해를 쫓을 필요가 없습니다.

대표적인 형태는 다음과 같습니다.

$$\text{minimize } f(x)$$

subject to

$$g_i(x) \le 0 \quad \text{for } i=1,\dots,m, \qquad Ax=b,$$

여기서 $f$와 각 $g_i$는 볼록이고, 등식 제약은 아핀입니다. 이런 조건에서는 실행 가능 집합이 볼록이므로 최적화 문제도 볼록입니다.

볼록 최적화의 정의

함수 $f$가 볼록이라는 것은, 그 정의역의 임의의 두 점 $x$와 $y$ 및 임의의 $0 \le t \le 1$에 대해

$$f(tx + (1-t)y) \le t f(x) + (1-t) f(y).$$

가 성립한다는 뜻입니다.

쉽게 말하면, 그래프 위의 두 점을 이은 선분이 그래프보다 위에 놓입니다. 한 변수의 경우 많은 볼록 함수가 그릇 모양처럼 보이지만, 실제 판정 기준은 이 부등식입니다.

집합이 볼록이라는 것은, 그 집합이 두 점을 포함하면 그 두 점을 잇는 직선 선분 위의 모든 점도 함께 포함한다는 뜻입니다.

필요한 것은 이 두 가지입니다.

• 볼록한 목적함수
• 볼록한 실행 가능 집합

둘 중 하나라도 성립하지 않으면 문제는 더 이상 볼록이 아닐 수 있습니다.

왜 볼록 최적화는 분석하기 쉬운가

최적화가 어려운 이유 중 하나는 골짜기가 여러 개 있을 수 있기 때문입니다. 알고리즘이 목적함수를 계속 줄이더라도 결국에는 주변에서만 가장 좋은 점에서 멈출 수 있습니다.

볼록 최적화는 바로 이런 실패 가능성을 없애 줍니다. 목적함수가 볼록이고 실행 가능 영역이 볼록이면, 국소적으로 더 개선할 수 없는 점은 이미 전역 최적해입니다. 그래서 볼록 문제는 통계, 머신러닝, 제어, 운용연구에서 중요합니다.

그렇다고 모든 볼록 문제가 쉽다는 뜻은 아닙니다. 어떤 문제는 여전히 규모가 크거나 계산 비용이 많이 듭니다. 다만 구조가 충분히 깔끔해서, 좋은 알고리즘이 잘못된 국소 거동에 갇히지 않고 진짜 최적해를 목표로 할 수 있다는 뜻입니다.

볼록 최적화 예제

다음의 무제약 문제를 생각해 봅시다.

$$\text{minimize } f(x) = (x-3)^2 + 2.$$

이 문제는 볼록 최적화 문제입니다. $f(x)$가 최고차항의 계수가 양수인 이차함수이므로 모든 실수에서 볼록하기 때문입니다.

최소화하는 점을 찾기 위해 미분하면

$$f'(x) = 2(x-3).$$

도함수를 0으로 두면

$$2(x-3)=0 \quad \Rightarrow \quad x=3.$$

이제 목적함수 값을 계산하면

$$f(3) = (3-3)^2 + 2 = 2.$$

따라서 최소값은 $2$이고, $x=3$에서 달성됩니다.

이 예시는 단순하지만 핵심 아이디어를 잘 보여 줍니다. 한 번 $x=3$에 도달하면, 다른 어딘가에 더 낮은 숨은 골짜기가 있을 가능성은 없습니다.

볼록 최적화의 대표적인 방법

어떤 방법을 쓸지는 문제의 구조에 따라 달라집니다.

매끄러운 무제약 문제나 제약이 단순한 문제에서는 경사 기반 방법이 흔히 사용됩니다. 경사의 반대 방향으로 움직이면 목적함수를 줄일 수 있기 때문입니다.

제약이 많은 볼록 문제에서는 내부점 방법이 널리 쓰입니다. 제약을 직접 다루면서도 실제로 좋은 성능을 보이는 경우가 많기 때문입니다.

비매끄러운 볼록 문제에서는 서브그래디언트 방법이나 proximal 방법이 더 적절할 수 있습니다. 중요한 것은 알고리즘 목록 자체가 아닙니다. 볼록 구조가 알고리즘에 안정적으로 작동할 수 있는 기반을 준다는 점입니다.

볼록 최적화에서 흔한 실수

그래프만 보고 볼록하다고 단정하기

어떤 그래프는 한 그림에서는 그릇 모양처럼 보여도, 전체 정의역이나 더 높은 차원에서는 볼록성이 성립하지 않을 수 있습니다. 스케치보다 정의나 표준적인 볼록성 판정 규칙이 더 중요합니다.

제약조건의 중요성을 잊기

볼록한 목적함수만으로는 충분하지 않습니다. 실행 가능 집합이 비볼록이면 전체 문제는 볼록 최적화 문제가 아닙니다.

모든 임계점을 최소값으로 취급하기

미분 가능한 볼록 함수에서는 기울기가 0인 점이 전역 최소해입니다. 하지만 볼록성이 없으면 이런 결론은 일반적으로 성립하지 않습니다.

볼록과 엄격한 볼록을 혼동하기

엄격한 볼록성은 더 강한 조건입니다. 이 경우 최적해가 유일한 경우가 많지만, 단순한 볼록성만으로는 항상 유일성이 보장되지는 않습니다.

볼록 최적화는 어디에 쓰일까

볼록 최적화는 실제 문제를 볼록 비용과 볼록 제약으로 모델링할 수 있을 때마다 등장합니다.

대표적인 예로는 최소제곱 적합, 서포트 벡터 머신, 볼록 위험 모형 아래의 포트폴리오 선택, 그리고 다양한 자원 배분 문제가 있습니다. 다만 정확한 모델이 중요합니다. 선택한 목적함수와 제약이 실제로 볼록 가정을 만족할 때만 그 응용은 볼록 문제가 됩니다.

실제로 볼록성이 도움이 되는 때

볼록 최적화는 단순히 숫자 하나가 필요할 때보다 더 많은 것이 필요할 때 특히 유용합니다. 보통은 얻은 답이 내가 세운 모델에 대해 정말 최적인지에 대한 보장도 원합니다.

이 보장은 공학과 데이터 작업에서 특히 중요합니다. 왜냐하면 다음 두 질문을 분리해 주기 때문입니다.

1. 우리가 수학적 문제를 올바르게 풀었는가?
2. 그 수학적 문제가 현실을 잘 모델링했는가?

볼록성은 첫 번째 질문에는 큰 도움을 줍니다. 하지만 두 번째 질문까지 자동으로 해결해 주지는 않습니다.

비슷한 문제를 직접 해보기

$f(x) = (x+1)^2 + 5$의 최소값을 구해 보세요. 그리고 이것을 볼록이 아니라 오목인 $f(x) = -(x+1)^2 + 5$와 비교해 보세요. 이렇게 나란히 비교하면 볼록성의 역할이 훨씬 더 분명해집니다.

다른 경우도 살펴보고 싶다면, 작은 최소제곱 문제를 직접 세워 보세요. 그리고 볼록한 오차 함수를 최소화하면 어떻게 안정적인 최적 적합이 나오는지 확인해 보세요.