约束优化

二次型通过特征值分析在单位向量约束下确定极值，正交约束逐层降维以依次提取各主方向的最优解，为高维优化问题提供理论框架。

1. 约束优化问题引入

约束优化（ $\text{constrained optimization}$ ）源于实际问题中需要在有限资源或条件下寻找最优解的需求，例如工程设计中的成本最小化或经济学中的收益最大化。它解决的是如何在满足给定约束条件的情况下优化目标函数的问题。在许多应用中，这类问题常表现为在特定集合上求解二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 的最大值和最小值。最常见的约束向量集合为单位向量约束，即向量的范数为 $~1~$ 。单位向量约束有以下几种等价形式：

\|\mathbf{x}\| = 1,\quad \|\mathbf{x}\|^2 = 1,\quad \mathbf{x}^T\mathbf{x} = 1,\quad x_1^2 + x_2^2 + \cdots + x_n^2 = 1

单位向量约束将向量限制在单位球面上，即在 $~\mathbb{R^n}~$ 空间中满足 $~x_1^2 + x_2^2 + \cdots + x_n^2 = 1~$ 的所有点的集合。这种约束不仅便于几何理解，还能将优化问题转化为特征值问题，从而求解目标函数的最大值或最小值。

2. 无交叉项二次型的极值求解

例 $~1~$ ：在单位向量约束 $~\mathbf{x}^T\mathbf{x} = 1~$ 下，求二次型 $~Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2~$ 的最大值和最小值。

二次型的结构 ：二次型 $~Q(x)=9x_1^2 + 4x_2^2 + 3x_3^2~$ 是一个无交叉项的二次型，其矩阵为对角矩阵：
$\mathbf{A} = \begin{bmatrix} 9 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 3 \end{bmatrix}$
确定最大值 ：由于 $~x_1^2 + x_2^2 + x_3^2 = 1~$ ，且 $~x_2^2~$ 和 $~x_3^2~$ 非负，可以推导：
$\begin{align*}Q(x) &= 9x_1^2 + 4x_2^2 + 3x_3^2 \\[2ex] &\leq 9x_1^2 + 9x_2^2 + 9x_3^2 \\[2ex] &= 9(x_1^2 + x_2^2 + x_3^2) \\[2ex] &= 9\end{align*}$
当 $\mathbf{x}=\begin{bmatrix}1 & 0 & 0\end{bmatrix}^T~$ 或 $~\mathbf{x}=\begin{bmatrix}-1 & 0 & 0\end{bmatrix}^T$ 时，最大值为 $~Q(x) = 9~$ 。
确定最小值 ：类似地，可以推导：
$\begin{align*}Q(x) &= 9x_1^2 + 4x_2^2 + 3x_3^2 \\[2ex] &\geq 3x_1^2 + 3x_2^2 + 3x_3^2 \\[2ex] &= 3(x_1^2 + x_2^2 + x_3^2) \\[2ex] &= 3\end{align*}$
当 $\mathbf{x}=\begin{bmatrix}0 & 0 & 1\end{bmatrix}^T~$ 或 $~\mathbf{x}=\begin{bmatrix}0 & 0 & -1\end{bmatrix}^T~$ 时，最小值为 $~Q(x) = 3~$ 。

从几何角度来看，二次型 $~Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2~$ 描述了一个椭球面集合。在单位球面 $~x_1^2 + x_2^2 + x_3^2 = 1~$ 的约束下， $~Q(x)~$ 的最小值和最大值分别对应于椭球面与单位球面的内切和外切时在切点处的位置。如下所示：

例 $~2~$ ：二次型 $~Q(\mathbf{x}) = \mathbf{x}^T\mathbf{A}\mathbf{x}=3x_1^2 + 7x_2^2~$ ，其中：

~\mathbf{A} = \begin{bmatrix}3 & 0 \\ 0 & 7\end{bmatrix}~

$\mathbf{x}~$ 是 $~\mathbb{R^2}~$ 中的向量。求 $~Q(x)~$ 在单位向量约束 $~\mathbf{x}^T\mathbf{x} = 1~$ （即 $x_1^2 + x_2^2 = 1$ ）下的最大值和最小值。

