最適化手法入門を読む 第1回

最適化手法入門

　第2章 線形計画と凸2次計画 をざっと読んだので演習問題を解き始めました。ここでは次の問題を解いてみます。

2.5 次の最適化問題を線形計画問題に帰着せよ
  (i) チェビシェフ近似問題
  ……

チェビシェフ近似問題とは下記の最適化問題です。

線形計画問題とは、目的関数と制約がともに1次式である最適化問題のことです。下記のノルムの定義から分かるように、チェビシェフ近似問題の目的関数は1次式ではありません。

目標は下記のⅠからⅢに帰着することです。

まずⅠ⇔Ⅱを示します。

あとはⅡ⇔Ⅲを示せばおしまいです。

　以上でチェビシェフ近似問題が線形計画問題に帰着できることが分かりました。
　と、ここまで書いてきましたが、特にⅠ⇔Ⅱは見れば見るほど当たり前に思えてきました。Ⅱの制約条件の下でyを小さくしようとしたら当然Ⅰの目的関数も小さくなるし、Ⅱで最適解のときは等号成立していなきゃいけないので……。これを滅茶苦茶丁寧に書いたらこんな感じになると思います。
　さらに、Ⅰ⇔Ⅱはノルムの定義やノルムの中身を使わずに議論できているので、もっと一般に下記のように帰着させることができそうです……。