单击此处编辑母版标题样式,,单击此处编辑母版文本样式,,第二级,,第三级,,第四级,,第五级,,信息与通信工程学院 庄伯金 bjzhuang@,*,信息与通信工程学院 庄伯金 bjzhuang@,1,凸优化理论与应用,第四章,对偶问题,信息与通信工程学院 庄伯金 bjzhuang@,2,优化问题的拉格朗日函数,设优化问题：,拉格朗日(,Lagrangian),函数：,对固定的 ，拉格朗日函数 为关于 和 的,仿射函数,信息与通信工程学院 庄伯金 bjzhuang@,3,拉格朗日对偶函数,拉格朗日对偶函数,(lagrange dual function),：,若拉格朗日函数没有下界，则令,拉格朗日对偶函数为,凹函数,对 和 ，若原最优化问题有最优值 ，则,信息与通信工程学院 庄伯金 bjzhuang@,4,对偶函数的例,Least-squares solution of linear equations,Standard form LP,Two-way partitioning problem,信息与通信工程学院 庄伯金 bjzhuang@,5,Least-squares solution of linear equations,原问题：,拉格朗日函数：,拉格朗日对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,6,Standard form LP,原问题：,拉格朗日函数：,拉格朗日对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,7,Two-way partitioning problem,原问题：,拉格朗日函数：,拉格朗日对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,8,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,9,Equality constrained norm minimization,问题描述：,共轭函数：,对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,10,Entropy maximization,原始问题：,共轭函数：,对偶函数,：,信息与通信工程学院 庄伯金 bjzhuang@,11,Minimum volume covering ellipsoid,原始问题：,对偶函数：,共轭函数：,信息与通信工程学院 庄伯金 bjzhuang@,12,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,信息与通信工程学院 庄伯金 bjzhuang@,13,LP,问题的对偶问题,标准,LP,问题,对偶函数,对偶问题,等价描述,信息与通信工程学院 庄伯金 bjzhuang@,14,弱对偶性,定理（弱对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 ，则 成立。
optimal duality gap,可以利用对偶问题找到原始问题最优解的下界信息与通信工程学院 庄伯金 bjzhuang@,15,强对偶性,强对偶性并不是总是成立的定义（强对偶性） ：设原始问题的最优值为 ，对偶问题的最优值为 若 成立，则称原始问题和对偶问题之间具有,强对偶性,凸优化问题,通常（但并不总是）,具有强对偶性Slater,定理：若凸优化问题存在严格可行解，即存在 ，满足,则优化问题具有强对偶性该条件称为,Slater,条件,信息与通信工程学院 庄伯金 bjzhuang@,16,强对偶性,存在 ，满足,弱化的,Slater,条件：若不等式约束条件的前 个为线性不等式约束条件，则,Slater,条件可以弱化为：,信息与通信工程学院 庄伯金 bjzhuang@,17,Least-squares solution of linear equations,原问题：,对偶问题：,具有强对偶性,信息与通信工程学院 庄伯金 bjzhuang@,18,Lagrange dual of QCQP,QCQP,：,拉格朗日函数：,对偶函数：,信息与通信工程学院 庄伯金 bjzhuang@,19,Lagrange dual of QCQP,对偶问题,：,Slater,条件：存在 ，满足,信息与通信工程学院 庄伯金 bjzhuang@,20,Entropy maximization,原始问题：,对偶函数：,对偶问题,：,信息与通信工程学院 庄伯金 bjzhuang@,21,Entropy maximization,弱化的,Slater,条件：存在 ，满足,信息与通信工程学院 庄伯金 bjzhuang@,22,Minimum volume covering ellipsoid,原始问题：,对偶函数：,对偶问题：,信息与通信工程学院 庄伯金 bjzhuang@,23,Minimum volume covering ellipsoid,弱化的,Slater,条件总成立，因此该优化问题具有强对偶性。
弱化的,Slater,条件：存在 ，满足,Mixed strategies for matrix games,双人零和博弈,,玩家,1,可以从 种策略中选择 ；,,玩家,2,可以从 种策略中选择 ；,,玩家,1,对玩家,2,回报 组成回报矩阵 ；,,玩家,1,希望回报值越小越好，而玩家,2,希望回报值越大越好；,,玩家,1,和玩家,2,以一定的概率分布选择各种策略，即,,,信息与通信工程学院 庄伯金 bjzhuang@,24,Mixed strategies for matrix games,玩家,1,对玩家,2,的期望回报为：,,,玩家,1,的策略分布选择问题,,,,,转换为,LP,问题,,信息与通信工程学院 庄伯金 bjzhuang@,25,Mixed strategies for matrix games,对偶问题,,,,,,玩家,2,的策略分布选择问题,,,信息与通信工程学院 庄伯金 bjzhuang@,26,Mixed strategies for matrix games,等价问题,,,,,,由于优化问题具有强对偶性，因此玩家,1,的优化问题和玩家,2,的优化问题完全等价。
信息与通信工程学院 庄伯金 bjzhuang@,27,信息与通信工程学院 庄伯金 bjzhuang@,28,对偶可行解的不等式,对于一优化问题，若 为一可行解， 为对偶问题可行解，则有如下不等式：,为 次优解，其中,不等式可以用于对次优解的精度估计,信息与通信工程学院 庄伯金 bjzhuang@,29,互补松弛条件,所以,设 为原始优化问题的最优解， 为对偶问题的最优解，若两者具有强对偶性，则,即,信息与通信工程学院 庄伯金 bjzhuang@,30,KKT,优化条件,因此， 是 的最优解设 为原始优化问题的最优解， 为对偶问题的最优解，若两者具有强对偶性，则,可得,信息与通信工程学院 庄伯金 bjzhuang@,31,KKT,优化条件,设优化问题中，函数 可微设 为原始优化问题的最优解， 为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件：,KKT,条件为必要条件！,信息与通信工程学院 庄伯金 bjzhuang@,32,凸优化问题的,KKT,条件,可微。
设 满足,KKT,条件，则 为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性设原始问题为凸优化问题中，函数,例,信息与通信工程学院 庄伯金 bjzhuang@,33,原始凸优化问题,KKT,条件,KKT,条件构成线性方程组系统,信息与通信工程学院 庄伯金 bjzhuang@,34,例,原始凸优化问题,,KKT,条件,信息与通信工程学院 庄伯金 bjzhuang@,35,例,其中,,解得,信息与通信工程学院 庄伯金 bjzhuang@,36,凸优化问题的对偶求解,存在唯一解 若 为原始问题的可行解，则 即为原始问题的最优解；若 不是原始问题的可行解，则原始问题不存在最优解设原始优化问题与对偶问题具有强对偶性，且 为对偶问题的最优解 存在唯一的最小解，即,例,信息与通信工程学院 庄伯金 bjzhuang@,37,原始凸优化问题,对偶问题,：,假设原问题存在可行解，即有 ，,,,则弱,Slater,条件满足，原问题与对偶问题具有强对偶性。
例,信息与通信工程学院 庄伯金 bjzhuang@,38,假设对偶问题的最优解为 ，则原问题可求解,可得,信息与通信工程学院 庄伯金 bjzhuang@,39,扰动问题,扰动问题：,当 时即为原始问题若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧记 为扰动问题的最优解若扰动问题无最优解，则记,信息与通信工程学院 庄伯金 bjzhuang@,40,灵敏度分析,设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有,若 在 处可微，则,信息与通信工程学院 庄伯金 bjzhuang@,41,选择定理,设原始问题的约束条件：,关于约束条件的优化问题描述：,最优值：,选择定理,信息与通信工程学院 庄伯金 bjzhuang@,42,对偶问题的不等式组,对偶问题,对偶问题的最优值：,选择定理,信息与通信工程学院 庄伯金 bjzhuang@,43,原问题与对偶问题的最优值,原问题的约束条件与对偶不等式组具有,弱选择性,。
定义（,弱选择性,）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性信息与通信工程学院 庄伯金 bjzhuang@,44,选择定理,对偶不等式组,设原始问题的严格不等式约束条件：,原始问题的严格不等式约束条件与对偶不等式组具有弱选择性信息与通信工程学院 庄伯金 bjzhuang@,45,定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性选择定理,对偶不等式组,设原始问题为凸优化问题，其严格不等式约束条件为：,若存在 ，满足 ，则上述两不等式约束系统具有强选择性信息与通信工程学院 庄伯金 bjzhuang@,46,选择定理,对偶不等式组,设原始问题为凸优化问题，其不等式约束条件为：,则原始问题的不等式约束条件与对偶不等式组具有强选择性若存在 ，满足 ，且下述优化问题存在最优解,作业,P273 5.1,,P276 5.11,,P279 5.20,,P282 5.29,信息与通信工程学院 庄伯金 bjzhuang@,47,。