弱对偶问题

拉格朗⽇乘⼦法、对偶问题、KKT 条件、半⼆次⽅分裂法、ADMMTo Be Continued~共轭函数假设 f :R n →R ，函数 f ∗:R →R 。

若两函数满⾜：f ∗(y )=sup x ∈domf (y T x −f (x ))则 f ∗ 是 f 的共轭函数，共轭函数是使上式的上确界⼩于 ∞ 的部分。

可以理解为对于每⼀个确定的 y ，y T x 都是⼀个线性函数，此时 y T x −f (x ) 变为线性函数与原函数在 x 的定义域上的差值，这个差值即为 y T x −f (x ) 的值域，若此时确定的 y 不能使值域的上确界⼩于⽆穷⼤，则不保留，反之则保留。

所有保留的 y 构成共轭函数的定义域，⽽所有 y T x −f (x ) 不是 ∞的上确界构成共轭函数的值域。

易知共轭函数是凸函数⽰例放射函数：f (x )=ax +b 的共轭函数为：f ∗(y )=sup (yx −ax −b )观察易得，如果 y ≠a ，那么⽆论 y 取值多少，yx −ax −b 的上确界都是 ∞。

但是当 y =a 时，yx −ax −b 为常数 −b ，上确界为 −b ，即此共轭函数定义域为 a ，值域为 −b 。

负对数函数：f (x )=−log x 的共轭函数为：f ∗(y )=sup x >0(yx +log x )⾸先f ∗(y )′′<0， 对于某⼀ y 有 f ∗(y )′=y +1x =0 时，共轭函数取得最⼤值，此时 x =−1y 使得共轭函数取得上确界，即共轭函数简化为 f ∗(y )=−log(−y )−1拉格朗⽇乘⼦法⾸先解释拉格朗⽇函数的形式的原因由简单的⼆维形式，并且受到等式约束的例⼦出发min f (x ,y )s .t .g (x ,y )=c其中 g (x ,y )=c 可以理解为等⾼线，即 z =g (x ,y ) 为三维曲⾯，当 z =c 时，可以想象为⽤平⾯ z =c 去截 z =g (x ,y ) 这个三维曲⾯所获得的曲线，⽽这条曲线上满⾜g (x ,y )=c 。

对偶理论的性质及证明性质1(对称性) 对偶问题的对偶问题是原问题证明证明 设原问题为设原问题为max z ..CXAX b s t X =£ìí³î (1) 对偶问题为对偶问题为min ..0w Yb YA Cs t X =³ìí³î(2) 对偶问题的对偶问题为对偶问题的对偶问题为max ..0CUAU b s tU j =£ìí³î (3) 比较式(1)和式(3), 显然二者是等价的, 命题得证.性质2(弱对偶性) 设原问题为设原问题为式式(1)(1),,对偶问题为式(2),X 是原问题的任意一个可行解,Y 是对偶问题的任意一个可行解,那么总有CX Yb £(4) 证明证明 根据式(1), 由于AX b £, 又由于0Y ³, 从而必有从而必有YAX Yb £(5) 根据式(2), 由于YA c ³, 又由于0X ³, 从而必有从而必有YAX CX ³(6) 结合式(5)和式(6), 立即可得CX Yb £,命题得证命题得证..性质3(最优性) 设*X 原问题式(1)的可行解,*Y 是对偶问题式(2)的可行解,当是**CX Y b =时,*X 是原问题式(1)的最优解,*Y 是对偶问题式(2)的最优解. 证明证明 设X 是式(1)的最优解, 那么有那么有*CX CX ³(7) 由于**CX Y b =,那么那么*CX Y b ³(8) 根据弱对偶性质根据弱对偶性质, , 又有又有*CX Y b £ (9)从而*CX CX =, 也就是*X 是原问题式是原问题式(1)(1)(1)的最优解。

的最优解。

的最优解。

同理，也可证明*Y 是对偶问题式是对偶问题式(2)(2)(2)的最优解。

第二章 线性规划的对偶理论与灵敏度分析主要内容 对偶问题、对偶基本性质、对偶单纯形方法、灵敏度分析、参数规划 讲授重点 对偶基本性质、对偶单纯形方法、灵敏度分析 讲授方式讲授式、启发式本章知识结构图第一节 线性规划的对偶问题一、对偶问题的提出首先通过实际例子看对偶问题的经济意义。

