正定矩陣的二次規劃

我們都知道 \(a > 0\) 的二次多項式

\[ ax^2 + bx + c \]

的最小值發生在 \(x = -\frac{b}{2a}\) 的地方。如果我們考慮由 \(n\times n\) 正定矩陣 \(A\) 所形成的多變數多項式

\[ \bx\trans A \bx + \bb\trans\bx + c, \]

其中 \(\bx\in\mathbb{R}^n\) 為變數向量、\(\bb\in\mathbb{R}^n\) 及 \(c\in\mathbb{R}\) 分別為給定的向量及常數。這樣的函數是否也會有類似的性質呢？這樣的問題屬於 二次規劃（quadratic programming） 的其中一型，更一般的二次規劃容許 \(A\) 不一定要正定、而也常夾帶 \(\bx\) 的其它條件。

就結論來說，的確這樣的函數有最小值，而且它會發生在 \(\bx = -\frac{1}{2}A^{-1}\bb\) 的地方。以下我們逐步觀察如何得到這個結論。

首先，如同正數有二次方根一般，每個正定矩陣 \(A\) 都可以找到另一個正定矩陣 \(P\) 使得 \(A = P^2\)；實際上這是個等價敘述，也就是如果找得到正定矩陣 \(P\) 讓 \(A = P^2\)，則 \(A\) 為正定。

接著我們試著將目標方程式配方，我們期望找到一個向量 \(\bq\) 使得

\[ \|P\bx + \bq\|^2 = (P\bx + \bq)\trans (P\bx + \bq) = \bx\trans P\trans P\bx + 2\bq\trans P\bx + \bq\trans \bq \]

和目標式有相同的二次項和一次項。注意到 \(P\) 是正定矩陣（所以對稱且可逆），因此 \(P\trans P = PP = A\)，而我們可以取 \(\bq = \frac{1}{2}P^{-1}\bb\) 使得

\[ \|P\bx + \bq\|^2 = \bx\trans A\bx + \bb\trans \bx + \frac{1}{4}\bb\trans A^{-1}\bb. \]

由於常數項不會影響函數值，我們知道目標式的最小值和 \(\|P\bx + \bq\|^2\) 的最小值發生在同一個地方，而後者的最小值只有在 \(P\bx = -\bq\) 時發生。因此目標式的最小值唯一發生在

\[ \bx = -P^{-1}\bq = -\frac{1}{2}A^{-1}\bb \]

時。

這樣的理論可用於解部份答案已知時的二次型的最小值。令

\[ L = \begin{bmatrix} A & B \\ B\trans & C \end{bmatrix} \]

為一對稱矩陣且 \(A\) 正定。考慮向量

\[ \bu = \begin{bmatrix} \bx \\ \by \end{bmatrix} \]

但其中 \(\by\) 為已知的部份。在這樣的情況下我們要如何求 \(\bu\trans L\bu\) 的最小值？

我們可以把目標式展開變成

\[ \bu\trans L\bu = \bx\trans A\bx + 2(B\by)\trans\bx + \by\trans C\by. \]

如此一來，基於前述的解法，我們就知道在這個情況下的最小值發生在 \(\bx = -A^{-1}B\by\) 的時候。

當 \(L\) 為圖 \(G\) 的拉普拉斯矩陣時，\(\bu\trans L\bu\) 為 \(G\) 所對應的彈簧系統的位能。所以這個問題可以解讀為：當 \(\by\) 的這些點的位置都給定時，\(\bx\) 的位置要如何調整才能讓位能最低？而這個讓最小值發生的 \(\bx\) 就是此彈簧系統最後穩定的位置。

想想以下問題：

  1. 利用正定矩陣特徵值全正的性質說明「\(A\) 是正定」和「存在正定矩陣 \(S\) 使得 \(A = S^2\)」兩敘述等價。
  2. 令
    \[ L = \begin{bmatrix} 1 & -1 & 0 & 0 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ 0 & 0 & -1 & 1 \end{bmatrix} \text{ and } \bu = \begin{bmatrix} 0 \\ x_1 \\ x_2 \\ 3 \end{bmatrix}. \]

    求 \(x_1, x_2\) 使得 \(\bu\trans L\bu\) 最小。