确定最大值 ：由于 $~x_1^2 + x_2^2 = 1~$ ，且 $~x_1^2~$ 和 $~x_2^2~$ 非负，可以推导：
$\begin{align*}Q(x) &= 3x_1^2 + 7x_2^2 \\[2ex] &\leq 7x_1^2 + 7x_2^2 \\[2ex] &= 7(x_1^2 + x_2^2) \\[2ex] &= 7\end{align*}$
当 $\mathbf{x}=\begin{bmatrix}0 & 1\end{bmatrix}^T~$ 或 $~\mathbf{x}=\begin{bmatrix}0 & -1\end{bmatrix}^T$ 时，最大值为 $~Q(x) = 7~$ 。
确定最小值 ：由于 $~x_1^2 + x_2^2 = 1~$ ，且 $~x_1^2~$ 和 $~x_2^2~$ 非负，可以推导：
$\begin{align*}Q(x) &= 3x_1^2 + 7x_2^2 \\[2ex] &\geq 3x_1^2 + 3x_2^2 \\[2ex] &= 3(x_1^2 + x_2^2) \\[2ex] &= 3\end{align*}$
当 $\mathbf{x}=\begin{bmatrix}1 & 0\end{bmatrix}^T~$ 或 $~\mathbf{x}=\begin{bmatrix}-1 & 0\end{bmatrix}^T$ 时，最小值为 $~Q(x) = 3~$ 。

从几何角度来看，二次型 $~Q(x) = 3x_1^2 + 7x_2^2~$ 在三维空间中表示沿 $~z-$ 轴正方向延伸的椭圆抛物面，约束条件 $~x_1^2 + x_2^2 = 1~$ 在三维空间中是一个沿 $~z-$ 轴正负方向延伸的无限高圆柱体，两者的交线就是圆柱体与抛物面的交集，这个交线上的点的 $~z~$ 值就是 $~Q(x)~$ 在单位圆上的取值，极值点是此曲线的最高点和最低点。如下所示：

3. 特征值与极值的关系

在前面的两个示例中，对称矩阵的特征值直接决定了二次型在单位向量约束下的极值，而极值点恰为对应的特征向量。这两个结论不仅适用于对角矩阵（无交叉项），还可以推广到任意对称矩阵，有如下定理：

定理 6

对称矩阵的特征值与二次型极值

对于对称矩阵 $~\mathbf{A}~$ ，定义 $~m~$ 和 $~M~$ 如下：

m = \min \{ \mathbf{x}^T A \mathbf{x} : \|\mathbf{x}\| = 1 \}, \quad M = \max \{ \mathbf{x}^T A \mathbf{x} : \|\mathbf{x}\| = 1 \}

则 $~M~$ 是 $~\mathbf{A}~$ 的最大特征值 $~\lambda_1~$ ，而 $~m~$ 是 $~\mathbf{A}~$ 的最小特征值。当 $~\mathbf{x}~$ 是对应于 $~M~$ 的单位特征向量时， $\mathbf{x}^T\mathbf{A}\mathbf{x} = M$ ；当 $~\mathbf{x}~$ 是 $~m~$ 对应的单位特征向量时， $\mathbf{x}^T\mathbf{A}\mathbf{x} = m$ 。

正交对角化矩阵

将对称矩阵 $~\mathbf{A}~$ 正交化为 $~\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}~$ ，其中：
- $\mathbf{P}~$ 是正交矩阵（列向量为 $~\mathbf{A}~$ 的单位正交特征向量 $~(\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3)~$ 。
- $\mathbf{D}~$ 是对角矩阵，对角线元素为 $~\mathbf{A}~$ 的特征值 $~a \geq b \geq c~$ 。
变量替换与二次型转换

