答levinc417──關於約束二次型極值

網友levinc417留言:

\mathbf{a}^T\mathbf{b}\mathbb{R}^n 中標準內積,且 \Vert\mathbf{a}\Vert^2=\mathbf{a}^T\mathbf{a}S=\{\mathbf{a}\in\mathbb{R}^n\vert\Vert\mathbf{a}\Vert=1\}。令 An\times n 實方陣,且考慮 f(\mathbf{x})=\mathbf{x}^TA\mathbf{x}\mathbf{x}\in S。假設 \mathbf{a}\in S,存在一正數 \delta > 0,使得 f(\mathbf{a})\geq f(\mathbf{x}),對所有 \mathbf{x}\in S 滿足 \Vert\mathbf{x}-\mathbf{a}\Vert < \delta。那麼我們可以說:f(\mathbf{a})\geq f(\mathbf{x}) 對所有 \mathbf{x}\in S 成立嗎? Prove or disprove it.

找到一個反例:

A=\begin{bmatrix}  1 & 0 & 0\\  0 & 0 & 0\\  0& 0 & 0  \end{bmatrix}

\mathbf{x}=\begin{bmatrix}  1\\  0\\  0  \end{bmatrix},~\mathbf{a}=\begin{bmatrix}  1/\sqrt{3}\\  \sqrt{2}/\sqrt{3}\\  0\end{bmatrix}

這樣可以嗎? 有誤解題目意思嗎?

 
答曰:

先將給出的數值代入計算 f,得到

\begin{aligned}  f(\mathbf{x})&=\mathbf{x}^TA\mathbf{x}=1\\  f(\mathbf{a})&=\mathbf{a}^TA\mathbf{a}=\frac{1}{3},  \end{aligned}

這與命題前提 f(\mathbf{a})\ge f(\mathbf{x}) 不符。如果將 \mathbf{x}\mathbf{a} 調換,即 \mathbf{a}=\begin{bmatrix}  1\\  0\\  0  \end{bmatrix}\mathbf{x}=\begin{bmatrix}  1/\sqrt{3}\\  \sqrt{2}/\sqrt{3}\\  0  \end{bmatrix},就有 f(\mathbf{a})\ge f(\mathbf{x})。事實上,此例不論我們如何選擇 \mathbf{x}\in S,上述不等式皆成立。但是這僅為原命題成立的一個特殊案例,若方陣 A 改變,此性質依然成立嗎?下面我用特徵分析方法證明原命題確實為真。

 
實函數 f(\mathbf{x})=\mathbf{x}^TA\mathbf{x} 稱作二次型 (quadratic form),對角化 A 是最常使用的分析技巧,然而 A 為任意實矩陣,故未必可對角化,那該怎麼辦?關鍵在於二次型具備的獨特形式。任何方陣 A 可分解為對稱矩陣與反對稱 (anti-symmetric) 矩陣之和,A=B+C,其中

\begin{aligned}  B&=\displaystyle\frac{1}{2}\left(A+A^T\right)\\  C&=\frac{1}{2}\left(A-A^T\right).  \end{aligned}

明顯地,B^T=BC^T=-C。考慮

\begin{aligned}  f(\mathbf{x})&=\mathbf{x}^TA\mathbf{x}=\mathbf{x}^T(B+C)\mathbf{x}\\  &=\mathbf{x}^TB\mathbf{x}+\mathbf{x}^TC\mathbf{x},  \end{aligned}

利用反對稱矩陣性質及 \mathbf{x}^T\mathbf{y}=\mathbf{y}^T\mathbf{x} 計算右項,

\begin{aligned}  \mathbf{x}^TC\mathbf{x}&=(C^T\mathbf{x})^T\mathbf{x}=(-C\mathbf{x})^T\mathbf{x}\\  &=-(C\mathbf{x})^T\mathbf{x}=-\mathbf{x}^T(C\mathbf{x})\\  &=-\mathbf{x}^TC\mathbf{x},  \end{aligned}

也就是說,任意 \mathbf{x} 皆使 \mathbf{x}^TC\mathbf{x}=0。因此,f(\mathbf{x})=\mathbf{x}^TB\mathbf{x},二次型的實矩陣 A 可替換為其對稱部分 B。實對稱矩陣具備兩個美好的性質:所有特徵值皆為實數,並可選擇一組單範正交 (orthonormal) 特徵向量。為方便討論,將實對稱矩陣 B 的特徵值按遞減排序:\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n。以下考慮簡化後的等價問題:

