以上で線形計画入門は完了になります。お疲れ様でした。
- 第一章では、線形計画入門で学ぶ内容を俯瞰しました
- 第二章では、最適化の用語についてを学びました
- 第三章では、線形計画を定式化しました
- 第四章では、線形計画の応用例を学びました
- 第五章では、線形計画を解析する上で重要な概念である基底解について学びました
- 第六章では、シンプレックス法という線形計画を解くためのアルゴリズムを学びました
- 第七章では、基底解が与えられない場合や縮退の場合の対処法を学びました
- 第八章では、最適化問題の緩和と双対問題について学びました
- 第九章では、線形計画の双対問題が線形計画になることと、最適値が主問題と一致することを示しました
- 第十章では、シンプレックス法と強双対定理を数値的に実験しました
このシリーズでは、教科書や講義では必ず取り上げられる、線形計画の図形的な解釈や感度分析についてはあえて取り上げませんでした。そのようなトピックについては、また別の所で取り上げたいと思います。それまでに知りたい方は以下の読書案内を参考にしてください。
現実上の最適化問題は非線形になったり、整数制約が課される場合も多いです。そのような問題に直面した場合、線形計画で学んだ内容が無駄になるかというと決してそうではありません。複雑な問題を、線形計画をサブルーチンとして呼び出して解くアルゴリズムは多く存在します。また、今回学んだ双対などの解析方法が非線形計画や整数制約に適用できる場合も多くあります。
最適化問題の枠組みの広さとアルゴリズムの効率はトレードオフの関係にあります。線形計画は枠組みとしては広くはないですが、綺麗な理論と高速なアルゴリズムが存在するので最適化の入門としては最適です。
線形計画を学び終わった後の次のステップとしては、線形計画よりも広い問題を扱える一方で、綺麗な理論やアルゴリズムが知られている凸計画や半正定値計画を学ぶのがおすすめです。例えば、これらの枠組みに対しても条件づきで強双対定理が成り立つことが知られています。凸計画や半正定値計画については、今後、新たな記事で紹介していく予定です。それまでに知りたい方は以下の読書案内を参考にしてください。
線形計画および最適化を学ぶために有用な教科書を紹介します。
線形計画をはじめ、最小二乗法や非線形最適化、離散最適化など、最適化のトピックが幅広く抑えられています。
例や図解が豊富に用いられているほか、理解の助けになる注釈も多く、独学にもおすすめです。
欠点としては、多くの定理が証明されず、例を紹介するに留まっているため、理論をきっちり学ぶのには適していないということがあります。
理論の厳密さよりもまずは直感的に概念を俯瞰できるようになることを目指す場合、とくに初学者には、おすすめな教科書です。
最適化の分野で世界的に有名な教科書です。こちらも最小二乗法や非線形最適化、離散最適化など、最適化のトピックが幅広く抑えられています。
口語調で分かりやすく説明が成されている一方で、厳密な証明がしっかり提供されているのが特徴的です。
欠点としては、邦訳が出ていないことと、値段が張ることです。
本格的に最適化を学ぶ際には買って損はない、自信をもっておすすめできる一冊です。
こちらも世界的に有名な教科書です。こちらの教科書は凸計画に話題を絞ってあります。線形計画も凸計画の特別な場合として取り上げられています。
こちらの教科書も、説明が分かりやすい一方で、証明がきちんと載っているため、しっかり学びたい方におすすめです。
上記の Numerical Optimization と比較すると、こちらの方が説明が丁寧で、例や数値実験も多いので初学者に優しい印象です。一方、Numerical Optimization はシンプレックス法など線形計画特有のトピックもカバーされているのに対し、こちらは線形計画はあくまで凸計画の一例として扱われているだけのため、線形計画に特化して学びたい場合はあまり適していません。凸計画全体を一気に学んでしまいたい場合はこちらの教科書がおすすめです。
欠点としては、邦訳が出ていないことと、値段が張ることですが、こちらは著者らの公式ページから電子版が無料でダウンロードできます。
こちらも本格的に最適化を学ぶ際には買って損はない、自信をもっておすすめできる一冊です。
