（应用数学专业论文）锥规划及其对偶锥规划的若干性质及应用.pdf

中文摘要 锥规划 c o n i co p t i m i z a t i o n 简称c o 是一种特殊的凸规划 是线性规划 的推广 它指的是在一个仿射空间与一个正则锥的交集上 求线性目标函数的极 小或极大值 这个问题总括了线性规划 1 i n e a rp r o g r a m m i n g 简称l p 凸二次 约束规划 c o n v e xq u a d r a t i cp r o g r a m m i n g 简称q c q p 半定规划 s e m i d e f i n i t e p r o g r a m m i n g 简称s d p 二次锥规划 s e c o n d o r d e rc o n i co p t i m i z a t i o n 简称 s o c p 从它的模型可以看出 它的约束条件和线性规划相比 既是非线性的也 是凸约束 近年来 由于它的理论和算法有很大的进展 并且在投资组合优化 最小风险套利 协方差矩阵的逼近等方面得到了广泛的应用 因此成为数学规 划领域中一个非常活跃的研究方向 本文围绕锥规划问题 对锥及其对偶锥的性质进行了研究 解决了一些特 殊锥 钝锥 直角锥 优劣钝锥 及其对偶锥之间的关系 并对它们存在的充 要条件给予了详细的证明 在此基础上 通过与线性规划作对比 将对偶定理 弱对偶性 强对偶性 互补松弛定理等推广到锥规划问题中 得到了一些有 意义的结论 并且得到了这两个规划的零对偶间隙的存在条件 本文主要由理 论研究和应用实践两部分组成 第一部分是理论研究 在线性规划的基础上重点 介绍了一种特殊的凸规划类型 锥规划及其对偶锥规划 并介绍了锥规划及 其对偶锥规划的发展及其性质 第二部分是应用实践 将所提出的锥规划及其对 偶锥规划应用在各个领域 例如最d 乘问题 多项式求解 协方差矩阵估计 以及在其它方面的运用 这些应用无不显示出研究锥规划的必要 本文的具体研 究内容如下安排 第一章介绍了国内外对锥规划及其对偶锥规划的研究现状 模型 指出本 文研究要解决的关键问题及研究内容 第二章介绍了本文要用到的锥及其对偶锥的主要性质 以及几类特殊锥及 其对偶锥的性质 充要条件等关键性问题都进行了详细的分析和证明 第三章是文章的主体部分 主要介绍了锥规划及其对偶锥规划的若干性质 研究主要有 利用n e s t e r o v 和t o d d 的齐次模型判断锥规划与其对偶锥规划解的 存在性 类似于线性规划推导出锥规划的k k t 条件 从锥规划的泛对偶性得到 锥规划与对偶锥规划的零对偶间隙存在的条件 从而了解泛对偶性与原一对偶 可行集的有界性之间的关系 第四章将锥规划及其锥规划的理论应用于实际问题中 第五章总揽全文 得出结论 并提出今后的研究展望 关键词 锥规划 对偶锥规划 对偶间隙 泛对偶性 i i a b s t r a c t c o n i co p t i m i z a t i o n c o i sap a r t i c u l a rc a s eo fc o n v e xp r o g r a m m i n g a n di ti s a l s oa ne x t e n s i o no fl i n e a rp r o g r a m m i n g i nc o n i co p t i m i z a t i o no n em i n i m i z e s o r m a x i m i z e s al i n e a ro b j e c t i v ef u n c t i o no v e rt h ei n t e r s e c t i o no fa l la f f i n es p a c ew i t ha r e g u l a rc o n ei nf i n i t ed i m e n s i o n t h i sp r o b l e mc o m p r i s e so fl i n e a rp r o g r a m m i n g l p c o n v e xq u a d r a t i cp r o g r a m m i n g q c q p s e m i d e f i n i t ep r o g r a m m i n g s d p s e c o n d o r d e rc o n i co p t i m i z a t i o n s o c p f r o mi t sm o d e l s i m i l a rt ot h el i n e a rp r o g r a m m i n g i t i sk n o w nt h a tt h ec o n s t r a i n tq u a l i f i c a t i o ni sn o to n l yn o n l i n e a r l yb u ta l s oc o n v e x i n r e c e n ty e a r s c o n i co p t i m i z a t i o nh a sb e e no n eo ft h em o s ta c t i v er e s e a r c ha r e a si n m a t h e m a t i c a lp r o g r a m m i n gb e c a u s ei t st h e o r ya n da l g o t i t h m sh a v ed e v e l o p e dg r e a t l y a n di t sn u m e r o u sa p p l i c a t i o n sh a v eb e e nf o u n di np o r t 1 i eo p t i m i z a t i o n m i n i m u m r i s ka r b i t r a g e a n da p p r o x i m a t i n gc o v a r i a n c em a t r i c e s a n ds oo n o nc o n i co p t i m i z a t i o n w ew o r ko v e rs o m ep r o p e r t i e so fc o n ea n di t sd u a lc o n e a n ds o l v et h er e l a t i o n sb e t w e e ns p e c i a lc o n e s o b t u s ec o n e o r t h o g o n a lc o n e s u p e r i o r a n di n f e r i o ro b t u s ec o n e s a n dt h e i rd u a lc o n e s f u r t h e r m o r e s u f f i c i e n ta n dn e c e s s a r y c o n d i t i o nu n d e rw h i c h 也e ye x i s ta r ep r o v e dd e t a i l e d b a s e do nm u c hk n o w l e d g e c o n t r a s t i n gt o l i n e a rp m g r a m m i n g w ee x t e n dd u a l i t yt h e o r e m i n c l u d i n gw e a k d u a l i t yt h e o r e ma n ds t r o n gd u a l i t yt h e o r e m c o m p l e m e n t a r ys l a c kt h e o r e mt oc o n i c o p t i m i z a t i o n h e n c ew e f i n do u ts o m e s i g n i f i c a t i v ec o n c l u s i o n s a n de x i s t i n g c o n d i t i o n su n d e rw h i c ht h e i rd u a l i t yg a pi sz e r oo ft w oo p t i m i z a t i o n s t h i sa r t i c l ei sm o s t l ym a d eu po ft h e o r ys t u d ya n da p p l i c a t i o np r a c t i c e i nf i r s t p a r ti tp a y sa t t e n t i o nt ot h e o r ys t u d y a f t e r w a r d s b a s e do nl i n e a rp r o g r a m m i n g w e i n t r o d u c es o m ep r o p e r t i e so fc o n i co p t i m i z a t i o na n di t sd u a lp r o b l e m w h i c ha r ea k i n do fe s p e c i a lc o n v e xp r o g r a m m i n g i ns e c o n dp a r t w ea p p l yt h e s et h e o r i e st o p r a c t i c e s u c ha sl e a s t s q u a r e sp r o b l e m s p o l y i l o m i a ls o l u t i o na n da p p r o x i m a t i n g c o v a r i a n c em a t r i c e s a n do t h e ra s p e c t s a l lo ft h a s ea p p l i c a t i o n ss h o wt h a ts t u d yo n c o n i co p t i m i z a t i o ni sn e c e s s a r y f o rd e t a i l w ec o n c l u d et h e ma sf o l l o w s t h em o d e l s f o r e i g na n di n t e r n a ls t u d ys i t u a t i o n so nc o n i co p t i m i z a t i o na n di t s d u a lp r o b l e ma r ei n t r o d u c e di nc h a p t e ro n e a n dw ep o i n to u tt h ek e yp r o b l e ma n d r e s e a r c hm a t t e r i l l c h a p t e rt w oi n t r o d u c e ss o m ep r i m a r yp r o p e r t i e so fac o n ea n di t sd u a lc o n e f u r t h e r m o r e s o m ep r o p e r t i e s s u f f i c i e n ta n dn e c e s s a r yc o n d i t i o no fs p e c i a lc o n e sa n d t h e i rd u a lc o n e sa r ea n a l y z e da n dp r o v e dd e t a i l e d c h a p t e rt h r e e i st h em o s tp r i n c i p a lp a r t i nt h i r dc h a p t e r s o m ei m p o r t a n t p r o p e r t i e s o fc o n i co p t i m i z a t i o na n di t sd u a lp r o b l e ma r ed e t a i l e di n t r o d u c e d w e u t i l i z en e s t e r o va n dt o d d sh o m o g e n e o u sm o d e lt oe s t i m a t et h ee x i s t e n c eo f s o l u t i o n sb e t w e e nc o n i co p t i m i z a t i o na n di t sd u a lc o n i co p t i m i z a t i o n s i m i l a rt o l i n e a rp r o g r a m m i n g w eg i v et h e k k t c o n d i t i o no ft h et w oo p t i m i z a t i o n s t h r o r l g h t h eu n i v e r s a ld u a l i t yi nc o n i cc o n v e xo p t i m i z a t i o n w eg a i nt h ee x i s t e n c ec o n d i t i o n u n d e rw h i c ht h ed u a l i t yg a po ft h et w op r o g r a m m i n g si sz e r o a c c o r d i n g l y w ek n o w t h ec o n n e c t i o no ft h eu n i v e r s a ld u a l i t ya n db o u n d n e s so fap r i m a l d u a lp a i rf e a s i b l e s e t w e a p p l yt h e s et h e o r i e st op r a c t i c a la p p l i c a t i o n si nc h a p t e r f o u r i nc h a p t e rf i v ew em a k em a n yc o n c l u s i o n sa n db r i n gf o r w a r dr e s e a r c h e x p e c t a t i o nf o rt h ef u t u r e k e y w o r d s c o n i co p t i m i z a t i o n d u a lc o n i co p t i m i z a t i o n d u a l i t yg a p u n i v e r s a l d u a l i t y 武汉理工大学硕士学位论文 第一章绪论雨一早殖y 匕 锥规划 c o 指的是在一个仿射空间与一个正则锥的交集上 求线性目标 函数的极小或极大值 这个问题总括了线性规划 l p 凸二次约束规划 q c q p 半定规划 s d p 和线性规划的约束条件相比 锥规划的约束条件既是非线性 的也是凸约束的 特别需要说明的是 本文所研究的都是锥线性规划 简称为锥 规划 本章首先介绍锥规划问题的起源 拟以线性规划为基础说明研究锥规划问 题的现实意义 接着讲述锥规划及其对偶锥规划的模型以及国内外研究现状 最后列出本文的内容提要和章节安排 1 1 选题的目的和意义 早在1 9 4 7 年 美国数学家g b d a n t z i g 丹捷格 最早提出了解一般线性规 划问题的单纯形法 后来人们对这个算法进行了一系列的改进 现在 线性规划 非线性规划以及随机规划 非光滑规划 多目标规划 几何规划 整数规划等 各种最优化问题的理论研究发展迅速 新方法不断出现 实际应用日益广泛 借 助于计算机 最优化计算方法在经济计划 工程设计 生产管理 交通运输等 方面得到了广泛应用 成为一门倍受关注的学科 正如s t a n f o r d 大学教授t r o c k f e l l a r 所说的那样 优化问题大的分水岭不在 于线性和非线性 而在于凸性和非凸性 1 9 9 3 年 而凸规划的构造是由n e s t e r o v 和n e m i r o v s k i i 所提出 他们指出 应用在线性规划 l p 中的内点法也可以应用 在大型凸规划中 2 3 t c h a m p i o n 还讨论了凸规划的对偶间隙问题 4 1 后来 f r a n c o i sg l i n e u r 还讨论了凸规划的特例 锥规划中的对偶间隙问题 5 6 凸优化和锥优化在金融 投资和工程方面都有实际的应用 近年来 由于凸 锥优化的广泛应用 很多学者相信凸锥优化将会比线性规划更加优越 1 9 9 4 年到 2 0 0 4 年间 一些学者发现了锥规划的理论和求解方法l 锥规划是处在线性规划和 非线性规划之间的一种特殊的规划类型 它允许非线性约束 称为锥约束 而且锥规划问题是凸的 这一点和线性规划类似 因此它也能够很快求解 在金 融 工程中有很多重要问题都是二次锥规划类型 大量投资问题 诸如选择有效 的投资组合 货币管理的类型分析 c v a r 的检测 养老基金的风险预算等等都 武汉理工大学硕士学位论文 是凸二次问题 它们都是二次锥规划的特殊情形 其中用来求解这种规划问题的 最新软件要数f r o n t l i n e sp r e m i u ms o l v e rp l a t f o r mv 6 0 对于更大型的问题 使 用者只需要安装m o s e k 软件即可 这为凸规划的应用开辟了更为广阔的前景 线性规划及其对偶问题有若干基本性质 诸如弱对偶定理 强对偶定理 最优性定理 对称性定理 对称式互补松弛定理及非对称式松弛定理 经研究 发现 锥规划及其对偶锥规划也有若干类似的性质 比如说弱对偶性 最优性 强对偶性等等 只是锥规划的强对偶性成立的条件要比线性规划的对偶条件弱的 多 因为它还需要 s l a t e r 条件 但也有某些类型的凸锥规划有较强的性质 即 零对偶间隙无需 s l a t e r 条件 有关锥规划及其对偶锥规划 它的最优解集合的 性质 最优解的存在性 最优解集的有界性等等 以及是否具有类似于线性规 划具有弱 强 对偶定理 松紧定理 性质等等也是近年来运筹学研究的重点 1 1 1 凸规划问题 规划是对客观事物和现象未来的发展进行超前性的调配和安排 是发现事 物多种联系的最优手段 是生产力布局的最优方法 能减少全局中局部决策的 个体局部性 提高决策的整体性和科学性擞学家们对规划问题产生浓厚的兴趣 最早起源于一个世纪前 他们主要是对其解方法以及解方法的有限性进行探讨 即寻找一个算法使得该规划问题在有限的步骤下终止 2 0 世纪中期 计算机在运 筹学领域的推广使用使得他们越来越对这些算法的实际应用感若趣 先前常常被 忽视的计算复杂度在这个时候被重新提上议程 这是因为数学家们发现 一个解 方法即使已经被证明是有限的 但是一旦时间或者初始操作次数随着问题的大 小增长得太快 它在实际中也是没有多少实用价值的 实际上 很多规划问题可 能很难求解 在实践上这些问题经常不易解答彳艮明显 遇到的问题越是一般化 所使用方法的效率越低 我们现在所熟知的线性规划只是一个理想化的规划 求 解它的有效算法包括单纯形算法 内点算法等等 但是 还有其它更多的问题不 能被简单的考虑成线性规划 这就需要我们考虑更为一般的凸规划 即目标函 数是凸的 约束条件被定义在一个可行的凸集上 事实上 要检验一个给定的规 划问题是不是凸规划 往往比解答这个问题本身困难得多 首先回忆一下凸规划的有关知识 函数f d 一月是凸的 当且仅当它的定义域和图都是凸集 其中函数 的 武汉理工大学硕士学位论文 俐e p i f 一虹 f k d sr 标准的凸规划问题模型 i n f f o x 1 1 j j 上 s 其中 目标函数 0 0 s 一月是定义在集合s 上的凸函数 s r 4 是闭凸集 与线性规划不同 定义在凸集上的凸函数如果要取得极大值不能转化为求 极小值的形式 而且很难求解 因此在这里我们主要考虑极小化的情形 目标函数 和可行域具有凸性这个条件非常重要 一方面 1 1 的任意 个局部最优解也 是一个整体最优解 这即是说 目标值就等于所有的局部最优值 而且所有的 局部最优值集合也是凸的 另一方面 1 1 存在着一个对偶的凸规划 这一对 原一对偶凸规划问题满足弱对偶性质 任意一个可行解的最优且标值是其对偶 问题最优目标值的一个界 而且在某些条件下 强对偶性质也是成立的 两个 问题的最优目标值相等 由泛函分析知识可以知道 凸函数在闭凸集上一定有最值 但是要真正求 解一个凸规划问题却相当困难 很多学者只是从理论上进行分析 把 1 1 的目标函数作线性处理后 它等价于下列形式 i n ft 牡j 17 1 2 s g s 其中s 一缸 t e r x r i z e s 0 s f r 1 如此定义了s 以后 对于任意的最优解o f 一定有 t 一 0 0 由于s 是凸函数 0 的图 所以等价的规划问题也是凸的 不失一般性 我们假定目标函数是线性的 记厂0 仁 c t x 其中向量c e r 4 以后我们主要考虑以下凸规划模型 i n fc 7 j 胪 1 3 s j 茗 s 武汉理工大学硕士学位论文 1 1 2 锥规划问题 数学规划的目标是在某些约束条件下 求一个目标函数 该函数依赖于几 个决策变量 的极大值或极小值 如果目标函数和约束条件都是线性的 就称为 线性规划 实际中还有大量问题 其目标函数或者约束条件很难用线性函数表达 如果目标函数和 或 约束条件中含有非线性函数 就称这种规划问题为非线 性规划问题 非线性规划是运筹学的重要分支之一 它在许多方面得到越来越广 泛的应用 典型应用领域有预报 生产流程的安排 科学管理 库存控制 质 量控制 系统控制 保养和维修 最优设计 会计过程以及资金预算等等 一般 说来 求解非线性规划问题要比求解线性规划问题困难得多 如果目标函数具有 凸性 约束条件也定义在一个可行的凸集上 那么这个规划问题将如何解决呢 1 9 7 4 年 e l y u 将数学规划推广为要求约束函数构成的向量属于某个事先给定 的闭凸锥 相应的规划就具有了锥结构的形式 例如我们熟知的半正定锥规划 1 7 嘲 二次锥规划 9 1 0 等等 锥规划是非线性规划中一个更加特殊的规划 近几 年来 国外关于锥规划及其对偶锥规划问题的研究非常热门 最新使用的求解 锥规划软件s e d u m i 主要由m c m a s t e r 大学的j o s e s t u r m 教授 于2 0 0 3 年去世 着手研制 1 l 现在由m e m a s t e r 大学的a d v o l 接手以求进一步完善 具体可见h a p s e d u m i m c m a s 眦c a 我们从图一1 上可以看到规划模型的发展历程 图一1 我们列出表一1 比较线性规划和锥规划 标准型 的异同点 武汉理工大学硕士学位论文 表一l 规划类型 相同点不同点结论 线性目标函数r a i n c 7 x 约束 工苫0 线性规划是 线性规划 约束 i xa b 特点 目标函数和约锥规划的特例 其中的4 是矩阵束条件都是线性的 约束 x c 线性目标函数r a i n c 7 x 特点 目标函数是线性锥规划是线性 锥规划 约束 血 b 的 约束在凸锥和一个规划的推广 其中的4 是线性算子仿射子空间的交集上 线性规划模型的应用如此广泛 其原因在于它有非常特殊的线性解析结构 可以应用于大型的规划问题中 然而 现实中很多问题不能单纯的用线性规划简 单描叙 为了解决非线性的相关问题 我们将非负卦限贮用非线性的凸锥c 来代 替 由此形成了一类新型的凸规划问题 锥规划问题 1 2 j 2 1 1 3 1 研究锥规划是非常 有意义的 一方面 很多的非线性规划问题都可以被模拟成锥规划 另一方面 在有些弱条件下 锥规划问题可以很有效的求解 近年来 人们越来越重视锥觌 划问题 原因在于在过去的二十几年里 线性规划的内点算法发生了很大的改 进 将它推广到锥规划时意外地获得了多项式时间方法1 1 这就为线性规划所不 能处理的问题开辟了新的领域 现在主要应用在控制理论 组合优化等等 本文所讨论的锥规划问题是非线性规划 凸规划中比较特殊的一类规 划 也是运筹学领域的一个重要分支 其主要目的是在约束集 凸锥与仿射空间 的交集 下 依靠某些决策变量的取值使得线性目标函数达到极大或极小值 1 2 锥规划及其对偶锥规划模型及国内外研究现状 现在为众多学者推荐的锥规划标准模型为 5 武汉理工大学硕士学位论文 p m i l lc 上 s l 产乱 l z c 其l a g r a n g e 对偶锥规划问题为 m a x y r b d s c 一爿7 v c 类似于线性规划 我们引入松弛变量s 后 将对偶问题化为以下形式 m a x v b j 阳7 y sac c 其中b y e r 鼠s e r 8 a x y 是一个有限维实向量空间上的线性算子 x r 一 y r 锥c 是正则锥 c 是锥c 的对偶锥 a 7 是a 的伴随算子 2 0 0 0 年 f r a n c o i sg l i a e u r 受到一般锥的启发 提出z 范数的锥也有类似的 对偶结果 即 一对可行的对偶f 范数的锥满足弱对偶性质 而且除了这一点 之外 它还有其它的两个性质 1 最优对偶间隙为零 2 至少有一个可行 解使得目标达到最优 m 这些结果也由p e t e r s o n e c k e r 给出 6 1 最近 t e d a k y 运用 标准的凸对偶理论 即凸f a r k a r s 定理 对此也有阐述i 蚓 2 0 0 4 年6 月 s i m o n p s c h u r r 等人提出在凸锥规划及其对偶锥规划中具有所谓的全局对偶性质 当然 约束条件必须具备三个性质 1 如果约束条件不满足 对偶间隙就不为零 2 条件具有可度量性和拓扑几何性 3 它们都可以转化为求解单一凸锥规划问 题 1 4 1 9 9 9 年 r o b e f l f r e u n d 等人利用条件测度研究出了锥线性系统的所谓 不 适定性距离 的一些特征 并且给出了条件测度和这个 不适定性距离 的相互关 系 1 0 1 关于锥规划的算法 1 9 5 8 年至1 9 6 2 年期间 r o s e n b l a t t 提出了感知算法 d a n t z i g 提出把收敛算法转换为多项式有界算法 1 j 1 9 9 4 年n e s t e r o v 和 n e m i r o v s k i i 提出了凸规划中应用内点多项式算法 1 4 j 对于线性不等式组系统 g o f f i n 提出了松弛算法 映射算法 2 0 0 0 年 p e n a r e n e g a r 提出 一旦内点算法 的迭代超过某个临界值 凸锥系统应用内点算法就会产生向前近似解和向后近 似解 3 2 1 2 0 0 2 年m a n u la n u n e l 对不适定的凸锥规划的特征给出了进一步的说 明 矧 武汉理工大学硕士学位论文 1 3 研究内容及提要 本文着重是对锥规划及其对偶锥规划的若干性质进行了研究 例如解的存 在性 弱对偶性 强对偶性 零对偶间隙的存在条件 泛对偶性 以及这两个 规划在实际中的应用问题进行了较为细致的探讨 具体内容安排如下 1 第二章在简单回顾了凸集的定义后引出了锥及其对偶锥的概念 而且还 介绍了几类特殊锥及其对偶锥的各种性质 2 第三章以常见的线性规划为基础 主要对锥规划及其对偶锥规划的基本 性质作了较为细致的阐述 例如这两个规划的解的存在性 弱对偶性 强对偶 性 齐次模型判断解的存在性 k k t 条件以及泛对偶性等等 3 第四章列举了规划在实践中的应用 4 第五章对两个规划进行总结 并提出今后的研究方向和展望 武汉理工大学硕士学位论文 第二章锥及其对偶锥的性质 在这一章里 我们将对各种常见的锥及其性质加以简单介绍 并限制在n 维 e u c l i d 空间e 内讨论问题 2 1 锥及其对偶锥的性质 2 1 1 锥及其性质 凸集是规划问题中必然要涉及到的基本概念 首先介绍凸集的相关知识 集合s 是凸集当且仅当对溉 e s 以及任意实数 o i 一1 k 七 2 都 i 有荟 工 s 其中善 1 设 c r 4 若对任意的 y 肘 均有 1 一 扛 毋 肼 其中h e r 则 称膨为仿射集 对mcr 1 必定存在唯一 个包含膨的最小的仿射集 我们记 为删 下面介绍内点和闭包 设s c e 4 i 己i n t s t x l 丑v 0 s j 也 砷c s j 为s 的内点集合 d s 4 弋 g s 的 闭包 g s c e r i s x e a f f s l 3 s o 培 n 秘 c s b 仁k s l j 则称 r i s 为s 的相对内点 设毒 e 集合c e 5 称为以善 为顶点的锥 如果对一切x e c a 0 都有工o a 一茗o e c 本文主要讨论以x oi0 为顶点的锥 简称为锥 锥的顶点不一定属于锥 但 一定属于锥的闭包 锥不一定是凸集 也不一定是闭集 可以既非闭又非开集 当 锥不仅只包含零向量时 一定是无界集 定义2 1 对于集合c 如果对v x e c 以及任意的实数a 0 均有缸 c 则称c 为锥 c o n e 根据锥c 的定义2 1 显然有0 e c 定义2 2 如果锥c c e 4 是凸集 则称c 为凸锥 c o n v e x c o n e 武汉理工大学硕士学位论文 特别地 当锥c 为闭集时 称c 为闭凸锥 c l o s e dc o n v e xc o n e 我们规定 空集既是锥又是凸锥 凸锥具有闭性 是指如果a e c i 1 2 i m 吼一n 一日e c 我们约定以后在说到闭凸锥c 时 指的是 1 锥c 具有凸性 2 是以x 0 为顶点的锥 3 锥c 是闭的 在得到锥的性质之前 我们先看一下凸集的性质 用记号t 石 y x r y 表示 c a r t e s i a n 内积 性质2 1 若s 为凸集 则c 盥也为凸集 由此可以知道 若c 为凸锥 n c l c 也为凸锥 性质2 2 若s 为凸集 则觑心也为凸集 性质2 0 设凸集最 s 2 e 贝l j r i s l s 2 1r i s 一r i s 2 定理2 1 锥c 是凸锥当且仅当垤 e c 任意数口 o i 1 k k 苫2 均有 i 口一一e c 用归纳法可证 命题2 1 锥c 为凸锥的充要条件是对v x y c 有t t t x 卢y c 其中口 卢是 任意的非负实数 命题2 2 若c 为锥 n c 为凸锥的充要条件是对魄 y c 有石 y e c 这也就是说 锥c 对加法满足封闭性 据此可以很容易推导出 若c 为凸锥 x e i n t c 则工 cc i n t c 定理2 2 1 任意多个凸锥的交仍是凸锥 2 若c 1 巴是凸锥 则c 1 c 也是凸锥 其中 c 1 c 2 一仁 y c e c l y c c 2 证明 由命题2 2 直接可得 设非空集合c e 称c 一1 k 7 ys o 慨 c 成立 为c 的极锥 p o l a rc o n e 或负极锥 特别地 当c 毋时 我们规定c e 定理2 3 1 1 4 1 设闭凸锥c e 4 则层 c c 2 1 2 对偶锥的性质 武汉理工大学硕士学位论文 定义2 3 如果c 是凸锥 我4 f 1 记c 一仁k 7 y o v y e c 称c 为锥c 的对 偶锥 d u a lc o n e 命题2 3 锥c 是闭凸锥 则对偶锥c 也是闭凸锥 证明 因为o e c 所以o c 即c 非空 任取y l y e c 则根据对偶锥 的定义 对每一个x e c a 芦 0 有 掣 缈 7 工 0 所以c 是凸锥 又设y i c f 1 2 z i m y f y 所以对每一z c 有儿7 z 苫0 即有 了7 x 苫o 这说明了 c 即c 是闭的 根据对偶锥的定义很容易得到 若锥c 彤 仁 r k zo j 则c z 0 若锥c o 贝u c r 7 定理2 4 设c c 是两个闭凸锥 则c nc c c 证明 因为c i c 是闭凸锥 任取x e c l c 根据对偶锥的定义 则有 工7 也 z 2 苫0 其中耳e c l z 2 c 2 又o c ln c 2 所以z 7 2 1 0 r x 7 x 2 苫0 这即是说x e c n c 定理2 5 设c 是r 4 中凸锥 m e r 是可逆矩阵 则似7 c 一m 1 c 其 中m 7 c 一仁i z m 7 z x e c 证明 任取 e m 7 c x e c y r m 7 工 0 卿 7 工 0 则存在 2 c s a t m y z t 得y m 1 z 膨7 c m 1 c 争y 膨 1 c 其中的不等 式关键用到了锥与对偶锥的关系 定义2 4 若锥c 的内点非空 i n t c 我们称之为立体锥 s o l i d 如果凸 锥c n 一c 一 o 我们称它为尖锥o o i n t e d 其中一c 铂一x c 也就是说对 x c 叫 c 则有工一0 若闭凸锥c 的内点非空 尖锥 则称此锥为正则锥 f u l lc o n e 也有学者 称此锥为p r o p e rc o l l e 或r e g u l a rc o n e 若锥c 是闭凸锥 则锥c 是正则锥当且仅当对偶锥c 是正则锥 根据凸分析的有关知识 有以下引理 引理2 1 切 1 6 j 令a r 一r 是一个线性算子 令s 墨 s 是r 一中的凸子 集 则 1 r i c l r i s c t r i c l 岱 2 r i s 1 f 2 r i 1 s 2 3 r i 0 a r i p 1 0 武汉理工大学硕士学位论文 4 若s 为凸锥 则s c l s 有时也称为双极定理 b i p o l a r t h e r o e m 特别地 如果s 为闭凸锥 则有s 一s 这一结果说明了锥规划与其对偶锥规 划有极好的对称性 5 如果s 5 都是闭凸锥 贝u c z s l s 24 p 1r t s 6 若s 为闭凸锥 则s 是尖锥当且仅当它的对偶锥s 也是尖锥 定理2 6 若锥q c 2 是非空的 r c c 则c c 2 证明 由于锥c 1 c 2 是非空的 由引理2 1 任取y c c 又c 12 c 取 x e c c 由对偶锥的定义 有y j 工 0 即是说y e 引理2 2 f 1 7 若c 为闭凸锥 y 诺c 则存在a e a 0 使得对v x e c 有 a t x 0 a r y o 定理2 7 若c 为闭凸锥 则c 一c 其中锥c 一 c j 证明 证法 i 由引理2 1 4 可证 i i 下面利用集合的包含关系证明 由对偶锥的定义不难得到 c c 下面证明 c c 假设存在y e c y 诺c 由引理2 2 存在a 一0 使得 对比 c 有n 7 工 0 a r y o 记 i n 即对于坛 c 都有 7 x 0 x o r y o 所以 c 但由于 7 y 0 可知y 圣c 矛盾 引理2 3 1 1 7 j 设s 为凸集 e i n t s y oe s a o 1 则有缸o 1 一a y oe i n t s 定理2 8 设c 为凸锥 i n t c 庐 则伽f c c 证明 因为i n t c c 由定理2 6 可知 z n t c c 又i n t c 西 取 y ou i n t c 对于任意膏o 心厂 及 c 帆e 0 4 1 由引理2 3 有 毋o 1 一a 弦i n t c 根据对偶锥的定义 有工0 2 x y o 1 一z x 苫o 令a 一0 则 对慨 c 有 7 z 0 放 c 即得 z n t c c 综上可得 i n t c ac 引理2 4 f 1 7 1 若仁k 7 y o v yc l c y o l 驴 用c l c 表示c 的闭包 则 铷7 y o c f c y o f i n t c 证明 假设存在点上 仁k 7 y o c l c y o l 且x 譬如酊 取一个序 列概 满足躲瓯一o 其中瓯 o 因为聋隹砌f c 对于椎 k 臣j t c 所 l i e 峥1 n l i m o y 一歹 则歹 c i c 歹一0 所以 歹 煳 7 y s 0 这与 武汉理工大学硕士学位论文 z 扛k 7 y o v y e c l c y o 矛盾 定理2 9 若i n t c n i n t c 仁k 7 y o v yc l c y 0 1 证明 首先证明i n t c 仁k 7 y o v yc l c y o 对于任意x e i n t c 存在d o f f n d 扛o c 故对 e c l c y 0 存在 a 0 使得z o 一砂 6 g o c 从而对v yc l c y 0 有 一砂 7 y2 0 即x 7 y 一 w 0 街l j x o y a 2 o 所以 龇7 y o v y c l c y o i 由引理2 4 得仁k 7 y o v y e c l c y o j i n t c 故如f c x l z 7 y 0 v yc l c y 0 推论2 1 若c 为闭凸锥 且如酊一毋 证明 因为c 是闭凸锥 由定理2 8 凸锥 则有c l c c 根据定理2 9 可知 贝j j i n t c 一体7 y 0 v y s c y o t 可以知道 c 一c 又因为c 也是闭 每k o v y e c l c y o 一k k y o v y c y o j 2 2 几类特殊锥与其对偶锥的性质 定义2 5 设c 是锥 r i n t c 妒 如果存在开半空间圩1 仁k o 满足 c l c c h l u o 则称c 为钝锥 o b t u s e c o n e 定理2 1 0 锥c 为钝锥的充要条件是i n t c 曲 证明 首先证明必要性 设c 为钝锥 受1 j 由定义可知 存在开半空间 h 扛j a r x o 协足c 1 c c h u 0 对于v y c l c y 0 f f a 7 y 0 即口 似7 y o v y c l c y o t 所以 d i n t c i n t c 毋 再证明充分性 i n t c 妒 由定理2 9 知扛k 7 o v y c z c y o t 庐 取 口 扛k 7 y o v y c 圮 y o t 4 e n l 体k 0 有 c l c c h u 0 由定义知 c 为钝锥 定义2 6 设c 为锥 如果对x c 当且仅当对v y c 有z 7 y 0 则称c 为 直角锥 o r t h o g o n a lc o n e 不难得到直角锥c 也是闭凸锥 武汉理工大学硕士学位论文 又由对偶锥的定义直接得 定理2 1 1 若c 为锥 则c 为直角锥的充要条件是c c 定义2 7 设c 为钝锥 如果存在直角锥c7 使得c c 则称c 为劣钝锥 如果存在直角锥c7 使得c c 则称c 为优钝锥 定理2 1 2 1 若c 为劣钝锥 则c 为优钝锥 且c c 2 若c 为优钝锥 则c 为劣钝锥 且c c 证明 1 若c 为劣钝锥 则由定义2 7 存在直角锥c 使得c c 由 定理2 6 c c 又由于c7 是直角锥 由定理2 1 1 有c c 即得 c c g c 故有c c c 即c 为优钝锥 2 的证明与上相仿 推论2 2c 为劣钝锥的充要条件是c 为优钝锥 c 为优钝锥的充要条件是 c 为劣钝锥 武汉理工大学硕士学位论文 第三章锥规划及其对偶锥规划的基本性质 3 1 规划问题的对偶理论 d u a ii t yt h e o r y 称 对规划问题关于某种含义的最优解 如有效解或弱有效解 是对偶的 是指它们满足下面的条件 1 它们中一个是极小化问题 另一个是极大化问题 2 极小化问题的任意可行解之相应的目标函数值 或标量化值 总是不 小于极大化问题的任意可行解之相应的目标函数值 或标量化值 3 它们中若一个问题存在某种含义的最优解 则另一问题也一定存在该 含义的最优解 而且相应的最优目标函数值 或标量化值 相等 对偶理论的主要内容是 在给定原问题之后 如何建立其相应的对偶问题 使其满足上述三个条件 其中第一个条件在建立对偶问题时 自然就做到了 而 第二个和第三个条件的验证是比较困难的 在对偶理论中通常把第二个条件叙述 为弱对偶定理 而把第三个条件叙述为强对偶定理 或者分述为直接对偶与逆 对偶两个定理 对偶理论深刻揭示了原问题与对偶问题的内在联系 为进一步深入研究各 种规划的理论和算法提供了基础 假设给定的原问题和所建立的对偶问题分别为 p i n 蜘1 x d 警g 0 其中 o g 0 均为向量值函数 丁 5 分别为p l d 的可行集 x 甜称为一对对 偶变量 d u a lv a r i a b l e 这样 对偶定理就可以这样叙述 弱对偶定理 w e a k d u a l i t y t h e o r e m 对任意的x e t 及 e s 都有i x 芑g 缸 或者存在权向量 n 使得标量化值r 仁 乏仃7 g 弱对偶理论说明 对偶问题的任何可行解的目标值都是原问题的任何可行 解的目标值的一个下界 强对偶定3 望 s t r o n gd u a l i t yt h e o r e m 若 尸 存在某种含义的最优解x 则 武汉理工大学硕士学位论文 d t 也存在该含义的最优解h 而且有f x g m 或者存在权向量a n 使得标量化值a b z g 0 假设线性规划的原一对偶规划有可行解 那么对偶规划问题的极大值一定 等于原规划问题的极小值 即对偶间隙等于零 对于锥规划来说 这一结论未必 成立 同理 线性规划的对偶定理包括弱对偶定理 强对偶定理 互补松弛性质 由此得到了对偶单纯形算法 对于锥规划来说 事情远远没有这么简单 3 2 锥规划与对偶锥规划解的存在性 先回忆一下线性规划的相关知识 假设原问题的约束条件全部是等式约束 这里 我们考虑的是线性规划的 标准型 即 m i l l z c t x r 4r b 3 1 t x o 则其l a g r a n g e 对偶