「しっかり学ぶ数理最適化」裏話その１

はじめに

この記事では，拙著「しっかり学ぶ数理最適化」について，本には書けなかった裏話を思いつくままに書いています．このブログを読んでいる方の大半はすでに購入済かと思いますが，そうでない方は手に取っていただけると幸いです．
はじめは，内容を整理して簡潔にまとめるつもりだったんですが，全く整理されていない乱文を公開する羽目になりました．見苦しくなってしまい大変申し訳ありません．著者の生の声を感じ取っていただければ幸いです．

この本を書いた動機

私自身は教科書を指定せずに作成したスライドを配布して授業を進めていました．そのため「数理最適化のおすすめの教科書を教えて下さい」と聞かれることが少なくありません．すると，初めの1冊として薦められる基本的なトピックが一通り抑えられる入門書が非常に少ないことに気付きました．ちなみに，私は以下の本を参考書として紹介していました．

• 福島雅夫，新版 数理計画入門，朝倉書店，2011．
• 久野誉人，繁野麻衣子，後藤順哉，数理最適化，オーム社，2012．
• 加藤直樹，数理計画法，コロナ社，2008．

私自身は福嶋先生の「数理計画入門」(旧版)で数理最適化の勉強を始めましたし，いずれの本も初学者向けの良い本なのですが，授業を重ねるうちに既刊の教科書では不十分だと感じることが多くなってきました．例えば・・・

• 線形計画法の単体法では，2次元の図で凸多角形の頂点を移動するイメージを説明した後に，単体表(シンプレックスタブロー)での計算を説明する流れが一般的ですが，単体表の更新手続きが凸多角形の隣の頂点に移動する操作に対応していると納得できる人がどれだけいるでしょうか？少なくとも私は納得するまでに相当の期間を要しました．また，例えば，双対問題を「問題(P)に対して，係数を入れ替えた以下の問題(D)を双対問題と呼ぶ」などと天下り的に定義している本は少なくありませんが，それでは双対問題の意義を理解することは難しいですし，非線形計画問題の双対問題を自分で作れるようにもなりません．
• 数理最適化は線形計画，非線形計画，組合せ最適化と非常に広い範囲に渡ります．私も含めて一口に数理最適化の研究者と言っても実際にはそれぞれ狭い範囲の専門家であり，数理最適化を広く深く理解した上で一冊の書籍にまとめることは容易ではありません．特に，組合せ最適化は，問題を特徴付ける離散構造が多様で，それぞれの離散構造に固有の理論体系があると言っても過言ではありません．以前は200ページを超す書籍の出版は難しかったようで，数理最適化の全体を俯瞰した上で要点を上手く抑えたバランス良い書籍は非常に少ないと感じていました．
• 書籍内で説明が完結している書籍が少ないことも気になっていました．例えば，逐次2次計画法は有効制約法をサブルーチンに使いますが，逐次2次計画法と有効制約法をあわせて説明している書籍はほとんどありません．分枝限定法も双対単体法をサブルーチンに使いますが，分枝限定法と双対単体法をあわせて説明している書籍もほとんどありません．
• 多くの書籍はアルゴリズムの説明に大半の紙面を割いていますが，実務では現実問題を最適化問題にモデル化する作業も重要です．数理最適化の専門家は，既知の最適化問題を変形したり組み合わせてモデル化するので，書籍で紹介される最適化問題が雛形に過ぎないことを良く知っています．ところが，初学者はそのようなことを知りませんから，書籍で紹介されている最適化問題を見て「こんなオモチャみたいな最適化問題が解けても，現実問題には対応できそうにもない」と失望することが少なくありません．事例の紹介や現実問題を最適化問題にモデル化するためのノウハウに紙面を割く書籍が少ないように思います．

一見すると数理最適化のスタンダードな教科書に見えるかも知れませんが，このように色々と思うところがあり，既刊の教科書とは異なるものを目指して執筆しました．もちろん，既刊の教科書にも良い部分は沢山ありますので，それらの部分は下手に独自性を追求せずにそのまま採用しています．

1章：数理最適化入門

• 最適化問題の例ですが，野菜ジュースの生産計画はフィクションなので悪しからず．もう1つの例は，理工系の大半の大学生が一度は計算するだろうと言うことで最小二乗法を取り上げました．
• 日本語で書かれた入門書での勉強が一通り終わると，次は英語で書かれた論文や専門書を読むことになりますが，専門用語が分からなくて困ることが少なくありません．そこで，本書では専門用語はできるだけ英文併記するよう心がけました．
• この章で一番悩んだのが最適化問題の分類です．はじめはベン図みたいなものを描いていました．しかし，最適化問題の分類は多面的で100人の専門家がいれば100通りの分類がありそうなので，無理に分類せずに代表的な最適化問題を紹介するだけに留めました．
• 本書を含む多くの数理最適化の書籍は線形計画から始めていますが，これが多くの初学者にはハードルが高いと感じる原因の1つだと思います．理工系の大学生は初年度に微積分と線形代数を学習しますから，制約なしの非線形計画問題の方が馴染み易いだろうと思っていました．2章を非線形計画にするかさんざん悩んだんですが，勇者にはなれず右に習えで線形計画から始めました．その代わりと言ってはなんですが，学習順序の例として3章の非線形計画から始めても構わない旨を書きました．

