凸最適化

📚 コンテンツ概要

凸最適化の理論、応用および数値アルゴリズムを網羅する大学院レベルのコースおよび教科書。工学および科学分野における凸問題の認識と定式化に重点を置く。

工学およびデータサイエンスにおいて、凸最適化の数学的基盤と実用的アルゴリズムを習得する。

著者: ステファン・ボイド、リーベン・ヴァンデンベーエ

謝辞: NSF の支援を受け、スタンフォード大学およびウCLAの学生や同僚からの貢献も含まれており、特にアラキ・ネミロフスキーおよびキシャン・バヘティに特別な言及がある。

🎯 学習目標

1. 目的関数、制約条件、変数を含む数学的最適化問題の構成要素を定義する。
2. 数学的性質に基づいて最小二乗法、線形計画法、凸最適化問題を区別する。
3. 局所最適化とグローバル最適化戦略を比較し、それぞれに伴う計算複雑性を評価する。
4. 演算記号を使用してアフィン集合、凸集合、錐体を定義し、区別する。
5. ユークリッド球、楕円体、多面体、正半定値錐などの標準的な凸集合を識別し表現する。
6. 交差、アフィン変換、射影関数など凸性を保つ操作を適用し、集合の性質を検証する。
7. アフィン関数の点ごとの上限およびベクトル合成則など、凸性を保つ操作を識別し適用する。
8. さまざまな関数のラグランジュ共役を導出し、ヤングの不等式を適用する。
9. 部分レベル集合および一階・二階微分可能な条件を用いて準凸性を特徴付ける。
10. 定式化と変換：スラック変数と制約消去を用いて、原始的な最適化問題を標準的な凸形式に変換する。

🔹 レッスン1: 数学的最適化入門

概要: このレッスンでは、数学的最適化の基礎的概念を紹介し、一般的な問題設定から最小二乗法や線形計画法といった具体かつ解けるクラスへと移行する。凸最適化と非凸最適化の重要な違いに注目し、凸手法が効率性の「分水嶺」として機能し、より困難な非線形問題に対処するための重要なツールを提供することを強調する。

学習成果:

• 目的関数、制約条件、変数を含む数学的最適化問題の構成要素を定義する。
• 数学的性質に基づいて最小二乗法、線形計画法、凸最適化問題を区別する。
• 局所最適化とグローバル最適化戦略を比較し、それぞれに伴う計算複雑性を評価する。

🔹 レッスン2: 凸集合の理論

概要: このレッスンでは最適化の基礎となる幾何学的構造について探求し、基本的な線形構造から凸集合や錐体の複雑な性質へと移行する。アフィン集合および凸集合の数学的定義を扱い、多面体や正半定値錐のような特定の幾何構造を検討し、高次元空間における凸集合の特徴付けと操作に必要な演算および定理を詳述する。

学習成果:

• 演算記号を使用してアフィン集合、凸集合、錐体を定義し、区別する。
• ユークリッド球、楕円体、多面体、正半定値錐などの標準的な凸集合を識別し表現する。
• 交差、アフィン変換、射影関数など凸性を保つ操作を適用し、集合の性質を検証する。

🔹 レッスン3: 凸関数とその性質

概要: このレッスンでは、点ごとの上限や特定の合成則など凸性を保つ高度な演算を扱い、ラグランジュ共役関数を導入する。凸性の概念を準凸関数および対数凹関数へと拡張し、一般化された不等式に関する凸性およびシュール補行列といった行列固有の性質についても考察する。これらの概念は、複雑な最適化問題の識別と定式化の数学的基盤を形成する。

学習成果:

• 点ごとの上限のアフィン関数およびベクトル合成則など、凸性を保つ操作を識別し適用する。
• さまざまな関数のラグランジュ共役を導出し、ヤングの不等式を適用する。
• 部分レベル集合および一階・二階微分可能な条件を用いて準凸性を特徴付ける。

🔹 レッスン4: 凸最適化問題の定式化

概要: このレッスンでは、凸最適化問題の正式な構造と変換について扱い、標準形、最適性条件、および特定の問題クラス（線形計画法（LP）、二次計画法（QP）、半正定値計画法（SDP））までをカバーする。学生はグローバル最適性の識別方法、準凸問題に対する二分法の使用、およびマルチクライテリアベクトル最適化へのスカラ化の適用を学ぶ。

学習成果:

• 定式化と変換：スラック変数と制約消去を用いて、原始的な最適化問題を標準的な凸形式に変換する。
• 最適性の分析：勾配ベースの最適性基準を適用し、ある点がグローバルに最適かどうかを判断する。
• 分類と解法：LP、QP、SOCP、GP、SDPを区別し、準凸関数に対して二分法などの専門的手法を適用する。

🔹 レッスン5: ラグランジュ双対性とKKT条件

