본문 바로가기
  • Fearless
기계학습/Optimization

[최적화] (4) Broyden's Method

by Albatross 2022. 2. 5.
반응형

이전글에 이어서 Broyden's Method를 살펴보자. 

Bk의 관계식 중 A를 우리는 Rank-one mtx라 부른다. 이는 yk - BkSk가 열벡터 u이고, S / SS는 행벡터 v이기 때문이다. 둘이 외적되어 형성된 것이 A다. A는 외적되었기 때문에 그 column 들이 모두 linear independent하다. 따라서 rank one matrix라 불리운다.

 

사실 우리가 구해야하는 것은 inverse of Bk다. Bk만 구해버리면 이를 다시 inverse 취해주어야하기 때문에 계산을 두번하는 셈이 된다. 이런 번거로움을 해소한 방법이 Broyden's method다. 

Broyden's method는 아예 inverse of B_k+1과 inverse of B_k 간의 관계식을 정의한다.

 

이는 Shemman-Morrison formular를 통해 전개할 수 있다. 

 

식을 전개하면 다음과 같고 맨 아랫 줄의 inverse of B_k+1와 B_k의 관계식이 도출된다. 

이 식을 활용하면 이전 quasi-newton에서 구했던 B_k 관계식을 쓰지 않아도 된다. 

inverse of B_k를 H_k로 재정의한다. 

 

Broyden's method 아래 기호는 위그림과 같다. 

 

이후 살펴볼 BFGS와 Broyden's method를 비교하면 다음과 같은 단점이 존재한다.

우선 Bk가 symmetric mtx가 아닐 가능성이 존재한다. rank-one mtx가 non-sym일 경우 Bk 또한 symmetric이 되지 않기 때문이다. 따라서 우리는 A=transpose of A 라는 constraints를 추가해서 Bk를 symmetric으로 만들어준다. 이게 단점이 되는 이유가 Bk는 원함수에 대한 hessian mtx이기 때문에 무조건 symmetric해야하기 때문이다. symmetric하지 않는다면 앞뒤가 맞지않는 역설의 상황에 놓인다.

 

Broyden's method는 두가지 관점에서 '꿀'이다. 첫째, newton's method에서 구하던 hessian mtx를 구하지 않아도 된다. 둘째, quasi-newton에서 하던 Bk에 역행렬 취해주던 것 안해도 된다. 즉 계산 관점에서 많이 효율화된 방법이란 것이다. 그러나 앞서 말했듯이 rank 1 mtx가 symmetric이 아닌 경우에 전제 자체가 뒤흔들리기 때문에 이를 보완한 다른 방법이 등장한다.

반응형