[최적화] Numerical optimization based on the L-BFGS method

https://medium.com/towards-data-science/numerical-optimization-based-on-the-l-bfgs-method-f6582135b0ca

Numerical optimization based on the L-BFGS method

https://aria42.com/blog/2014/12/understanding-lbfgs

Numerical Optimization: Understanding L-BFGS

https://stats.stackexchange.com/questions/284712/how-does-the-l-bfgs-work

How does the L-BFGS work?

 

해당 아티클들을 읽고 정리한 내용임을 밝힙니다. 

 

---

먼저 L-BFGS의 개략적 내용을 이해하고,시각화해본 뒤에,

수학적 내용으로 넘어가도록 하겠음!

(수학적 내용은 추가 공부가 필요한데 내가 과연 또 할수 있을지..?😂)

 

Intro 

최적화 문제는 목적 함수의 최저점 혹은 최고점을 찾는 것을 목표로 한다. 

최적화 문제는 두 개의 접근이 있는데, 1차 미분(such as gradient descent, steepest descent) , 그리고 이차 미분( such as Newton's method) 이다. 

 

1차 미분법의 경우 그라디언트를 통해 함수의 솔루션을 찾는다. 2차 미분은 그라이언트의 그라디언트(헤시안) 을 통해 더 효율적으로 함수의 최소점을 찾을 수 있다. (2차 미분은 솔루션의 'direction'과 'step size'를 제시하기 때문!)

 

L-BFGS 알고리즘은 이차 미분을 이용한 최적화이며, Quasi-Newton method에 속한다. 해당 알고리즘은 2차 미분을 근사하는 형태로 수행된다. 2차 미분법의 경우 헤시안 매트릭스의 역행렬을 계산해야 하는데, 이는 굉장한 컴퓨팅 자원을 소모하기 때문이다. 

 

BFGS 알고리즘은 헤시안 메트릭스를 매 반복마다 다시 계산하지 않고 계산을 업데이트한다. (이건 몬 소리일까...)

그러나, 헤시안 매트릭스와 그 역행렬의 크기가 이슈가 되기 때문에, L-BFGS는 전 반복 단계에서 헤시안의 역행렬을 단순화한다고 가정함으로써 이 문제를 해결한다. 

....😤

 

그라디언트의 full history를 사용하는 BFGS와 다르게, L-BFGS는 최근의 5~20 그라디언트만 사용함으로서 메모리 사용을 줄일 수 있다. 

 

 L-BFGS implementation

 

앞서 구현했던 매출 최적화 논문에서 짜놓았던 식을 이용해서 시각화를 해보도록 하겠음.

실행은 매우 쉬운데, 다음 포스팅에서 SLSQP를 이용해 실행을 할 예정임!

 

from matplotlib import cm
def plot_objective(objective):
    figRos=plt.figure(figsize=(12,7))
    axRos=plt.subplot(111,projection='3d')
    
    X=np.arange(0.3,0.6,0.001)
    Y=np.arange(0.3,0.6,0.001)
    X,Y=np.meshgrid(X,Y)
    XX=(X,Y)
    Z=objective(XX)

    surf=axRos.plot_surface(X,Y,Z,cmap="inferno")
    figRos.colorbar(surf,shrink=0.5,aspect=10)
    # plt.savefig('objective_function.png',bbox_inches='tight',dpi=200)
    plt.show()

i=5
def objective(x):
    y=(q[7] - 3.40 * (price *(1-x[0]) - price *(1-p[7])) * q[7] /(price * (1-p[7]))) \
                * (price * (1-x[0]) + 16208)  \
        + ((q[i] +1.28 * (price *(1-x[1]) - price *(1-p[i])) * q[1] /(price * (1-p[i]))) \
                * (price * (1-x[1]) )) 
    return y

plot_objective(objective)

 

목적 함수에 들어가있는 -3.40의 경우 수요탄력성을 나타냄.

해당 코드를 실행하면 surface plot이 실행되면서 매출식의 모습을 3d로 볼 수 있다. 

 

 해당 매출식이 어디에서 최고점(-를 붙였으므로) 인지 시각화 할수 있게 해준다.