凸优化理论与应用-对偶问题PPT课件.ppt

可编辑 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条件 存在 满足 Mixedstrategiesformatrixgames 双人零和博弈玩家1可以从种策略中选择 玩家2可以从种策略中选择 玩家1对玩家2回报组成回报矩阵 玩家1希望回报值越小越好 而玩家2希望回报值越大越好 玩家1和玩家2以一定的概率分布选择各种策略 即 可编辑 24 Mixedstrategiesformatrixgames 玩家1对玩家2的期望回报为 玩家1的策略分布选择问题转换为LP问题 可编辑 25 Mixedstrategiesformatrixgames 对偶问题玩家2的策略分布选择问题 可编辑 26 Mixedstrategiesformatrixgames 等价问题由于优化问题具有强对偶性 因此玩家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 定义 强选择性 若两个不等式 等式 系统 恰有一个可解 则称这两个系统具有强选择性 选择定理 对偶