A Gentle Introduction to Optimization（やさしい最適化入門）

引用

Guenin, B., Könemann, J., & Tunçel, L. (2014). A Gentle Introduction to Optimization. Cambridge University Press.

章の要約

本書は約280ページと短く、7つの章と計算量に関する付録からなり、140題を超える演習を収めている。アスタリスク付きの節や章は飛ばしても支障がないように作られており、ほとんどの章は「Further reading and notes（さらなる文献と注）」の節で締めくくられる。序文は、緩和、主双対の考え方、凸性、幾何学的解釈を本書全体を貫く糸として挙げている。

第1章：序論

この章の主題は解法ではなくモデル化である。架空の企業WaterTechの小さな生産計画問題から始め、問題の言葉による記述と数理的な定式化を区別し、定式化が正しいとはどういうことかを説明する。続いて線形計画（多期間モデルを含む）、整数計画（割当問題とナップサック問題）、グラフ上の最適化問題（最短路と最小費用完全マッチング。まず問題として述べ、のちに整数計画として書き直す）、そして非線形計画を導入する。非線形計画の例には、ガジェットの価格設定や線形計画の「中心的な」実行可能解を求める問題がある。

第2章：線形計画の解法

線形計画の3通りの結果（実行不能、非有界、最適解あり）から出発し、問題を標準等式形に直し、基底と標準形（canonical form）を定義したうえで、1回の反復から単体法を組み立てる。最初の実行可能解を見つけるための2段階法も扱う。単体法のタブロー版はアスタリスク付きの節である。章の最後では多面体の幾何、凸性、端点を扱い、単体法を幾何学的に解釈する。序文によれば、この提示は実装の細部よりも主要なアイデアを意図的に優先している。

第3章：例を通じた双対性

双対性は2つの組合せ問題、すなわち最短路問題と2部グラフの最小費用完全マッチングを通じて導入される。それぞれについて、直観的な下界を見つけ、それを一般的な弱双対性の議論に変え、そこからアルゴリズムを導き、その正しさを証明する。序文は、2つの問題のどちらか一方で十分だとしている。

第4章：双対性理論

例のあとに一般理論が続く。線形計画の弱双対性と強双対性、相補性条件、最適性の幾何学的な特徴づけである。Farkasの補題はアスタリスク付きの節になっている。

第5章：双対性の応用*

3つの応用からなる任意の章である。集合被覆問題に対する主双対近似アルゴリズムとそれと貪欲法との比較、双対変数の経済学的解釈、そして完全単模行列を用いて証明される最大流最小カット定理を扱う。

第6章：整数計画の解法

整数計画をその線形計画緩和と比較し、古典的な2つの解法、すなわち切除平面法（単体法と関連づけて扱う）と分枝限定法を示す。アスタリスク付きの節では、分離アルゴリズムを用いて巡回セールスマン問題を扱う。

第7章：非線形最適化

例と、非常に難しい非線形計画もあることを示す節のあと、凸関数、エピグラフ、レベル集合を展開し、劣勾配と支持半空間によって凸問題を緩和し、Karush–Kuhn–Tuckerの定理を、まず微分可能な凸問題について、次にラグランジアンを通じて、さらに非凸問題について証明する。アスタリスク付きの節では非凸問題の凸緩和と、線形計画に対する多項式時間の内点法を扱う。序文は、KKT定理に実解析なしで、線形代数と幾何だけで到達することを強調している。

付録A：計算量

アルゴリズムが速い・遅いとはどういうことかを簡潔に紹介する。ビッグO記法、入力サイズ、多項式時間と指数時間、クラスP、NP、co-NP、帰着とNP完全性を、本書自身のアルゴリズムを例にとって説明する。

主要概念

第1–2章：定式化と単体法

• 定式化：変数、目的関数、制約からなる数理モデル。その実行可能解が言葉による記述の実行可能解と対応するとき、正しいと判断される。
• 線形計画・整数計画・非線形計画：定式化の3つの種類。最も解きやすいため、本書は可能な限り線形計画として定式化しようとする。
• 基底と標準形：単体法が移動していく頂点の代数的な表現。
• 端点：多面体の角。単体法の反復の幾何学的な意味を与える。

第3–5章：双対性

• 弱双対性：双対問題の任意の実行可能解が主問題の最適値の限界を与える。
• 強双対性と相補性条件：最適解が存在するとき2つの最適値は一致し、最適解の組は対応するゼロ条件を満たす。
• 主双対アルゴリズム：主問題の解と双対問題の解を同時に保持する方法。最短路、マッチング、集合被覆に用いられる。
• 完全単模行列：線形計画がすでに整数の最適解をもつような制約行列。最大流最小カット定理を導く。

第6章：整数計画

• 緩和：整数条件を外して線形計画を得ること。その値は整数計画の最適値の限界になる。
• 切除平面法と分枝限定法：整数計画とその緩和との差を埋める古典的な2つの方法。

第7章と付録A：非線形最適化と計算量

