볼록 최적화

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. 알고리즘[편집]

• 내점법(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).
• ADMM. 문제를 두 블록으로 쪼개고 증강 라그랑지안을 번갈아 최소화한다. 각 부분문제가 닫힌 형태로 풀리는 구조라면 대규모·분산 환경에서 강력하다. 수렴은 느리지만 “중간 정확도까지 빨리”가 필요한 통계·영상 문제에서 사실상 표준.

7. 공학에서의 쓰임[편집]

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

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

8. 관련 문서[편집]

• 최적설계 · 지역 최적해
• 카루시-쿤-터커 조건 · 라그랑주 승수법
• 이차계획법 · 선형 상보성 문제
• 경사하강법 · 확률적 경사하강법 · 라인서치
• 준-뉴턴법 · 신뢰 영역 방법 · 헤세 행렬
• 위상 최적화 · 형상 최적화

9. Footnotes[편집]

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

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

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

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