线性代数 Cheat Sheet 7-3：条件优化

Author: nex3z 2018-12-16

　　工程中常常需要寻找一些特定集合内的 $\boldsymbol x$ 值，使得二次型 $Q(\boldsymbol x)$ 取得最大值或最小值。具有代表性的是，这类问题可化为 $\boldsymbol x$ 在一组单位向量中的变量的优化问题。

　　$\mathbb{R}^n$ 中的一个单位向量 $\boldsymbol x$ 可用以下几种等价形式来描述：

$$\begin{equation} \lVert \boldsymbol x \rVert = 1, \; \lVert \boldsymbol x \rVert^2 = 1, \; \boldsymbol x^\mathsf{T} \boldsymbol x = 1 \end{equation}$$

和

$$\begin{equation} x_1^2 + x_2^2 + \cdots + x_n^2 = 1 \tag{1} \end{equation}$$

在应用中经常使用 $\boldsymbol x^\mathsf{T} \boldsymbol x = 1$ 的展开式 $(1)$。

　　当一个二次型没有交叉项乘积时，可以很容易得到在 $\boldsymbol x^\mathsf{T} \boldsymbol x = 1$ 下的最大值和最小值。

　　可以证明，对任何对称矩阵 $A$，在 $\lVert \boldsymbol x \rVert = 1$ 条件下，$\boldsymbol x^\mathsf{T} A \boldsymbol x$ 所有可能值的集合是闭区间。分别用 $m$ 和 $M$ 表示区间的左端点和右端点，即取

$$\begin{equation} m = \min\{\boldsymbol x^\mathsf{T} A \boldsymbol x: \lVert \boldsymbol x \rVert = 1\}, \; M = \max\{\boldsymbol x^\mathsf{T} A \boldsymbol x: \lVert \boldsymbol x \rVert = 1\} \tag{2} \end{equation}$$

　　如果 $\lambda$ 是一个特征值，那么 $m \leq \lambda \leq M$，$m$ 和 $M$ 本身也是特征值。

　　定理 6　设 $A$ 是对称矩阵，且 $m$ 和 $M$ 的定义如 $(2)$ 式所示，那么 $M$ 是 $A$ 的最大特征值 $\lambda_1$，$m$ 是 $A$ 的最小特征值。如果 $\boldsymbol x$ 是对应于 $M$ 的单位特征向量 $\boldsymbol u_1$，那么 $\boldsymbol x^\mathsf{T} A \boldsymbol x$ 的值等于 $M$。如果 $\boldsymbol x$ 是对应于 $m$ 的单位特征向量，那么 $\boldsymbol x^\mathsf{T} A \boldsymbol x$ 的值等于 $m$。

　　定理 7　设 $A, \lambda_1, \boldsymbol u_1$ 的定义如定理 6 所示。在如下限制条件下：

$$\begin{equation} \boldsymbol x^\mathsf{T} \boldsymbol x = 1, \; \boldsymbol x^\mathsf{T} \boldsymbol u_1 = 0 \end{equation}$$

$\boldsymbol x^\mathsf{T} A \boldsymbol x$ 的最大值是第二大特征值 $\lambda_2$，且这个最大值可以在 $\boldsymbol x$ 是对应于 $\lambda_2$ 的特征向量 $\boldsymbol u_2$ 处达到。

　　限制条件 $\boldsymbol x^\mathsf{T} \boldsymbol u_1 = 0$ 意味取到最大值的解 $\boldsymbol x$ 要与最大特征值对应的特征向量 $\boldsymbol u_1$ 正交。假设在 $\mathbb{R}^3$ 中，有 $\boldsymbol u_1 = (1, 0, 0)$，则为了满足此限制条件， $\boldsymbol x$ 的第一个元素要为 $0$，即 $x_1 = 0$。

　　定理 8　设 $A$ 是一个 $n \times n$ 的对称矩阵，其正交对角化为 $A = PDP^{-1}$，将对角矩阵 $D$ 上的元素重新排列，使得 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$，且 $P$ 的列是其对应的单位特征向量 $\boldsymbol u_1, \cdots, \boldsymbol u_n$，那么对 $k = 2, \cdots, n$，在以下限制条件下：

$$\begin{equation} \boldsymbol x^\mathsf{T} \boldsymbol x = 1, \; \boldsymbol x^\mathsf{T} \boldsymbol u_1 = 0, \; \cdots, \; \boldsymbol x^\mathsf{T} \boldsymbol u_{k-1} = 0 \end{equation}$$

$\boldsymbol x^\mathsf{T} A \boldsymbol x$ 的最大值是特征值 $\lambda_k$，且这个最大值在 $\boldsymbol x = \boldsymbol u_k$ 处可以达到。