最適化理論

数学では、与えられた関数 $f: X \to \mathbb{R}$ の最大値と最小値を見つけることを最適化と言います。この目的関数が私たちの生活の問題に直結している場合、応用数学の観点から大きな関心を集め、その解法である最適化理論の重要性は言うまでもありません。

• 数学での最適化技術
  • 最適値：最大値と最小値 $\max$, $\min$
  • 最適解：最大引数と最小引数 $\text{argmax}$, $\text{argmin}$
  • 1次必要条件
  • 2次必要/十分条件
• 交互最適化

線形計画法

• 線形計画問題

標準形

• 方程式フォーム
  • 最適解の存在
• 基底可能解
  • 基底可能解の一意性
  • 最適解が存在するなら、そのうちの一つは基底可能解である
• 線形計画法の基本定理の証明

シンプレックス法

• ディクショナリとタブロー
• シンプレックス法
  • 初期化と補助問題
  • 目的関数の無限大
  • シンプレックス法のサイクリング
• シンプレックス法のブランドルール

双対性

• プライマル問題とデュアル問題
• 弱い双対性定理の証明
• 強い双対性定理の証明

実践

• エクセルで線形計画問題を解く方法
• Juliaで線形計画問題を解く方法 JuMP.jl
• Pythonで線形計画問題を解く方法 scipy
• MATLABで線形計画問題を解く方法 Optimization Toolbox
• Rで線形計画問題を解く方法 lpSolve

非線形計画法

• ラグランジュ乗数法

勾配降下法

• 勾配降下法
• 確率的勾配降下法
• ニュートン法
• サブグラディエント
• サブグラディエント法

プロキシメータルアルゴリズム

• プロキシメータルオペレーター $\operatorname{prox}_{\lambda f} (\mathbf{x})$
• プロキシメータル最小化アルゴリズム $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda f}(\mathbf{x}^{(k)})$
• プロキシメータル勾配法 $\mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)})) $
• PALM(Proximal Alternating Linearized Minimization)

進化計画法

ヒューリスティック

パーティクルスウォーム

主要参考文献

• Luenberger. (2021). Linear and Nonlinear Programming (5th Edition)
• Matousek. (2007). Understanding and Using Linear Programming
• Vanderbei. (2020). Linear Programming(5th Edition)