制約付き最適化の 3 手法を統一的に導出する ラグランジュ関数の視点から | opt の競プロブログ

を考えます．これは「$g(x) = \0$ という制約を満たす $x \in \R^n$ のうち，$f(x)$ を最小化するものを求めよ」という問題です． 関数 $f, g$ の凸性や線形性は仮定しません．ただしそのような仮定が無いと，問題 \eqref{problem} の最適解を求めるのは大変難しくなります．この記事で紹介する手法でも，一般に最適解は求まりませんが，弱い仮定の下で「ある程度良い解」が得られることは知られています1． ラグランジュ関数の導入制約付き問題を解くための典型的な戦略に，「制約無し問題に変形する」というものがあります．問題 \eqref{problem} を制約無し問題に変形するため，ラグランジュ関数を導入します．「ラグランジュの未定乗数法」でも使うアレです． 問題 \eqref{problem} のラグランジュ関数 $L : \R^n \times \R^m \

[maghrib]

“opt の競プロブログ”