目次
開催案内
最適化アルゴリズムの実装
日時
2023年2月9日（木）16:45〜18:15
開催形式
対面(北部構内)とオンライン(Zoom)のハイブリッド
参加登録 https://forms.gle/Ndz5BwrGFDuZdh4t9
登録されたアドレスに教室の場所とZoomの接続情報を送付いたします。
講師
田中 未来 氏（統計数理研究所 数理・推論研究系 准教授）
要旨
ある性質 (制約条件) を満たすもの (解) の中である指標 (目的関数) が最小あるいは最大となるもの (最適解) を求める問題を最適化問題という. 講演者は様々な最適化問題を解くためのアルゴリズムに関する研究を行なってきた. 最適化アルゴリズムの研究は, 問題の構造を利用したアルゴリズムを構築し, 数学的な解析によってアルゴリズムの理論的な性能保証を与えた上で, 計算機実験によって実際の性能を評価するといった段階を経ることが多い. 最適化アルゴリズムによっては, 元の最適化問題よりも容易に解くことができる最適化問題 (子問題) を外部のソフトウェアを用いて繰り返し解くことで元の問題を解くものがある. そのようなアルゴリズムを実装する際には, 子問題が実際にどのように解かれるかを気にする必要がある. 本講演では, 最適化アルゴリズムの研究について概説したのち, 講演者が開発したある最適化アルゴリズムのソースコードについて解説する.
備考
◎問い合わせ先：itami.masato.7u ＊ kyoto-u.ac.jp（＊を@に変えてください）
開催報告
統計数理研究所の田中未来さんに「最適化アルゴリズムの実装」というタイトルで講演していただきました。
講演は数理最適化における基礎事項の説明から始まりました。制約条件の下で目的関数を最小（あるいは最大）にする変数を求める問題を数理最適化問題といい、その問題を解くアルゴリズムのことを最適化アルゴリズムと呼ぶそうです。講演では、最適化アルゴリズムの具体例として、最急降下法・Newton法・分岐限定法が紹介されました。
続いて、数理最適化におけるプログラミングについて解説していただきました。代表的な最適化アルゴリズムはソフトウェアとして実装されており、最適化ソルバとよばれるそうです。具体的に最適化問題を解く際は、ボトルネック部分には最適化ソルバを用いることが多く、ボトルネック以外の部分は多少低速でも全体の計算時間に影響しないこともあり、CやFortranではなくPython（や近年はJulia）でプログラムを作成することが多いようです。講演では、混合整数最適化問題用の最適化ソルバであるGurobiを利用して簡単な線形最適化問題を解くPythonプログラムのコードを紹介していただきました。
最後のトピックでは、船舶航行計画問題に関する田中さんの近年の研究と、そこで用いたPythonのコードを紹介していただきました。船舶航行計画問題とは、船舶の航路と船速をうまく決めて燃料の総消費量を最小化する問題です。まずは、船舶航行計画問題を定式化し、適切に変数と制約を追加することで混合整数二次錐最適化問題へと帰着させることで、最適化ソルバを使う方法が解説されました。残念ながら、この愚直な方法では中規模以上の問題は解けないそうです。そこで、航路を固定して最適な船速を求める問題と、船速を固定して最適な航路を見つける問題なら容易に最適解が求まることを利用して、分岐限定法を行えば中規模の問題でも良い解が求められることが説明されました。
講演中も講演後も多くの質問が出て、最適化ソルバを利用する際のコツや最適化アルゴリズムの選択方法などに関して活発な議論が行われました。
（文責：伊丹將人）