Logo

约束优化

1. 约束优化问题引入

约束优化(constrained optimization)(\text{constrained optimization})源于实际问题中需要在有限资源或条件下寻找最优解的需求，例如工程设计中的成本最小化或经济学中的收益最大化。它解决的是如何在满足给定约束条件的情况下优化目标函数的问题。在许多应用中，这类问题常表现为在特定集合上求解二次型 xTAx ~\mathbf{x}^T\mathbf{A}\mathbf{x}~的最大值和最小值。最常见的约束向量集合为单位向量约束，即向量的范数为 1 ~1~。单位向量约束有以下几种等价形式：
∥x∥=1,∥x∥2=1,xTx=1,x12+x22+⋯+xn2=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
单位向量约束将向量限制在单位球面上，即在 Rn ~\mathbb{R^n}~空间中满足 x12+x22+⋯+xn2=1 ~x_1^2 + x_2^2 + \cdots + x_n^2 = 1~的所有点的集合。这种约束不仅便于几何理解，还能将优化问题转化为特征值问题，从而求解目标函数的最大值或最小值。

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

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

  1. 二次型的结构：二次型 Q(x)=9x12+4x22+3x32 ~Q(x)=9x_1^2 + 4x_2^2 + 3x_3^2~是一个无交叉项的二次型，其矩阵为对角矩阵：
    A=[900040003]\mathbf{A} = \begin{bmatrix} 9 & 0 & 0 \\ 0 & 4 & 0 \\ 0 & 0 & 3 \end{bmatrix}
  2. 确定最大值：由于 x12+x22+x32=1 ~x_1^2 + x_2^2 + x_3^2 = 1~，且 x22 ~x_2^2~和 x32 ~x_3^2~非负，可以推导：
    Q(x)=9x12+4x22+3x32≤9x12+9x22+9x32=9(x12+x22+x32)=9\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*}
    当x=[100]T \mathbf{x}=\begin{bmatrix}1 & 0 & 0\end{bmatrix}^T~或 x=[−100]T~\mathbf{x}=\begin{bmatrix}-1 & 0 & 0\end{bmatrix}^T时，最大值为 Q(x)=9 ~Q(x) = 9~。
  3. 确定最小值：类似地，可以推导：
    Q(x)=9x12+4x22+3x32≥3x12+3x22+3x32=3(x12+x22+x32)=3\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*}
    当x=[001]T \mathbf{x}=\begin{bmatrix}0 & 0 & 1\end{bmatrix}^T~或 x=[00−1]T ~\mathbf{x}=\begin{bmatrix}0 & 0 & -1\end{bmatrix}^T~时，最小值为 Q(x)=3 ~Q(x) = 3~。

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

例 2 ~2~：二次型 Q(x=xTAx=3x12+7x22 ~Q(\mathbf{x} = \mathbf{x}^T\mathbf{A}\mathbf{x}=3x_1^2 + 7x_2^2~，其中：
 A=[3007] ~\mathbf{A} = \begin{bmatrix}3 & 0 \\ 0 & 7\end{bmatrix}~
x \mathbf{x}~是 R2 ~\mathbb{R^2}~中的向量。求 Q(x) ~Q(x)~在单位向量约束 xTx=1 ~\mathbf{x}^T\mathbf{x} = 1~（即x12+x22=1x_1^2 + x_2^2 = 1）下的最大值和最小值。

  1. 确定最大值：由于 x12+x22=1 ~x_1^2 + x_2^2 = 1~，且 x12 ~x_1^2~和 x22 ~x_2^2~非负，可以推导：
    Q(x)=3x12+7x22≤7x12+7x22=7(x12+x22)=7\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*}
    当x=[01]T \mathbf{x}=\begin{bmatrix}0 & 1\end{bmatrix}^T~或 x=[0−1]T~\mathbf{x}=\begin{bmatrix}0 & -1\end{bmatrix}^T时，最大值为 Q(x)=7 ~Q(x) = 7~。
  2. 确定最大值：由于 x12+x22=1 ~x_1^2 + x_2^2 = 1~，且 x12 ~x_1^2~和 x22 ~x_2^2~非负，可以推导：
    Q(x)=3x12+7x22≥3x12+3x22=3(x12+x22)=3\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*}
    当x=[10]T \mathbf{x}=\begin{bmatrix}1 & 0\end{bmatrix}^T~或 x=[−10]T~\mathbf{x}=\begin{bmatrix}-1 & 0\end{bmatrix}^T时，最大值为 Q(x)=3 ~Q(x) = 3~。

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

