최적화 정의·정리

다음 꼴의 문제를 최적화 문제(optimization problem)라 합니다.

집합 $C$의 임의의 두 점 $\mathbf x, \mathbf y$와 $0 \le \theta \le 1$에 대해 $\theta\mathbf x + (1 - \theta)\mathbf y \in C$이면 $C$를 볼록집합(convex set)이라 합니다.

볼록집합들의 교집합은 볼록집합입니다.

볼록집합에서 정의된 $f$가 모든 $\mathbf x, \mathbf y$와 $0 \le \theta \le 1$에 대해

미분가능한 $f$가 볼록일 필요충분조건은 모든 $\mathbf x, \mathbf y$에 대해

두 번 미분가능한 $f$가 볼록일 필요충분조건은 모든 $\mathbf x$에서 헤세 행렬 $\nabla^2 f(\mathbf x)$가 양의 준정부호(positive semidefinite, 모든 고윳값 $\ge 0$)인 것입니다. 일변수이면 $f''(x) \ge 0$입니다.

볼록집합 위의 볼록함수에서는 모든 국소 최솟값이 전역 최솟값입니다. 순볼록이면 최적해가 많아야 하나입니다.

$f$가 미분가능하고 $\mathbf x^*$가 (제약 없는) 국소 최솟값이면 $\nabla f(\mathbf x^*) = \mathbf 0$입니다.

$f$가 볼록이고 미분가능하면, $\nabla f(\mathbf x^*) = \mathbf 0$은 $\mathbf x^*$가 전역 최솟값일 필요충분조건입니다.

$\nabla f(\mathbf x^*) = \mathbf 0$일 때 헤세 행렬 $H = \nabla^2f(\mathbf x^*)$에 대해

$A$가 대칭이고 양의 정부호일 때 $f(\mathbf x) = \frac12\mathbf x^\top A\mathbf x - \mathbf b^\top\mathbf x$의 유일한 최솟값은 $\mathbf x^* = A^{-1}\mathbf b$이고, 최솟값은 $-\frac12\mathbf b^\top A^{-1}\mathbf b$입니다.

두 번 미분가능한 $f$의 헤세 행렬 고윳값이 모든 점에서 $m \le \lambda \le L$($m > 0$)이면, $f$를 $m$-강볼록(strongly convex)이고 $L$-매끄럽다(smooth)고 합니다. 비 $\kappa = L/m$을 조건수(condition number)라 합니다.

$f$가 $L$-매끄러우면(헤세 행렬의 고윳값 $\le L$) 모든 $\mathbf x, \mathbf y$에 대해

$\eta \le 1/L$로 경사하강법을 한 번 하면

$f$가 볼록이고 $L$-매끄러우며 $\eta = 1/L$이면

$f$가 $m$-강볼록이고 $L$-매끄러우며 $\eta = 1/L$이면

$\mathbf x_{k+1} = \mathbf x_k - [\nabla^2f(\mathbf x_k)]^{-1}\nabla f(\mathbf x_k)$.

$\nabla^2f$가 최솟값 $\mathbf x^*$에서 양의 정부호이고 립시츠 연속이면, $\mathbf x_0$가 충분히 가까울 때 상수 $C$가 있어

매 단계 데이터 $B$개(미니배치)를 무작위로 뽑아 $\mathbf g_k = \frac1B\sum_{i \in \text{batch}}\nabla\ell_i(\boldsymbol\theta_k)$로 그래디언트를 어림하고 $\boldsymbol\theta_{k+1} = \boldsymbol\theta_k - \eta_k\mathbf g_k$로 움직입니다.

모멘텀과 RMSProp을 합칩니다. $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-8}$이 기본값입니다.

$\min f(\mathbf x)$ s.t. $h_j(\mathbf x) = 0$ ($j = 1, \dots, p$)의 국소 최솟값 $\mathbf x^*$에서 $\nabla h_j(\mathbf x^*)$들이 일차독립이면, 수 $\nu_1, \dots, \nu_p$가 있어

적당한 정칙 조건 아래에서 $\mathbf x^*$가 국소 최솟값이면 $\boldsymbol\lambda^*, \boldsymbol\nu^*$가 있어 다음 네 조건이 성립합니다.

라그랑주 쌍대 함수(Lagrange dual function)는

$\boldsymbol\lambda \ge \mathbf 0$이면 $d(\boldsymbol\lambda, \boldsymbol\nu) \le p^*$입니다. 여기서 $p^*$는 원문제의 최솟값입니다.

원문제가 볼록이고, 모든 부등식 제약을 엄격하게 만족하는 점($g_i(\mathbf x) < 0$)이 하나라도 있으면 $d^* = p^*$(강한 쌍대성)입니다.

다음 꼴의 문제를 선형계획(linear program, LP)이라 합니다.

선형계획에 최적해가 있고 실행 가능 영역에 꼭짓점이 있으면, 최적해 가운데 적어도 하나는 꼭짓점입니다.

원문제와 쌍대 문제 중 하나에 최적해가 있으면 다른 하나에도 있고, 두 최적값이 같습니다.