볼록 최적화

1. 개요

볼록 최적화(convex optimization)는 볼록집합 위에서 볼록함수를 최소화하는 문제의 총칭이다. 최적화 이론에서 이 부류가 특별대우를 받는 이유는 딱 하나, 지역 최소가 곧 전역 최소이기 때문이다. 이 성질 하나가 “초기값을 어디에 두느냐”, “이 답이 진짜 최적인가”라는 최적화의 두 가지 만성 고민을 통째로 지워 버린다.

스티븐 보이드(Stephen Boyd)와 리번 반덴베르허(Lieven Vandenberghe)의 교과서가 유명하게 정리한 관점은 이렇다 — 어려운 문제와 쉬운 문제를 가르는 선은 선형/비선형이 아니라 볼록/비볼록이다.¹ 선형 문제는 쉽지만, 비선형이라도 볼록이면 다항시간 안에 전역해가 나오고, 반대로 비볼록이면 이차식이어도 NP-완전 부류로 떨어질 수 있다(부정치 이차계획이 그 대표다).

2. 볼록집합과 볼록함수

집합 $C$ 가 볼록이라는 것은 임의의 두 점을 잇는 선분이 통째로 집합 안에 들어 있다는 뜻이다.

$$x, y \in C,\ \theta \in [0,1] \ \Longrightarrow\ \theta x + (1-\theta) y \in C$$

함수 $f$ 가 볼록이라는 것은 정의역이 볼록집합이고, 그래프 위의 두 점을 이은 현이 함수보다 위에 있다는 뜻이다.

$$f(\theta x + (1-\theta) y) \le \theta f(x) + (1-\theta) f(y)$$

미분 가능하면 훨씬 쓰기 좋은 판정조건이 나온다. 1차 조건은 접평면이 항상 함수의 아래에 깔린다는 것이고,

$$f(y) \ge f(x) + \nabla f(x)^{\mathsf T} (y - x) \quad \forall x, y$$

2차 조건은 헤세 행렬이 정의역 전체에서 반양정치(positive semidefinite)라는 것이다.

$$\nabla^2 f(x) \succeq 0$$

즉 헤세 행렬의 고유값이 전부 0 이상. 헤세 행렬이 강양정치($\succ 0$)면 강볼록(strongly convex)이고, 이때는 최소점이 유일하며 수렴 속도 보장까지 따라온다. 참고로 볼록성은 놀랄 만큼 잘 보존된다 — 볼록함수의 비음수 가중합, 최댓값(pointwise maximum), 아핀 변환과의 합성은 전부 볼록이다. 실무에서 새 문제를 볼록으로 “인식”하는 작업의 90%는 이 규칙들을 조립해 확인하는 일이다.²

3. 지역 최소 = 전역 최소

이게 전부다. 증명도 세 줄이다. $x^\star$ 가 지역 최소인데 더 나은 점 $y$ 가 있다고 하자($f(y) < f(x^\star)$). 두 점을 잇는 선분 위의 점 $z = \theta y + (1-\theta)x^\star$ 에 대해 볼록성에서

$$f(z) \le \theta f(y) + (1-\theta) f(x^\star) < f(x^\star)$$

$\theta$ 를 아무리 작게 잡아도 이 부등식이 성립하므로, $x^\star$ 의 임의로 작은 근방 안에 더 낮은 점이 있다. 지역 최소라는 가정과 모순. 끝.

지역 최적해에 갇히는 문제, 유전 알고리즘이나 담금질 모사 같은 전역 탐색 휴리스틱이 필요한 이유, 다중 시작점(multi-start) 전략 — 볼록 세계에서는 이 모든 게 필요 없다. 대신 “내 문제가 정말 볼록인가”를 증명하는 부담이 앞단으로 옮겨 갈 뿐이다.

4. 문제 계층

볼록 문제는 표현력에 따라 깔끔하게 포개진 계층을 이룬다.

