최적화

제한된 조건에서 가장 좋은 선택을 찾는 문제이다. 비용 최소화, 이익 최대화, 인공지능의 학습(오차 최소화)이 모두 최적화이다.

핵심 개념

  • 무제약 최적화: $\nabla f=\mathbf0$인 점을 찾고 이계도함수로 판정
  • 제약 최적화: 라그랑주 승수법 $\nabla f=\lambda\nabla g$ (해석학 ‘라그랑주 승수법’ 단원)
  • 선형계획법: 일차 부등식 조건 아래에서 일차 함수를 최대·최소로. 최적해는 가능 영역의 꼭짓점에서 나온다.
  • 경사하강법: $\mathbf x_{k+1}=\mathbf x_k-\eta\nabla f(\mathbf x_k)$ ($\eta$: 학습률)
  • 볼록함수: 그래프 위의 두 점을 잇는 선분이 그래프 위에 있는 함수. 극소가 곧 최소이다.
등고선 위에서 경사하강법으로 최솟값에 다가가는 경로
기울기의 반대 방향으로 조금씩 내려간다

핵심 정리

  • 선형계획법의 최적해는 (존재한다면) 가능 영역의 꼭짓점 중 하나에서 나온다.
  • 볼록함수의 극소점은 최소점이다.
증명 보기

선형계획법. 목적함수 $z=c_1x+c_2y$의 등고선은 평행한 직선들이다. 가능 영역은 볼록다각형이고, 직선을 평행이동하며 영역과 만나는 마지막 순간은 꼭짓점(또는 변 전체)에서 일어난다. 일반적으로 볼록다각형 위의 점은 꼭짓점들의 가중평균 $\sum t_iv_i$ ($t_i\ge0$, $\sum t_i=1$)이고 목적함수가 일차식이므로 $z(\sum t_iv_i)=\sum t_iz(v_i)\le\max z(v_i)$이다.

볼록함수. $x^*$가 극소이고 어떤 $y$에서 $f(y)<f(x^*)$라 하자. 볼록성에 의해 $0<t<1$에서 $f((1-t)x^*+ty)\le(1-t)f(x^*)+tf(y)<f(x^*)$이다. $t$를 작게 하면 $x^*$에 얼마든지 가까운 점에서 더 작은 값이 나오므로 극소라는 데 모순이다. $\blacksquare$

예제 (선형계획법)

$x+y\le4$, $x+3y\le6$, $x,y\ge0$에서 $z=3x+5y$의 최댓값: 꼭짓점 $(0,0)$, $(4,0)$, $(3,1)$, $(0,2)$에서 $z=0,12,14,10$이므로 최댓값 $14$ (점 $(3,1)$)

확인 문제

$f(x)=x^2$에서 학습률 $\eta$로 경사하강법을 할 때 $x_{k+1}=(1-2\eta)x_k$이다. 수렴하려면 $\eta$는 어떤 범위여야 하는가?

풀이 보기

$x_k=(1-2\eta)^kx_0$이 $0$으로 수렴하려면 $|1-2\eta|<1$, 즉 $0<\eta<1$이다. $\eta$가 너무 크면($\eta>1$) 최솟값을 지나쳐 발산하고, 너무 작으면 매우 느리다.

정리

  • 선형계획법: 꼭짓점을 확인한다.
  • 볼록함수는 극소 = 최소, 경사하강법은 학습률 선택이 중요하다.
알림: 보호된 콘텐츠입니다.