无约束之前梯度类算法中介绍的最速下降法、牛顿法和拟牛顿法，可以直接使用的条件之一为：决策变量都是无约束的。 用数学语言描述的话，可以表达为：决策变量为，目标函数为 但在实际问题中，大部分都是包含约束的，比如多个决策变量之间存在耦合关系、资源有上限等。其中，有些是等式约束，有些则是不等式约束。在求解这类包含约束的最优化问题时，就需要一些新的方法。本文主要介绍拉格朗日乘子法和KKT条件。 等式约束当最优化问题中只包含等式约束时，数学模型可以表达为 相比无约束的情况，多了的限制。 求解这类问题的思路是，想办法将等式约束去掉，将原问题转化为无约束优化问题，这样就可以使用梯度类算法求解了。 拉格朗日乘子法是很常用的一种转化方法，该方法是构造如下的优化问题： 其中 相比原优化问题，新优化问题是无约束的，但是多了一组优化变量。看起来，两者是有些差异的，那么它们的最优解是否相同呢？答案是相同的，接下来详细解释一下。 针对，求一阶导数，并令其等于0： 上述两式即为取极值的必要条件。第一个公式暂时不需要关心，主要看第二个公式。也就是说，假设存在一组使得取到极值点，那么必然有 即等式约束已经被满足。此时 即最优解也等价。 虽然已经证明了，但好像依然挺绕的。接下来再画一个二维最优化问题的示意图，直观理解一下。 如下图所示。蓝色曲线为约束条件，所以可行解只能在该曲线上。3条黑色圈为原目标函数的等高线，其值从外向内越来越小，分别为5、3和1。蓝色曲线和黑色等高线存在3种空间关系，分别是不相交、相交和相切。针对不相交的情况（图中C点），显然，所以是不可行解；针对相交的情况（图中B点），从相交点开始，沿着等高线降低方向寻找，必然存在更优解；针对相切的情况（图中A点），则恰好为最优解。 现在来看一下相切点处的特征。首先是，即取极值的第二个必要条件，自必不多说；其次是由于相切，和的法向量共线，即梯度共线，由此可以推导出取极值的第一个必要条件。所以，原问题和新问题是完全等价的。 这里还需要额外说的一点是：图中的方向肯定是向外的，因为梯度的定义表明了其是指向变大方向的；但是的方向是不明确的，因为我们只有的信息，并不清楚朝哪个方向能让变大，所以图中只是一个示意图。 不等式约束如果最优化问题中不仅包含等式约束，还包含不等式约束，数学模型可以表达为 求解该类问题的思路也很简单：先将不等式约束转化为等式约束，然后再按照第二节中介绍的拉格朗日乘子法继续求解。 将不等式约束变为等式约束的方式是增加松弛变量： 至此，可以构造新的拉格朗日函数： 求一阶导数，可以得到最优解的必要条件如下： KKT条件事实上，针对包含不等式约束的情况，除了先转化为等式约束再使用拉格朗日乘子法这种“曲线救国”的方法，还有更直接的求解方法，那就是KKT条件。 针对上述同时包含等式和不等式约束的最优化问题，KKT条件为 需要注意的有三点：（1）相比上一节转化的拉格朗日乘子法，KKT中新增了约束；（2）相比KKT条件，拉格朗日乘子法中新增了变量；（3）拉格朗日乘子法中的和KKT条件中的是等价的。 接下来理解一下KKT条件。 假设为原问题的最优解。针对，存在两种可能性： （1）。此时该约束没起到作用，可以直接去掉，问题退化为第二节的等式约束问题，此时即可。 （2）。此时该约束相当于新的等式约束，把第二节中的二维最优化图再搬运过来看一下。到了这里后，我们发现，和的法向量不仅要共线，而且方向还一定要恰好相反，即必然在右侧。这是因为如果在左侧，则C点满足不等式约束，且目标函数值比A点更优，与矛盾。
|
|
|
来自： taotao_2016 > 《it》
综上可以推导出：