令 $~\mathbf{x} = \mathbf{P}\mathbf{y}~$ ，则二次型可转换为：
$\mathbf{x}^T \mathbf{A} \mathbf{x} = \mathbf{y}^T \mathbf{D} \mathbf{y} = a\mathbf{y}_1^2 + b\mathbf{y}_2^2 + c\mathbf{y}_3^2$
由于 $~\mathbf{P}~$ 是正交矩阵，有 $~\|\mathbf{x}\| = \|\mathbf{P}\mathbf{y}\| = \|\mathbf{y}\|~$ ，因此 $~\|\mathbf{x}\|=1~$ 当且仅当 $~\|\mathbf{y}\| = 1$ 。
推导最大值 $~M~$

对任意单位向量 $~\mathbf{y} = \begin{bmatrix}y_1 & y_2 & y_3\end{bmatrix}^T~$ ，利用特征值排序 $~a \geq b \geq c~$ ：
$\begin{align*} \mathbf{y}^T \mathbf{D} \mathbf{y} &= a \mathbf{y}_1^2 + b \mathbf{y}_2^2 + c \mathbf{y}_3^2 \\[2ex] &\leq a \mathbf{y}_1^2 + a \mathbf{y}_2^2 + a \mathbf{y}_3^2 \\[2ex] &= a(\mathbf{y}_1^2 + \mathbf{y}_2^2 + \mathbf{y}_3^2) \\[2ex] &= a \end{align*}$
当 $\mathbf{y} = \mathbf{e}_1 = \begin{bmatrix}1 & 0 & 0 \end{bmatrix}^T$ 时， $\mathbf{y}^T\mathbf{D}\mathbf{y} = a$ 对应 $~\mathbf{x} = \mathbf{P}\mathbf{e}_1 = \mathbf{u}_1~$ ，即：
$M = a = \mathbf{u}_1^T\mathbf{A}\mathbf{u}_1$
推导最小值 $~m~$

类似地，利用 $~a \leq b \leq c~$ ：
$\begin{align*} \mathbf{y}^T \mathbf{D} \mathbf{y} &= a \mathbf{y}_1^2 + b \mathbf{y}_2^2 + c \mathbf{y}_3^2 \\[2ex] &\geq c \mathbf{y}_1^2 + c \mathbf{y}_2^2 + c \mathbf{y}_3^2 \\[2ex] &= c(\mathbf{y}_1^2 + \mathbf{y}_2^2 + \mathbf{y}_3^2) \\[2ex] &= c \end{align*}$
当 $\mathbf{y} = \mathbf{e}_3 = \begin{bmatrix}0 & 0 & 1\end{bmatrix}^T$ 时， $\mathbf{y}^T\mathbf{D}\mathbf{y} = c$ 对应 $~\mathbf{x} = \mathbf{P}\mathbf{e}_3 = \mathbf{u}_3~$ ，即：
$M = c = \mathbf{u}_1^T\mathbf{A}\mathbf{u}_3$
结论
- $M = a~$ 是最大特征值，在 $~\mathbf{x} = \mathbf{u}_1~$ 时取得。
- $m = c~$ 是最小特征值，在 $~\mathbf{x} = \mathbf{u}_3~$ 时取得。

例 $~3~$ ：给定一个对称但非对角的矩阵 $~\mathbf{A}~$ ：

\mathbf{A} = \begin{bmatrix} 3 & 2 & 1 \\ 2 & 3 & 1 \\ 1 & 1 & 4 \end{bmatrix}

要求找到二次型 $~Q(\mathbf{x}) = \mathbf{x}^T\mathbf{A}\mathbf{x}~$ 在单位球面 $~\mathbf{x}^T\mathbf{x} = 1~$ 上的最大值，并确定达到此最大值的单位向量。

