制約無し凸二次計画問題を手計算で解く例題

今日は、制約無し凸二次計画問題(最適化問題)を手計算で解いてみます。

制約無し凸二次計画問題って何？という方や解法の手順を詳しく知りたい人は、下記の記事を参考にしてください。

www.letsopt.com

例題

$\begin{array}{ll} \min_{x} & 2x^2 + y^2 + x y + x + y\\ \text{s.t.} & x \in \mathbb{R}^n \end{array}$

変数として $x, y$ の二つを持つ最適化問題です。

$\begin{align} f(x) &= 2x^2 + y^2 + x y + x + y\\ &= (\begin{array}{cc} x & y \end{array}) \left( \begin{array}{cc} 2 & 0.5\\ 0.5 & 1 \end{array} \right) \left(\begin{array}{c} x\\ y \end{array}\right) + (\begin{array}{cc} 1 & 1 \end{array}) \left(\begin{array}{c} x\\ y \end{array}\right) \end{align}$

目的関数が凸関数であるとき(係数行列が半正値対称行列であるとき)、例題の最適解を求めるには、次の連立方程式を解きます(解法の詳細な説明はこちら)。

$2 \left( \begin{array}{cc} 2 & 0.5\\ 0.5 & 1 \end{array} \right) \left(\begin{array}{c} x\\ y \end{array}\right) = -\left(\begin{array}{c} 1\\ 1 \end{array}\right)$