• 凸関数と劣勾配：非線形問題を扱いやすくし、半空間による緩和を可能にする構造。
• Karush–Kuhn–Tucker条件：制約付き非線形問題の最適性条件。本書では幾何とラグランジアンを通じて導かれる。
• P、NP、NP完全性：易しい問題と難しい問題を区別するための用語。

批判的分析

長所

• 入口は低く、到達点は本格的。 序文が求めるのは大学1年の線形代数だけだが、本書は双対性、整数計画、Karush–Kuhn–Tuckerの定理にまで達する。より進んだ最適化の授業への準備を目的としており、各章の「Further reading and notes」が次の道筋を示す。
• 双対性をまず問題を通じて教える。 第4章で一般理論を述べる前に、第3章で最短路とマッチングの直観的な下界から弱双対性と正しいアルゴリズムを導くので、抽象的な結果の背後に具体的な内容がある。
• さまざまな授業のために作られている。 アスタリスク付きの内容は飛ばせ、序文はおよそ10通りの章の組み合わせを示している。モデル化と応用、線形計画のみ、計算機科学科向けの線形・離散最適化、線形・非線形最適化などである。草稿は4年間にわたり12人の教員によって使われ、受講者は会計やビジネスから純粋数学、計算機科学まで多岐にわたった。
• 連続的手法と並んで組合せ論と計算量を扱う。 グラフ問題、近似アルゴリズム、完全単模性、PとNPに関する付録が、凸性やKKT条件と同じ短い本に収められているため、連続数学の学生だけでなく、オペレーションズ・リサーチや計算機科学の学生にも役立つ。

短所

• 非線形問題のアルゴリズムが少ない。 第7章は凸性と最適性条件を主題としており、線形計画に対するアスタリスク付きの内点法を除けば、目次には非線形問題を解くアルゴリズムが見当たらない。
• 意図して簡潔。 序文は本文を簡潔に保ち、発展的な話題や周辺的な話題をアスタリスク付きの節や演習に回す方針を掲げている。ある話題をより深く学びたい学生には2冊目が必要になる。
• 解答は教員向けのみ。 出版社によれば解答は教員に提供されており、独学者には答え合わせの手段がない。
• ソフトウェアを扱わない。 目次にはモデリング言語やソルバーに関する内容がなく、定式化は手で書き下される。計算は授業の側で補う必要がある。

コースにおける位置づけ

本書は、このコースの最適化分野で最初に読む教科書として自然な位置にある。Alain Goriely の Applied Mathematics: A Very Short Introduction は、応用数学者がどのようにモデルを作り分析するかを、ほとんど数式を使わずにずっと短く述べた本で、本書の前に、あるいは並行して読む背景として適している。Ian Jacques の Mathematics for Economics and Business と Adam Ostaszewski の Advanced Mathematical Methods は、最適化を経済学やビジネスなどへの応用のための数学的手法の一部として扱い、線形計画と双対性を中心にはしていない。

アルゴリズムを学びたい読者にとっては、Chong、Lu、Żak の An Introduction to Optimization が次の一歩である。制約なし・制約付きの非線形最適化と線形計画をより深く扱い、機械学習への応用も含み、本書の第7章の主な空白を埋める。Boyd と Vandenberghe の Convex Optimization は、凸集合、凸関数、双対性、アルゴリズムについてのより充実した、より高度な扱いであり、本書の第4章と第7章を終えた読者には、その考え方がなじみ深く感じられるだろう。

本書の使い方

本書は、大学1年の線形代数を履修した、数学、計算機科学、工学、ビジネス、経済学の1、2年生に適している。必要なのは行列の操作と連立1次方程式の解法だけである。双対性や正しさの議論は述べるだけでなく証明されるので、短い証明を読むことに慣れていると役立つ。

1学期の授業のための読書計画：

• 中核： モデル化のための第1章、単体法のための第2章（タブローの節は飛ばしてよい）、第3章の2つの問題のうち1つ、そして第4章。
• 次に選択： 離散最適化なら第6章、非線形最適化なら第7章、あるいは両方。第5章は任意で、経済学的解釈の節はビジネスや経済学の学生に、集合被覆と最大流最小カットは計算機科学の学生に向いている。
• モデル化の授業なら、序文の提案に従って第1、2、3、6、7章を読む。単体法をすでに知っているなら、第3章から始める。
• 計算量の付録は単体法に慣れたあとで読むとよい。線形計画が易しく整数計画が難しいとされる理由を説明している。

最も時間をかけるべきなのは第1章の定式化の演習である。正しいモデルを書くことは、本書の残りの部分が依拠する技能だからである。第1章と同じように、言葉で述べられた問題の実行可能解がすべて定式化の実行可能解に対応し、逆も成り立つかを問うことで、自分のモデルを確かめるとよい。解答は教員にしか提供されないので、小さなモデルを何らかの線形計画ソルバーで解いて計算機で答えを確かめ、アスタリスク付きの演習は2周目に回すのがよい。