求解特征方程 ：
$\begin{align*} &\det(\mathbf{A} - \lambda \mathbf{I}) = 0 \\[2ex] \Rightarrow \quad &-\lambda^3 + 10\lambda^2 - 27\lambda + 18 = 0 \\[2ex] \Rightarrow \quad &-(\lambda - 6)(\lambda -3)(\lambda - 1) = 0 \\[2ex] \Rightarrow \quad &\lambda_1 = 6, \quad \lambda_2 = 3, \quad \lambda_3 = 1 \end{align*}$
求解对应特征向量并单位化 。 $\mathbf{A}~$ 最大特征值为 $~6~$ ，解方程 $~(\mathbf{A} - 6\mathbf{I})\mathbf{x} = 0~$ 得：
$\mathbf{v} = \begin{bmatrix}1 \\ 1 \\ 1\end{bmatrix}$
单位化：
$\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{3} \\ 1/\sqrt{3}\\ 1/\sqrt{3}\end{bmatrix}$
结论
- 由定理 $~6~$ 可知，二次型在单位球面约束 $~\|\mathbf{x}\| = 1~$ 下的最大值为 $~6~$ ，取得最大值的单位向量 $~\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{3} & 1/\sqrt{3} & 1/\sqrt{3} \end{bmatrix}^T~$ 。

从几何角度来看，二次型 $~Q(x) = 3x_1^2 + 3x_2^2 + 4x_3^2 + 4x_1x_2 + 2x_1x_3 + 2x_2x_3~$ 描述了一个倾斜的椭球面集合。在单位球面 $~x_1^2 + x_2^2 + x_3^2 = 1~$ 的约束下， $Q(x)~$ 的最大值对应于椭球面与单位球面的外切时在切点处的位置。如下所示：

4. 附加正交约束下的优化

在优化问题中，若仅依赖单一约束（如定理 $~6~$ 中 $~\mathbf{x}^T\mathbf{x} = 1~$ ），这种解仅反映单一方向的信息，无法揭示矩阵的其他特征。例如，在分析多维数据时，若仅关注最大方差方向，可能忽略次要但独立的结构信息；定理 $~7~$ 引入正交约束 $~\mathbf{x}^T\mathbf{u}_1 = 0~$ ，将优化问题限制在与 $~\mathbf{u}_1~$ 垂直的子空间中：

定理 7

正交约束下二次型的第二大特征值

设 $~\mathbf{A}~$ 为对称矩阵，其最大特征值为 $~\lambda_1~$ ，对应的单位特征向量为 $~\mathbf{u}_1~$ 。则在以下约束条件

\mathbf{x}^T\mathbf{x} = 1,\quad \mathbf{x}^T\mathbf{u}_1 = 0

下，二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 的最大值为第二大特征值 $~\lambda_2~$ ，且当 $~\mathbf{x}~$ 为对应于 $~\lambda_2~$ 的单位特征向量 $~\mathbf{u}_2~$ 时，达到次最大值。

例 $~4~$ ：求二次型 $~Q(x) = 9x_1^2 + 4x_2^2 + 3x_3^2~$ 在约束条件 $~\mathbf{x}^T\mathbf{x} = 1,~\mathbf{x}^T\mathbf{u}_1 = 0~$ 下的最大值。

简化约束条件
- $\mathbf{x}^T\mathbf{x} = 1$ 。对应 $x_1^2 + x_2^2 + x_3^2 = 1$ 。
- $\mathbf{x}^T\mathbf{u}_1 = 0$ 。计算内积得：
  $\mathbf{x}^T\mathbf{u}_1 = x_1\cdot 1 + x_2\cdot 0 + x_3 \cdot 0 = x_1 = 0$
综合上面两个约束条件为： $~x_2^2 + x_3^2 = 1~$ 。
代入约束计算目标函数

代入 $~x_1 = 0~$ 到 $~Q(x)~$ ：
$Q(x) = 9\cdot 0^2 + 4x_2^2 + 3x_3^2 = 4x_2^2 + 3x_3^2$
问题转化成了在约束条件 $x_2^2 + x_3^2 = 1$ 下，求 $~Q(x) = 4x_2^2 + 3x_3^2~$ 的最大值。
评估最大值 $~M~$
$\begin{align*}Q(x) &= 4x_2^2 + 3x_3^2 \\[2ex] &\leq 4x_2^2 + 4x_3^2\\[2ex] &=4(x_2^2 + x_3^2)\\[2ex] & = 4 \end{align*}$
取得最大值的条件是 $~x_1 = 0, ~ x_2 = 1, ~ x_3 = 0~$ ， $\mathbf{x}~$ 取值为 $~\lambda_2~$ 对应的单位特征向量 $~\mathbf{u}_2 = \begin{bmatrix}0 & 1 & 0\end{bmatrix}^T~$ 。
结论
- $M = \lambda_2 = 4~$ 是最大特征值，在 $~\mathbf{x} = \mathbf{u}_2 = \begin{bmatrix}0 & 1 & 0\end{bmatrix}^T~$ 时取得。

