是否所有的优化问题都可以转化成对偶问题?

最近在学凸优化的内容,感觉把原问题转化成对偶问题的思路真的很神奇。虽然转化后问题的对偶间隙不一定为0,求解最优结果不一定是原问题的最优结果,但是也毕竟算是提供了一种思路。 通过乘以一些算子,把不等式,等式约束拉入到目标函数中构建拉格朗日函数,就可以完成了转化对偶问题的第一步。 我不是学数学出身的,但是感觉有些问题在转化后表达式过于复杂,感觉转化为对偶问题有些吃力,比如下面这个例子: 虽然用CVX工具可…
关注者
221
被浏览
6544
作者:JohnnyLee
链接:一些疑惑的最优化问题,希望大神帮忙解答一下,非常感谢!? - JohnnyLee 的回答
来源:知乎
著作权归作者所有,转载请联系作者获得授权。
--------------------------------------
以下回答有重大漏洞,我在上面链接的原版本中已修改答案,希望大家多多指教。
--------------------------------------
我来说说我的个人愚见吧!
首先,我想说一下我的个人理解:为什么要把对偶问题引入!!!!

依我现在的水平,我是这么告诉自己的,我总结出我学的任何知识一般来说只有两个作用:1. 直接解决问题的方法。 2. 简化解决问题的方法(找一个新问题的解,证明新问题的解逼近原问题)。

而我总结出来的就是对偶问题很明显就是第二种作用。首先,其实你实际做research能formulate出一个Optimization的问题就已经是初步成功了(比如machine learning中的很多方法,以SVM:support vector machine为例),最后我们无非要找的是方程在最大值或最小值时的解。

这时候你可以向你高中时如何解决这个问题的,就是找极值点嘛,然后再判断导数在极值点两边极限的正负去判断是极大值还是极小值。如果要是一元二次方程极大值就是最大值,极小值就是最小值。实际上optimization我觉得就是一个在多维空间中的找极大/小值(最大/小值)的问题,和高中求极值只有两点不同:一,从一位转向了多维(仅仅只是求导和运算不同,你需要的是矩阵求导和运算)。二,从无限制条件到有某些边界条件(就是类似你初中是学过的线性规划的那种条件)。

现在问题就来了,由于有了边界条件,所以我们没办法像高中那样去做目标函数的导数然后让它等于0去求解极值,因为它们不一定满足限制条件,而这个限制条件往往十分恶心,是很多很大的不等式(一个优化问题可能有n个限制条件,n可以无限大)。所以这真的是很尼玛恶心人。人类就要思索我能不能把这些条件去除了并且还不影响(或基本不影响)原来的最优解呢?(此处表达一下我对为人类做出贡献的人的敬意)于是乎!!!对偶方法应运而生!!!!

我们给每一个特别尼玛复杂的不等式限制条件附加一个lagrangian multiplier(\alpha_1吧,下标代表第一个constraint的lagrangian multiplier),这个乘子就是一个很简单的变量。所以对n个不等式,我们就有n个乘子,这n个乘子就引入了一个新的变量vector \alpha(这是一个向量变量里面包含了从\alpha_1到\alpha_n)。现在聪明的思想就出来了,我们就是要把原问题转化为可以对原变量直接求导的问题,然后再解决变量只有拉格朗日乘子的问题。

我随便来举个例子:

所以,最终我们可以直接利用高中的方法先把最内层的x的最大值求出来,因为此时x已经没有了限制条件,直接对x求偏导然后等于0,用\alpha表示的x的最优解带入到原目标函数,最终得到一个完全是constraint lagrangian multiplier为变量的优化问题,此优化问题已经十分好做了,因为此时:第一,只有一个变量(\alpha vector)。第二,此变量的constraint十分简单为>0。后面再处理新的对偶问题就非常容易了。因为约束条件已经被大大简化了。而且我们知道目标函数永远是关于\alpha的线性表达式,由于linear既是convec也是concave,一般很容易都能求。