부류	목적함수 / 제약 형태	대표 응용
LP (선형계획)	선형 목적 + 선형 부등식	자원 배분, 생산 계획
QP (이차계획법)	볼록 이차 목적 + 선형 제약	SVM, MPC, 접촉 문제
SOCP (2차 원뿔)	노름 제약 형태	강건 최적화, 빔포밍, 압축센싱
SDP (반정부호)	행렬 반정부호 제약	제어 LMI, 조합 완화

포함 관계는 LP $\subset$ QP $\subset$ SOCP $\subset$ SDP. 상위로 갈수록 표현력은 커지고 풀이 비용도 커진다. 실무에서 문제를 “SOCP로 캐스팅했다”는 말은 곧 “상용 솔버에 던지면 전역해가 나온다”는 뜻이라, 모델링 단계에서 어느 계층까지 내려앉힐 수 있는지가 승부처가 된다.

5. 쌍대성과 KKT 조건

제약 문제 $\min f_0(x)$ s.t. $f_i(x) \le 0$, $Ax = b$ 에 라그랑주 승수법을 적용해(일반론은 쌍대성 문서가 다룬다) 라그랑지안 $L(x,\lambda,\nu) = f_0(x) + \sum \lambda_i f_i(x) + \nu^{\mathsf T}(Ax-b)$ 을 만들고, $x$ 에 대해 최소화하면 쌍대함수 $g(\lambda,\nu) = \inf_x L$ 을 얻는다. 이 함수는 원 문제가 볼록이든 아니든 항상 오목하고, 항상 하한을 준다(약쌍대성).

$$d^\star = \sup_{\lambda \succeq 0,\,\nu} g(\lambda,\nu) \ \le\ p^\star$$

원 문제가 볼록이고 슬레이터 조건(비아핀 부등식 제약을 엄격히 만족하는 내부점이 하나라도 존재)이 성립하면 이 부등식이 등호가 된다. 이것이 강쌍대성이고, 쌍대간극(duality gap)이 0이 되는 순간이다. 그래서 볼록 솔버는 반복 도중 언제든 원 목적값과 쌍대값의 차이를 보고 “지금까지 답이 최적에서 얼마나 떨어져 있는지”를 증명서 형태로 제시할 수 있다. 비볼록에서는 꿈도 못 꾸는 사치다.

같은 조건 아래에서 카루시-쿤-터커 조건은 필요조건에서 필요충분조건으로 승격된다. 비볼록에서는 KKT점이 안장점이나 지역 최대일 수도 있지만, 볼록에서는 KKT를 만족하는 점 = 전역해다. 실무적으로 이 한 줄이 “수렴 판정 = 최적성 판정”을 성립시킨다.

6. 손으로 끝까지 가는 검산 세 개

쌍대성과 중심 경로는 말로만 들으면 추상적인데, 변수 한 개짜리 예제로 전부 확인된다.

(1) 강쌍대성이 성립하는 경우. $\min x^2$ s.t. $x \ge 1$. 눈으로 봐도 $p^\star = 1$($x^\star = 1$)이다. 라그랑지안 $L = x^2 + \lambda(1-x)$ 를 $x$ 로 최소화하면 $x = \lambda/2$ 이므로

$$g(\lambda) = \lambda - \frac{\lambda^2}{4}, \qquad \max_{\lambda \ge 0} g = g(2) = 1 = p^\star$$

쌍대간극이 0이다. KKT 로 교차검증해 보면 정류조건 $2x - \lambda = 0$ 에서 $\lambda^\star = 2$, 상보여유 $\lambda(1-x)=0$ 에서 $x^\star = 1$ — 쌍대해와 정확히 맞는다. 슬레이터 조건도 $x=2$ 라는 엄격 내부점이 있으니 성립한다.