对例 $~4~$ 的求解过程适用于任意二次型，从而可以证明定理 $~7~$ 的正确性。从几何角度来理解，在由 $~x_2^2 + x_3^2 = 1~$ 表示的平面的约束下（此平面与 $~\mathbf{u}_1~$ 正交）， $\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 的最大值由第二大特征值 $~\lambda_2~$ 决定，方向为 $~\lambda_2~$ 对应的单位特征向量 $~\mathbf{u}_2~$ 。如下所示：

例 $~5~$ ：设矩阵 $~\mathbf{A} = \begin{bmatrix}3 & 2 & 1 \\ 2 & 3 & 1 \\ 1 & 1 & 4\end{bmatrix}~$ ，且 $~\mathbf{u}_1~$ 是 $~\mathbf{A}~$ 对应最大特征值的单位特征向量。求二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 在约束条件：

\mathbf{x}^T\mathbf{x} = 1,\quad \text{且} \quad \mathbf{x}^T\mathbf{u}_1 = 0

下的最大值，并找到使得最大值成立的单位向量 $~\mathbf{x}~$ 。

求解特征方程 ：
$\begin{align*} &\det(\mathbf{A} - \lambda \mathbf{I}) = 0 \\[2ex] \Rightarrow \quad &-\lambda^3 + 10\lambda^2 - 27\lambda + 18 = 0 \\[2ex] \Rightarrow \quad &-(\lambda - 6)(\lambda -3)(\lambda - 1) = 0 \\[2ex] \Rightarrow \quad &\lambda_1 = 6, \quad \lambda_2 = 3, \quad \lambda_3 = 1 \end{align*}$
第二大特征值为： $~\lambda=3~$
解方程 $~(\mathbf{A} - 3\mathbf{I})\mathbf{x} = 0~$ ：
$\mathbf{A} - 3\mathbf{I} = \begin{bmatrix} 0 & 2 & 1 \\ 2 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 1/2 \\ 0 & 1 & 1/2 \\ 0 & 0 & 0 \end{bmatrix}$
得基础解 $~\mathbf{v} = \begin{bmatrix}1 & 1 & -2\end{bmatrix}^T~$ ，向量模长 $~\|\mathbf{v}\| = \sqrt{1^2 + 1^2 + (-2)^2} = \sqrt{6}~$ ，单位化后得：
$\mathbf{u}_2 = \begin{bmatrix}1/\sqrt{6} \\ 1/\sqrt{6} \\ -2/\sqrt{6}\end{bmatrix}$
结论：根据定理 $~7~$ 可知，二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 的在单位向量以及正交约束（ $\text{与}~\mathbf{u}_1~$ ）下的最大值为 $~\lambda_2 = 3~$ ，对应的单位向量为 $~\mathbf{u}_2 = \begin{bmatrix}1/\sqrt{6} & 1/\sqrt{6} & -2/\sqrt{6}\end{bmatrix}^T~$ 。

从几何角度来理解，二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 对应的几何图形是一个椭球，其特征值决定各主轴长度（半轴长为 $~1/\sqrt{\lambda_i}~$ ）。约束条件 $~\mathbf{x}^T\mathbf{x} = 1~$ 定义了三维单位球面，而正交约束 $~\mathbf{x}^T\mathbf{u}_1 = 0~$ 进一步将解空间限制在该球面与约束平面 $~x_1 + x_2 + x_3 = 0~$ 的交集上（一个单位圆）。如下所示：

定理 $~7~$ 指出，二次型在正交约束下的最大值由第二大特征值决定。通过逐步添加与主特征向量正交的约束（强制解向量避开已优化的方向），并将搜索空间逐层降维（如三维球面→二维平面→一维曲线），极值依次由后续特征值主导。这个结论由下面给出：

