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

1 1凸优化理论与应用凸优化理论与应用第四章第四章 对偶问题对偶问题2 2优化问题的拉格朗日函数n设优化问题：设优化问题：n拉格朗日拉格朗日(Lagrangian)函数：函数：n对固定的对固定的 ，拉格朗日函数，拉格朗日函数 为关于为关于 和和 的的仿仿射函数射函数。3 3拉格朗日对偶函数n拉格朗日对偶函数拉格朗日对偶函数(lagrange dual function)：若拉格朗日函数没有下界，则令若拉格朗日函数没有下界，则令n拉格朗日对偶函数为拉格朗日对偶函数为凹函数凹函数。n对对 和和 ，若原最优化问题有最优值，若原最优化问题有最优值 ，则，则4 4对偶函数的例nLeast-squares solution of linear equationsnStandard form LPnTwo-way partitioning problem5 5Least-squares solution of linear equationsn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：6 6Standard form LPn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：7 7Two-way partitioning problemn原问题：原问题：n拉格朗日函数：拉格朗日函数：n拉格朗日对偶函数：拉格朗日对偶函数：8 8对偶函数与共轭函数n共轭函数共轭函数n共轭函数与对偶函数存在密切联系共轭函数与对偶函数存在密切联系n具有线性不等式约束和线性等式约束的优化问题：具有线性不等式约束和线性等式约束的优化问题：对偶函数：对偶函数：9 9Equality constrained norm minimizationn问题描述：问题描述：n共轭函数：共轭函数：n对偶函数：对偶函数：1010Entropy maximizationn原始问题：原始问题：n共轭函数：共轭函数：n对偶函数对偶函数：1111Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n共轭函数：共轭函数：1212拉格朗日对偶问题n拉格朗日对偶问题的描述：拉格朗日对偶问题的描述：n对偶可行域对偶可行域n最优值最优值n最优解最优解1313LP问题的对偶问题n标准标准LP问题问题n对偶函数对偶函数n对偶问题对偶问题n等价描述等价描述1414弱对偶性n定理（弱对偶性）定理（弱对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 ，则，则 成立。成立。noptimal duality gapn可以利用对偶问题找到原始问题最优解的下界。可以利用对偶问题找到原始问题最优解的下界。1515强对偶性n强对偶性并不是总是成立的。强对偶性并不是总是成立的。n定义（强对偶性）定义（强对偶性）：设原始问题的最优值为：设原始问题的最优值为 ，对偶问，对偶问题的最优值为题的最优值为 。若。若 成立，则称原始问题和成立，则称原始问题和对偶问题之间具有对偶问题之间具有强对偶性强对偶性。n凸优化问题凸优化问题通常（但并不总是）通常（但并不总是）具有强对偶性。具有强对偶性。nSlater定理：若凸优化问题存在严格可行解，即存在定理：若凸优化问题存在严格可行解，即存在 ，满足，满足则优化问题具有强对偶性。该条件称为则优化问题具有强对偶性。该条件称为Slater条件条件。1616强对偶性存在存在 ，满足，满足n弱化的弱化的Slater条件：若不等式约束条件的前条件：若不等式约束条件的前 个为线性个为线性不等式约束条件，则不等式约束条件，则Slater条件可以弱化为：条件可以弱化为：1717Least-squares solution of linear equationsn原问题：原问题：n对偶问题：对偶问题：n具有强对偶性具有强对偶性1818Lagrange dual of QCQPnQCQP：n拉格朗日函数：拉格朗日函数：n对偶函数：对偶函数：1919Lagrange dual of QCQPn对偶问题对偶问题：nSlater条件：存在条件：存在 ，满足，满足2020Entropy maximizationn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题对偶问题：2121Entropy maximizationn弱化的弱化的Slater条件：存在条件：存在 ，满足，满足2222Minimum volume covering ellipsoidn原始问题：原始问题：n对偶函数：对偶函数：n对偶问题：对偶问题：2323Minimum volume covering ellipsoidn弱化的弱化的Slater条件总成立，因此该优化问题具有强对偶条件总成立，因此该优化问题具有强对偶性。性。n弱化的弱化的Slater条件：存在条件：存在 ，满足，满足Mixed strategies for matrix gamesn双人零和博弈双人零和博弈n玩家玩家1可以从可以从 种策略中选择种策略中选择 ；n玩家玩家2可以从可以从 种策略中选择种策略中选择 ；n玩家玩家1对玩家对玩家2回报回报 组成回报矩阵组成回报矩阵 ；n玩家玩家1希望回报值越小越好，而玩家希望回报值越小越好，而玩家2希望回报值越大越好；希望回报值越大越好；n玩家玩家1和玩家和玩家2以一定的概率分布选择各种策略，即以一定的概率分布选择各种策略，即2424Mixed strategies for matrix gamesn玩家玩家1对玩家对玩家2的期望回报为：的期望回报为：n玩家玩家1的策略分布选择问题的策略分布选择问题n转换为转换为LP问题问题2525Mixed strategies for matrix gamesn对偶问题对偶问题n玩家玩家2的策略分布选择问题的策略分布选择问题2626Mixed strategies for matrix gamesn等价问题等价问题n由于优化问题具有强对偶性，因此玩家由于优化问题具有强对偶性，因此玩家1的优化问题和玩的优化问题和玩家家2的优化问题完全等价。的优化问题完全等价。27272828对偶可行解的不等式对偶可行解的不等式n对于一优化问题，若对于一优化问题，若 为一可行解，为一可行解，为对偶问题可行解，为对偶问题可行解，则有如下不等式：则有如下不等式：为为 次优解，其中次优解，其中n不等式可以用于对次优解的精度估计不等式可以用于对次优解的精度估计2929互补松弛条件互补松弛条件所以所以n设设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则即即3030KKT优化条件优化条件因此，因此，是是 的最优解。的最优解。n设设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，为对偶问题的最优解，若两者具有强对偶性，则若两者具有强对偶性，则可得可得3131KKT优化条件优化条件n设优化问题中，函数设优化问题中，函数 可微。设可微。设 为原始优化问题的最优解，为原始优化问题的最优解，为对偶问题的最优解，且两为对偶问题的最优解，且两者具有强对偶性，则者具有强对偶性，则 满足如下条件：满足如下条件：KKT条件为条件为必要条件！必要条件！3232凸优化问题的凸优化问题的KKT条件条件可微。设可微。设 满足满足KKT条件，则条件，则 为原始问题的最优解，为原始问题的最优解，而而 为对偶问题的最优解，且两者具有强对偶性。为对偶问题的最优解，且两者具有强对偶性。n设原始问题为凸优化问题中，函数设原始问题为凸优化问题中，函数例3333n原始凸优化问题原始凸优化问题nKKT条件条件nKKT条件构成线性方程组系统条件构成线性方程组系统3434例例n原始凸优化问题原始凸优化问题KKT条件条件3535例例其中其中解得解得3636凸优化问题的对偶求解凸优化问题的对偶求解存在唯一解存在唯一解 。若。若 为原始问题的可行解，则为原始问题的可行解，则 即为原始问即为原始问题的最优解；若题的最优解；若 不是原始问题的可行解，则原始问题不存在不是原始问题的可行解，则原始问题不存在最优解。最优解。n设原始优化问题与对偶问题具有强对偶性，且设原始优化问题与对偶问题具有强对偶性，且 为对偶问为对偶问题的最优解。题的最优解。存在唯一的最小解，即存在唯一的最小解，即例3737n原始凸优化问题原始凸优化问题n对偶问题对偶问题：n假设原问题存在可行解，即有假设原问题存在可行解，即有 ，则弱则弱Slater条件满足，原问题与对偶问题具有强对偶性。条件满足，原问题与对偶问题具有强对偶性。例3838n假设对偶问题的最优解为假设对偶问题的最优解为 ，则原问题可求解，则原问题可求解 n可得可得3939扰动问题扰动问题n扰动问题：扰动问题：n当当 时即为原始问题。时即为原始问题。n若若 为正，则第为正，则第 个不等式约束被放宽；若个不等式约束被放宽；若 为负，则第为负，则第 个个不等式约束被收紧。不等式约束被收紧。n记记 为扰动问题的最优解。若扰动问题无最优解，则记为扰动问题的最优解。若扰动问题无最优解，则记4040灵敏度分析灵敏度分析n设对偶问题存在最优解，且与原始问题具有强对偶性，若非干设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为扰问题的最优对偶解为 ，则有，则有n若若 在在 处可微，则处可微，则4141选择定理选择定理n设原始问题的约束条件：设原始问题的约束条件：n关于约束条件的优化问题描述：关于约束条件的优化问题描述：n最优值：最优值：选择定理选择定理4242n对偶问题的不等式组对偶问题的不等式组n对偶问题对偶问题n对偶问题的最优值：对偶问题的最优值：选择定理选择定理4343n原问题与对偶问题的最优值原问题与对偶问题的最优值n原问题的约束条件与对偶不等式组具有原问题的约束条件与对偶不等式组具有弱选择性弱选择性。n定义（定义（弱选择性弱选择性）：若两个不等式（等式）系统，至多有一个）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。可解，则称这两个系统具有弱选择性。4444选择定理选择定理n对偶不等式组对偶不等式组n设原始问题的严格不等式约束条件：设原始问题的严格不等式约束条件：n原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。4545n定义（强选择性）：若两个不等式（等式）系统，恰有一个可定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。解，则称这两个系统具有强选择性。选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其严格不等式约束条件为：设原始问题为凸优化问题，其严格不等式约束条件为：n若存在若存在 ，满足，满足 ，则上述两不等式约束系统，则上述两不等式约束系统具有强选择性。具有强选择性。4646选择定理选择定理n对偶不等式组对偶不等式组n设原始问题为凸优化问题，其不等式约束条件为：设原始问题为凸优化问题，其不等式约束条件为：则原始问题的不等式约束条件与对偶不等式组具有强选择性。则原始问题的不等式约束条件与对偶不等式组具有强选择性。n若存在若存在 ，满足，满足 ，且下述优化问题存在最优，且下述优化问题存在最优解解作业作业nP273 5.1nP276 5.11nP279 5.20nP282 5.294747