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