对偶函数

拉格朗⽇函数、对偶上升法、对偶分解法

拉格朗⽇函数

⽤于解决满⾜约束条件的最值问题

注意，该⽅法均只能保证求得的结果是必要条件。只有当原函数是凸函数时，才能保证求得的结果是充要条件

拉格朗⽇乘⼦法

适⽤于具有等式约束的最⼤值/最⼩值问题

其中被称为拉格朗⽇函数，系数被称为拉格朗⽇乘⼦或者对偶变量。通过计算后，可得到候选集，然后从候选集中验算选择满⾜条件的结

果即可。（：依次对函数所有⾃变量求偏导）

KKT条件

适⽤于同时具有等式约束和不等式约束的最⼩值问题

上述式⼦成⽴的必要前提是KKT条件：

其中被称为拉格朗⽇乘⼦或者对偶变量

下⾯直观地说下为什么会有第三个条件要成⽴

由于，所以；⼜因为，所以仅有在下才能取得最⼤值，故这是KKT第三个条件必须要成⽴的原因——即第三个条件满⾜时，它意味着有

，接下来就是求解，所以该过程⼜可记为：

这种类型的约束最优解的解法，其实就是根据KKT的三个条件来求解，步骤如下：

【1】列出拉格朗⽇函数

【2】对该函数分别求的偏导函数并分别赋值为0，获得偏导函数组

【3】枚举KKT条件三中的所有情况：和

【4】将【3】中的每种情况依次带⼊【2】中的偏导函数组中进⾏求解，查看是否有解

【5】将【4】中获得的所有候选解带⼊原函数，挑选最⼩结果的那个

例⼦：

解：

对偶上升法

前提知识：共轭函数、对偶函数、线性约束下对偶函数的共轭形式、对偶问题

共轭函数

其中，表⽰函数在整个定义域中的最⼤值，则取任意常数or常向量。

这样，对每⼀个值，都会对应⼀个值。将扩展到整个取值范围后，就可得到关于函数，即函数的共轭函数。（与下⾯的对偶函数类似，

只不过⼀个是取最⼩，⼀个是取最⼤）

拉格朗⽇对偶函数

对于定义域D上的所有取值，拉格朗⽇函数的最⼩值即为拉格朗⽇对偶函数(dualfunction)：

该式表⽰：将视为常数，则则是只关于⾃变量的函数。对整个定义域D内所有的值，都有与之对应的关于只关于⾃变量的函数，这些函

数集合在整个⾃变量取值范围中的最⼩值，即为拉格朗⽇对偶函数。如下图所⽰：

所以恒成⽴，即拉格朗⽇对偶函数是最优解的下界

线性约束下拉格朗⽇函数对偶函数的共轭形式

考虑线性约束（即⾃变量的幂均为1）下的最优化问题：

其共轭形式求解如下

即

对偶问题

求解上述对偶函数的最⼤值，就是原优化问题的拉格朗⽇对偶问题(dualproblem)：

由于

所以对偶问题的求解，即对偶函数的最优解，即为的最优解（⽤于替代求解，是其简化版）。

若复杂，⽽简单，则可通过下述步骤求解最优解：

1.求解得到

2.将代⼊，然后求解得到

3.即为最优解

注意，该过程实现了：将language乘⼦将带有约束的最⼩最⼤化问题转化为⽆约束的language函数求解

对偶上升法

关键：利⽤上述的求解最优解的步骤

对偶上升法处理步骤：

1.假设已经是对偶问题的最优解

2.求解得到：

3.显然，曲线处于所有曲线中的最下⾯，根据上述对偶函数的定义可知：

4.利⽤梯度上升法更新对偶问题最优解：

5.按1~4迭代进⾏

对偶分解法

假设⽬标函数是可分解的：

则拉格朗⽇函数可分解，即：

所以可以将对偶上升法中的第2步修改为：

即可并⾏计算的每个元素，从⽽快速得到