(2) 슬레이터가 깨지면 간극이 열린다. 볼록성만으로는 부족하다는 반례가 보이드 교과서에 있다.³ $\min e^{-x}$ s.t. $x^2/y \le 0$, 정의역은 $y > 0$. 제약은 $x = 0$ 을 강제하므로 $p^\star = e^0 = 1$. 그런데 쌍대함수는 $\lambda \ge 0$ 전체에서 $g(\lambda) = \inf_{x,\,y>0}(e^{-x} + \lambda x^2/y) = 0$ 이다($x \to \infty$, $y$ 를 더 빠르게 $\to \infty$). 따라서 $d^\star = 0$, 쌍대간극 1. 목적함수도 제약함수도 볼록인데 간극이 열렸다 — 엄격 내부점이 없어서다($x^2/y < 0$ 은 불가능). 그래서 “볼록이면 강쌍대성”이 아니라 “볼록 + 슬레이터면 강쌍대성”이라고 써야 한다.

(3) 중심 경로의 간극이 정확히 $m/t$. $\min x$ s.t. $x \ge 1$ 에 로그 장벽을 씌우면 $t x - \log(x-1)$ 이고, 미분해서 0으로 두면 $t - 1/(x-1) = 0$, 즉 $x(t) = 1 + 1/t$ 다. $p^\star = 1$ 이므로 간극은 $1/t$ — 부등식 제약이 $m=1$ 개이니 공식 $m/t$ 그대로다. $t = 1,\,10,\,100$ 에서 간극이 $1,\,0.1,\,0.01$ 로 정직하게 내려간다.

이 셋째 식이 실무적으로 왜 중요한가 하면, 멈출 시점을 미리 계산할 수 있다는 뜻이기 때문이다. 부등식 제약 $m = 100$ 개짜리 문제에서 간극 $10^{-8}$ 을 원한다면 $t \ge m/\epsilon = 10^{10}$ 까지만 키우면 되고, 외부 반복마다 $t$ 를 10배씩 올린다면 $t_0 = 1$ 에서 시작해 외부 반복 10번이면 끝이다. 각 반복의 뉴턴-랩슨법 스텝이 몇 번뿐이므로 전체 수십 스텝 — 상용 볼록 솔버가 문제 크기와 거의 무관하게 “스텝 20~50번”으로 수렴한다는 현장 경험담의 정체가 이것이다.

7. 알고리즘

• 내점법(interior-point method). 부등식 제약을 로그 장벽 $\phi(x) = -\sum_i \log(-f_i(x))$ 로 목적함수에 흡수시켜 $t f_0(x) + \phi(x)$ 를 푼다. $t$ 를 키워 가며 얻는 해의 궤적이 중심 경로(central path)이고, 이때 쌍대간극이 정확히 $m/t$ ($m$은 부등식 제약 개수)로 묶인다. 각 $t$ 에서 뉴턴-랩슨법을 몇 번 돌리면 되고, 전체 뉴턴 스텝 수가 $O(\sqrt{m}\,\log(1/\epsilon))$ 로 묶인다는 것이 네스테로프-네미로프스키의 자기일치(self-concordant) 이론의 결론이다.
• 근접 경사법(proximal gradient). 목적이 “매끄러운 부분 + 볼록하지만 미분 불가능한 부분”($f + g$)일 때 쓴다. $x_{k+1} = \mathrm{prox}_{\eta g}(x_k - \eta \nabla f(x_k))$ 로 매끄러운 쪽만 경사하강법으로 밀고, 나머지는 근접연산자로 정확히 처리한다. $g = \lambda \|x\|_1$ 이면 근접연산자가 소프트 임계화가 되어 그 유명한 ISTA가 나오고(라쏘·압축센싱의 주력 솔버다), 네스테로프 가속을 얹으면 수렴률이 $O(1/k)$ 에서 $O(1/k^2)$ 로 올라간다(FISTA, 벡·테불레 2009).
• ADMM(교대방향 승수법). 문제를 두 블록으로 쪼개고 증강 라그랑지안을 번갈아 최소화한다. 각 부분문제가 닫힌 형태로 풀리는 구조라면 대규모·분산 환경에서 강력하다. 수렴은 느리지만 “중간 정확도까지 빨리”가 필요한 통계·영상 문제에서 사실상 표준.

