数理情報学演習 1 最適化問題，凸集合・凸関数 2007 年 4 月 26 日 担当: 金森 敬文 (kanamori@is.nagoya-u.ac.jp) 1 最適化 最適化問題は，ある関数 f : Rn → R をある制約条件 x ∈ S ⊂ Rn のもとで最小化数理情報学演習 1 最適化問題，凸集合・凸関数 2007 年 4 月 26 日 担当: 金森 敬文 (kanamori@is.nagoya-u.ac.jp) 1 最適化 最適化問題は，ある関数 f : Rn → R をある制約条件 x ∈ S ⊂ Rn のもとで最小化 (もしくは最 大化) する，という問題である．具体的には次の２つ • 最小値を達成するような x ∈ S の数学的な条件 (最適性条件)． • 最小値や解を具体的に計算するためのアルゴリズム について考える． 最適化問題は，関数 f : Rn −→ R と集合 S ⊂ Rn に対して 最小化 f(x) 条件 x ∈ S と記述される．上の最適化問題は，「最小化」を「min」，「条件」を「s.t. (subject to)」と書いて min f(x) s.t. x ∈ S (1) と記述することが多い． 例 1. 学校の配置
