【TypeScript】二次関数の最小値を求める『三分探索』

前回の二分探索に続いて三分探索を紹介します。

やりたいこと

こういう二次関数の最小値を求めたいです。
https://study-club.jp/news/quadraticfunction-maxmin/

y = x^2 + 2x + 3

最小値はx=-1の時y=2だそうです。

グラフにすると一目瞭然ですね。

手段

前回同様、方程式を解くのではなく適当な値を代入していって近しい値を見つけます。
やり方はこうです。

アルゴリズムの概要

中心となるアイディアは、グラフを三等分するということです。
グラフを三等分すると、起こるのはこの三通りしかありません。

• 最小値が一番左のマスにある
• 最小値が中央のマスにある
• 最小値が一番右のマスにある

そしてこの時、次のことが言えます。
f(左壁) > f(分割線1) > f(分割線2) ならば最小値は左のマスか中央のマスにある
f(分割線1) < f(分割線2) < f(右壁)ならば最小値は中央のマスか右のマスにある
そのどちらでもなければ最小値は分割線1から分割線2の中央にある

これを利用すると徐々に最小値の存在する範囲を狭めていくことができます

アルゴリズムの詳細

1. とても大きな値(10000など)を右端、とても小さな値(-10000など)を左端とする
2. 右端と左端の間に２本の線を引き三等分する
3. 左右の端と分割線を仮のxとし、式に代入してみる
   1. f(左壁) > f(分割線1) > f(分割線2) ならば右壁に分割線2を代入
   2. f(分割線1) < f(分割線2) < f(右壁) ならば左壁に分割線1を代入
   3. どちらでもなければ左壁に分割線1を、右壁に分割線2を代入
4. 2に戻って繰り返す

コード

function f(x: number): number {
  return x * x + 2 * x + 3;
}

function main() {
  let left = -10000,
    right = 10000;

  for (let i = 0; i < 1000; i++) {
    let line1 = left + (right - left) / 3;
    let line2 = right - (right - left) / 3;

    let y1 = f(left);
    let y2 = f(line1);
    let y3 = f(line2);
    let y4 = f(right);

    if (y2 < y3 && y3 < y4) {
      right = line2;
    } else if (y1 > y2 && y2 > y3) {
      left = line1;
    } else {
      left = line1;
      right = line2;
    }
  }

  console.log(`x=${left}, y=${f(left)}`);
}

main();

x=-1.0000000050253126, y=2

拡張

ちなみに、今回は下に凸の場合のみを扱いました。
ちょっと工夫するだけで上に凸でも動くコードになります。