2章：線形計画

• 最適化問題の定式化の説明にかなり力を入れました．線形計画問題では直観的ではない例を取り上げて記述力の高さをアピールするように心がけました．
• 単体法はイメージを掴むことが難しいので，2章では先に具体的な例を挙げて丁寧に説明するよう心がけました．3-4章とは意識して説明のスタイルを変えています．説明のスタイルに一貫性がないのは良くないと感じる読者もいるかと思いますが，いきなり2章でつまづいて欲しくなかったので，一貫性を犠牲にしても分かり易さを優先しました．具体例から先に入ったことで，定義が曖昧になった部分があるのは勘弁して下さい．
• 2.2.2節「単体法の概略」と2.2.3節の「単体法の例」の説明は完全なオリジナルです．凸多面体の面が制約条件に対応し，さらに，制約条件が非基底変数に対応していることを意識した説明になっています．ここでは，基底変数ではなく非基底変数が主役になります．
• 単体法の説明では，フバータル(Chvatal)の「Linear Programming」に倣って辞書を使いました．単体表(シンプレックス表)よりも，連立1次方程式を解いてる感じが伝わるので好みです．辞書の更新時でも説明の分かり易さを優先して掃出し法ではなく代入法を使いました．
• 2.2.4節「単体法の原理」の説明はスタンダードです．線形計画問題は，連立1次方程式の拡張だと考えています．例えば，中高生には「変数が等式制約より多いと解が一意に決まらないですよね．そこで，目的関数を導入して制約を満たす最も良い解を見つける問題を考える．これが線形計画問題です．」と説明しています．その上で「等式制約と同数の変数を選んで連立1次方程式を解く手続きを繰り返せば線形計画問題を解けます」という感じで単体法の概略を説明しています．すると，前節とは逆に基底変数が主役になります．
• 2.2.5節「退化と巡回」では，巡回が生じる自明でない例を描こうと丸一日頑張りました．そのうちどう頑張っても作れない気がして文献を調べたら，少なくとも6個の変数(3個以上の非基底変数)と2本の制約条件が必要であることが判明しました．ちゃんと論文にまとめてくれた人に感謝です．
• 2段階単体法は，1段階目から2段階目に移る手続きが分かりづらいので丁寧に説明することを心がけました．
• 本書に限らず数理最適化の書籍では，最初から最後まで最適化問題の定義を一貫させることは非常に難しいです．できる限り最適化問題の定義を変更せずに済ませようと努力したのですが，そのために説明が煩雑になる箇所が多く生じることが分かり泣く泣く諦めました．最適化問題の定義を変える際には脚注を添えて注意をうながしたのですが，全ての読者に納得してもらうことはなかなか難しいようです．
• 本書も含めて線形計画問題では目的関数を最大化することが多いです．これは，単体法を説明する際に原点が最適解ではない自明な実行可能解であることが都合が良いためです．線形計画問題の標準形では全ての変数に非負制約が付くため，目的関数を最小化すると原点が実行可能解ならば自明な最適解となってしまいます．2.3.4節「感度分析」で目的関数を最小化したのは，1章の野菜ジュース製造を例に使ったことが理由なのですが，これは改善の余地があったかも知れません．
• 線形計画問題の制約条件を等式と不等式のいずれで表すかも非常に悩ましい問題です．制約条件を等式で表すと，線形計画問題の例を図で描いた際に実行可能領域が点になってしまいます．一方で，単体法を説明するには制約条件を等式で表した方が都合が良いです．このような事情から，2章では幾度となく等式と不等式を行き来することになりました．特に，2.3.3節「双対定理」では線形計画問題の制約条件を不等式から等式に変更しました．これは，定理2.2「強双対定理」を証明する際に単体法から得られる最適解を使いたかったためです．
• 定理2.2「強双対定理」はファルカスの補題を使って証明した方がスマートだというご意見もあります．しかし，証明なしにファルカスの補題から導かれると書かれても納得できないわけで，そうすると，ファルカスの補題そのものを証明する必要が生じるわけですが，初学者にはハードルが高くて心が折れそうだと思ったので止めました．
• 本書では双対問題の有用性をアピールしたかったので，感度分析と双対単体法の説明には力を入れました．この章ではピンとこなかった読者も多いでしょうが，双対単体法は分枝限定法，切除平面法で重要な役割を果たします．双対問題も，最小費用流問題に対する最短路繰返し法や，頂点被覆問題に対する主双対法で重要な役割を果たします．このように，本書では伏線を張るというか，各トピックの繋がりを意識してます．