807补充（六）（拉格朗日乘子篇）.md

807补充（六）（拉格朗日乘子篇）

一.解的存在性

在上一篇中，我们用拉格朗日乘子法求得了以下优化问题的解 $$ \begin{aligned} &\text{maxmize} \ \ \ \ \text{tr}(\boldsymbol W^T(\boldsymbol S_w+\boldsymbol S_b)\boldsymbol W)\ &s.t \ \ \ \ \ \ \ \ \ \ \ \ \ \boldsymbol W^T\boldsymbol S_w \boldsymbol W=\boldsymbol I \end{aligned} $$ 其解为$\boldsymbol {W}=\boldsymbol {\hat W}\boldsymbol Q$,且必须满足以下条件 $$ \boldsymbol{\hat W}由\boldsymbol S_w^{-1}\boldsymbol S_b特征向量组成\ \boldsymbol Q\boldsymbol Q^T=\boldsymbol I\ \boldsymbol{\hat W}^T\boldsymbol S_W\boldsymbol {\hat W}=\boldsymbol I $$ 为此我们有必要分析一下得出的解是否存在，即是否能找到彼此关于矩阵$\boldsymbol S_w$正交的特征向量，或者讨论当$\boldsymbol S_w$与$\boldsymbol S_b$满足什么条件时有解。

$\boldsymbol {\hat W}=[\boldsymbol {\hat w_1},\boldsymbol {\hat w_2},\cdots,\boldsymbol {\hat w_d}]$,其中$\boldsymbol {\hat w_i}$是按特征值从大到小的特征向量。

求解问题可转化为求以下问题是否有解 $$ \forall i,j\ \ \ \ \ \ \ \boldsymbol S_w^{-1}\boldsymbol S_b\boldsymbol {\hat w_i}=\lambda_j \boldsymbol {\hat w_i},且满足\ \boldsymbol {\hat w_i}^T\boldsymbol S_w\boldsymbol {\hat w_j}=\begin{cases} 1,&\qquad i=j\ 0,&\qquad i\neq j \end{cases} $$ 为将问题推广至一般情况，记$\boldsymbol B\overset{\text{def}}{=}\boldsymbol S_w^{-1}\boldsymbol S_b,\boldsymbol A\overset{\text{def}}{=}\boldsymbol S_w$。问题可写为 $$ \forall i,j\ \ \ \ \ \ \ \boldsymbol B\boldsymbol {\hat w_i}=\lambda_j \boldsymbol {\hat w_i},且满足\ \boldsymbol {\hat w_i}^T\boldsymbol A\boldsymbol {\hat w_j}=\begin{cases} 1,&\qquad i=j\ 0,&\qquad i\neq j \end{cases} $$

二.相同特征值的情况（充分性）

首先让我们考虑一下特征值相同时解的情况 $$ \forall i,j\ \ \ \ \ \ \ \boldsymbol B\boldsymbol {\hat w_i}=\lambda \boldsymbol {\hat w_i},且满足\ \boldsymbol {\hat w_i}^T\boldsymbol A\boldsymbol {\hat w_j}=\begin{cases} 1,&\qquad i=j\ 0,&\qquad i\neq j \end{cases} $$ 如果存在一组向量满足以上条件，那$\boldsymbol A$应当满足什么条件？

假设寻到向量组 $\boldsymbol {\hat w_1} ， \cdots \boldsymbol {\hat w_s}$ 使 $\boldsymbol {\hat w_i}^T A \boldsymbol {\hat w_j}=\delta_{i j}, s=\operatorname{dim} W$,则$\boldsymbol {\hat w_1} ， \cdots \boldsymbol {\hat w_s}$线性无关，故为一组基。 $$ \begin{aligned} & \text { 设 } \forall x \in W \text {, 则 } \exists k_1, \cdots k_s, x=k_1 \boldsymbol {\hat w_1}+\cdots+k_s \boldsymbol {\hat w_s}=\left[\boldsymbol {\hat w_1}, \cdots \boldsymbol {\hat w_s}\right]\left[\begin{array}{c} k_1 \ \vdots \ k_s \end{array}\right] \ & \text { 故 } x^{\top} A x=\left(\begin{array}{c} k_1 \ \vdots \ k_3 \end{array}\right)^{\top}\left(\begin{array}{c} \boldsymbol {\hat w_1}^{\top} \ \vdots \ \boldsymbol {\hat w_s}^{\top} \end{array}\right) A \left(\boldsymbol {\hat w_1} \cdots \boldsymbol {\hat w_s}\right)\left(\begin{array}{c} k_1 \ \vdots \ k_3 \end{array}\right) \ & =\left(\begin{array}{c} k_1 \ \vdots \ k_s \end{array}\right)^{\top} I_s\left(\begin{array}{c} k_1 \ \vdots \ k_s \end{array}\right)=k_1^2+\cdots+k_s^2 \geqslant 0 \text {, 且 } x^{\top} A x=0 \Leftrightarrow k_1=\cdots=k_s=0 \Leftrightarrow x=0 \ & \end{aligned} $$

故$\boldsymbol A$必为正定矩阵。

三.相同特征值的情况（必要性）