概要: このレッスンではラグランジュ双対性の基礎理論を探索し、ラグランジュ双対関数の定義から双対問題の構成までを扱う。プライマルとダウアルの最適値の間の重要なギャップ、これらの関係の幾何学的およびゲーム理論的解釈、および最適解を特徴付けるカルーシュ＝クーン＝タッカー（KKT）条件を詳細に説明する。最後に、これらの概念を感度解析とシャドウプライスに拡張する。

学習成果:

• ラグランジュ双対関数を導出し、さまざまな最適化問題に対して双対問題を構成する。
• 弱双対性・強双対性およびスレイターの制約適合性条件を用いて、プライマル問題とダウアル問題の関係を評価する。
• KKT最適性条件を適用し、凸および非凸問題の最適解を解き、検証する。

🔹 レッスン6: 近似、フィッティング、正則化

概要: このレッスンでは、連立一次方程式の解の近似およびデータへの関数フィッティングの数学的基盤と実践的な応用を扱う。ノルムに基づく近似、罰則関数および正則化による外れ値やスパース性の管理、データ不確実性に対応するロバスト最適化技術をカバーする。さらに、凸性や単調性といった特定の制約下での関数フィッティングの詳細も述べる。

学習成果:

• ノルム近似問題を定式化・解き、最小二乗法、チェビシェフ法、L1アプローチの幾何学的および統計的差異を解釈する。
• 残差誤差、解の大きさ、スパース性のトレードオフを達成するために正則化された近似モデルを設計・実装する。
• データ行列の不確実性を考慮したロバスト近似フレームワークを構築する。

🔹 レッスン7: 統計的推定と推論

概要: このレッスンでは統計的推論と凸最適化の交差点を探索する。最大尤度推定、非パラメトリック分布推定、最適検出器設計などの推定問題を凸計画として定式化する。学生は最適化を使ってパラメータを求める方法や情報量豊富な実験を設計する方法を学ぶ。

学習成果:

• 最大尤度推定（MLE）およびロジスティック回帰問題を凸最適化として定式化・解く。
• 線形計画法（LP）を用いて最適検出器を設計し、受信者動作特性（ROC）を解釈する。
• 最大エントロピーおよびカルバック・ライブラー距離最小化を含む非パラメトリック推定技術を適用する。

🔹 レッスン8: 幾何学的問題と分類

概要: このレッスンでは凸最適化の幾何学的応用を扱い、集合への点の射影、集合間の距離計算、集合の中心の特徴付けを含む。さらに、これらの幾何学的原理を線形・非線形分類、最適施設配置、幾何学的プログラミングを用いた床面積計画といった実世界のタスクに拡張する。

学習成果:

• KKT条件および双対表現を用いて、凸集合間の射影および距離問題を定式化・解く。
• 最大体積楕円体を用いて複雑な凸集合を近似し、その効率係数を特定する。
• 異常値に強い判別および分類に応用する各種集合の中心を計算する。

🔹 レッスン9: 無制約最小化アルゴリズム

概要: このレッスンでは、凸関数に対する無制約最小化の理論的基盤とアルゴリズム実装を扱う。勾配降下法から二階のニュートン法までの下降法を詳細に説明する。特に収束解析に焦点を当て、強い凸性および自己調和性のアフィン不変理論について深く探求する。

学習成果:

• 強凸性を定義し、最適解への乖離および部分最適性の上界を導くためにその影響を利用する。
• ユークリッド、二次、L1ノルム下での勾配降下法と最急降下法を比較・対比する。
• ニュートンステップおよびニュートン減少量を計算し、ニュートン法がアフィン不変である理由を説明する。

🔹 レッスン10: 等式制約最小化

概要: このレッスンでは、線形等式制約を持つ凸最適化問題の解法を扱う。ニュートンステップの導出と実装に焦点を当て、可能解スタート法と不可能解スタート法を比較し、それらのステップをプライマル・ダウアル枠組みの中で解釈する。特に、KKTシステムのブロック消去を用いた効率的な数値実装に重点を置く。

学習成果:

• 等式制約付き問題におけるニュートンステップおよび減少量を計算・解釈する。
• 等式制約付きニュートン法とそれらの制約の消去の等価性を示す。
• 不可能解スタートニュートン法を実装し、そのプライマル・ダウアル残差削減特性を説明する。

🔹 レッスン11: 内部点法

概要: このレッスンでは、不等式制約を持つ凸最適化問題を解く内部点法を扱う。対象となるのは、対数バリア関数を用いて不等式制約を持つ問題を、一連の等式制約問題に還元し、ニュートン法を適用するものである。中核となるのは、中央パスを追跡し最適解に至ること、およびプライマル・ダウアル枠組みを用いた効率性と堅牢性の向上である。

学習成果:

• 対数バリア関数を定義・構成し、中央パスおよびそれに伴う双対点を特徴付ける。
• バリア法を実装し、中心化ステップと外部反復の間のトレードオフを理解する。
• 厳密な初期点を見つけるためのフェーズIの妥当性問題を定式化・解く。