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
分别画出这两个分布的图如下, 约束是一个圆,为了方便起见我们将圆投影到了目标函数上去了。
以图形上来看,我们并不能太看出这个问题怎么来解。我们并不能在圆上选取一个初始值,然后迭代去找最值,因为这样非常容易就到了局部最优了。\
这里介绍一种新的思路,将目标函数的等值线求出来,研究等值线的变化。如下图所示是目标函数的等值线。
等值线应该就是梯度的垂直方向(值不变)。等值线与往外,其与圆上交点,在目标数中的值就越大。那么最大的就是切线了。不仅是这个例子中,我们可以得出来一个比较通用的结论: 在约束与等值线相切得地方,是求得最值得地方;进一步得出,在目标函数的梯度与约束函数的梯度在同一个方向上时,求得最值。
通过如上分析,我们可以得出如下等式
以上有三个方程,刚好可以解三个不等式,解出来x,y分别有两组解,根据组合,一共可以得到4组可能的解,将四组解带入到目标函数中,就可以获得相应的值,就能解决这个问题了。
Insight lagrangian multiplier
在上一节的介绍中,我们可以看到约束的梯度与目标的提取是一个线性关系,这个拉格朗日乘子的性质在这一节中进行介绍。\
这里介绍lagrangian 乘子法。
然后求
the λ
在解
这里尚未证明,但是结论非常有意思,这表示的是如果我增加b(在金融中是budget),那么带来的最大收益会增加多少(那这个值在决策中就非常有用了。
proof of the conclusion
证明比较简单,为了简单起见使用*表示最优值
这里也就是上一节中给出来的结论了。