如果当$\boldsymbol A$为正定矩阵时，又如何求出合适的特征向量？

对$\boldsymbol A$进行矩阵分解$\boldsymbol A =\boldsymbol S^T\boldsymbol S$,$\boldsymbol {\hat w_i}^T A \boldsymbol {\hat w_j}=\boldsymbol {\hat w_i}^T \boldsymbol S^T\boldsymbol S \boldsymbol {\hat w_j}=(\boldsymbol S \boldsymbol w_i)^T(\boldsymbol S \boldsymbol w_j)$

即基$\boldsymbol S \boldsymbol w_i$ 彼此之间是正交的，可用史密斯正交化求出一组正交基$\boldsymbol S \boldsymbol w_i$,再求出$\boldsymbol w_i$

或者考虑以下问题 $$ \begin{aligned} \beta_1 & =\alpha_1 \ \beta_2 & =\alpha_2-k_{21} \beta_1 \ \beta_3 & =\alpha_3-k_{31} \beta_1-k_{32} \beta_2 \ & \vdots \ \beta_s & =\alpha_s-k_{s1} \beta_1-\cdots-k_{s(s-1)} \beta_{s-1} \end{aligned} $$ (1) $\beta_1^{\top} A \beta_2=0 \Rightarrow \beta_1^{\top} A \alpha_2-k_{21} \beta_1^{\top} A \beta_1=0 \Rightarrow k_{21}=\frac{\beta_1^{\top} A \alpha_2}{\beta_1^{\top} A \beta_1}$

(2) $$ \begin{gathered} \beta_1^{\top} A \beta_3=0 \Rightarrow \beta_1^{\top} A \alpha_3-k_3 \beta_1^{\top} A \beta_1=0 \Rightarrow k_{31}=\frac{\beta_1^{\top} A \alpha_3}{\beta_1^{\top} A \beta_1} \ \beta_2^{\top} A \beta_3=0 \Rightarrow \beta_2^{\top} A \alpha_3-k_{32} \beta_2^{\top} A \beta_2=0 \Rightarrow k_{32}=\frac{\beta_1^{\top} A \alpha_3}{\beta_2^{\top} A \beta_2} \ \end{gathered} $$ ​ $\vdots$

​ $\vdots$

(s) $$ \begin{aligned} & \beta_1^{\top} A \beta_s=0 \Rightarrow \beta_1^{\top} A \alpha_s-k_{s 1} \beta_1^{\top} A \beta_1=0 \Rightarrow k_{s 1}=\frac{\beta_1^{\top} A \alpha_s}{\beta_1^{\top} A \beta_1} \ & \beta_{s-1}^{\top} A \beta_s=0 \Rightarrow \beta_{s-1}^{\top} A \alpha_s-k_{s(s-1)} \beta_{s-1}^{\top} A \beta_{s-1} \Rightarrow k_{s(s-1)}=\frac{\beta_{s-1}^{\top} A \alpha_s}{\beta_{s-1}^{\top} A \beta_{s-1}} \end{aligned} $$ 当$\boldsymbol A$为正定矩阵时,必可求出一组关于$\boldsymbol A$正交的基。

四.不同特征值的情况

如果在每一特征值形成的特征子空间都求出一组关于$\boldsymbol A$正交的基，对于最开始的问题仅需继续证明两两不同的特征值的特征向量彼此关于$\boldsymbol A$正交。

设$\boldsymbol x,\boldsymbol y$是$\boldsymbol B$不同特征值对应的特征向量,当$(\boldsymbol A \boldsymbol B)^T=\boldsymbol A \boldsymbol B$时可以确定$\boldsymbol x^{\top} \boldsymbol A \boldsymbol y=0$ $$ \begin{gathered} \left(\boldsymbol x^{\top} \boldsymbol A \boldsymbol B \boldsymbol y\right)^{\top}=\boldsymbol y^{\top} \boldsymbol B^{\top} \boldsymbol A^{\top} \boldsymbol x \ \Downarrow \ \boldsymbol x^{\top} \boldsymbol A \boldsymbol B \boldsymbol y=y^{\top} \boldsymbol A \boldsymbol B \boldsymbol x \ \Rightarrow \lambda_1 \boldsymbol x^{\top} \boldsymbol A \boldsymbol y=\lambda_2 \boldsymbol y^{\top} \boldsymbol A \boldsymbol x \ \Rightarrow \boldsymbol x^{\top} \boldsymbol A \boldsymbol y=0 \end{gathered} $$ 若$(\boldsymbol A \boldsymbol B)^T\neq\boldsymbol A \boldsymbol B$,则不同特征值之间的特征向量未必关于$\boldsymbol A$正交，即解不一定存在。

五.结论

当$\boldsymbol A\succ 0$时且$(\boldsymbol A \boldsymbol B)^T=\boldsymbol A \boldsymbol B$时必定有解，且$\boldsymbol A\succ0$是有解的必要条件。

又因$\boldsymbol B=\boldsymbol S_w^{-1}\boldsymbol S_b,\boldsymbol A=\boldsymbol S_w$,其中$\boldsymbol S_b$是是实对称矩阵，$\boldsymbol S_w$通常情况下是正定的，因此解必存在。