拉格朗日乘子法--带约束的最优化问题求解

实际工程场景与带约束最小化问题建模

一般情况下，我们通常会遇到这样一种情况，对于一个状态x，我们会对其有很多形如\(f_i(x)=0\)的观测，同时状态x，其本身满足\(g(x)=0\)这样的约束条件。我们想要求解的是在如上已知条件下状态x的最优估计。好了，既然已经有了问题，那么我们需要对其进行一个精确的数学建模。首先，无论如何最后求解得到的状态x是需要满足 \[ g(x) = 0 \] 同时，对于所有的\(f_i(x)=0\)的观测，我们需要明确一点，那就是其是一个超定的观测方程，根据这个方程我们也许可以直接解出x，但是这个x基本不可能满足\(g(x)=0\)。但是！所有的f观测其实都是存在噪声影响的，而约束g是不存在噪声影响的，因此我们可以据此构建带约束的优化问题如下 \[ min \sum_{i=1}^{n} f_i^2(x) \\ s.t. g(x) = 0 \] 如上，不带噪声的g是必须满足的约束条件，带噪声的观测f们通过一个最小化的求解来获得最优解（之所以取平方是因为我们是想让每一个观测的相对误差都尽量小）。下面会介绍如何对此类问题进行求解。

问题描述：

\[ min \ f(x,y) \\ s.t. \ g(x,y)=0 \]

表示在约束g的情况下求解f的最小值。（其中s.t.表示subject to，服从于的意思）

其实上面这个问题等价于 \[ \begin{bmatrix}{l} \nabla f(x,y)=\lambda \nabla g(x,y) \\ g(x,y)=0 \end{bmatrix} \]

其中\(\nabla f(x,y)\)表示的是梯度。上面两个式子又等价于求\(f(x,y)-\lambda g(x,y)\)的极值（其中\(\lambda\)也是变量，因此其极值在函数对三个变量的求导都为0时）。

此处的意思是说，第二个式子表示的约束本身是g函数的一个等高线，f函数在取不同值时也会有很多等高线，只有f和g相切时上述带约束的最小化问题刚好得到解。

举个例子：

例子来源 \[ min \ f(x,y)=x^2+y^2 \\ s.t. \ x^2y=3 \] 等价于： \[ \begin{bmatrix}{l} \nabla f(x,y)= {\begin{bmatrix} 2x \\ 2y \end{bmatrix}} = \lambda {\begin{bmatrix}{*{20}{c}} 2xy \\ x^2 \end{bmatrix}} = \lambda \nabla g(x,y) \\ g(x,y)= x^2y - 3 = 0 \end{bmatrix} \] 求解上述三元方程组可得 \[ \left\{\begin{array}{l} x \approx \pm 1.61 \\ y \approx 1.1 \\ \lambda \approx 0.87 \end{array}\right. \]