最適化問題の1つである 制約無し凸二次最適化問題(二次計画問題) の 解法 をどこよりもシンプルに解説します。
目次
制約無し凸二次最適化問題とは?
目的関数が凸関数ならば、いろんなソフトウェアやライブラリーで解くことができますが、凸ならこの問題はソフトウェアやライブラリーを使うまでも無く簡単に解けるんです。
制約無し凸二次最適化問題の解法
目的関数 (最小化したい関数)を とします:
目的関数 が 凸関数 のとき、
$$ \nabla f(x) = 0 $$
を満たす は上記の最適化問題の最適解となります。
ただし、 は勾配ベクトルです。
勾配ベクトルを計算してみると、
$$ \nabla f(x) = 2 Q x + p $$
よって、勾配ベクトルが0となる は、
$$ x^* = - \frac{1}{2} Q^{-1} p $$
となります。
実際には、逆行列を求めずに、
$$ \nabla f(x) = 2 Q x + p = 0 $$
の線形方程式を解くことで、最適解を求めます。
ちなみに、最適値 を計算するときは、直接代入せずに、
と変形して代入すれば、計算量が少なくてすみます。
解法手順まとめ
- 最適解
を求める
- 勾配ベクトル
が0となる
を求める
- 実際には、線形方程式を解く
- 勾配ベクトル
- 最適値
を求める
- 直接代入せずに、(A) に 1.で求めた
を代入
- 直接代入せずに、(A) に 1.で求めた
以上、目的関数が凸関数であるときの、
制約無し二次最適化問題の解法でした!
そのうち、実際にプログラムで制約無し凸二次最適化問題を解く記事を書きます。