新浪博客

拉格朗日对偶问题

2018-10-21 22:35阅读：

http://blog.sina.cn/dpool/blog/u/1653392055

本文参考: 1、https://www.cnblogs.com/ooon/p/5723725.html
2、https://blog.csdn.net/ytusdc/article/details/78904035
3、https://blog.csdn.net/blackyuanc/article/details/67640844
4、https://blog.csdn.net/xierhacker/article/details/72673207
一、目标函数形式
在优化理论中，目标函数f(x)会有多种形式：如果目标函数和约束条件都为变量x的线性函数，称该问题为线性规划；如果目标函数为二次函数，约束条件为线性函数，称该最优化问题为二次规划；如果目标函数或者约束条件均为非线性函数，称该最优化问题为非线性规划。每个线性规划问题都有一个与之对应的对偶问题，对偶问题有非常良好的性质：
（1）对偶问题的对偶是原问题
（2）无论原始问题是否为凸的，对偶问题都是凸优化问题（这里说的是凸优化而非凸函数，事实上对偶函数都是凹函数）
（3）对偶问题可以给出原始问题一个下界
（4）当满足一定条件时，原始问题与对偶问题的解是完全等价的
举例说明（对偶的图像应该是错误的，因为对偶函数都是凹函数）：
拉格朗日对偶问题
二、拉格朗日乘数法思想
将含有n个
变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日问题的约束都是等号形式的。
广义拉格朗日乘数法：不等式约束比等式约束更为常见，扩展了拉格朗日乘数法，增加了KKT条件之后可以用拉格朗日乘数法求解不等式约束的优化问题。
KKT条件：满足一些有规则的条件下，一个非线性规划问题能有最优化解法的一个必要和充分条件。
三、原始问题与对偶问题
给出不等式约束优化问题
拉格朗日对偶问题
拉格朗日定义如下:
拉格朗日对偶问题
根据以上公式可以得到一个重要结论：
拉格朗日对偶问题
因为满足约束条件的x会使得 拉格朗日对偶问题，因此第二项消掉了；而 拉格朗日对偶问题和 拉格朗日对偶问题，从而 拉格朗日对偶问题，所以最大值只能在它们都取零的时候得到，这个时候就只剩下f(x)了。反之如果有任意一个约束条件不满足，则只需令其相应的乘子趋于 拉格朗日对偶问题，则会得到 拉格朗日对偶问题，这样将导致问题无解，因此必须满足约束条件。经过这样一转变，约束都融合到了一起而得到如下的无约束的优化目标：
拉格朗日对偶问题
上式与原优化问题等价，将之称作原始问题，其实只是一个形式上的重写，方便找到其对应的对偶问题。其对偶问题表述为：
拉格朗日对偶问题
对偶函数与原始问题的形式非常类似，只是把min和max交换了一下。
记原始问题的解为 拉格朗日对偶问题，对偶问题的解为 拉格朗日对偶问题。对偶问题和原始问题的最优解并不相等，而是满足如下关系：
拉格朗日对偶问题
无论原始问题是什么形式，对偶问题总是一个凸优化的问题。即：拉格朗日对偶函数一定是凹函数，且其凹性与最优化函数和约束函数无关，具体证明见：https://blog.csdn.net/u014540876/article/details/79153913
四、KKT条件

拉格朗日对偶问题是弱对偶性，而 拉格朗日对偶问题是强对偶性。强对偶是一个非常好的性质，因为在强对偶成立的情况下，可以通过求解对偶问题来得到原始问题的解。其实只要满足一些条件，强对偶性是成立的，比如说KKT条件。
假设 拉格朗日对偶问题分别是原始问题（并不一定是凸的）和对偶问题的最优解，且满足强对偶性，则相应的极值的关系满足：
拉格朗日对偶问题
由此可得到KKT条件：
拉格朗日对偶问题
总结来说：任何满足强对偶性的优化问题，只要其目标函数与约束函数可微，任一对原始问题与对偶问题的解都是满足KKT条件的。

我的更多文章

下载客户端阅读体验更佳

APP专享