Zenn
💮

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

2024/12/24に公開
数理最適化
idea

はじめに

この記事は、数理最適化アドベントカレンダー2024の24日目の記事です。
「しっかり学ぶ数理最適化」裏話その１」の続きで、拙著「しっかり学ぶ数理最適化」について、本には書けなかった裏話を思いつくままに書いています。出版から4年、前回の裏話その1から3年も経ってるので、本当に今更という感じなんですが、ご一読いただければ幸いです。

3章：非線形計画

  • 連続最適化は専門ではないため執筆では大いに苦しみました。「しっかり学ぶ組合せ最適化」で良いじゃないかと投げかけたことも一度や二度ではありませんでした。幸いなことに連続最適化を専門とするD先生やT先生にアドバイスを貰い何とかまとめることができました。
  • 連続最適化に詳しい読者が多いのか3章の内容に関する質問や指摘が非常に多かったです。逆に、私自身は連続最適化は専門ではないため、いちいち回答に確信が持てず大変でした。
  • 各章は応用例から始めていますが、普段は連続最適化に取り組む機会が少ないので、まずここで頭を抱えました。本書では機械学習と金融工学の応用例を挙げましたが、物理や制御など面白い応用例は数多くあるので深堀りできなかったのは残念です。
  • 非線形計画では凸関数が重要な役割を果たすので、基本的な性質についてはつたないながらも頑張ってまとめました。関数の凸性の判定は固有値の計算に行き着くわけですが、ところで固有値ってそんなに効率良く計算できるものだっけ？と思ったのは自分だけではないはず。
  • 関数の凸性や最適性の条件の証明では、関数の微分可能性に関する仮定が必要ですが、「2回連続的微分可能」が必要なのか「微分可能」だけで良いのか一つ一つ確認するのが大変でした。関連書籍を漁りまくりました。
  • 等式制約付き最適化問題の局所最適解の例は、3次元空間で制約条件が2本の例も描くべきだったなと後で反省しました。制約条件が1本の例だけだと定理とのギャップが大きかったですね。
    最適性の条件を満たさない例
  • 制約付き最適化問題の最適性条件に関する定理では証明を省略しました。これが、コアな読者の多くに非線形計画の内容が不十分だと評価された原因だろうと思ってます。これらの定理の証明は、局所最適解に収束する点列などの準備が必要となり内容がかなり重くなるため、さんざん悩んだ末に省略しました。
  • 1次独立制約想定が成り立たない例や双対定理の主問題と双対問題の関係図を追加したのは良かったと思ってます。
  • 有効制約法は必ず書こうと思っていたものの、とにかく参考文献が少なくてまとめるのに苦労しました。ところで、部分問題に現れる等式制約付き凸2次計画問題はラグランジュ乗数法で解いています。ここで、ふと「あれ？等式制約付き線形計画問題って、なんで、連立1次方程式に帰着できないんだ？」と急に疑問が湧いてしまいました。これは大きな勘違いで、線形計画法で扱う「等式標準形」は各変数にx_j \ge 0と不等式制約が課せられてるので等式制約付き線形計画問題ではないというオチでした。
  • 初稿にはアルゴリズムの実行例はありませんでした。しかし、アルゴリズムの挙動の具体的なイメージを持ってもらった方が良いだろうと考えて後で追加しました。始めは手計算で実行例を作ろうとしたのですが、さすがに無理だと判断してPythonでプログラムを書く羽目になりました。問題例が小さいと収束の早い遅いが分からないのがとても残念でした。一方で、内点法や逐次2次計画法の挙動が可視化できたのは自身の理解を深める助けにもなったので良かったなと思いました。
  • 拡張ラグランジュ関数法、内点法、逐次2次計画法は、自分自身の理解が浅かったため執筆は難航しました。分からん分からんとD先生やT先生に何度も質問してようやくエッセンスがつかめたような気持ちになれて、非線形計画法は執筆を通じて自身の理解が深まったなとしみじみ思いました。

