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

信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * KKT优化条件 设优化问题中，函数 可微。设 为原始优化问题的最优解， 为对偶问题的最优解，且两者具有强对偶性，则 满足如下条件： KKT条件为必要条件！ 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 凸优化问题的KKT条件 可微。设 满足KKT条件，则 为原始问题的最优解，而 为对偶问题的最优解，且两者具有强对偶性。 设原始问题为凸优化问题中，函数 例 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 原始凸优化问题 KKT条件 KKT条件构成线性方程组系统 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 例 原始凸优化问题 KKT条件 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 例 其中 解得 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 凸优化问题的对偶求解 存在唯一解 。若 为原始问题的可行解，则 即为原始问题的最优解；若 不是原始问题的可行解，则原始问题不存在最优解。 设原始优化问题与对偶问题具有强对偶性，且 为对偶问题的最优解。 存在唯一的最小解，即 例 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 原始凸优化问题 对偶问题： 假设原问题存在可行解，即有 ， 则弱Slater条件满足，原问题与对偶问题具有强对偶性。 例 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 假设对偶问题的最优解为 ，则原问题可求解 可得 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 扰动问题 扰动问题： 当 时即为原始问题。 若 为正，则第 个不等式约束被放宽；若 为负，则第 个不等式约束被收紧。 记 为扰动问题的最优解。若扰动问题无最优解，则记 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 灵敏度分析 设对偶问题存在最优解，且与原始问题具有强对偶性，若非干扰问题的最优对偶解为 ，则有 若 在 处可微，则 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 选择定理 设原始问题的约束条件： 关于约束条件的优化问题描述： 最优值： 选择定理 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 对偶问题的不等式组 对偶问题 对偶问题的最优值： 选择定理 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 原问题与对偶问题的最优值 原问题的约束条件与对偶不等式组具有弱选择性。 定义（弱选择性）：若两个不等式（等式）系统，至多有一个可解，则称这两个系统具有弱选择性。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 选择定理 对偶不等式组 设原始问题的严格不等式约束条件： 原始问题的严格不等式约束条件与对偶不等式组具有弱选择性。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 定义（强选择性）：若两个不等式（等式）系统，恰有一个可解，则称这两个系统具有强选择性。 选择定理 对偶不等式组 设原始问题为凸优化问题，其严格不等式约束条件为： 若存在 ，满足 ，则上述两不等式约束系统具有强选择性。 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu.cn * 选择定理 对偶不等式组 设原始问题为凸优化问题，其不等式约束条件为： 则原始问题的不等式约束条件与对偶不等式组具有强选择性。 若存在 ，满足 ，且下述优化问题存在最优解 作业 P273 5.1 P276 5.11 P279 5.20 P282 5.29 信息与通信工程学院 庄伯金 bjzhuang@bupt.edu