定理 8

多正交约束下的二次型的最大值

设 $~\mathbf{A}~$ 是一个对称的 $~n\times n~$ 矩阵，且具有正交对角化 $~\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}~$ ，其中对角矩阵 $~\mathbf{D}~$ 的元素按 $~\lambda_1 \geq \lambda_2 \geq \cdots \lambda_n~$ 排列， $\mathbf{P}~$ 的列是对应的单位特征向量 $~\mathbf{u}_1,\cdots,\mathbf{u}_n~$ 。则对于 $~k=2,\cdots,n~$ ，二次型 $~\mathbf{x}^T\mathbf{A}\mathbf{x}~$ 在约束条件：

\mathbf{x}^T\mathbf{x} = 1,\quad \mathbf{x}^T\mathbf{u}_1 = 0,\quad \cdots, \quad \mathbf{x}^T\mathbf{u}_{k-1} = 0

下的最大值为特征值 $~\lambda_k~$ ，且最大值在 $~\mathbf{x} = \mathbf{u}_k~$ 时取得。

5. 应用示例：公共工程优化

例 $~6~$ ：某县政府计划修复 $~x~$ 百公里道路和桥梁，并改善 $~y~$ 百公顷的公园和娱乐区。资源约束条件为 $~4x^2 + 9y^2 \leq 36~$ ，需最大化效用函数 $~q(x,y) = xy~$ 。

将原约束 $~4x^2 + 9y^2 = 36~$ 转换为单位球面形式：

(\frac{x}{3})^2 + (\frac{y}{2})^2 = 1

定义新变量：

x = 3x_1, \quad y = 2x_2 \quad \Rightarrow \quad x_1^2 + x_2^2 = 1

原函数 $~q(x,y) = xy~$ 转换为新变量：

q(3x_1, 2x_2) = 6x_1x_2

设向量 $~\mathbf{x} = \begin{bmatrix}x_1 & x_2\end{bmatrix}^T~$ ，则二次型为：

Q(\mathbf{x}) = 6x_1x_2 = \mathbf{x}^T\mathbf{A}\mathbf{x},\quad \mathbf{A} = \begin{bmatrix}0 & 3 \\ 3 & 0\end{bmatrix}

矩阵 $~\mathbf{A}~$ 的特征方程为：

\det(\mathbf{A} - \lambda\mathbf{I}) = \lambda^2 - 9 = 0 \quad \Rightarrow \quad \lambda = \pm 3

最大特征值为 $~\lambda_{max} = 3~$ 。

解方程 $~(\mathbf{A} - 3\mathbf{I})\mathbf{x} = 0~$ ：

\begin{bmatrix}-3 & 3 \\ 3 & -3\end{bmatrix}\begin{bmatrix}x_1 \\ x_2\end{bmatrix} = \mathbf{0} \quad \Rightarrow \quad x_1 = x_2

单位特征向量为：

\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{2} \\ 1/\sqrt{2}\end{bmatrix}

新变量下的解为 $~x_1 = 1/\sqrt{2},~x_2 = 1/\sqrt{2}~$ ，转换为原变量：

x=3x_1 = 3/\sqrt{2} \approx 2.1~(\text{~百公里~}), \quad y = 2x_2 = \sqrt{2} \approx 1.4~(~\text{百公顷}~)

7.2 二次型

7.4 奇异值分解

约束优化

1. 约束优化问题引入

2. 无交叉项二次型的极值求解

解例 1 ~1~ 1

解例 2 ~2~ 2

3. 特征值与极值的关系

证定理 6 ~6~ 6

解例 3 ~3~ 3

4. 附加正交约束下的优化

解例 4 ~4~ 4 ，含对定理 7 ~7~ 7 的推导

解例 5 ~5~ 5 ，利用定理 7 ~7~ 7 的结论

5. 应用示例：公共工程优化

1变量替换标准化约束条件

2转换原函数为二次型

3求解矩阵 A ~\mathbf{A}~ A 的特征值

4确定最大特征值对应的特征向量

5回代原变量得到最优解