3.1 问题介绍

考虑线性最小二乘问题

\min _ {x \in \mathbb {R} ^ {n}} \| A x - b \| _ {2} ^ {2}, \tag {3.1}

其中 $A\in \mathbb{R}^{m\times n},b\in \mathbb{R}^{m}$ 问题(3.1)的解称为最小二乘解

为了讨论方便，本讲假定 $A$ 是满秩的

3.1.1 超定方程组

当 $m > n$ 时, 线性方程组 $Ax = b$ 的解可能不存在. 此时一般考虑求解最小二乘问题 (3.1). 记

J (x) \triangleq \| A x - b \| _ {2} ^ {2}.

易知 $J(x)$ 是关于 $x$ 的二次函数, 而且是凸函数 (当 $A$ 满秩时, $J(x)$ 的Hessen阵是正定的). 因此, 由凸函数的性质可知, $x_*$ 是问题 (3.1) 的解当且仅当 $x_*$ 是 $J(x)$ 的稳定点. 令其一阶导数为零, 可得

A ^ {\mathsf {T}} A x - A ^ {\mathsf {T}} b = 0.

于是将最小二乘问题转化为一个线性方程组, 这就是后面的正规方程.

如果 $A$ 不是满秩, 则 $A^{\top} A$ 半正定, 此时解不唯一.

若 $m < n$ , 则线性方程组 $Ax = b$ 存在无穷多个解 (假定 $A$ 满秩). 这时我们通常寻求最小范数解, 即所有解中范数最小的解. 于是原问题就转化为下面的约束优化问题

\min _ {A x = b} \frac {1}{2} \| x \| _ {2} ^ {2} \tag {3.2}

对应的Lagrange函数为

\mathcal {L} (x, \lambda) = \frac {1}{2} \| x \| _ {2} ^ {2} + \lambda^ {\mathsf {T}} (A x - b),

其中 $\lambda = [\lambda_1, \lambda_2, \dots, \lambda_m]^{\mathsf{T}}$ 是Lagrange乘子.此时优化问题(3.2)的解就是 $\mathcal{L}(x, \lambda)$ 的鞍点，即下面方程组的解：

\frac {\partial \mathcal {L}}{\partial x} = x + A ^ {\intercal} \lambda = 0, \quad \frac {\partial \mathcal {L}}{\partial \lambda} = A x - b = 0.

写成矩阵形式为

\left[ \begin{array}{c c} I & A ^ {\mathsf {T}} \\ A & 0 \end{array} \right] \left[ \begin{array}{c} x \\ \lambda \end{array} \right] = \left[ \begin{array}{c} 0 \\ b \end{array} \right].

如果 $A$ 满秩, 即 $\operatorname{rank}(A) = m$ , 则系数矩阵非奇异 (见练习 3.1), 上述方程组存在唯一解.