4章：整数計画と組合せ最適化

  • 組合せ最適化と言えば製造と物流みたいな風潮に辟易としていたので、できる限りそれ以外の分野の事例をとりあげるよう心がけました。
  • 前書きでも触れたように、モデリングは数理最適化ソルバーを使いこなす上で重要なので、整数計画問題の定式化では頑張ってノウハウをまとめました。
  • 長方形詰込み問題の定式化はオリジナルです。学生の頃に後輩との議論で、長方形詰込み問題って混合整数計画問題に定式化できるんじゃない？という話になってまとめたものです。ただし、予想通りに整数計画ソルバーでは効率良く解けないのでお蔵入りになってました。
  • しばらく前からQUBO(Quadratic Uncostrained Binary Optimization)いわゆるイジングモデルが流行ってますが、整数線形計画問題に定式化できることはちゃんと断っておきたかったので書きました。ちなみに、QUBOは新しく始めた人達が勝手に名付けたものです。数理最適化では、1980年代からUBQP(Unconstrained Binary Quadratic Program)と呼ばれて研究されており、特に、メタヒューリスティクスでは割とまとまった数の論文が発表されています。なお、整数線形計画問題に定式化できると言うだけで、整数計画ソルバーで効率良く解けるかといえばお察しです。
  • 整数計画問題では、問題規模の大小よりも問題構造の良し悪しが求解効率に大きく影響します。そこで、整数性を持つ整数計画問題を紹介しました。もちろん、現実問題はさまざまな制約条件が追加されるので、整数計画問題が整数性を持つことは稀ですが、ベースとなる整数計画問題が整数性を持つならば、整数計画ソルバーで効率良く解けることが期待できます。
  • 巡回セールスマン問題を整数計画問題に定式化する際に、グラフの連結制約を表すMTZ制約がよく導入されます。しかし、グラフの連結性と聞いて真っ先に思い付くのは最小全域木だろうと思っていたので、最小全域木でMTZ制約を紹介しました。最小全域木と言えば貪欲法とマトロイドの話ばかりで、整数計画問題の定式化を見つけるのは本当に苦労しました。
  • 整数計画問題の定式化の最後に、実践的なテクニックとしてパターン列挙を紹介しました。個人的にはとても気に入っており、車両の1ルート内の訪問件数が少ないトレーラー型配送計画問題などハマると絶大な威力を発揮します。とにかく、定式化がスッキリするのが大変にありがたいです。
  • 組合せ最適化問題と言えば「NP完全性」「NP困難問題」ですが、数理最適化はもちろんアルゴリズムとデータ構造の教科書でも、これらの概念をコンパクトかつ分かり易く説明した入門書がないことに大きな不満を持っていたので頑張ってまとめました。問題(problem)と問題例(instance)の区別を明確に述べた上で、さらにアルゴリズムとの関係から問題の難しさの評価を説明したくだりは気に入ってます。
  • 組合せ最適化は問題やアルゴリズムに多様性がありすぎて理論体系もバラバラで全体の構成が本当に難しかったです。これが組合せ最適化の入門書が少ない理由なんだろうなと思います。本書では、効率良く解ける問題から順に貪欲法、動的計画法、ネットワークフロー、NP困難問題では、厳密解法から順に分枝限定法、性能保証付き近似解法、メタヒューリスティクスとまとめました。
  • 資源配分問題は、貪欲法と動的計画法の両方に現れるのでお気に入りです。恩師の茨木先生がまとまった研究をされており、解説記事や書籍を参考にさせていただきました。
  • ネットワークフローの残余ネットワークのアイデアはお気に入りです。学生の頃に勉強したときに全くピンとこなかったのはなぜなんだ。画像分割の応用事例は面白いですよね。これは、J.KleinbergとE.Tardosの『アルゴリズムデザイン』でも紹介されてます。この本は他にも組合せ最適化の面白い事例が紹介されていて好きです。
  • 双対問題はこれなくして数理最適化を語るべからずというエッセンスで、本書でも、線形計画、非線形計画、組合せ最適化と繰り返し何度も紹介しています。特に、自分は主双対法が大好きで、読者の皆さんに双対問題の凄さを知ってもらおうと、最小費用問題と頂点被覆問題で主双対法を紹介しました。その分だけ内容が難しくなってしまったのはご愛嬌と言うことで。
  • 分枝限定法と切除平面法は、読者に整数計画ソルバーの中身を理解してもらいたいという気持ちで紹介しました。なぜ、整数計画ソルバーの求解性能が入力データに敏感なのか、いつまで経っても最適解が求まらない時にソルバーの内部で何が起こっているのかを理解する助けになればと思ってまとめました。ちなみに、分枝限定法と切除平面法で2章で紹介した双対単体法が使われているというのは本書の伏線の一つです。これが、2章で双対単体法を紹介した大きな理由の一つです。
  • 性能保証付き近似解法は、全くアプローチの異なる手法ばかりなのでまとめるのに苦労しました。特にビンパッキング問題のアルゴリズムあたりは、天才が頭の良さだけで殴ってるみたいな証明で、何をどうやったらあれを思い付くのか訳が分からないですよね。
  • 性能保証付き近似解法における頂点被覆問題の主双対法とかナップサック問題の動的計画法とか、個人的には伏線回収って感じで書いてて気持ち良かったです。
  • 自身の専門がメタヒューリスティクスだったおかげで、組合せ最適化の最後まで内容が手薄になることなく書き切ることができたのは本当に良かったです。
  • これまでのトピックと異なり、メタヒューリスティクスは理論的なバックグラウンドがないので、アイデアを次から次に並べるだけのようになってしまい納得感を十分に出せなかったのは残念でした。この反省が、後の「メタヒューリスティクスの設計と実装」というセミナーの企画に繋がりました。
  • アニーリング法や遺伝的アルゴリズム（進化計算）はもう少し掘り下げられたなと、特に、前者はマルコフ連鎖モンテカルロ法から説明すれば良かったなあと反省しています。
  • 最後のラグランジュヒューリスティクスは、数理最適化とメタヒューリスティクスの融合を書きたいという個人的な趣味です。このようなアプローチはmatheuristicsと呼ばれます。