Bn\times n 實對稱矩陣,考慮 f(\mathbf{x})=\mathbf{x}^TB\mathbf{x}\mathbf{x}\in S。假設 \mathbf{a}\in S,存在一正數 \delta > 0,使得 f(\mathbf{a})\geq f(\mathbf{x}),對所有 \mathbf{x}\in S 滿足 \Vert\mathbf{x}-\mathbf{a}\Vert < \delta。那麼我們可以說:f(\mathbf{a})\geq f(\mathbf{x}) 對所有 \mathbf{x}\in S 成立嗎?

 
換個較為白話的說法:如果 f(\mathbf{a}) 是局部極大值 (local maximum),那麼它也是全域極大值 (global maximum)?顯然,局部極大值未必是全域極大值,除非所有的局部極大值亦為全域極大值。我們用約束最佳化來回答這個問題。考慮這個問題

\displaystyle  \begin{array}{ll}  \hbox{maximize}&\mathbf{x}^TB\mathbf{x}\\  \hbox{subject to}&\mathbf{x}^T\mathbf{x}=1.  \end{array}

寫出 Lagrangian 函數

\displaystyle  L(\mathbf{x},\alpha)=\mathbf{x}^TB\mathbf{x}-\alpha(\mathbf{x}^T\mathbf{x}-1)

其中 \alpha 稱為 Lagrange 乘數。求 L 的偏導數,

\displaystyle\frac{\partial L}{\partial\mathbf{x}}=2B\mathbf{x}-2\alpha\mathbf{x}

極值發生於 \partial L/\partial\mathbf{x}=\mathbf{0},即 B\mathbf{x}=\alpha\mathbf{x}\alphaB 的特徵值。又因為 \Vert\mathbf{x}\Vert=1L=\mathbf{x}^T(B\mathbf{x})=\mathbf{x}^T(\alpha\mathbf{x})=\alpha。明顯地,欲使 L 最大化,我們理當選擇最大特徵值 \alpha=\lambda_1,也就是說,符合命題前提的 \mathbf{a} 即是對應 \lambda_1 的單位特徵向量。在此情況下,對任意 \mathbf{x}\in S,定有 f(\mathbf{a})\ge f(\mathbf{x})

 
讀者或許懷疑:如果令 \mathbf{a} 為其他向量,譬如對應第二特徵值 \lambda_2 的單位特徵向量,能否滿足命題前提,即存在一正數 \delta > 0,使得 f(\mathbf{a})\geq f(\mathbf{x}),對所有 \mathbf{x}\in S 滿足 \Vert\mathbf{x}-\mathbf{a}\Vert < \delta?倘若此條件成立,那不就推翻了命題?這個問題不難回答。令 \mathbf{q}_i 代表對應特徵值 \lambda_i 的特徵向量,且 \{\mathbf{q}_1,\ldots,\mathbf{q}_n\} 是一個單範正交向量集,即 \mathbf{q}_i^T\mathbf{q}_j=1i=j\mathbf{q}_i^T\mathbf{q}_j=0i\neq j。考慮 \mathbf{a}=\mathbf{q}_2,則 f(\mathbf{a})=\mathbf{q}_2^TB\mathbf{q}_2=\mathbf{q}_2^T(\lambda_2\mathbf{q}_2)=\lambda_2。設 \mathbf{x}=c_1\mathbf{q}_1+c_2\mathbf{q}_2,其中 c_1^2+c_2^2=1 以使 \Vert\mathbf{x}\Vert=1,且 c_1^2+(c_2-1)^2<\delta^2 使得 \Vert\mathbf{x}-\mathbf{a}\Vert<\delta。但是

\begin{aligned}  f(\mathbf{x})=\mathbf{x}^TB\mathbf{x}&=(c_1\mathbf{q}_1+c_2\mathbf{q}_2)^TB(c_1\mathbf{q}_1+c_2\mathbf{q}_2)\\  &=(c_1\mathbf{q}_1+c_2\mathbf{q}_2)^T(\lambda_1c_1\mathbf{q}_1+\lambda_2c_2\mathbf{q}_2)\\   &=\lambda_1c_1^2+\lambda_2c_2^2\\  &\ge\lambda_2(c_1^2+c_2^2)=\lambda_2=f(\mathbf{a}),  \end{aligned}

這說明對應第二特徵值的特徵向量不滿足前提條件(除非 \lambda_1=\lambda_2),運用同樣推理方式可推論唯有對應最大特徵值 \lambda_1 的單位特徵向量才符合命題要求,故局部極大值即為全域極大值。

Advertisements
本篇發表於 答讀者問, 二次型 並標籤為 , 。將永久鏈結加入書籤。

2 則回應給 答levinc417──關於約束二次型極值

  1. levinc417 說道:

    謝謝老師的提醐灌頂! 所以說在 S 的設定下,局部最大值就可以說(若且唯若)是全域最大值囉?換個方式問,受限制的二次式型式是不是就能隱含了「局部最大即全域最大」?

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s