최적화 이론 (Optimization Theory)

최적화 이론(Optimization Theory)은 주어진 조건 아래에서 어떤 값을 가장 크게 또는 가장 작게 만드는 방법을 연구하는 수학 분야입니다. "가장 좋은 답"을 체계적으로 찾는 학문이라고 할 수 있습니다.

이런 곳에 쓰여요

선수 지식: 미적분학, 선형대수학

난이도: ★★★★☆ (대학교)

최적화 문제의 정의

기본 구조

최적화 문제(Optimization Problem)란 목적함수(Objective Function)를 제약조건(Constraints) 하에서 최소화 또는 최대화하는 문제입니다. 표준 형식은 다음과 같습니다.

여기서 $f(x)$는 목적함수, $g_i(x) \le 0$은 부등식 제약조건(Inequality Constraint), $h_j(x) = 0$은 등식 제약조건(Equality Constraint)입니다. 모든 제약조건을 만족하는 $x$의 집합을 실행가능 영역(Feasible Region)이라 합니다.

최적해와 전역/지역 최적

실행가능 영역 내의 모든 점 $x$에 대해 $f(x^*) \le f(x)$를 만족하는 $x^*$를 전역 최적해(Global Optimum)라 합니다. 반면, $x^*$의 근방에서만 최소인 점을 지역 최적해(Local Optimum)라 합니다.

볼록집합과 볼록함수 (Convex Sets and Functions)

볼록집합의 정의

볼록집합(Convex Set)이란 집합 내의 임의의 두 점을 잇는 선분이 항상 집합 안에 포함되는 집합을 말합니다. 수학적으로, 집합 $C$가 볼록이면:

볼록함수의 정의

볼록함수(Convex Function)란 함수의 그래프 위의 임의의 두 점을 잇는 선분이 항상 그래프 위에 있거나 같은 함수를 말합니다.

볼록함수의 대표적인 예시는 다음과 같습니다.

• $f(x) = x^2$ — 이차함수 (위로 볼록하지 않은 포물선)
• $f(x) = e^x$ — 지수함수
• $f(x) = |x|$ — 절댓값 함수
• $f(x) = \max(0, x)$ — ReLU 함수 (딥러닝에서 자주 사용)

볼록 최적화의 핵심 성질

이 성질이 볼록 최적화(Convex Optimization)가 중요한 이유입니다. 볼록 문제에서는 "더 좋은 답이 다른 곳에 숨어 있을까?"라는 걱정을 할 필요가 없습니다.

무제약 최적화

필요조건 (1차 조건)

제약조건이 없는 최적화 문제 $\min_{x} f(x)$에서, $x^*$가 지역 최적해이면 반드시 다음을 만족합니다.

$\nabla f$는 그래디언트(Gradient)로, 각 변수에 대한 편미분을 모아 놓은 벡터입니다. 이 조건을 만족하는 점을 정류점(Stationary Point)이라 합니다.

충분조건 (2차 조건)

$\nabla f(x^*) = 0$을 만족하는 점이 지역 최소인지 확인하려면, 헤시안 행렬(Hessian Matrix) $H(x^*) = \nabla^2 f(x^*)$을 검사합니다.

예시: $f(x,y) = x^2 + 4y^2 - 2x + 8y$에서 $\nabla f = (2x-2, 8y+8) = (0,0)$을 풀면 $x^* = 1, y^* = -1$입니다. 헤시안 $H = \begin{pmatrix} 2 & 0 \\ 0 & 8 \end{pmatrix}$의 고유값이 $2, 8$으로 모두 양수이므로, $(1,-1)$은 지역(그리고 전역) 최솟값입니다.

경사하강법 (Gradient Descent)

기본 아이디어

경사하강법(Gradient Descent)은 현재 위치에서 함수값이 가장 빨리 감소하는 방향, 즉 음의 그래디언트(Negative Gradient) 방향으로 조금씩 이동하는 반복 알고리즘입니다.

여기서 $\alpha > 0$는 학습률(Learning Rate) 또는 스텝 크기(Step Size)라 합니다.

학습률의 영향

학습률 $\alpha$의 선택은 수렴 속도와 안정성에 큰 영향을 줍니다.

• $\alpha$가 너무 작으면: 수렴이 매우 느립니다. 산에서 아기 걸음으로 내려가는 것과 같습니다.
• $\alpha$가 너무 크면: 최솟값을 지나쳐서 발산할 수 있습니다. 산에서 너무 큰 걸음으로 내딛다가 반대편 산으로 넘어가는 것과 같습니다.
• $\alpha$가 적절하면: 빠르고 안정적으로 수렴합니다.

