Convex Optimization（凸最適化）

引用

Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press. 公式の無料版：https://web.stanford.edu/~boyd/cvxbook/

章の要約

本書は全11章で、理論・応用・アルゴリズムの3部と3つの付録からなり、各章末に演習問題がある。序文は目標を、凸最適化の実用的な知識、すなわち凸問題を見抜き、定式化し、解く力としている。

第1章：Introduction（序論）

一般的な最適化問題を示したうえで、確実な解法がある問題クラスとして最小二乗法と線形計画を取り上げ、凸最適化をその共通の一般化として位置づける。局所最適化と大域最適化を対比し、凸問題が非凸問題の扱いをどう助けるか（初期点の与え方、疎な解を求めるヒューリスティクス、下界）を示し、3部の構成を概観する。

第2章：Convex sets（凸集合）

アフィン集合と凸集合、錐、そして標準的な例（超平面、球と楕円体、ノルム錐、多面体、半正定値錐）から始まる。続いて凸性を保つ演算、真錐に関する一般化不等式、分離超平面と支持超平面、双対錐を扱う。

第3章：Convex functions（凸関数）

1階・2階の条件、劣水準集合、エピグラフ、Jensenの不等式によって凸関数を定義し、多数の例を挙げる。次に凸性を保つ演算の「計算規則」（和、各点最大、合成、最小化、透視）を整え、共役関数、準凸関数、対数凹・対数凸関数、一般化不等式に関する凸性へと進む。

第4章：Convex optimization problems（凸最適化問題）

定式化の章である。標準形、等価な問題、微分可能な目的関数に対する最適性条件を述べたうえで、一般性の順に主な問題族を並べる。線形計画、二次計画と2次錐計画、幾何計画、錐計画と半正定値計画、そしてPareto最適性とスカラー化を伴うベクトル（多目的）最適化である。

第5章：Duality（双対性）

Lagrange関数、双対関数、双対問題から、弱双対性、強双対性、Slaterの制約想定へ進む。続いて幾何的解釈と鞍点解釈、KKT最適性条件、摂動と感度分析、双対化の前に問題を変形する具体例、選択定理、一般化不等式への拡張が述べられる。

第6章：Approximation and fitting（近似とフィッティング）

ノルム近似、最小ノルム問題、正則化近似（二目的のトレードオフ、平滑化、ノイズ除去を含む）、ロバスト近似（確率的な場合と最悪の場合）、関数のフィッティングと補間を扱う。フィッティングの話題には基底追跡による疎な表現も含まれる。

第7章：Statistical estimation（統計的推定）

最尤推定と最大事後確率推定、ノンパラメトリックな分布推定、最適検出器の設計と仮説検定、ChebyshevとChernoffの上界、実験計画を、いずれも凸問題として定式化する。

第8章：Geometric problems（幾何の問題）

集合への射影、集合間の距離、ユークリッド距離と角度の問題、体積極値楕円体、中心化（Chebyshev中心、最大体積楕円体の中心、解析的中心）、線形・非線形判別による分類、配置と位置決め、フロアプランニングを扱う。

第9章：Unconstrained minimization（制約なし最小化）

強凸性の仮定のもとで降下法を導入し、勾配降下法、さまざまなノルムでの最急降下法、Newton法を、それぞれ収束解析と数値例とともに述べる。続いて自己協和性を導入する。これはNewton法のさらなる収束解析の土台となる条件である。最後にNewton方向の計算に関する実装上の注意を述べる。

第10章：Equality constrained minimization（等式制約付き最小化）

Newton法を線形等式制約のある問題へ拡張する。まず変数消去と双対を通じた解法を述べ、次に等式制約付きのNewton方向と実行不可能初期点Newton法を扱う。応用として凸凹ゲームが登場し、実装の節ではKKT系の解法を論じる。

第11章：Interior-point methods（内点法）

対数障壁関数と中心パスから障壁法へ進み、収束解析、実行可能点を見つけるフェーズI法、自己協和性に基づく計算量解析が続く。さらに障壁法を一般化不等式へ拡張し、主双対内点法を説明し、線形計画・半正定値計画・ネットワークのレート最適化の実装で締めくくる。計算量の節のまとめは、最悪の場合の上界が実際に観察される反復回数よりはるかに大きいと述べている。

付録A–C：Mathematical background；Problems involving two quadratic functions；Numerical linear algebra background（数学的背景；2つの二次関数を含む問題；数値線形代数の背景）

付録Aはノルム、解析、関数、導関数、線形代数をまとめ、記法を定める。付録Bは2つの二次関数を含む最適化問題（S-procedureと2つの対称行列の値域）を扱い、それらに関する強双対性の証明を含む。付録Cは行列の構造と演算量、分解して解く方法、LU・Cholesky・LDL^T分解、ブロック消去とSchur補元を扱う。

主要概念

第2〜3章：凸集合、凸関数

• 凸性を保つ演算：共通部分、アフィン写像、非負の和、各点最大などの規則。複雑な集合や関数を単純な部品に分けて凸だと見抜くことができる。
• 一般化不等式：真錐によって定まる順序。ベクトルや行列の不等式をスカラーの不等式のように扱える。

第4章：凸最適化問題

• 問題の階層：線形、二次、2次錐、幾何、半正定値の各計画は、順に一般性が増す凸問題のクラスである。
• Pareto最適性：多目的問題における最適なトレードオフの概念で、スカラー化を通じて調べられる。

