Function Optimization using a Ternary Search

IDEA

 Ternary search는 아래로 볼록인 함수에서 최솟값, 위로 볼록인 함수에서 최대값을 찾을 때 이용할 수 있다.

어떤 함수 \( f(\boldsymbol{\mathrm{x}}) \)가 있다고 하자. 이 함수는 \(\boldsymbol{\mathrm{x}}_i \) for all \(i\)에 대해서 아래로 볼록이다. 즉, fixed \(\boldsymbol{\mathrm{x}}_j\) for all \(j \neq i\) 이면, \(f(\boldsymbol{\mathrm{x}})\)는 아래로 볼록이다. 이때, 각 \(\boldsymbol{\mathrm{x}}_i\)에 대해서 ternary search를 이용해 optimization을 해주면, 함수는 조금씩 최적화 될 것이라는 생각을 할 수 있다. 모든 \(\boldsymbol{\mathrm{x}}_i\)에 대해 ternary search를 이용해 optimization을 해주는 과정을 하나의 step이라고 하겠다.

 이 방법은 단층 퍼셉트론을 최적화 하는데에 이용할 수 있으며, 보통 경사하강법 보다 좋다. 하지만, 다층 퍼셉트론의 경우 함수 개형은 감소 → 증가와 같은 형태가 아니므로, 이용할 수 없다.

Implementation

  Ternary search만 제대로 구현해주면 된다. 자세한것은 아래 코드 참고

 

https://github.com/Sora-Sugiyama/Libs/blob/main/Function-Optimization/FOTS.h