3. 特征值与极值的关系

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

  1. 正交对角化矩阵
    将对称矩阵 A ~\mathbf{A}~正交化为 A=PDP−1 ~\mathbf{A} = \mathbf{P}\mathbf{D}\mathbf{P}^{-1}~，其中：

    • P \mathbf{P}~是正交矩阵（列向量为 A ~\mathbf{A}~的单位正交特征向量 (u1,u2,u3) ~(\mathbf{u}_1,\mathbf{u}_2,\mathbf{u}_3)~。

    • D \mathbf{D}~是对角矩阵，对角线元素为 A ~\mathbf{A}~的特征值 a≥b≥c ~a \geq b \geq c~。

  2. 变量替换与二次型转换
    令 x=Py ~\mathbf{x} = \mathbf{P}\mathbf{y}~，则二次型可转换为：
    xTAx=yTDy=ay12+by22+cy32\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
    由于 P ~\mathbf{P}~是正交矩阵，有 ∥x∥=∥Py∥=∥y∥ ~\|\mathbf{x}\| = \|\mathbf{P}\mathbf{y}\| = \|\mathbf{y}\|~，因此 ∥x∥=1 ~\|\mathbf{x}\|=1~当且仅当 ∥y∥=1~\|\mathbf{y}\| = 1。
  3. 推导最大值 M ~M~
    对任意单位向量 y=[y1y2y3]T ~\mathbf{y} = \begin{bmatrix}y_1 & y_2 & y_3\end{bmatrix}^T~，利用特征值都排序 a≥b≥c ~a \geq b \geq c~：
    yTDy=ay12+by22+cy32≤ay12+ay22+ay32=a(y12+y22+y32)=a\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*}
    当y=e1=[100]T\mathbf{y} = \mathbf{e}_1 = \begin{bmatrix}1 & 0 & 0 \end{bmatrix}^T时，yTDy=a\mathbf{y}^T\mathbf{D}\mathbf{y} = a对应 x=Pe1=u1 ~\mathbf{x} = \mathbf{P}\mathbf{e}_1 = \mathbf{u}_1~，即：
    M=a=u1TAu1M = a = \mathbf{u}_1^T\mathbf{A}\mathbf{u}_1
  4. 推导最小值 m ~m~
    类似地，利用 a≤b≤c ~a \leq b \leq c~：
    yTDy=ay12+by22+cy32≥cy12+cy22+cy32=c(y12+y22+y32)=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*}
    当y=e3=[001]T\mathbf{y} = \mathbf{e}_3 = \begin{bmatrix}0 & 0 & 1\end{bmatrix}^T时，yTDy=c\mathbf{y}^T\mathbf{D}\mathbf{y} = c对应 x=Pe3=u3 ~\mathbf{x} = \mathbf{P}\mathbf{e}_3 = \mathbf{u}_3~，即：
    M=c=u1TAu3M = c = \mathbf{u}_1^T\mathbf{A}\mathbf{u}_3
  5. 结论

    • M=a M = a~是最大特征值，在 x=u1 ~\mathbf{x} = \mathbf{u}_1~时取得。

    • m=c m = c~是最小特征值，在 x=u3 ~\mathbf{x} = \mathbf{u}_3~时取得。

