凸优化理论与应用对偶问题

.,1,凸优化理论与应用,第四章对偶问题,.,2,优化问题的拉格朗日函数,设优化问题：,拉格朗日(Lagrangian)函数：,对固定的，拉格朗日函数为关于和的仿射函数。,.,3,拉格朗日对偶函数,拉格朗日对偶函数(lagrangedualfunction)：,若拉格朗日函数没有下界，则令,拉格朗日对偶函数为凹函数。,对和，若原最优化问题有最优值，则,.,4,对偶函数的例,Least-squaressolutionoflinearequations,StandardformLP,Two-waypartitioningproblem,.,5,Least-squaressolutionoflinearequations,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,6,StandardformLP,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,7,Two-waypartitioningproblem,原问题：,拉格朗日函数：,拉格朗日对偶函数：,.,8,对偶函数与共轭函数,共轭函数,共轭函数与对偶函数存在密切联系,具有线性不等式约束和线性等式约束的优化问题：,对偶函数：,.,9,Equalityconstrainednormminimization,问题描述：,共轭函数：,对偶函数：,.,10,Entropymaximization,原始问题：,共轭函数：,对偶函数：,.,11,Minimumvolumecoveringellipsoid,原始问题：,对偶函数：,共轭函数：,.,12,拉格朗日对偶问题,拉格朗日对偶问题的描述：,对偶可行域,最优值,最优解,.,13,LP问题的对偶问题,标准LP问题,对偶函数,对偶问题,等价描述,.,14,弱对偶性,定理（弱对偶性）：设原始问题的最优值为，对偶问题的最优值为，则成立。,optimaldualitygap,可以利用对偶问题找到原始问题最优解的下界。,.,15,强对偶性,强对偶性并不是总是成立的。,定义（强对偶性）：设原始问题的最优值为，对偶问题的最优值为。若成立，则称原始问题和对偶问题之间具有强对偶性。,凸优化问题通常（但并不总是）具有强对偶性。,.,16,强对偶性,存在，满足,弱化的Slater条件：若不等式约束条件的前个为线性不等式约束条件，则Slater条件可以弱化为：,.,17,Least-squaressolutionoflinearequations,原问题：,对偶问题：,具有强对偶性,.,18,LagrangedualofQCQP,QCQP：,拉格朗日函数：,对偶函数：,.,19,LagrangedualofQCQP,对偶问题：,Slater条件：存在，满足,.,20,Entropymaximization,原始问题：,对偶函数：,对偶问题：,.,21,Entropymaximization,弱化的Slater条件：存在，满足,.,22,Minimumvolumecoveringellipsoid,原始问题：,对偶函数：,对偶问题：,.,23,Minimumvolumecoveringellipsoid,弱化的Slater条件总成立，因此该优化问题具有强对偶性。,弱化的Slater条件：存在，满足,.,24,Mixedstrategiesformatrixgames,双人零和博弈玩家1可以从种策略中选择；玩家2可以从种策略中选择；玩家1对玩家2回报组成回报矩阵；玩家1希望回报值越小越好，而玩家2希望回报值越大越好；玩家1和玩家2以一定的概率分布选择各种策略，即,.,25,Mixedstrategiesformatrixgames,玩家1对玩家2的期望回报为：玩家1的策略分布选择问题转换为LP问题,.,26,Mixedstrategiesformatrixgames,对偶问题玩家2的策略分布选择问题,.,27,Mixedstrategiesformatrixgames,等价问题由于优化问题具有强对偶性，因此玩家1的优化问题和玩家2的优化问题完全等价。,.,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,定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。,选择定理,对偶不