最大最小对偶.ppt

* * 最大最小对偶 目标函数: x方的目标是无论y怎样，都应使F越小越好； y方的目标是无论x怎样，都应使F越大越好； 立于不败之地的决策方法 ——保守主义决策 相关结论： ——一对对偶问题 ——弱对偶定理 ——对偶间隙 最大最小对偶举例——博弈 最大最小对偶 鞍点条件: 对 相关结论： ——弱对偶定理 ——对偶间隙 若有点 则称(x*,y*)满足鞍点条件。 ——强对偶定理 满足鞍点条件。 原规划: Lagrange对偶 Lagrange函数 Lagrange对偶 弱对偶性: ——弱对偶定理 ——对偶间隙 原规划 凹函数 Lagrange对偶举例 像集 连续可微凸规划: 强对偶定理：连续可微凸规划，满足一约束规格，则 Lagrange对偶的强对偶定理 f、g可微凸，h线性 1)：若原问题有解，则对偶问题也有解； 2)：若原问题与对偶问题分别有可行解，则他们是最优解的充分必要条件是他们对应相同的目标值(对偶间隙为0). 证1)：即证可微凸规划的最优解 与其KKT条件的乘子 满足鞍点条件！ 证2)：利用鞍点条件可得。 参阅《Nonlinear Programming-Theory and Algorithm》第6章 M. S. Bazaraa C. M. Shetty(图书馆有中译本) 3)：对偶问题无上界，则原问题不可行；原问题无下界，则对偶问题不可行。 连续可微凸规划: Wolfe对偶： Wolfe对偶 f、g可微凸，h线性 1)：若原问题有解，则对偶问题也有解； 2)：若原问题与对偶问题分别有可行解，则他们是最优解得充分必要条件是他们对应相同的目标值(对偶间隙为0). Lagrange函数 Wolfe对偶定理：连续可微凸规划，满足一约束规格，则 凸规划对偶举例(Q正定) 二次规划(Q正定) 推广一： 推广二： Lagrange对偶 共轭对偶、广义Lagrange对偶 ——参阅《非线性规划及其理论》第6章 应玖茜、魏权龄