[최적화] (8) Infeasible Start Newton's Method

시작에 앞서 양질의 강의를 무료로 제공해주시는 혁펜하임(https://www.youtube.com/watch?v=Nj2aLgatB1Y)님께 감사인사를 전합니다. 본 게시물은 강의를 듣고난 후 정리용도에 불과하니 강의 수강을 권합니다. 

 

지속적으로 강조하지만 연산과정의 복잡성 때문에 optimization problem의 대부분을 algorythm으로 푼다.

newton's method의 핵심을 복기해보면 결국 2차 이상의 목적함수 f(x)의 local min/max를 알고리즘적으로 찾는 것이다. 이 때 우리는 taylor series를 활용한다. 만약 f(x)가 2차함수라면 아래 그림과 같이 특정 지점 Xk에서 talyor series로 근사한다. 근사된 함수의 local min/max point가 있을텐데, 이는 Xk가 f(x)의 local min/max가 아님을 뜻하니 다시 X_k+1에서 동일과정을 반복한다. 이렇게 X_k+1 = X_k - f'(Xk)/f''(Xk)을 찾는다.

그런데 사실 원함수에서 2차 taylor series를 통해 근사한 것이나, 원함수의 1계도함수 f'(x)에서 1차 taylor series한 것이나 기실 같은 것이기 때문에 1차 taylor series를 통해 newton's method를 진행한다.

 

Equality constraint가 추가된 Lagrangian Method 또한 이런 Newton's Method 아이디어를 차용해서 해결한다.

Lagrangain Method의 핵심은 local min/max의 필요조건이 del_x L = 0 and h(x)=0라는 것이다. 그렇다면 우리는 vector x, vector lambda를 묶어 이를 R(w)과 같이 표현한뒤, R(w)=0이 되는 x, lambda를 찾으면 된다.

 

참고로 del_x L 과정에서 f(x)를 x transpose로 편미분한 값이 행벡터로 도출되니 이에 다시 tranpose를 취해 열벡터화해준다. A^T*lambda 또한 동일한 이유에서 tranpose를 취했다. 해당 내용은 아래 게시글을 참조하길 바란다.

https://alba-tross.tistory.com/78?category=999369

 

그럼 newton's method를 똑같이 적용하여 R(w)의 1차 taylor series가 0이 되게하는 w벡터를 찾아주면 된다.

X_k+1 = Xk - f(x)/f'(x) 였듯이 W_k+1 = Wk - R(Wk)/R'(Wk)로 정리할 수 있다.

R'(Wk)가 결국 핵심인데 이는 vector R(w)를 vector w로 미분해주는 것이니 jacobian mtx가 도출된다.

 

생각해보면 Z=AX를 만족하는 X 중에서 f(x)가 minimize되는 X를 솎아내는 기존의 방식과는 달리, 

newton's method를 활용하면 Z=AX & del_x L를 만족하는 X를 infeasible set에서부터 찾아나간다. 따라서 우리는 이를 "Infeasible start Newton's Method"라고도 부른다.