例 3 ~3~：给定一个对称但非对角的矩阵 A ~\mathbf{A}~：
A=[321231114]\mathbf{A} = \begin{bmatrix} 3 & 2 & 1 \\ 2 & 3 & 1 \\ 1 & 1 & 4 \end{bmatrix}
要求找到二次型 Q(x)=xTAx~Q(\mathbf{x}) = \mathbf{x}^T\mathbf{A}\mathbf{x}在单位球面 xTx=1 ~\mathbf{x}^T\mathbf{x} = 1~上的最大值，并确定达到此最大值的单位向量。

  1. 求解特征方程：
    det⁡(A−λI)=0⇒−λ3+10λ2−27λ+18=0⇒−(λ−6)(λ−3)(λ−1)=0⇒λ1=6,λ2=3,λ3=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*}
  2. 求解对应特征向量并单位化。A \mathbf{A}~最大特征值为 6 ~6~，解方程 (A−6I)x=0 ~(\mathbf{A} - 6\mathbf{I})\mathbf{x} = 0~得：
    v=[111]\mathbf{v} = \begin{bmatrix}1 \\ 1 \\ 1\end{bmatrix}
    单位化：
    u1=[1/31/31/3]\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{3} \\ 1/\sqrt{3}\\ 1/\sqrt{3}\end{bmatrix}
  3. 结论

    • 由定理 6 ~6~可知，二次型在单位球面约束 ∥x∥=1 ~\|\mathbf{x}\| = 1~下的最大值为 6 ~6~，取得最大值的单位向量 u1=[1/31/31/3]T ~\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{3} & 1/\sqrt{3} & 1/\sqrt{3} \end{bmatrix}^T~。

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

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

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

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

  1. 简化约束条件

    • xTx=1\mathbf{x}^T\mathbf{x} = 1。对应x12+x22+x32=1x_1^2 + x_2^2 + x_3^2 = 1。

    • xTu1=0\mathbf{x}^T\mathbf{u}_1 = 0。计算内积得：
      xTu1=x1⋅1+x2⋅0+x3⋅0=x1=0\mathbf{x}^T\mathbf{u}_1 = x_1\cdot 1 + x_2\cdot 0 + x_3 \cdot 0 = x_1 = 0

      • 综合上面两个约束条件为： x22+x32=1 ~x_2^2 + x_3^2 = 1~。

  2. 代入约束计算目标函数
    代入 x1=0 ~x_1 = 0~到 Q(x) ~Q(x)~：
    Q(x)=9⋅02+4x22+3x32=4x22+3x32Q(x) = 9\cdot 0^2 + 4x_2^2 + 3x_3^2 = 4x_2^2 + 3x_3^2
    问题转化成了在约束条件x22+x32=1x_2^2 + x_3^2 = 1下，求 Q(x)=4x22+3x32 ~Q(x) = 4x_2^2 + 3x_3^2~的最大值。
  3. 评估最大值 M ~M~
    Q(x)=4x22+3x32≤4x22+4x32=4(x22+x32)=4\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*}
    取得最大值的条件是 x1=0, x2=1, x3=0 ~x_1 = 0, ~ x_2 = 1, ~ x_3 = 0~，x \mathbf{x}~取值为 λ2 ~\lambda_2~对应的单位特征向量 u2=[010]T ~\mathbf{u}_2 = \begin{bmatrix}0 & 1 & 0\end{bmatrix}^T~。
  4. 结论

    • M=λ2=4 M = \lambda_2 = 4~是最大特征值，在 x=u2=[010]T ~\mathbf{x} = \mathbf{u}_2 = \begin{bmatrix}0 & 1 & 0\end{bmatrix}^T~时取得。

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

