Linearism › 최적화 › OP.2

2장. 최적성 조건

최적화 · 1부. 볼록성과 최적성

기본 · 약 10분 · 연습문제 5

요약

임계점과 1계 필요조건, 2계 충분조건, 안장점, 강볼록성과 조건수, 이차함수의 닫힌 해

최솟값이 어디에 있는지 알려면 먼저 “최솟값이라면 반드시 만족해야 하는 조건”(필요조건)과 “이것만 확인하면 최솟값이라고 말할 수 있는 조건”(충분조건)을 알아야 합니다. 고등학교에서 f′(x)=0f'(x) = 0을 풀고 f′′f''의 부호를 본 것을 여러 변수로 넓힌 것이 이 장입니다. 그리고 반복 알고리즘이 얼마나 빨리 수렴할지를 정하는 수, 조건수를 소개합니다.

2.1 1계 필요조건

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

증명. 어떤 방향 d\mathbf d로 ∇f(x∗)⊤d<0\nabla f(\mathbf x^*)^\top\mathbf d < 0이면, 그 방향으로 조금 가면 ff가 줄어듭니다. 그래디언트가 0이 아니면 d=−∇f(x∗)\mathbf d = -\nabla f(\mathbf x^*)가 그런 방향이므로 모순입니다. □

∇f(x)=0\nabla f(\mathbf x) = \mathbf 0인 점을 임계점(critical point) 또는 정류점(stationary point)이라 합니다. 임계점은 최솟값일 수도, 최댓값일 수도, 둘 다 아닌 안장점일 수도 있습니다.

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

증명. 1장 정리 1.8에 ∇f(x∗)=0\nabla f(\mathbf x^*) = \mathbf 0을 넣으면 모든 y\mathbf y에 대해 f(y)≥f(x∗)f(\mathbf y) \ge f(\mathbf x^*)입니다. □

2.2 2계 조건

볼록이 아니면 헤세 행렬로 임계점을 분류합니다(다변수 미적분 4장).

정리 2.3. ∇f(x∗)=0\nabla f(\mathbf x^*) = \mathbf 0일 때 헤세 행렬 H=∇2f(x∗)H = \nabla^2f(\mathbf x^*)에 대해

  • HH가 양의 정부호(고윳값이 모두 양수)이면 순 국소 최솟값,
  • 음의 정부호이면 순 국소 최댓값,
  • 양수와 음수 고윳값이 섞여 있으면 안장점(saddle point),
  • 0인 고윳값이 있으면 이 판정으로는 알 수 없습니다.

예제 2.4. f(x,y)=x3−3x+y2f(x, y) = x^3 - 3x + y^2. ∇f=(3x2−3,2y)=0\nabla f = (3x^2 - 3, 2y) = \mathbf 0에서 임계점은 (1,0)(1, 0)과 (−1,0)(-1, 0). 헤세 행렬 diag(6x,2)\mathrm{diag}(6x, 2)는 (1,0)(1, 0)에서 diag(6,2)\mathrm{diag}(6, 2)로 국소 최솟값, (−1,0)(-1, 0)에서 diag(−6,2)\mathrm{diag}(-6, 2)로 안장점입니다.

고차원에서는 안장점이 국소 최솟값보다 훨씬 흔합니다. 고윳값 nn개가 모두 양수일 확률보다 섞여 있을 확률이 훨씬 크기 때문입니다. 딥러닝 이론에서 “학습이 멈추는 곳은 대부분 나쁜 국소 최솟값이 아니라 안장점 근처의 평평한 곳”이라는 주장이 여기서 나옵니다.

2.3 이차함수

가장 중요한 모형 문제입니다. 모든 매끄러운 함수는 최솟값 근처에서 이차함수처럼 보이기 때문입니다(테일러 전개).

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

증명. ∇f=Ax−b=0\nabla f = A\mathbf x - \mathbf b = \mathbf 0에서 x∗=A−1b\mathbf x^* = A^{-1}\mathbf b. 헤세 행렬 AA가 양의 정부호이므로 순볼록이고 유일한 최솟값입니다. 대입하면 12b⊤A−1b−b⊤A−1b=−12b⊤A−1b\frac12\mathbf b^\top A^{-1}\mathbf b - \mathbf b^\top A^{-1}\mathbf b = -\frac12\mathbf b^\top A^{-1}\mathbf b. □

그러므로 “이차함수를 최소화하는 것”과 “연립일차방정식 Ax=bA\mathbf x = \mathbf b를 푸는 것”은 같은 문제입니다.

예제 2.6. A=(2008)A = \begin{pmatrix}2 & 0\\0 & 8\end{pmatrix}, b=(2,4)\mathbf b = (2, 4)이면 x∗=(1,12)\mathbf x^* = (1, \frac12), 최솟값은 −12(2⋅1+4⋅12)=−2-\frac12(2\cdot1 + 4\cdot\frac12) = -2입니다.

2.4 강볼록성과 조건수