例1 第一章例1中美佳公司利用该公司资源生产两种家电产品时，其线性规划问题为： (LP 1) max z ＝2x l +x 2⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤0,524261552121212x x x x x x x现从另一角度提出问题。

假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源。

显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。

设分别用y 1、y 2、和y 3代表单位时间(h)设备A 、设备B 和调试工序的出让代价。

因美佳公司用6小时设备A 和1小时调试可生产一件家电I ，盈利2元；用5小时设备A ，2小时设备B 及1小时调试可生产一件家电Ⅱ，盈利1元。

由此y1，y2，y3的取值应满足 6y 2+y 3≥25y 1+2y 2+y 3≥1 (2.1) 又另一公司希望用最小代价把美佳公司的全部资源收买过来，故有min z ＝15y 1+24y 2+5y 3 (2.2) 显然y i ≥0(i ＝l ，2，3)，再综合(2.1)，(2.2)式有。

(LP 2) min ω＝15y 1+24y 2+5y 3⎪⎩⎪⎨⎧≥≥+≥+0,,125263212132y y y y y y y上述LP 1和LP 2是两个线性规划问题，通常称前者为原问题，后者是前者的对偶问题。

二、对称形式下对偶问题的一般形式定义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“≤”号，当目标函数求极小时均取“≥”号’。

（1）对称性：对偶问题的对偶是原问题MaxZ CX AX b X =⎧≤⎨≥⎩MinS Yb YA C Y =⎧≥⎨≥⎩--，--，0MinS Yb YA C Y =≤≥证明：变换对偶问题模型ax 0M S YbYA C Y =−⎧−≤−⎨≥⎩MinZ CX AX b X =−⎧−≥−⎨≥⎩MaxZ CX AX b X =⎧≤⎨≥⎩2.3 对偶问题的性质b Y X C ≤（2）弱对偶性：若是原问题的可行解，是对偶问题的可行解，则存在有XY 证明：MaxZ CXAX b X =⎧≤⎨≥⎩MinS Yb YA C Y =⎧≥⎨≥⎩因是原问题的可行解，是对偶问题的可行解，所以有：XY ;Y AX Yb Y AX C X≤≥b Y X C ≤•弱对偶性的图形解释MinS=b Y最优目标MaxZ=XC（3）可行解是最优解的性质：若是原、对的可行解，当Y Xˆ,ˆ b Y X C ˆˆ= 则：是最优解Y X ˆ,ˆ b Y MinS =最优XC MaxZ =b Y XC ˆˆ=（4）对偶定理若原问题有最优解，那么对偶问题也有最优解，且原问题与对偶问题最优目标函数值相等。

