최적화 방법

최적화(optimization) 문제

어떤 목적함수(objective function)의 함수값을 최소화(혹은 최대화)시키는 파라미터(변수) 조합을 찾는 문제이다.

 

최적화 원리

최적화 문제를 최소화 문제로 한정했을때, 현재 위치에서 함수값이 감소하는 방향으로 조금씩 파라미터 값을 이동하는 것을 반복하여 함수값이 최소화 되는 지점을 발견하는 것이다

 

. 

기본적인 반복 최적화 방법에는 뉴턴 방법 , 경사하강법 이 있다.

이 글에서는 각 방법을 단일변수 함수에 한정지어 식을 설명할 예정이다.

 

1.  뉴턴 방법

 

 

$x_{k+1}=x_{k}-\frac{f(x_{k})}{f'(x_{k})}, k=1,2,…$

 

초기값 $x_1$에서 시작해서 위 수식에 따라 x를 이동시켜 나가서 x값의 변화가 거의 없을 때까지 반복하는 것이다. 

 

위 식을 이용하면 $f(x)=0$에 수렴하는 $x$값을 구할 수 있다.

하지만 우리는 $f(x)$가 최소가 되는 $x$값이 궁금한 것이므로 식을 살짝 변형해야 한다.

 

$x_{k+1}=x_{k}-\frac{f'(x_{k})}{f''(x_{k})}, k=1,2,…$

위 식을 이용하면 $f'(x)=0$인 지점을 구할 수 있으므로 곧 $f(x)$가 최소가 되는 지점을 구하는 최적화 문제를 해결할 수 있다.

 

$f(x)=x^2$일때 뉴턴 방법의 최적화를 파이썬 으로 구현한 코드는 다음과 같다.

import time
def ftn(x):
    z = x**2
    return(z)
def newton():
    xt = 100
    h = 0.000000001
    epsilon = 0.000001
    i = 1
    start = time.time()
    while 1 == True:
        ftn_drv = (ftn(xt+h) - ftn(xt-h))/ (2*h)
        xt1 = xt - ftn(xt)/ftn_drv
        dist = abs(xt1 - xt)

        if dist <= epsilon :
            break
        else :
            xt = xt1
            i += 1

    print("%s / %s / %s / %5e"%(i, xt1, ftn(xt1), time.time()-start))
    
newton()

 

2. 경사하강법

 

 

$x_{k+1}=x_{k}-𝜆f'(x_{k}) ,  k=1,2,…$

$𝜆$는 매 차례 얼마나 이동할지를 조절하는 step size파라미터로 𝜆$>0$로 가정합니다.

$f'(x_k)>0$ 이면 위 그림과 같이 왼쪽으로 이동하게 되며

$f'(x_k)<0$ 이면 오른쪽으로 이동하여 $f'(x)=0$ 인 점 $x$를 찾는다.