例 5 ~5~：设矩阵 A=[321231114] ~\mathbf{A} = \begin{bmatrix}3 & 2 & 1 \\ 2 & 3 & 1 \\ 1 & 1 & 4\end{bmatrix}~，且 u1 ~\mathbf{u}_1~是 A ~\mathbf{A}~对应最大特征值的单位特征向量。求二次型 xTAx ~\mathbf{x}^T\mathbf{A}\mathbf{x}~在约束条件：
xTx=1,且,xTu1=0\mathbf{x}^T\mathbf{x} = 1,\quad \text{且}, \quad \mathbf{x}^T\mathbf{u}_1 = 0
下的最大值，并找到使得最大值成立的单位向量 x ~\mathbf{x}~。

  1. 求解特征方程：
    det⁡(A−λI)=0⇒−λ3+10λ2−27λ+18=0⇒−(λ−6)(λ−3)(λ−1)=0⇒λ1=6,λ2=3,λ3=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*}

    第二大特征值为： λ=3 ~\lambda=3~

  2. 解方程 (A−3I)x=0 ~(\mathbf{A} - 3\mathbf{I})\mathbf{x} = 0~：
    A−3I=[021201111]∼[101/2011/2000]\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}
    得基础解 v=[11−2]T ~\mathbf{v} = \begin{bmatrix}1 & 1 & -2\end{bmatrix}^T~，向量模长 ∥v∥=11+12+(−2)2=6 ~\|\mathbf{v}\| = \sqrt{1^ 1 + 1^2 + (-2)^2} = \sqrt{6}~， 单位化后得：
    u2=[1/61/6−2/6]\mathbf{u}_2 = \begin{bmatrix}1/\sqrt{6} \\ 1/\sqrt{6} \\ -2/\sqrt{6}\end{bmatrix}
  3. 结论：根据定理 7 ~7~可知，二次型 xTAx ~\mathbf{x}^T\mathbf{A}\mathbf{x}~的在单位向量以及正价约束( 与 u1 )(~\normalsize{与}~\mathbf{u}_1~)下的最大值为 λ2=3 ~\lambda_2 = 3~，对应的单位向量为 u2=[1/61/6−2/6]T ~\mathbf{u}_2 = \begin{bmatrix}1/\sqrt{6} & 1/\sqrt{6} & -2/\sqrt{6}\end{bmatrix}^T~。

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

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

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

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

将原约束 4x2+9y2=36 ~4x^2 + 9y^2 = 36~转换为单位球面形式：
(x3)2+(y2)2=1(\frac{x}{3})^2 + (\frac{y}{2})^2 = 1
定义新变量：
x=3x1,y=2x2⇒x12+x22=1x = 3x_1, \quad y = 2x_2 \quad \Rightarrow \quad x_1^2 + x_2^2 = 1

原函数 q(x,y)=xy ~q(x,y) = xy~转换为新变量：
q(3x1,2x2)=6x1x2q(3x_1, 2x_2) = 6x_1x_2
设向量 x=[x1x2]T ~\mathbf{x} = \begin{bmatrix}x_1 & x_2\end{bmatrix}^T~，则二次型为：
Q(x)=6x1x2=xTAx,A=[0330]Q(\mathbf{x}) = 6x_1x_2 = \mathbf{x}^T\mathbf{A}\mathbf{x},\quad \mathbf{A} = \begin{bmatrix}0 & 3 \\ 3 & 0\end{bmatrix}

矩阵 A ~\mathbf{A}~的特征方程为：
det⁡(A−λI)=λ2−9=0⇒λ=±3\det(\mathbf{A} - \lambda\mathbf{I}) = \lambda^2 - 9 = 0 \quad \Rightarrow \quad \lambda = \pm 3
最大特征值为 λmax=3 ~\lambda_{max} = 3~。

解方程 (A−3I)x=0 ~(\mathbf{A} - 3\mathbf{I})\mathbf{x} = 0~：
[−333−3][x1x2]=0⇒x1=x2\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
单位特征向量为：
u1=[1/21/2]\mathbf{u}_1 = \begin{bmatrix}1/\sqrt{2} \\ 1/\sqrt{2}\end{bmatrix}

新变量下的解为 x1=1/2, x2=1/2 ~x_1 = 1/\sqrt{2},~x_2 = 1/\sqrt{2}~，转换为原变量：
x=3x1=3/2≈2.1 ( 百公里 ),y=2x2=2≈1.4 ( 百公顷 )x=3x_1 = 3/\sqrt{2} \approx 2.1~(\normalsize{~百公里~}), \quad y = 2x_2 = \sqrt{2} \approx 1.4~(~\normalsize{百公顷}~)

7.2 二次型

7.4 奇异值分解

bei an浙ICP备2024102481号