정의 2.7 (강볼록성과 매끄러움). 두 번 미분가능한 ff의 헤세 행렬 고윳값이 모든 점에서 m≤λ≤Lm \le \lambda \le L(m>0m > 0)이면, ff를 mm-강볼록(strongly convex)이고 LL-매끄럽다(smooth)고 합니다. 비 κ=L/m\kappa = L/m을 조건수(condition number)라 합니다.

  • m>0m > 0: 그릇이 적어도 이만큼은 휘어 있습니다(바닥이 평평하지 않음).
  • LL: 그릇이 이보다 가파르게 휘지는 않습니다.
  • κ\kappa: 그릇이 얼마나 길쭉한가. κ=1\kappa = 1이면 동그란 그릇, κ\kappa가 크면 좁고 긴 골짜기입니다.

예제 2.8. f(x,y)=x2+50y2f(x, y) = x^2 + 50y^2은 헤세 행렬 diag(2,100)\mathrm{diag}(2, 100)이므로 m=2m = 2, L=100L = 100, κ=50\kappa = 50입니다. 등위선은 매우 길쭉한 타원입니다.

3장에서 보듯이 경사하강법의 수렴 속도는 κ\kappa로 정해집니다. 입력 특성의 크기를 맞추는 정규화(feature scaling)나 배치 정규화가 학습을 빠르게 하는 것은 조건수를 줄이기 때문입니다.

2.5 이 장의 요약

  • 국소 최솟값이면 ∇f=0\nabla f = \mathbf 0(필요). 볼록이면 이것으로 충분.
  • 헤세 행렬의 고윳값 부호로 최소·최대·안장점을 판정합니다.
  • 이차함수의 최솟값 x∗=A−1b\mathbf x^* = A^{-1}\mathbf b.
  • 조건수 κ=L/m\kappa = L/m = 그릇이 길쭉한 정도.

쓰이는 곳. “stationary point”, “saddle point”, “ill-conditioned”, “condition number”는 최적화·딥러닝 논문에 자주 나오는 말입니다. 신경망 손실 지형 연구(헤세 행렬의 고윳값 분포), 사전조건화(preconditioning), 입력 정규화가 학습을 안정시키는 이유, 수치해석에서 연립방정식이 얼마나 오차에 민감한지가 이 장의 개념으로 설명됩니다.

문제

2.1 [계산] · 확인 문제

f(x,y)=x2+xy+y2−3xf(x, y) = x^2 + xy + y^2 - 3x의 임계점을 구합니다.

좌표 값
xx [?]
yy [?]
정답
2
-1
풀이

∂xf=2x+y−3=0\partial_x f = 2x + y - 3 = 0, ∂yf=x+2y=0\partial_y f = x + 2y = 0. 둘째 식에서 x=−2yx = -2y, 첫째에 넣으면 −3y=3-3y = 3, y=−1y = -1, x=2x = 2입니다. 헤세 행렬의 고윳값이 1,31, 3이므로 전역 최솟값입니다.

2.2 [개념]

f(x,y)=x2−4xy+y2f(x, y) = x^2 - 4xy + y^2의 원점은 어떤 점인가요?

  1. 국소 최솟값
  2. 국소 최댓값
  3. 안장점
  4. 판정할 수 없음
정답
3
풀이

헤세 행렬 (2−4−42)\begin{pmatrix}2 & -4\\-4 & 2\end{pmatrix}의 고윳값은 6,−26, -2로 부호가 섞여 있으므로 안장점입니다.

2.3 [계산] · 확인 문제

A=(4223)A = \begin{pmatrix}4 & 2\\2 & 3\end{pmatrix}, b=(2,1)\mathbf b = (2, 1)일 때 f(x)=12x⊤Ax−b⊤xf(\mathbf x) = \frac12\mathbf x^\top A\mathbf x - \mathbf b^\top\mathbf x의 최솟값은?

정답
-1/2
풀이

Ax=bA\mathbf x = \mathbf b를 풀면 x∗=(12,0)\mathbf x^* = (\frac12, 0)이고, 최솟값은 −12b⊤x∗=−12⋅1=−12-\frac12\mathbf b^\top\mathbf x^* = -\frac12\cdot1 = -\frac12입니다.

2.4 [계산] · 확인 문제

f(x,y)=3x2+2xy+3y2f(x, y) = 3x^2 + 2xy + 3y^2의 조건수 κ\kappa는?

정답
2
풀이

헤세 행렬 (6226)\begin{pmatrix}6 & 2\\2 & 6\end{pmatrix}의 고윳값은 4,84, 8이므로 κ=8/4=2\kappa = 8/4 = 2입니다.

2.5 [증명]

∇f(x∗)=0\nabla f(\mathbf x^*) = \mathbf 0이고 헤세 행렬에 음의 고윳값 λ\lambda가 있으면, 고유벡터 방향으로 조금 움직일 때 ff가 줄어듦을 테일러 전개로 보입니다.

풀이

고유벡터 v\mathbf v(∥v∥=1\|\mathbf v\| = 1)에 대해 f(x∗+tv)=f(x∗)+t∇f⊤v+t22v⊤Hv+o(t2)=f(x∗)+λt22+o(t2)f(\mathbf x^* + t\mathbf v) = f(\mathbf x^*) + t\nabla f^\top\mathbf v + \frac{t^2}2\mathbf v^\top H\mathbf v + o(t^2) = f(\mathbf x^*) + \frac{\lambda t^2}{2} + o(t^2)입니다. λ<0\lambda < 0이므로 작은 t≠0t \ne 0에서 f(x∗)f(\mathbf x^*)보다 작아집니다. 그러므로 x∗\mathbf x^*는 국소 최솟값이 아닙니다.