组合优化与凸优化 学习笔记5 对偶拉格朗日函数
有的时候约束条件有点难搞,我们可以把它放到目标函数里面。
记得之前凸函数的时候的结论吗?一大堆函数,每一段都取最大的,最后会得到一个凸函数。同理,每一段都取最小的,得到的是一个凹函数。就这样,我们强行把问题变成了一个凹函数,就算原本的f(x)既不凸也不凹。
可以看到之前的对偶函数是最优值的下界,毕竟加了一大堆0或者比0还小的东西。
一个例题:
其实就是和高数里面求给定条件的极大极小值用的方法,一模一样。
拉格朗日对偶问题
拉格朗日函数是原本问题的下界,现在我们要求这个函数最大是多少,这样就可以尽量靠近原始函数了。
弱对偶性
这是一个非常强的条件:
Slater条件
但显然这个条件不总是成立。那要怎么样才能保证成立呢?