その他

文献ノート：
章末に参考文献を掲載しました。本書の多くのトピックは参考文献が元ネタです。後発なんだから、参考文献より上手くまとめて当たり前だと自身を奮い立たせてました。

演習問題：
とにかく自分は試験問題や演習問題を作るのが大変に苦手で、編集者のYさんから演習問題を付けて下さいと言われて頭を抱えました。演習問題では、本文で紹介できなかった最適化問題もいくつか取りあげています。自身が演習問題の略解しか掲載されていない教科書に大変に苦しめられたので、本書では詳細な解答を付けようと頑張りました。

コラム：
恩師の茨木先生が「Cによるアルゴリズムとデータ構造」で書かれたコラムはアルゴリズムに関わるトリビアで非常に面白かったので、少しでもそういう雰囲気が出せればと思っていました（遠い目）。自分にはコラムを紡ぎ出す能力はないと早々に諦めて、数理最適化に関する昔話を集めることにしました。ダンツィクとフォン・ノイマンの逸話は有名なのですぐに決まりましたが、残りの話題を絞り出すのは非常に難しかったです。

サポートページ：
本書は大学で担当していた数理最適化の授業をベースにしていたので、補助資料としてスライドなどをアップロードするためにサポートページを準備していました。初版発行時にサポートページのURLを書いておけば良かったと反省しています。

出版後のあれこれ

  • 本書では紹介しなかった数理最適化のトピックとしては、半正定値計画問題、錐計画問題、確率的勾配法、確率計画法、ロバスト最適化、劣モジュラ関数、マトロイドなどが挙げられます。いずれも追加しようか悩んだのですが、あれもこれもと切りがなさそうですし、本書は入門書なのだから後は参考文献で取りあげた、それぞれのトピックに特化した専門書を当たってもらえば良いと割り切ることにしました。
  • 最終校正では原稿全ページを4回読み直したのですが、出版したら読者の皆さんから次から次へと間違いの指摘をいただきまして嬉しいやら悲しいやら複雑な気持ちで一つ一つ対応しました。自分は間違いの指摘を受けると即座に対応しないと気持ち悪く思う人間なので、出版直後は仕事の手が止まることがたびたびあってしばらくは大変でした。さすがにこの1-2年は間違いの指摘も少なくなりましたが、つい先日もS先生から最短路問題に関する定理の仮定が抜けてるとのご指摘をいただいてグェーとなってました。

最後に

これで、ようやく最後（？）の宿題も終わりました。出版から4年も経って次回作の話なんかしても信憑性の欠片もありませんが、次は実務家向けの書籍を執筆したいと思ってます。本書は、研究室の学生が卒論・修論に取り組む前に数理最適化を一通り学ぶための入門書として執筆しました。しかし、エンジニアやデータサイエンティストが最速で数理最適化を実務で活用できることを目指すなら、本書とはかなり異なるカリキュラムとなるはずです。すでに、いくつかの企業で実務向けのカリキュラムに基づく数理最適化セミナーを実施しており、それをベースにした書籍をそのうちに出版できればなあと思ってます。

皆さん、最後まで駄文に長々と付きあっていただきありがとうございました。

Discussion