对偶理
最大最小对偶 目标函数： F(x,y) x∈X,y∈Y x方的目标是无论y怎样，都应使越小越好 y方的目标是无论x怎样，都应使F越大越好； minmax F(x,y) 立于不败之地的决策方法 x∈Xy∈Y 对对偶问题 maxmin F(x,y) 保守主义决策 yeYx∈X 相关结论： 1) minF(x,y)≤F(x,y)≤maxF(x,y),x∈X,y∈Y XEX vEY 2) max min F(x,y)<minmax F(x,y) 一弱对偶定理 yEY xEX x∈XyeY 3) g仰=min max F(x,y)-max min F(x,y)一对偶间隙 x∈XyeY yEY xEX inf 2 min max→ sup
2 最大最小对偶 x X y Y minmax ( , ) F x y F x y x X y Y ( , ) , y Y x X maxmin ( , ) F x y 目标函数: x方的目标是无论y怎样，都应使F越小越好； y方的目标是无论x怎样，都应使F越大越好； 立于不败之地的决策方法 ——保守主义决策 相关结论： ——一对对偶问题 x X y Y 1) min ( , ) ( , ) max ( , ), , F x y F x y F x y x X y Y y Y y Y x X x X 2) maxmin ( , ) minmax ( , ) F x y F x y ——弱对偶定理 x X x X y Y y Y 3) minmax ( , ) maxmin ( , ) gap F x y F x y = − ——对偶间隙 min max inf sup
最大最小对偶举例一博弈 x∈X={1,2},y∈Y={1,2,F(x,y)=ag, 4a,)[日 min max F(x,y)=2 xEX yEY 8p=0 max min F(x,y)=2 yeYx∈X =,[日到 min max F(x,y)=2 x∈XyeY 8吧=1≠0 max min F(x,y)=1 vEY xEX 3
3 最大最小对偶举例——博弈 x X y Y minmax ( , ) 2 F x y = x X y Y = = 1,2 , 1,2 , y Y x X maxmin ( , ) 2 F x y = F x y axy ( , ) , = A aij 1 2 ( ) 4 3 − = = gap = 0 A aij 1 2 ( ) 4 1 − = = x X y Y minmax ( , ) 2 F x y = y Y x X maxmin ( , ) 1 F x y = gap = 1 0
最大最小对偶 鞍点条件：对 F(x,y),x∈X,y∈Y,若有点x∈X,y∈Y F(x,y)≤F(x,y)≤F(x,Jy),x∈X,y∈Y 则称(x*y*)满足鞍点条件。 相关结论： 1) minF(x,y)≤F(x,y)≤maxF(x,y),x∈X,y∈Y XEX yey 2) max min F(x,y)≤min max F(x,y)一弱对偶定理 yEY xEX xEx yEY 3) gap minmax F(x,y)-max min F(x,y) x∈XyeY yEY xEX 一对偶间隙 4) minmax F(x,y)=max min F(x,y) xEX yEY yEY xEX 台(x,y)满足鞍点条件。 强对偶定理 4
4 最大最小对偶 鞍点条件: 对 F x y x X y Y ( , ), , , 相关结论： x X y Y 1) min ( , ) ( , ) max ( , ), , F x y F x y F x y x X y Y y Y y Y x X x X 2) maxmin ( , ) minmax ( , ) F x y F x y ——弱对偶定理 x X x X y Y y Y 3) minmax ( , ) maxmin ( , ) gap F x y F x y = − ——对偶间隙 若有点 * * x X y Y , F x y F x y F x y x X y Y * * * * ( , ) ( , ) ( , ), , 则称(x*,y*)满足鞍点条件。 x X x X y Y y Y 4) minmax ( , ) maxmin ( , ) F x y F x y = ——强对偶定理 x y * * ( , ) 满足鞍点条件
Lagrange对偶 min f(x) 原规划： s.t.gxy≤0，h(x)=0 Lagrange函数 L(x,u,v)=f(x)+u'g(x)+vh(x) (u≥0) Lagrange对偶 maxθ(u,y) 凹函数 ≥0，y 其中i)=mi{f)+ug()+vx},u≥0 弱对偶性： 1) x∈S,w≥0，y, f(x),x∈S minL(x,4,y)≤L(x,u,y)=f(x)≤maxL(x,u,y)= x∈R" 20,y +o0,x庄S 2) max min L(x,w,)=max(u,)≤min max L(x,D弱对偶定理 u20,v xER" l≥0，y XER,v 原规划 min max L(x,u,v)-max min L(x,u,v) x∈R"20,y ≥0，yx∈R" 一对偶间隙 5
5 f x s t g(x) h x min ( ) . . 0, ( ) 0 = 原规划: Lagrange对偶 T T Lagrange函数 L x u v f x u g x v h x u ( , , ) ( ) ( ) ( ) ( 0) = + + Lagrange对偶 n T T x R ( , ) min ( ) ( ) ( ) , 0 u v f x u g x v h x u 其中 = + + 弱对偶性: n n u v u v u v x R x R L x u v u v L x u v 0, 0, 0, 2) maxmin ( , , ) max ( , ) minmax ( , , ) = n x R u v f x x S L x u v L x u v f x L x u v 0 , x S ( ), min ( , , ) ( , , ) ( ) max ( , , ) , = = + 1) , 0, , x S u v n n x R x R u v u v L x u v L x u v 0, 0, 3) minmax ( , , ) maxmin ( , , ) − ——弱对偶定理 ——对偶间隙 原规划 u v u v 0, max ( , ) 凹函数