算法lsme及例题讲解

LSME（Least Squares Method with Equality constraints）是一种最小二乘法，它可以用于求解带有等式约束的优化问题。在LSME中，我们需要最小化一个目标函数，同时满足一些线性等式约束条件。

具体来说，假设我们要最小化的目标函数为：

$$ f(\mathbf{x}) = \frac{1}{2} \left\|\mathbf{Ax} - \mathbf{b}\right\|^2 $$

其中，$\mathbf{x}$ 是我们要求解的变量向量，$\mathbf{A}$ 是一个 $m \times n$ 的矩阵，$\mathbf{b}$ 是一个 $m$ 维的向量。同时，我们还需要满足以下 $p$ 个线性等式约束条件：

$$ \mathbf{Cx} = \mathbf{d} $$

其中，$\mathbf{C}$ 是一个 $p \times n$ 的矩阵，$\mathbf{d}$ 是一个 $p$ 维的向量。

LSME 的思路是将等式约束条件转化为矩阵形式，然后利用拉格朗日乘子法将原问题转化为一个无约束的问题。具体来说，我们可以构造拉格朗日函数：

$$ L(\mathbf{x}, \boldsymbol{\lambda}) = f(\mathbf{x}) + \boldsymbol{\lambda}^\top(\mathbf{Cx} - \mathbf{d}) $$

其中，$\boldsymbol{\lambda}$ 是一个 $p$ 维的向量，称为拉格朗日乘子向量。然后，我们可以将 $L(\mathbf{x}, \boldsymbol{\lambda})$ 对 $\mathbf{x}$ 求导，并令导数为 $0$：

$$ \nabla_{\mathbf{x}} L(\mathbf{x}, \boldsymbol{\lambda}) = \mathbf{A}^\top (\mathbf{Ax} - \mathbf{b}) + \mathbf{C}^\top \boldsymbol{\lambda} = \mathbf{0} $$

解上述方程可以得到 $\mathbf{x}$ 的解析解：

$$ \mathbf{x} = (\mathbf{A}^\top \mathbf{A})^{-1} (\mathbf{A}^\top \mathbf{b} - \mathbf{C}^\top \boldsymbol{\lambda}) $$

然后，将 $\mathbf{x}$ 带回约束条件 $\mathbf{Cx} = \mathbf{d}$ 中，可以得到拉格朗日乘子 $\boldsymbol{\lambda}$ 的解析解：

$$ \boldsymbol{\lambda} = (\mathbf{C} (\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{C}^\top)^{-1} \mathbf{C} (\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{A}^\top \mathbf{b} $$

最终，我们可以得到带有等式约束的最小二乘解 $\mathbf{x}$：

$$ \mathbf{x} = (\mathbf{A}^\top \mathbf{A})^{-1} (\mathbf{A}^\top \mathbf{b} - \mathbf{C}^\top (\mathbf{C} (\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{C}^\top)^{-1} \mathbf{C} (\mathbf{A}^\top \mathbf{A})^{-1} \mathbf{A}^\top \mathbf{b}) $$

下面是一个例子，假设我们要最小化的目标函数为：

$$ f(x_1, x_2) = \frac{1}{2} (x_1 - 1)^2 + \frac{1}{2}(x_2 - 2)^2 $$

同时，我们需要满足以下等式约束条件：

$$ 2x_1 - x_2 = 1 $$

我们可以将约束条件写成矩阵形式：

$$ \begin{bmatrix} 2 & -1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 1 \end{bmatrix} $$

然后，利用上述公式求解，可以得到最小二乘解为：

$$ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = \begin{bmatrix} 1.6 \\ 2.2 \end{bmatrix} $$

其中，$\boldsymbol{\lambda} = \begin{bmatrix} 1.4 \end{bmatrix}$。