凸优化学习笔记5(中科大)对偶
5 对偶
sup 的定义:一个集合最小的上界
inf 的定义:一个集合最大的下界
5.1 Lagrange对偶函数
5.1.1 Lagrange函数
注:问题(5.1)不一定是凸问题。
5.1.2 Lagrange对偶函数
对偶函数一定是凹函数;
5.1.3 最优值的下界
5.1.4 通过线性逼近来理解
5.1.5 例子
(1)线性方程组的最小二乘解
(2)标准形式的线性规划
(3)双向划分问题
5.1.6 Lagrange对偶函数和共轭函数
(1)考虑如下问题:
所以,对偶函数为(-v)的共轭函数的相反数。
(2)
5.2 Lagrange对偶问题
性质:
(1)d* <= p*
(2)称lamda*, v*为最优拉格朗日乘子
(3)Lagrange对偶问题是凸优化问题
5.2.1显式表达对偶约束
(1)标准形式线性规划的Lagrange对偶
(2)不等式形式线性规划的Lagrange对偶
5.2.2 弱对偶性
5.2.3 强对偶性和Slater准则
(1)强对偶性
(2)相对内部(relint D)定义
relint D = {x属于D | B(x,r)(x为圆心r为半径的弧) 交aff D(D的仿射包) 是D的子集,存在r>0}
(3)Slater条件(只是充分条件)
5.2.4 例子
(1)线性方程组的最小二乘解
(2)二次约束二次规划的Lagrange对偶
5.3 几何解释
5.3.1 通过函数值集合理解强弱对偶性
5.3.2 在约束准则下强对偶性成立的证明
5.4 鞍点解释
5.4.1 强弱对偶性的极大极小描述
5.4.2 鞍点解释
满足
的x*、lamda*叫做鞍点。
5.4.3 多目标解释
5.4.4 经济学解释
5.5 最优性条件
5.5.1 次优解认证和终止准则
5.5.2 互补松弛性
5.5.3 KKT最优性条件
(1)非凸问题:KKT条件为必要条件
(2)凸问题:
(3)例子
5.6 扰动及灵敏度分析
5.6.1 扰动的问题
5.6.2 一个全局不等式
5.6.3 局部灵敏度分析
5.7 例子
5.7.1 引入新的变量以及相应的等式约束
5.7.2 变换目标函数
5.7.3 隐式约束
习题
Feb_d: 请问 这些内容可以在哪本书上找到呢,特别是凸函数透视 的保凸的性质
一起加油一定: 谢谢大佬,麻烦你了
呜哇呜哇shhh: 不能保证我的代码能达到最优解,如果想要更好的解,可能要试试别的方法了
一起加油一定: 大佬,我就是运行的你上边的程序,数据也没变,调大M也不行,最好的一次显示8000多。使用确定的数像16为开始城市也不行,你还有法救救我吗?
呜哇呜哇shhh: 你好,你用的是遗传算法吗,可以多跑几次,调节一下参数试试