数学やプログラミングの備忘録

数理最適化, Python, C++をメインに紹介するブログ。

MENU
トップ > 数理最適化 > 制約無し凸二次最適化問題の解法 (理論編)

制約無し凸二次最適化問題の解法 (理論編)

数理最適化 数理最適化-二次計画法

最適化問題の1つである 制約無し凸二次最適化問題(二次計画問題) の 解法 をどこよりもシンプルに解説します。

目次

制約無し凸二次最適化問題とは？

\begin{array}{ll} \min_{x} & x^T Q x + p^T x + r\\ \text{s.t.} & x \in \mathbb{R}^n \end{array}
  • 名前の通り、制約無しの最適化問題
  • x は実数をとる
  • 行列 Q が半正定値行列ならば、目的関数は凸関数
    • この場合、制約無し凸二次最適化問題
    • 正定値のときは、目的関数は狭義凸関数

目的関数が凸関数ならば、いろんなソフトウェアやライブラリーで解くことができますが、凸ならこの問題はソフトウェアやライブラリーを使うまでも無く簡単に解けるんです。

制約無し凸二次最適化問題の解法

\begin{array}{ll} \min_{x} & x^T Q x + p^T x + r\\ \text{s.t.} & x \in \mathbb{R}^n \end{array}

目的関数 (最小化したい関数)を f(x) とします:

f(x) = x^T Q x + p^T x + r

目的関数 f(x) が 凸関数 のとき、

$$ \nabla f(x) = 0 $$

を満たす x は上記の最適化問題の最適解となります。
ただし、 \nabla f(x) は勾配ベクトルです。

勾配ベクトルを計算してみると、

$$ \nabla f(x) = 2 Q x + p $$

よって、勾配ベクトルが０となる x^* は、

$$ x^* = - \frac{1}{2} Q^{-1} p $$

となります。

実際には、逆行列を求めずに、

$$ \nabla f(x) = 2 Q x + p = 0 $$

の線形方程式を解くことで、最適解を求めます。

ちなみに、最適値 f(x^*) を計算するときは、直接代入せずに、

\begin{align} f(x^*) &= (x^*)^T Q x^* + p^T x^* + r \\ &= (x^*)^T Q (-\frac{1}{2} Q^{-1} p) + p^T x^* +r \\ &= - \frac{1}{2} (x^*)^T p + p^T x^* + r \\ &= \frac{1}{2} p^T x^* +r\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (A) \end{align}

と変形して代入すれば、計算量が少なくてすみます。

解法手順まとめ

  1. 最適解 x^* を求める
    • 勾配ベクトル \nabla f が０となる x^* を求める
    • 実際には、線形方程式を解く
  2. 最適値 f(x^*) を求める
    • 直接代入せずに、(A) に 1.で求めた x^* を代入

以上、目的関数が凸関数であるときの、
制約無し二次最適化問題の解法でした！

そのうち、実際にプログラムで制約無し凸二次最適化問題を解く記事を書きます。