1ˆ−=B C Y B01≤−−A B C C B()()XA B C C b B C X B C C X N B C C X B B C C b B C X B C C X N B C C b B C X C X C X B C NX B C b B C X C X C X C X X X C C C CX Z X B NX B b B X b X X X I N B AX B B S B S N B N B B B B SB S N B N B SS N N S B N B B S S N N B B S N B S N B SN B S N B )()()()()()(111111111111111−−−−−−−−−−−−−−−−+=−+−+−+=−+−+=++−−=++=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡==−−==⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=01≤−−A B C C B•检验数的推导：（5）互补松弛性：若分别是原问题和对偶问题的可行解，那么当且仅当为最优解Y Xˆ,ˆ 0ˆ0ˆ==X Y X Y S S和Y X ˆ,ˆ 11ˆˆˆ0,0ˆˆˆ,0,0若则有即若即则有==>==<>=∑∑ni ijj i si j nijj i si i j yaxb x ax b xy⚫对偶变量的经济含义----影子价格资源的单位改变量引起目标函数值（Z ）的改变量，通常称为影子价格（shadow price ）或边际价格（marginalprice ）。

对偶理论知识点总结一、一般理解对偶理论是运筹学和数学中的一个重要理论，主要研究优化问题的对偶性质和利用对偶问题来解决原始问题的方法。

优化问题是现实世界中的一种普遍问题，它的目标是在一定的约束条件下找到最优解。

而对偶理论则是研究优化问题的一个重要角度，它告诉我们，对于每一个原始问题都存在一个对偶问题，通过对偶问题我们可以获得原始问题的一些重要信息，比如最优解的下界。

二、对偶问题的定义在深入了解对偶理论之前，我们首先需要了解什么是对偶问题。

对于一个原始优化问题：\[ \begin{cases} inf \ c^T x \\ Ax=b \\ x\geq0 \end{cases}\]它的对偶问题可以定义为：\[ \begin{cases} sup \ b^T y \\ A^Ty+c=y \\ y\geq0 \end{cases}\]其中，\(c,x\)是原始问题的目标函数和解向量，\(A,b\)是原始问题的约束条件，对偶问题的目标函数和解向量分别为\(b,y\)。

原始问题和对偶问题之间存在着一种对偶关系，通过对偶问题我们可以获得原始问题的一些重要信息。

三、对偶性质对偶理论的一个重要性质就是对偶性质，它告诉我们原始问题和对偶问题之间存在着一种非常紧密的联系。

具体来讲，对偶性质包括弱对偶性和强对偶性两个方面。

1. 弱对偶性：对于任意一个优化问题，其对偶问题的目标函数值不会超过原始问题的目标函数值，即对于原始问题的任意可行解x和对偶问题的任意可行解y，有\[c^Tx\geqb^Ty\]2. 强对偶性：若原始问题和对偶问题均存在最优解，则它们的目标函数值相等，即\[inf \c^Tx=sup \ b^Ty\]这两个对偶性质告诉我们，对偶问题的解可以为原始问题的最优解提供一个下界，并且在某些情况下，对偶问题的解可以等于原始问题的最优解。

四、对偶问题的应用对偶理论不仅仅是一种理论概念，更是一种实际问题求解的工具。

在实际问题中，我们经常可以通过对偶问题来求解原始问题，或者通过对偶问题的解来获得原始问题的解。

线性规划的对偶原理3。

1 线性规划的对偶问题一、 对偶问题的提出换位思考家具厂的线性规划问题,该问题站在家具厂管理者的角度追求销售收入最大213050m ax x x z +=⎪⎩⎪⎨⎧≥≤+≤+0,50212034212121x x x x x x某企业家有一批待加工的订单，有意利用该家具厂的木工和油漆工资源来加工他的产品。

他 需要与家具厂谈判付给该厂每个工时的价格。

如果该企业家已对家具厂的经营情况有详细了 解，他可以构造一个数学模型来研究如何才能既让家具厂觉得有利可图,肯把资源出租给他, 又使自己付的租金最少.目标：租金最少；1y —付给木工工时的租金；2y -付给油漆工工时的租金2150120m in y y w +=所付租金应不低于家具厂利用这些资源所能得到的利益1）支付相当于生产一个桌子的木工、油漆工的租金应不低于生产一个桌子的收入 502421≥+y y2）支付相当于生产一个椅子的木工、油漆工的租金应不低于生产一个椅子的收入 30321≥+y y3）付给每种工时的租金应不小于零 0,021≥≥y y二、 原问题与对偶问题的数学模型1. 对称形式的对偶原问题和对偶问题只含有不等式约束时，一对对偶问题的模型是对称的，称为对称形式的对偶。

原问题:⎪⎩⎪⎨⎧≥≥=0min X b AX CX z对偶问题:⎪⎩⎪⎨⎧≥≤=0max Y C YA Yb w2. 非对称形式的对偶若原问题的约束条件全部是等式约束（即线性规划的标准型）,即⎪⎩⎪⎨⎧≥==0min X b AX CX z则其对偶问题的数学模型为⎪⎩⎪⎨⎧≤=是自由变量Y C YA Yb w max可把原问题写成其等价的对称形式:min z =CX AX ≥b AX ≤b X ≥0即 min z =CX⎥⎦⎤⎢⎣⎡-A A X ≥⎥⎦⎤⎢⎣⎡-b bX ≥0设Y 1=(y 1,y 2,…,y m ）， Y 2=（y m+1，y m+2，…,y 2m ）。