Constrained Optimization

Overview

本教程主要有如下部分组成1: overview of constrained optimization. 2. lagarange solution to this problem. 3. insight to the lagrange solution。

从上图可以看出，之前在解决graph优化的时候，我们采用的都是目标函数都是cost function（energy function）。所采用的constraints都是softconstraints。（每一个目标项只是尽可能靠近）。在下面我们将介绍constraints都是hard constrints的情况。\

Example

我以以下的例子为例，来讲解constrained optimization

$$\begin{equation}\begin{split} \text{maximize }&f(x,y) = x^2y\\ \text{subject to } &x^2+y^2=1 \end{split}\end{equation}$$
分别画出这两个分布的图如下, 约束是一个圆，为了方便起见我们将圆投影到了目标函数上去了。

以图形上来看，我们并不能太看出这个问题怎么来解。我们并不能在圆上选取一个初始值，然后迭代去找最值，因为这样非常容易就到了局部最优了。\
这里介绍一种新的思路，将目标函数的等值线求出来，研究等值线的变化。如下图所示是目标函数的等值线。

等值线应该就是梯度的垂直方向（值不变）。等值线与往外，其与圆上交点，在目标数中的值就越大。那么最大的就是切线了。不仅是这个例子中，我们可以得出来一个比较通用的结论： 在约束与等值线相切得地方，是求得最值得地方；进一步得出，在目标函数的梯度与约束函数的梯度在同一个方向上时，求得最值。

通过如上分析，我们可以得出如下等式 $$\begin{equation}\begin{split} [2xy,x^2]&=\lambda[2x,2y]\\ x^2+y^2&=1 \end{split}\end{equation}$$
以上有三个方程，刚好可以解三个不等式，解出来x,y分别有两组解，根据组合，一共可以得到4组可能的解，将四组解带入到目标函数中，就可以获得相应的值，就能解决这个问题了。

Insight lagrangian multiplier

在上一节的介绍中，我们可以看到约束的梯度与目标的提取是一个线性关系，这个拉格朗日乘子的性质在这一节中进行介绍。\
这里介绍lagrangian 乘子法。