《武汉工程大学学报》 2008年02期
120-122
出版日期：2008-02-28
ISSN:1674-2869
CN:42-1779/TQ
由共轭函数构造锥规划的对偶规划
0引言锥规划在金融、工程等领域有着广泛的应用\[1,2\]，因而成为近年来数学规划领域的一个引人注目的方向，很多学者从锥规划本身研究了锥规划的求解方法和某些性质\[1~8\].对偶规划是数学规划中的一个很重要的概念，但一些文献\[3,4\]仅零星地提到锥规划的对偶，文献\[7\]用线性规划的思想定义了锥规划的对偶规划，并全面讨论了锥规划对偶规划的结构.作为凸规划特殊情况的锥规划，其一定保留了凸规划的对偶性.本文以共轭函数和凸规划的对偶规划为基础，利用对偶锥的概念，推导出一般锥规划——含隐式约束的锥规划的对偶规划. 1概念与引理本文引用文章\[5~7\]中关于锥、对偶锥、锥规划的一些概念，并设锥为非空闭凸锥. 设C为Rn中非空集合，如x∈C，l∈R，l≥0，都有lx∈C，则称集合C为锥；设C为Rn中的锥，记C*={y|y∈Rn,x∈C有xTy≥0}，则称集合C*为C的对偶锥.如Rn、{o}(o表示Rn中的原点)、Rn+（{x|x≥0，x∈Rn}）均为锥. 其对偶，(Rn)*={o}、({o})*= Rn，而Rn+为自对偶的，即它们的对偶锥为其自身.当取l=o时，即得：Rn中任意锥都包含坐标原点.由于所处理的锥为非空闭凸锥，则对偶锥的对偶为原锥，即锥的对偶运算具有对称性\[5，7\].锥的直积仍为锥，且锥的直积与对偶运算具有可交换性，即(Cx×Cy)*=C*x×C*y\[7\].设变量x∈Rn，常数c∈Rn，b∈Rm，A∈Rm×n，Cx为Rn中的锥、Cy为Rm中的锥，锥规划指：(CP)min cTxs.t. Ax-b∈Cy、x∈Cx当Cy=Rm+、Cx=Rn+时，规划(CP)为线性规划，即锥规划为线性规划的推广形式.因设所用锥为非空闭凸锥，所以规划(CP)可行域D为凸集，即锥规划为凸规划的特殊形式. 引理1 (1) maxx、wAx-b-w∈Cy{f(x)+λTw}=maxx{f(x)+λT(Ax-b)}λ∈C*y;
+∞其它；(2) maxx{λTx}=0λ=0
+∞其它证：(1)记Ax-b- w= y∈Cy，则等式左边maxx、yy∈Cy{f(x)+λT(Ax-b-y)}＝maxx、yy∈Cy{f(x)+λT(Ax-b)-λTy}=maxx{f(x)+λT(Ax-b)}+maxy∈Cy{-λTy}当λ∈C*y时，即y∈Cy有λTy≥0，或-λTy≤0，而y=0∈Cy有-λTy=0.
则maxy∈Cy{-λTy}=0即等式左边=maxx{f(x)+λT(Ax-b)}当λC*y时，即y∈Cy有λTy≤o，或-λTy≥0，而α≥0，αy∈Cy有：
limα→+∞(-λTαy)=+∞故maxy∈Cy{-λTy}=+∞即原式=+∞.(2) 当λ=o时，等式成立；当λ≠o时，则λ有分量非0，不妨设第一个分量λ1≠0，取x的第一个分量x1=αλ1(α≥0)，其它分量全为0，于是，λTx=αλ21limα→+β(λTx)=+∞故maxx{λTx}=+∞即等式成立.2锥规划的对偶规划下面利用共轭函数构造锥规划(CP)的对偶规划\[9\].(1) 针对(CP)定义函数：φ(x)=cTxAx-b∈Cy,x∈Cx
+∞其它则(CP)等价minxφ(x).(2) 在(CP)的约束中引入扰动向量，w∈Rm、u∈Rn，即：
φ(x，w，u)=cTxAx-b-w∈Cy,x-u∈Cx
+∞其它于是，(CP)又等价minxφ(x,o,o).(3) 求φ(x，w，u)的共轭函数：第2期安中华：由共轭函数构造锥规划的对偶规划
武汉工程大学学报第30卷
设ξ、z∈Rn，y∈Rm.φ*(ξ，y，z)=maxx、w、u{ζTx+yTw+zTu-φ(x,w,u)}=maxx、w、uAx-b-w∈Cyx-u∈Cx{ζTx+yTw+zTu-cTx}由引理1的(1)得：
φ*(ξ，y，z)=
maxx{ζTx+yT(Ax-b)+zTx-cTx}y∈C*y,z∈C*x
+∞其它=
maxx{(ζT+yTA+zT-cT)x-yTb}y∈C*y,z∈C*x
+∞其它由引理1的(2)得：
φ*(ξ，y，z)=
-yTby∈C*y,z∈C*x,ζ+ATy+z-c=0
+∞其它(4) 得(CP)的对偶规划：maxy、z{-φ*(o,y,z)}=maxy,zy∈C*y,z∈C*ATy+z-c=o{yTb}消除松弛变量z，即得：定理1锥规划(CP)的对偶规划为：(DCP)maxbTys.t. c-ATy∈C*x、y∈C*y其中C*x、C*y分别为Cx、Cy的对偶锥.易知，规划(DCP)也为锥规划.称锥规划(CP)为锥规划(DCP)的原规划.由文献\[7，9\]得锥规划的对偶有下列性质：(1) 对称性.对偶规划的对偶是原规划，即锥规划(CP)与(DCP)互为对偶；(2) 弱对偶性.x为原规划(CP)的任一可行解，y为对偶规划(DCP)的任一可行解，则cTx ≤bTy；(3) 最优性.x0、y0分别为原规划和其对偶规划的可行解，且cTx0 =bTy0，则x0、y0分别为原规划和其对偶规划的最优解；(4) 强对偶性.如原规划有最优解，则其对偶规划也有最优解，且它们的最优值相等.3常见锥规划的对偶规划(1) 线性规划令Cx=Rn+（={x|x≥o，x∈Rn}）Cy=Rm+（={y|y≥o，y∈Rm}），则(Rn+)*=Rn+、(Rm+)*=Rm+.此时锥规划及其对偶规划为线性规划：mincTxs.t.Ax≥b、x≥o与其对偶规划：maxbTys.t.ATy≤c、y≥o(2) 标准锥规划对锥规划(CP)，令xs=Ax-b，则xs∈Cy，xs为锥规划(CP)的松驰变量.锥规划(CP)引入松驰变量xs后，其有等价形式：(SCP)mincTxs.t.Ax-xs=b、x∈Cx，x s∈Cy(SCP)称为(CP)的标准形式.对一般标准型锥规划：(SSCP)mincTxs.t.Ax=b、x∈Cx其对偶规划为：(DSSCP)maxbTys.t.c- ATy∈C*x因为，在(CP)中令Cy={o}，则此时的(CP)即为(SSCP)，且C*y= Rm.由定理1得(SSCP)的对偶规划为：maxbTys.t.c-ATy∈C*x，y∈Rm 省除无用约束y∈Rm，即得对偶规划(DSSCP).(3) 标准二次锥规划文献\[3\]的原规划为：(P1)mincT xs.t.Ax=b，x∈K其中K是二次锥.K是自对偶的，即K*=K.将(P1)改写为：mincT x s.t.Ax-b∈{o}，x∈K其中{o}*=Rm.由定理1得(P1)的对偶为：maxbTys.t.c-A Ty∈K*=K，y∈{0}*=Rm引进松驰变量s=c-A Ty∈K，并省除无用约束y∈Rm得(P1)的对偶为：(D1)maxbTys.t.ATy+s = c，s∈K与文献\[3\]的结论一致.(4) 其它锥规划文献\[4\]的原规划为：(P2)minf Txs.t.Ax =b，Cx-d∈K其中K为锥，A∈Rm×n，C∈Rl×n.将(P2)改写为：minfTxs.t.Ax-b∈{o}，Cx-d∈K，x∈Rn 其中{o}*=Rm，{Rn}*={o}.即为(CP1)中c1=f，c2=o，x1=x，A11=A，A12=o，b1=b，Cy1={o}，A21=C，A22=o，b2=d，Cy2=K，Cx1=Rn，Cx2=Rk.由定理3得(P2)的对偶为：maxbTy+dTws.t.f-(ATy+CTw)∈{o}，o∈{o}，y∈Rm，w∈K*省除无用约束y∈Rm、o∈{o}得(P2)的对偶为：(D2)maxbTy+dTws.t.f=ATy+CTw，w∈K*也与文献\[4\]的结论一致.4结语本文以共轭函数和凸规划的对偶规划为基础，利用对偶锥的概念，全面讨论了一般锥规划——含隐式约束的锥规划的对偶问题，严格推导出锥规划的对偶规划的表示形式，其形式与文献\[7\]的定义相同.同时给出了锥规划的主要对偶性质——对称性、弱对偶性、最优性和强对偶性，并用这些结果研究了常见锥规划的对偶性. 从所得结论可见，利用共轭函数和对偶锥，推导出锥规划的对偶规划具有表示形式简单、便于应用和适用于任意锥规划等优点.这为进一步研究锥规划提供了便利.