수렴성 분석

$f$가 볼록이고 그래디언트가 립시츠 연속(Lipschitz Continuous)일 때, 즉 $\|\nabla f(x) - \nabla f(y)\| \le L\|x-y\|$를 만족하면, 학습률 $\alpha = 1/L$에서 경사하강법의 수렴 속도는 다음과 같습니다.

즉 $O(1/k)$의 속도로 수렴하며, 이를 차선 수렴(Sublinear Convergence)이라 합니다.

$f$가 강볼록(Strongly Convex)이면, 즉 $\nabla^2 f(x) \succeq \mu I$이면 선형 수렴(Linear Convergence)을 달성합니다.

뉴턴법과 준뉴턴법

뉴턴법 (Newton's Method)

뉴턴법(Newton's Method)은 2차 도함수 정보(헤시안)까지 활용하여 더 빠르게 수렴하는 방법입니다.

뉴턴법은 최적점 근처에서 이차 수렴(Quadratic Convergence)을 보입니다. 즉, 반복할 때마다 유효 자릿수가 대략 두 배씩 늘어납니다.

준뉴턴법 (Quasi-Newton Methods)

준뉴턴법(Quasi-Newton Method)은 헤시안을 직접 계산하지 않고 근사(Approximation)하여 사용합니다. 가장 유명한 방법이 BFGS(Broyden-Fletcher-Goldfarb-Shanno) 알고리즘입니다.

여기서 $s_k = x_{k+1} - x_k$, $y_k = \nabla f(x_{k+1}) - \nabla f(x_k)$입니다. BFGS는 헤시안 역행렬의 근사를 $O(n^2)$에 갱신하므로 대규모 문제에서도 실용적입니다.

메모리 제한이 있는 대규모 문제에서는 L-BFGS(Limited-memory BFGS)가 널리 사용됩니다. 최근 $m$개(보통 $m \approx 10$)의 벡터 쌍 $(s_k, y_k)$만 저장하여 $O(mn)$의 메모리와 계산량으로 동작합니다.

라그랑주 승수법 (Lagrange Multipliers)

등식 제약 최적화

등식 제약조건 $h(x) = 0$ 하에서 $f(x)$를 최소화하는 문제를 생각합니다. 라그랑주 함수(Lagrangian)를 다음과 같이 정의합니다.

여기서 $\lambda$는 라그랑주 승수(Lagrange Multiplier)입니다.

기하학적 해석

등식 제약조건 $h(x) = 0$이 정의하는 곡면 위에서 $f$의 최적점에서는, $f$의 그래디언트와 $h$의 그래디언트가 평행합니다. 즉, 제약 곡면을 따라서는 $f$를 더 줄일 수 없다는 뜻입니다.

예시

$f(x,y) = x^2 + y^2$를 $h(x,y) = x + y - 1 = 0$ 하에서 최소화합니다.

라그랑주 함수: $\mathcal{L} = x^2 + y^2 + \lambda(x + y - 1)$

필요조건:

$2x = 2y$이므로 $x = y = 1/2$, $\lambda = -1$입니다. 최솟값은 $f(1/2, 1/2) = 1/2$입니다.

KKT 조건 (Karush-Kuhn-Tucker)

부등식 제약이 포함된 경우

라그랑주 승수법을 부등식 제약조건까지 확장한 것이 KKT 조건(Karush-Kuhn-Tucker Conditions)입니다. 일반적인 최적화 문제의 라그랑주 함수는 다음과 같습니다.

상보 이완성의 의미

상보 이완성 $\mu_i^* g_i(x^*) = 0$은 두 가지 경우를 뜻합니다.

• $g_i(x^*) < 0$ (제약이 여유가 있음) → $\mu_i^* = 0$ (해당 제약은 최적해에 영향을 주지 않음)
• $\mu_i^* > 0$ (제약이 최적해에 영향을 줌) → $g_i(x^*) = 0$ (제약이 등호로 만족됨, 즉 활성 제약(Active Constraint))

볼록 최적화 문제에서는 KKT 조건이 필요충분조건입니다. 즉, KKT 조건을 만족하는 점은 반드시 전역 최적해입니다.

쌍대성 (Duality)

라그랑주 쌍대함수

라그랑주 함수를 $x$에 대해 최소화한 것을 라그랑주 쌍대함수(Lagrange Dual Function)라 합니다.

쌍대함수는 항상 원래 문제의 최적값의 하한을 제공합니다. 이를 약쌍대성(Weak Duality)이라 합니다.

약쌍대성과 강쌍대성

슬레이터 조건이란 실행가능 영역의 내부에 모든 부등식 제약을 엄격하게 만족하는 점이 존재한다는 것입니다. 즉, $g_i(x) < 0$을 모든 $i$에 대해 만족하는 $x$가 존재해야 합니다.

쌍대 문제의 활용

쌍대성이 중요한 이유는 다음과 같습니다.

• 원초 문제보다 쌍대 문제가 풀기 쉬운 경우가 많습니다.
• 쌍대 간극을 이용하여 현재 해의 최적성 보증(Optimality Certificate)을 얻을 수 있습니다.
• 서포트 벡터 머신(SVM) 등 머신러닝 알고리즘에서 쌍대 문제가 핵심적으로 사용됩니다.

선형계획법 (Linear Programming)

표준형

선형계획법(Linear Programming, LP)은 목적함수와 제약조건이 모두 선형(1차)인 최적화 문제입니다.

여기서 $c \in \mathbb{R}^n$은 비용 벡터, $A \in \mathbb{R}^{m \times n}$은 제약 행렬, $b \in \mathbb{R}^m$은 제약 상한입니다.

실행가능 영역의 기하

LP의 실행가능 영역은 볼록 다면체(Convex Polytope)이며, 선형 목적함수의 최적값은 반드시 다면체의 꼭짓점(Vertex)에서 달성됩니다.

심플렉스법 (Simplex Method)

조지 단치그(George Dantzig)가 1947년에 발명한 심플렉스법(Simplex Method)은 다면체의 꼭짓점을 따라 이동하면서 목적함수를 개선하는 알고리즘입니다.

1. 실행가능 꼭짓점에서 출발합니다.
2. 인접한 꼭짓점 중 목적함수 값이 더 좋은 곳으로 이동합니다.
3. 더 이상 개선할 수 없으면 현재 꼭짓점이 최적해입니다.

최악의 경우 지수 시간이 걸릴 수 있으나, 실제로는 매우 효율적으로 동작합니다. 다항 시간 알고리즘으로는 카르마르카르(Karmarkar)의 내부점법(Interior Point Method)이 있습니다.

이차계획법 (Quadratic Programming)

정의

이차계획법(Quadratic Programming, QP)은 목적함수가 이차(2차)이고 제약조건이 선형인 최적화 문제입니다.

여기서 $Q$는 대칭 행렬입니다. $Q$가 양의 반정부호(Positive Semidefinite)이면 볼록 QP이고, 효율적으로 풀 수 있습니다.

활용 예시

• 포트폴리오 최적화(Portfolio Optimization): 마코위츠 모형에서 기대 수익률 제약 하에 분산을 최소화하는 문제가 QP입니다. $$\min_{w} \frac{1}{2} w^\top \Sigma w, \quad \text{s.t.} \quad \mu^\top w \ge r, \; \mathbf{1}^\top w = 1, \; w \ge 0$$
• 서포트 벡터 머신(SVM): 마진(Margin)을 최대화하는 분류기를 학습하는 문제가 QP로 정식화됩니다.

반정부호 계획법 (Semidefinite Programming)

정의

반정부호 계획법(Semidefinite Programming, SDP)은 변수가 행렬이고, 그 행렬이 양의 반정부호(Positive Semidefinite)라는 제약을 가지는 최적화 문제입니다.

여기서 $\langle C, X \rangle = \text{tr}(C^\top X)$는 행렬 내적이고, $X \succeq 0$는 $X$가 양의 반정부호임을 뜻합니다.

LP, QP, SDP의 관계

SDP는 LP와 QP를 포함하는 더 넓은 범위의 문제입니다.

SDP는 제어이론, 조합 최적화의 완화(Relaxation), 양자 정보 이론 등에서 중요하게 활용됩니다.

정수계획법과 조합 최적화

정수계획법 (Integer Programming)

정수계획법(Integer Programming, IP)은 변수의 일부 또는 전부가 정수여야 하는 최적화 문제입니다. 변수가 0 또는 1만 취하는 경우를 이진 계획법(Binary Programming)이라 합니다.

정수 제약이 추가되면 문제가 극도로 어려워집니다. 일반적으로 정수계획법은 NP-난해(NP-hard)입니다.

대표적인 조합 최적화 문제

• 외판원 문제(Traveling Salesman Problem, TSP): $n$개의 도시를 모두 방문하고 출발점으로 돌아오는 최단 경로를 구하는 문제입니다.
• 배낭 문제(Knapsack Problem): 제한된 용량의 배낭에 물건을 담아 가치를 최대화하는 문제입니다.
• 그래프 색칠 문제(Graph Coloring): 인접한 정점이 같은 색을 갖지 않도록 하면서 사용하는 색의 수를 최소화하는 문제입니다.

풀이 방법

• 분기한정법(Branch and Bound): LP 완화를 이용하여 해 공간을 체계적으로 탐색합니다.
• 절단평면법(Cutting Plane Method): LP 완화의 최적해가 정수가 아니면 제약을 추가하여 정수해로 유도합니다.
• 메타휴리스틱(Metaheuristic): 유전 알고리즘, 시뮬레이티드 어닐링 등으로 근사 해를 구합니다.

응용

머신러닝 (Machine Learning)

머신러닝에서 모델 학습은 곧 최적화 문제입니다. 손실함수(Loss Function)를 최소화하여 모델의 파라미터를 결정합니다.

• 선형 회귀: $\min_w \|Xw - y\|^2$ — 볼록 QP, 해석적 해 $w = (X^\top X)^{-1}X^\top y$
• 로지스틱 회귀: 볼록 최적화, 경사하강법 또는 뉴턴법으로 풀이
• 딥러닝: 비볼록 최적화, 확률적 경사하강법(SGD)과 Adam 등의 적응적 방법 사용
• SVM: 쌍대 QP 문제, SMO(Sequential Minimal Optimization) 알고리즘

제어이론 (Control Theory)

동적 시스템의 제어 문제는 최적 제어(Optimal Control)로 정식화됩니다.

여기서 $x(t)$는 상태, $u(t)$는 제어 입력입니다. 폰트리아긴 최대 원리(Pontryagin's Maximum Principle)와 동적 프로그래밍(Dynamic Programming)이 주요 풀이 도구입니다.

경제학 (Economics)

경제학에서 최적화는 핵심 방법론입니다.

• 소비자 이론: 예산 제약 하에서 효용을 최대화하는 문제
• 생산자 이론: 비용을 최소화하거나 이윤을 최대화하는 문제
• 균형 이론: 내쉬 균형(Nash Equilibrium)은 각 참여자가 자신의 전략을 최적화한 결과

볼록성 심화 (Advanced Convexity)

분리 정리 (Separating Hyperplane Theorem)

두 볼록집합이 서로 만나지 않으면, 이들을 분리하는 초평면이 존재합니다. 이를 분리 정리(Separating Hyperplane Theorem)라 합니다.

이 정리는 볼록 최적화에서 쌍대성 이론의 기초가 되며, 서포트 벡터 머신(SVM)의 이론적 근거이기도 합니다.

지지 초평면 정리 (Supporting Hyperplane Theorem)

볼록집합의 경계 위의 임의의 점에서 집합 전체를 한쪽에 포함하는 초평면이 존재합니다.

볼록 결합과 볼록 껍질 (Convex Combination and Convex Hull)

볼록 결합(Convex Combination)이란 점들 $x_1, \ldots, x_k$에 대해 다음과 같은 조합을 말합니다.

점들의 집합 $S$에 대한 볼록 껍질(Convex Hull) $\text{conv}(S)$은 $S$의 모든 볼록 결합의 집합이며, $S$를 포함하는 가장 작은 볼록집합입니다.

볼록 쌍대성 (Convex Duality)

볼록함수 $f$의 켤레 함수(Conjugate Function) 또는 르장드르 변환(Legendre Transform)은 다음과 같이 정의됩니다.

켤레 함수의 주요 성질은 다음과 같습니다.

• $f^*$는 항상 볼록함수입니다 (원래 $f$가 볼록이 아니더라도).
• $f$가 닫힌 볼록함수이면, $f^{**} = f$입니다 (쌍대 대칭성).
• 펜첼 부등식(Fenchel's Inequality): $f(x) + f^*(y) \ge y^\top x$.
• $y \in \partial f(x) \iff x \in \partial f^*(y) \iff f(x) + f^*(y) = x^\top y$.

대표적인 켤레 함수의 예시는 다음과 같습니다.

• $f(x) = \frac{1}{2}\|x\|^2 \implies f^*(y) = \frac{1}{2}\|y\|^2$
• $f(x) = e^x \implies f^*(y) = y\ln y - y$ ($y > 0$)
• $f(x) = \|x\|_1 \implies f^*(y) = I_{\|y\|_\infty \le 1}(y)$ (지시 함수)

경사하강법 심화

수렴률 분석의 상세

경사하강법의 수렴 속도를 정밀하게 분석하기 위해 함수의 성질에 따른 분류가 중요합니다.

가속 경사하강법 — 네스테로프 가속 (Nesterov's Accelerated Gradient)

유리 네스테로프(Yurii Nesterov)는 1983년에 볼록함수에 대한 최적의 1차 방법을 제시하였습니다. 네스테로프 가속 경사하강법(Nesterov's Accelerated Gradient Descent, NAG)의 갱신 규칙은 다음과 같습니다.

NAG는 볼록함수에서 $O(1/k^2)$의 수렴 속도를 달성하며, 이는 1차 방법의 최적 수렴률(Optimal Rate)임이 증명되어 있습니다.

모멘텀 방법 (Momentum Method)

폴리악(Polyak)의 중량 볼 방법(Heavy Ball Method)은 관성을 이용하여 수렴을 가속합니다.

여기서 $\beta \in [0,1)$는 모멘텀 계수입니다. 물리적으로 이해하면, 무거운 공이 경사면을 굴러 내려갈 때 관성에 의해 골짜기를 빠르게 통과하는 것과 같습니다.

조건수 $\kappa$가 클 때, 가속 방법은 표준 경사하강법에 비해 $\sqrt{\kappa}$배 빠르게 수렴합니다.

확률적 경사하강법 (Stochastic Gradient Descent)

기본 SGD

목적함수가 합의 형태 $f(x) = \frac{1}{n}\sum_{i=1}^{n} f_i(x)$일 때 (예: 머신러닝에서 각 데이터 샘플의 손실), 전체 그래디언트를 계산하는 비용이 큽니다. 확률적 경사하강법(Stochastic Gradient Descent, SGD)은 매 반복에서 무작위로 하나의 $f_i$를 선택하여 그래디언트를 추정합니다.

핵심 성질은 $\mathbb{E}[\nabla f_{i_k}(x_k)] = \nabla f(x_k)$, 즉 불편 추정량(Unbiased Estimator)이라는 점입니다. 다만 분산이 존재하므로, 학습률을 점진적으로 감소시켜야 수렴합니다.

미니배치 SGD (Mini-batch SGD)

실제로는 하나의 샘플 대신 미니배치(Mini-batch) $B_k \subset \{1,\ldots,n\}$를 사용하여 분산을 줄입니다.

미니배치 크기 $|B_k|$가 커지면 분산은 $1/|B_k|$에 비례하여 감소합니다.

Adam (Adaptive Moment Estimation)

Adam은 킹마와 바(Kingma & Ba, 2015)가 제안한 적응적 학습률 방법으로, 1차 모멘트(평균)와 2차 모멘트(비중심 분산)를 지수 이동 평균으로 추정합니다.

여기서 $g_k = \nabla f_{i_k}(x_k)$이고, 기본 하이퍼파라미터는 $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$입니다.

AdaGrad

AdaGrad(Duchi et al., 2011)는 각 파라미터별로 과거 그래디언트의 누적 제곱합에 반비례하여 학습률을 조절합니다.

희소한(Sparse) 그래디언트를 가지는 문제에서 효과적이나, 학습률이 단조 감소하여 학습이 너무 일찍 멈출 수 있다는 단점이 있습니다.

RMSProp

RMSProp(Hinton, 2012)은 AdaGrad의 학습률 소멸 문제를 해결하기 위해 지수 이동 평균을 사용합니다.

일반적으로 $\gamma = 0.9$을 사용합니다. RMSProp는 Adam의 2차 모멘트 부분과 동일한 구조입니다.

내부점 방법 (Interior Point Methods)

장벽 함수 (Barrier Function)

내부점 방법(Interior Point Method)은 부등식 제약 $g_i(x) \le 0$을 목적함수에 장벽(Barrier)으로 포함시켜 제약 없는 문제로 변환하는 접근법입니다.

로그 장벽 함수(Logarithmic Barrier Function)를 사용한 근사 문제는 다음과 같습니다.

여기서 $t > 0$는 장벽 매개변수입니다. $t$가 커질수록 근사 문제의 해가 원래 문제의 해에 가까워집니다.

중심 경로 (Central Path)

$t$를 변화시킬 때 근사 문제의 해 $x^*(t)$가 그리는 궤적을 중심 경로(Central Path)라 합니다. 내부점 방법은 이 중심 경로를 따라 이동하면서 최적해에 접근합니다.

알고리즘 절차

1. 실행가능 영역의 내부점 $x_0$에서 출발하고, $t := t_0 > 0$, $\mu > 1$로 설정합니다.
2. 중심화 단계(Centering Step): 뉴턴법으로 $\min_x \; t \cdot f(x) - \sum \ln(-g_i(x))$를 풀어 $x^*(t)$를 구합니다.
3. $m/t < \epsilon$이면 종료합니다 (쌍대 간극 $\le m/t$).
4. $t := \mu \cdot t$로 갱신하고 2단계로 돌아갑니다.

원-쌍대 방법 (Primal-Dual Methods)

원-쌍대 내부점 방법

원-쌍대 내부점 방법(Primal-Dual Interior Point Method)은 원초 변수 $x$와 쌍대 변수 $(\lambda, \mu)$를 동시에 갱신하는 방법입니다. KKT 조건을 변형한 다음 시스템을 뉴턴법으로 풉니다.

여기서 두 번째 방정식의 $(1/t)\mathbf{1}$은 상보 이완성 조건을 완화한 것입니다. $t \to \infty$이면 정확한 KKT 조건에 수렴합니다.

장벽 방법과의 비교

• 장벽 방법: 외부 루프(매개변수 $t$ 갱신)와 내부 루프(뉴턴 반복)의 이중 루프 구조입니다.
• 원-쌍대 방법: 단일 루프 구조로 원초·쌍대 변수를 동시 갱신하여 실제로 더 빠른 수렴을 보이는 경우가 많습니다.

교대 방향 승수법 (ADMM)

교대 방향 승수법(Alternating Direction Method of Multipliers, ADMM)은 증강 라그랑주 방법의 변형으로, 분리 가능한 구조를 가진 문제에 효과적입니다.

문제 $\min_{x,z} f(x) + g(z), \; \text{s.t.} \; Ax + Bz = c$에 대해, ADMM의 갱신 규칙은 다음과 같습니다.

여기서 $\rho > 0$는 페널티 매개변수, $u_k$는 스케일링된 쌍대 변수입니다. ADMM은 분산 최적화, LASSO 회귀, 합의 최적화(Consensus Optimization) 등에 널리 사용됩니다.

반정부호 계획법 심화

SDP 완화 (SDP Relaxation)

NP-난해 조합 최적화 문제의 근사해를 구하는 강력한 도구가 SDP 완화(SDP Relaxation)입니다. 기본 아이디어는 정수 변수 $x_i \in \{-1, +1\}$를 행렬 변수 $X = xx^\top$로 치환하고, $\text{rank}(X) = 1$ 제약을 완화하여 $X \succeq 0$으로 대체하는 것입니다.

MAX-CUT 문제와 게만스-윌리엄슨 알고리즘

MAX-CUT 문제는 그래프의 정점을 두 집합으로 분할하여, 집합 사이를 지나는 간선의 가중치 합을 최대화하는 NP-난해 문제입니다. 정수 계획법 형태로 쓰면:

이를 SDP로 완화하면:

여기서 $L$은 가중 라플라시안 행렬입니다.

원뿔 최적화 (Conic Optimization)

원뿔 계획법의 일반 형태

원뿔 계획법(Conic Programming)은 볼록 원뿔 $\mathcal{K}$ 위의 제약을 가지는 최적화 문제입니다.

원뿔의 종류에 따라 다양한 문제 유형이 나타납니다.

• $\mathcal{K} = \mathbb{R}^n_+$ (비음 직교형) → 선형계획법(LP)
• $\mathcal{K} = \mathcal{Q}^n$ (2차 원뿔) → 2차 원뿔 계획법(SOCP)
• $\mathcal{K} = \mathcal{S}^n_+$ (양의 반정부호 행렬 원뿔) → 반정부호 계획법(SDP)

2차 원뿔 계획법 (SOCP)

2차 원뿔 계획법(Second-Order Cone Programming, SOCP)은 다음 형태의 제약을 가집니다.

이는 2차 원뿔(Second-Order Cone) 또는 로렌츠 원뿔(Lorentz Cone) $\mathcal{Q}^n = \{(x,t) : \|x\|_2 \le t\}$ 위의 제약입니다.

SOCP의 응용 예시는 다음과 같습니다.

• 강건 선형계획법: 데이터에 불확실성이 있는 LP 문제
• 시설 배치 문제: 유클리드 거리를 포함하는 최적화
• 포트폴리오 최적화: 위험 제약이 노름 형태인 경우

조합 최적화 심화

분기한정법 (Branch and Bound)

분기한정법(Branch and Bound)은 정수계획법을 정확하게 푸는 대표적인 알고리즘입니다. 해 공간을 체계적으로 분할(Branch)하고, 각 부분 문제의 하한(Bound)을 구하여 가능성이 없는 가지를 가지치기(Pruning)합니다.

1. 완화(Relaxation): 정수 제약을 완화한 LP를 풀어 하한을 구합니다.
2. 분기(Branching): LP 해에서 정수가 아닌 변수 $x_j = f$를 선택하여, $x_j \le \lfloor f \rfloor$와 $x_j \ge \lceil f \rceil$로 두 개의 하위 문제를 만듭니다.
3. 한정(Bounding): 하위 문제의 LP 완화 최적값이 현재까지의 최적 정수해보다 나쁘면 가지치기합니다.
4. 모든 가지를 탐색할 때까지 반복합니다.

동적 프로그래밍 (Dynamic Programming)

동적 프로그래밍(DP)은 문제를 하위 문제로 분할하고, 하위 문제의 해를 재활용하여 전체 문제를 효율적으로 풀어내는 기법입니다. 벨만 방정식(Bellman Equation)이 핵심입니다.

여기서 $V(S)$는 상태 $S$에서의 최적 비용, $A(S)$는 가능한 행동, $T(S,a)$는 전이 함수입니다.

배낭 문제의 DP 풀이를 예로 들면, 아이템 $i$의 무게 $w_i$, 가치 $v_i$, 배낭 용량 $W$에 대해:

시간 복잡도는 $O(nW)$로, 이를 의사 다항 시간(Pseudo-polynomial Time)이라 합니다.

근사 알고리즘과 근사비

NP-난해 문제에 대해 다항 시간 내에 최적해에 가까운 해를 보장하는 근사 알고리즘(Approximation Algorithm)이 중요합니다.

확률적 최적화 (Stochastic Optimization)

기본 구조

확률적 최적화(Stochastic Optimization)는 불확실성이 있는 상황에서의 최적 의사결정을 다룹니다. 목적함수나 제약조건이 확률변수 $\xi$에 의존합니다.

기회 제약 최적화 (Chance-Constrained Optimization)

기회 제약(Chance Constraint)은 확률적 제약이 높은 확률로 만족되기를 요구합니다.

여기서 $\epsilon$은 허용되는 위반 확률입니다. 예를 들어, 발전량 계획에서 "수요를 95% 이상의 확률로 충족해야 한다"는 제약을 $\epsilon = 0.05$로 모형화합니다.

$\xi$가 정규분포 $\mathcal{N}(\bar{\xi}, \Sigma)$이고 $g$가 $\xi$에 대해 선형이면, 기회 제약은 SOCP로 변환할 수 있습니다.

강건 최적화 (Robust Optimization)

강건 최적화(Robust Optimization)는 불확실성의 확률 분포를 가정하지 않고, 불확실성 집합 $\mathcal{U}$ 내의 최악의 경우에 대해 최적화합니다.

불확실성 집합의 형태에 따라 변환 결과가 달라집니다.

• $\mathcal{U}$가 다면체(Polyhedral) → LP로 변환 가능
• $\mathcal{U}$가 타원체(Ellipsoidal) → SOCP로 변환 가능
• $\mathcal{U}$가 반정부호 행렬 집합 → SDP로 변환 가능

다목적 최적화 (Multi-Objective Optimization)

파레토 최적 (Pareto Optimality)

여러 목적함수를 동시에 최적화하는 문제를 다목적 최적화(Multi-Objective Optimization)라 합니다.

일반적으로 모든 목적을 동시에 최적화하는 해는 존재하지 않으며, 대신 파레토 최적(Pareto Optimal) 해의 집합을 구합니다.

파레토 최적 해의 집합이 목적함수 공간에서 이루는 곡면을 파레토 전선(Pareto Front)이라 합니다.

풀이 방법

• 가중합 방법(Weighted Sum): $\min_x \sum_{i=1}^p w_i f_i(x)$, $w_i \ge 0$. 가중치를 변경하며 파레토 전선을 탐색합니다. 볼록이 아닌 파레토 전선은 찾지 못할 수 있습니다.
• $\epsilon$-제약법($\epsilon$-Constraint): 하나의 목적만 최적화하고 나머지는 제약으로 변환합니다. $\min f_1(x), \; \text{s.t.} \; f_i(x) \le \epsilon_i$. 비볼록 파레토 전선도 찾을 수 있습니다.
• 진화 알고리즘: NSGA-II(Non-dominated Sorting Genetic Algorithm II)가 대표적입니다.

비선형 계획법 (Nonlinear Programming)

순차 이차 계획법 (SQP)

순차 이차 계획법(Sequential Quadratic Programming, SQP)은 비선형 제약 최적화 문제를 반복적으로 QP 부분 문제로 근사하여 푸는 방법입니다.

일반 비선형 계획 문제:

각 반복에서 라그랑주 함수의 2차 근사로부터 다음 QP 부분 문제를 풉니다.

여기서 $B_k$는 라그랑주 함수의 헤시안 또는 그 근사이고, $d$는 탐색 방향입니다. $x_{k+1} = x_k + \alpha_k d_k$로 갱신합니다.

증강 라그랑주 방법 (Augmented Lagrangian Method)

증강 라그랑주 방법(ALM)은 라그랑주 함수에 제약 위반에 대한 2차 페널티 항을 추가합니다.

순수 페널티 방법과 달리, $\rho$를 무한대로 보내지 않아도 수렴하며 수치적 조건이 양호합니다.

응용 심화

포트폴리오 최적화 (Portfolio Optimization)

마코위츠 평균-분산 모형(Mean-Variance Model)은 기대 수익률과 위험(분산)의 최적 균형을 찾습니다.

여기서 $w$는 자산 비중 벡터, $\Sigma$는 자산 수익률의 공분산 행렬, $\mu$는 기대 수익률 벡터, $r_{\text{target}}$은 목표 수익률입니다.

실무에서는 다음과 같은 확장이 사용됩니다.

• CVaR(Conditional Value at Risk) 최소화: 꼬리 위험을 관리하는 모형으로, LP로 정식화 가능합니다.
• 강건 포트폴리오 최적화: 기대 수익률 $\mu$의 불확실성을 고려한 모형입니다.
• 거래 비용 포함: 포트폴리오 재조정 비용을 반영합니다.

제어 이론에서의 최적화

선형 시스템 $\dot{x} = Ax + Bu$의 LQR(Linear Quadratic Regulator) 문제는 다음과 같습니다.

이 문제의 해는 리카티 방정식(Riccati Equation)을 풀어 얻습니다.

최적 제어 입력은 $u^*(t) = -R^{-1}B^\top P x(t)$입니다.

모델 예측 제어(MPC, Model Predictive Control)는 매 시점에서 유한 구간의 최적 제어 문제를 풀어 실시간 제어를 수행합니다. 각 시점에서 QP 또는 비선형 계획 문제를 풀어야 하므로 고속 최적화 솔버가 필수적입니다.

신경망 학습과 최적화

딥러닝에서 신경망의 학습은 대규모 비볼록 최적화 문제입니다.

여기서 $\theta$는 네트워크 파라미터, $\ell$은 손실함수입니다. 주요 최적화 관련 현상은 다음과 같습니다.

• 손실 곡면의 특성: 고차원 비볼록 문제에서 지역 최솟값은 대부분 전역 최솟값에 가까운 성능을 보입니다. 진정한 문제는 안장점(Saddle Point)입니다.
• 학습률 스케줄링: 워밍업(Warmup), 코사인 감쇠(Cosine Decay), 단계적 감쇠(Step Decay) 등의 전략이 사용됩니다.
• 배치 정규화(Batch Normalization): 손실 곡면을 매끄럽게 하여 최적화를 용이하게 합니다.
• 가중치 감쇠(Weight Decay): $L_2$ 정규화 $\|\theta\|^2$를 추가하여 과적합을 방지합니다. 이는 Adam과 결합 시 AdamW로 구현됩니다.

요약 비교표

참고 문헌 및 관련 페이지

• Boyd, S. & Vandenberghe, L. — Convex Optimization, Cambridge University Press
• Nocedal, J. & Wright, S. J. — Numerical Optimization, Springer
• Bertsimas, D. & Tsitsiklis, J. N. — Introduction to Linear Optimization, Athena Scientific
• Luenberger, D. G. & Ye, Y. — Linear and Nonlinear Programming, Springer
• 미적분학 — 그래디언트, 헤시안의 기초
• 선형대수학 — 행렬, 고유값, 양정부호 행렬
• 수치해석 — 반복법의 수렴 분석
• 확률론 — 확률적 최적화
• 인공지능 수학 — 머신러닝에서의 최적화 응용