Lecture 10 对偶理论
Note: The lecture from cxt.
对偶问题基础
-
为什么要构造原问题的对偶问题?
- 非凸问题NP-hard:对偶问题便于计算分析;
- 对偶问题解与原问题解的关联;
- 对偶将一系列约束优化转化成更少的约束优化甚至无约束优化;
- 对偶提供一些新的解法;
-
如何构造对偶
- 拉格朗日对偶
- Fenchel对偶
-
对偶问题与原问题的关系
-
对偶
-
对偶不仅适用于连续优化,整数规划等也适用对偶理论;
-
鲁棒优化、锥优化很需要对偶分析
-
拉格朗日对偶
-
拉格朗日函数
- 将原问题的约束条件转化通过乘子合并为一个新的目标函数,减少约束,只剩;
- 对拉格朗日函数关于求最小值,要比原问题带有多个约束要简单,并且给一组的值,就可以得到关于的最小值,最小值是关于的函数;
-
对偶函数
-
其中为原问题的可行域(不仅是还有约束条件)
- 上式第一个不等号因为在一个可行域大的集合()里肯定能取到更小的值;
- 上式第二个不等式因为在可行域里,两个乘子项部分是的;
-
结论:,,是原问题最优值,对偶问题是原问题最优值的下界,通过不同的可以算出不同的下界;
-
-
拉格朗日对偶问题:在许多个下界中找出最大下界
-
如果先对先求最大,再对求最小呢?:还原成原问题
-
原问题可以看成拉格朗日函数先对乘子求最大,然后对变量求最小,即的问题
-
对偶问题可以看成拉格朗日函数先对变量求最小,然后对乘子求最大,即的问题
-