---

凸計画問題について

凸計画問題はシンプレックス法などで解が与えられない非線形計画の一つである

定義と性質

• 凸であるとは、なめらかに大局解に接続されていること
• 非凸とは、局所解があること

性質

• エピグラフが凸集合であることは凸関数であることと同値
• \(f_1\)と\(f_2\)が凸関数のとき、この合成は凸関数である

• 凸計画問題では任意の局所最適解は大域最適解である

• 凸関数\(f\)の\(\triangledown^2 f(x)\)はヘッセ行列と呼ぶ
  • ヘッセ行列$H$は任意の\(A\)に対して\(A^THA\geq0\)の半正定値が成立している必要がある

最急降下法

凸関数であるとき、以下のような式で解に近づけるとき

\[x^{(k+1)} = x^k + \alpha d(x^k)\]

降下方向の勾配\(d\)は以下のように定義できる

\[d(x) = -\triangledown f(x)\]

ニュートン法は\(\alpha\)がヘッセ行列の逆であるときである(解析的に導出できる)

\[x^{(k+1)} = x^k -\triangledown^2 f(x)^{-1} \triangledown f(x)\]