8. 공학에서의 쓰임

구조 최적화 쪽에서 볼록성은 대개 선물이 아니라 만들어 내는 것이다. 응력·변위 제약이 설계변수에 대해 비볼록이라, 위상 최적화의 주력 알고리즘인 MMA(Method of Moving Asymptotes, 스반베리 1987)와 그 전신 CONLIN은 매 반복에서 원 문제를 엄격히 볼록이고 분리 가능한 근사 부분문제로 바꿔 푸는 방식으로 동작한다. 근사 부분문제가 볼록이므로 안정적으로 풀리고, 점근선 위치를 갱신하며 원 문제를 따라간다. 형상 최적화와 민감도 해석 기반 설계 루프 전반이 같은 패턴을 쓴다.

제어 쪽에서는 모델 예측 제어가 매 샘플링 시각마다 유한구간 이차계획법 문제를 실시간으로 푸는 구조라, 볼록성이 곧 “정해진 밀리초 안에 답이 나온다”는 실시간 보장으로 직결된다. 통계·기계학습에서는 최소자승법, 라쏘, 로지스틱 회귀, 서포트 벡터 머신이 전부 볼록이며, 그래서 확률적 경사하강법의 수렴 보장이 깔끔하게 나온다. 반대로 심층 학습의 신경망은 비볼록이고, 그럼에도 잘 되는 이유는 아직 완전히 설명되지 않았다는 점이 이 대비를 더 흥미롭게 만든다.⁴⁵

9. 관련 문서

• 최적설계 · 지역 최적해
• 카루시-쿤-터커 조건 · 라그랑주 승수법
• 이차계획법 · 선형 상보성 문제
• 경사하강법 · 확률적 경사하강법 · 라인서치
• 준-뉴턴법 · 신뢰 영역 방법 · 헤세 행렬
• 쌍대성 · 내점법 · 근접 경사법 · 교대방향 승수법
• 선형계획법 · 이차계획법 · 반정부호 계획법 · 볼록 완화
• 위상 최적화 · 형상 최적화

10. Footnotes

1. Boyd, S. & Vandenberghe, L. (2004). Convex Optimization. 저자가 PDF를 무료로 공개해 둔 덕에, 이 바닥에서 “보이드 책 몇 쪽”이라는 말이 통용되는 몇 안 되는 교과서가 됐다. ↩

2. 그래서 CVX·CVXPY 같은 모델링 언어는 아예 “규율 있는 볼록 계획(DCP)“이라는 문법 규칙을 강제한다. 사용자가 규칙에 맞게 식을 쓰면 볼록성이 구성적으로 보장되고, 규칙을 어기면 파서가 거부한다. 수학적으로 볼록인데도 거부당해서 식을 다시 배열하는 것은 입문자의 통과의례. ↩

3. 보이드·반덴베르허 Convex Optimization 의 §5.3.2 예제다. 강의에서 이 예제를 만나면 “볼록이면 다 되는 줄 알았는데” 하는 표정이 강의실에 번진다. 다행히 실무에서 마주치는 문제는 거의 다 슬레이터를 만족한다 — 거의. ↩

4. 볼록 최적화 강의를 듣고 나면 세상 모든 문제를 볼록으로 캐스팅하려는 시기가 온다. 그러다 응력 제약이 있는 구조 문제를 만나 좌절하고, MMA 논문을 읽으며 “볼록으로 근사해서 반복하면 되잖아”로 돌아오는 것이 이 바닥 성장 서사다. ↩

5. 참고로 “볼록 완화(convex relaxation)“는 비볼록 문제에 던지는 표준 카드다. 조합 문제를 SDP로 완화해 풀고 반올림하는 계열(Goemans-Williamson의 MAX-CUT 0.878 근사가 대표)이 여기 속한다. 완화해서 얻은 값은 항상 원 문제의 하한이라, 최소한 “얼마나 나쁠 수 있는지”는 알 수 있다. ↩