第5章：双対性

• Lagrange双対と強双対性：双対問題は最適値の下界を与え、Slater条件は凸問題でその下界が厳密になることを保証する。
• KKT条件：主問題と双対問題の実行可能性に相補性条件を組み合わせた最適性条件。
• 感度分析：制約を変えたとき最適値がどう変わるかを双対変数から読み取る。

第6〜8章：応用

• 正則化とロバスト性：データへの適合と第2の基準とのトレードオフ、またはデータの不確かさへの備え。
• 最尤推定：パラメータ推定を対数尤度関数の最大化として定式化すること。

第9〜11章：アルゴリズム

• Newton方向とNewton減少量：二次モデルから得られる降下方向と、進捗の測定や停止に使う量。
• 自己協和性：3階微分に関する条件で、Newton法の計算量の上界を支える。
• 障壁法と中心パス：不等式制約付き問題を、等式制約付き問題の列として解く方法。

批判的分析

長所

• 定式化の力を軸にした構成。 序文と第1章は、凸最適化の技が問題を見抜き定式化することにあると論じ、構成もそれに沿う。第2〜4章は集合・関数・問題クラスの一覧で見抜く力を養い、第II部がそれを応用する。
• 短くて読みやすい応用。 第II部は統計、幾何、データフィッティングの簡略化した事例を用い、専門外の読者にも読めるよう短くまとめている。
• 明快なアルゴリズムの階層。 第III部は二次問題から出発し、等式制約付きNewton法を経て内点法へ進むので、各手法がより単純な問題の列に帰着される。
• 定式化を鍛える演習。 凸性の証明や問題の定式化を求める演習が多く、数値演習の一部は少量のプログラミングで足りる。

短所

• 凸解析の理論書ではない。 序文は、本書が主に凸解析を扱うものではなく、結果を最も一般的な形では述べないと断っている。その深さが必要な読者は別の教科書に当たる必要がある。
• 扱うアルゴリズムは限られる。 第III部はNewton型と内点法に限られ、それも簡略化した形である。著者は準Newton法、共役勾配法、バンドル法、切除平面法を扱わないクラスとして挙げている。
• 演習の難易度にばらつきがある。 序文は、難易度が予告なしに易しいものから厄介なものまで変わると述べているので、問題の選択には少し注意が要る。
• 一定の数学的成熟度が前提。 序文は高度な微積分と線形代数の十分な知識を求め、基礎的な解析や確率を学んでいない読者も要点は得られるが、すべての議論を追えるとは限らないとしている。

コースにおける位置づけ

Boyd と Vandenberghe は、このコースで凸最適化に絞った教科書である。リスト中のほかの2冊は、より手前から始まる。A Gentle Introduction to Optimization は線形代数の入門を終えた学生向けで、線形計画・整数計画と単体法を扱う。Chong、Lu、Żak の An Introduction to Optimization は、上級の学部生向けに制約なし最適化、線形計画、制約付き非線形最適化を扱う。どちらも、本書の前に最適性条件と線形計画の土台を築くのに役立つ。本書の序文自身が、高度な線形代数と線形計画を自然な先行トピックとしている。

Boyd と Vandenberghe がこれらと違うのは、すべてを凸性を軸に組み立てている点で、双対性、錐計画、内点法が後付けではなく中心に置かれる。リスト中の残り2冊（高度な数学的方法、経済・ビジネスのための数学）は範囲が広く、最適化はその一部にすぎない。したがって、凸問題を本格的に定式化して解く必要があるときには本書を使うとよい。

本書の使い方

本書は、最適化を使う研究者・科学者・技術者を対象とし、大学院の講義にも向く。著者は、1クォーター制の大学院講義で、詳細には立ち入らずに大部分を扱え、1セメスターならより多くの応用と小さなプロジェクトを入れられるとしている。必要な前提は高度な微積分と線形代数のみで、解析と確率の知識があればすべての議論を追えるという。

実際的な進め方：

• 中核： 第1章、第2・3章は選択的に（例と凸性を保つ演算のほうがすべての証明より重要）、第4・5章は全部。この4章が定式化と双対性の力を担う。
• 応用： 関心に応じて第6〜8章から選ぶ。たとえば第6章はフィッティングと正則化、第7章は統計、第8章は幾何と分類。
• アルゴリズム： 第9〜11章を順に読む。各章が前章の上に立つからである。11.5節の計算量解析は最初は飛ばしてよい。その節自身のまとめが、主に理論的な関心のためのものだとしている。
• 付録： 記法は付録Aで確認し、Newton方向とKKT系を実装する前に付録Cを読む。

定式化や凸性の証明を求める演習を数値演習より先に解き、各定式化を標準形で書き出すこと。小さな例題をソルバーで解いて定式化を確かめるのが、理解を試す最も直接的な方法である。

版と出典

本ガイドは第1版（Cambridge University Press、2004年）を対象とし、著者のサイトで公開されている版、すなわち2009年の訂正入り第7刷に基づく。公式の無料版は https://web.stanford.edu/~boyd/cvxbook/ にある。この版については、序文、完全な目次、すべての節・項の見出し、序論の全文、各章からの抜粋（第11章の計算量のまとめとNewton方向の実装に関する説明を含む）を根拠としている。