双层规划对偶理论及应用

《双层规划对偶理论及应用》由会员分享，可在线阅读，更多相关《双层规划对偶理论及应用（82页珍藏版）》请在金锄头文库上搜索。

1、一一 一一 一一 一一 一 一一 一一 一山 东大学博士学位论文双层规划的对偶理论及其应用宿 洁 山东大学 数学与系 统科学学院摘要随着科学技术的发展和实际应用范围的扩展，人们研究的对象逐步由描述简 单系统优化问题的数学规划模型转向了描述复杂系统优化问题的数学规划模型. 对复杂的数学规划问题的研究正成为规划论的一个重要领域。而作为数学规划理 论的一个重要内容一一对偶理论，对于研究数学规划的最优性条件及算法的设计 等有重要的作用。本文的主要工作就是讨论几类双层规划的对偶理论，以及对偶理论在算法设 计中的应用。伍第 一 章 中 ， 首 先 简 单 回 顾 了 数 学 规 划 理 论 的 发 展 历

2、 史 : 从 ; 9 4 : 年 线 性 规 划 的产生到2 0 世纪7 0 年代， 规划理论先后经历了从线性到非线性、从连续到离散、 从确定到动态的发展过程: 进入2 0 世纪8 0 年代后，规划理论又有新的发展 由 对简单系统优化问题的描述发展到对复杂系统优化问题的描述，因此，新的数 学规划形势就应运而生。然后，又简要介绍了 数学规划的 对偶规划的多种形式以 及对偶理论从特殊到 一般的发展过程。最 后， 在 1 .3 中， 以 一 般凸 规 划( 1 .3 . 1 ) 的 三种 对 偶形式L a g r a n g e 对 偶 ( L D ) , S u b g r a d ie n t

3、对 偶 ( S D ) 和W o l f e 对 偶 ( ” ) 为 例， 讨论 一 般凸 规 划的 对 偶 形 式 之间 统 一性，得到三种对偶形式之间的关系为:定 理 1 .3 . 1 3设 在规 划( 1 .3 . 1 ) 中f ， 9 (i = 1，.， m)为凸 集C E R “ 上的 次 可 微凸 函 数，则对偶形式L D与S D等价。引 理 1 .3 . 1 4设 在规 划( 1 .3 . 1 ) 中f , 8 , ( i = 1 ,.二 ， m ) 为凸 集C E R “ 上的 可微凸 函 数 且y 2 0 ， 则 规 划( 1 .3 . 1 ) 的 对 偶 形 式S D 与R

4、 ，相同。第二章中， 利用J o h r i 对偶的思想， 考虑三类值型双层规划的对偶规划形式及 其对偶性质。在 势 2 . 1 中 ， 考 虑非 减 值 型 双线 性 双 层 规划的 对 偶。 首 先， 给出 值 型 双 线 性 双 层规划的一般形式，并分析了非增值型双线性双层规划与非减值型双线性双层规山东大学博士学位论文 三巴，巴，=巴巴巴=巴巴巴巴巴巴 划 的 区 别 。 然 后 ， 讨 论 非 减 值 型 双 线 性 双 层 规 划( 2 . 1 .3 ) 的J o h ri 对 偶 ， 得 到 其 对 偶 为 非 减 值型 双 线 性双 层规 划( 2 . 1 . 1 0 ) .分

5、析 其 对 偶 性 质， 可 得 双 层 规 划( 2 . 1 .3 ) 和 对 偶 双 层 规划( 2 . 1 . 1 0 ) 之间 对 偶间 隙 为零的条件:定 理2 . 1 . 1 4 双 层 规 划( 2 . 1 .3 ) 和 对 偶 双 层 规 划( 2 . 1 . 1 0 ) 有 最 优 解 且 其 对 偶间 隙 等 于 零的 充 分 必 要 条 件是 交 叉 规 划【 4 4 ( 2 . 1 . 1 5 ) 有 均 衡 解。.进 一 步， 考 虑 双 层 规 划( 2 . 1 .3 ) 和( 2 . 1 . 1 0 ) 的 最 优 解与 交 叉 规 划( 2 . 1 . 1 5

6、) 的 均衡 解之间的关系，有:推 论2 . 1 . 1 6 若( x , 幻是 交 叉 规 划( 2 . 1 . 1 5 ) 的 均衡 解， 则 其同 时 也 是 双 层 规划户 ( 2 . 1 .8 ) 和双层规划( 2 . 1 . 1 2 ) 的 最 优解。推 论2 . 1 . 1 7 若( X , 乃、 ( z , 匀分 别 为 双 层 规 划( 2 . 1 .1 2 ) 和 双 层 规 划( 2 . 1 .8 ) 的 最 优 解 ， 且 其 对 应 的 最 优 值 相 等 ， 则( X , 为、 ( z , 乃均 是 交 叉 规 划( 2 . 1 . 1 5 ) 的 均 衡 解。在

7、2 .2 中， 考虑值型凸二次双层规划的 对偶。 首先， 给出 值型凸二次双层规 划的一般形式，并把一般值型凸二次双层规划等价转化为非增值型凸二次双层规 划的 形式。 然后， 讨论非减 值型凸 二次 双层规 划( 2 .2 . 1 ) 的J o h r i 对偶， 得到其对偶 为非 减 值型凸 二次双层规划( 2 .2 . 1 1 ) .进 一步 分 析， 可知 该 对 偶 形 式 具 有强 对 偶 性， 且 双 层规 划( 2 .2 . 1 ) 和 对偶 双 层规 划( 2 .2 . 1 1 ) 的 最 优解 之间 满足 如 下关 系:定 理2 .2 . 1 5 若( x , Y ) 是 双

8、 层 规 划( 2 .2 . 1 ) 的 最 优解， 且( u , v ) 是 规 划( 2 .2 .6 ) 的 参 变 量 为: 时 的 最 优解， ( A , ,u ) 是 规 划( 2 .2 . 1 0 ) 的 参 变 量 为v 时的 最 优解， 则( u , v , A , ,U ) 是 双层 规划( 2 .2 . 1 1 ) 的 最优解， 且对应的 最 优值 相等。推论2 . 2 . 1 6若( u , v , ) 是双层规划( 2 .2 . 1 1 ) 的最优解， 且x 是双层规划( 2 .2 .9 ) 下层 子规划的 参变量为v 时的 最 优解， Y 是 双 层规划 .( 2 .

9、2 . 1 ) 下层子规 划的 参 变A为 x 时 的 最 优 解， 则( x , 力为 双 层规 划( 2 .2 . 1 ) 的 最 优 解， 且 对应的 最 优 值相 等。在虽2 . 3 中， 讨论一类特殊的值型凸 双层规划一一下层只含线性约束的 值型凸 规划的对偶。首先给出该类值型凸双层规划的一般形式，并把该类值型凸双层规 划的一般形式等价转化为非增值型凸双层规划的形式。然后，讨论该类非减值型 凸 双 层规划( 2 . 3 . 1 ) 的J o h ri 对偶， 得 到其 对偶 为 双层规划( 2 . 3 . 1 1 ) .考 虑 对 偶 性 质可 知， 该 对偶 形 式 具 有强 对

10、偶 性， 且 双层 规 划( 2 .3 . 1 ) 与 对 偶双 层 规 划( 2 . 3 . 1 1 ) 的 最 优解之间满 足如下 关系:定 理2 .3 .1 3若( X , y ) 是 双 层 规 划( 2 .3 . 1 ) 的 最 优解， 且( u , v ) 是规 划( 2 .3 .7 ) 的 参 变 量为x 时的 最 优 解， RP ) 是 规 划( 2 .3 . 1 0 ) 的 参 变量 为， 时的 最 优 解， 则( u , v , A , At ) 是双层规划( 2 .3 . 1 1 ) 的最优解。第三章利用D C 规划共扼对偶的思想， 考虑解型线性双层规划的对偶形式及其薇绷

11、 从牡默她玲山东大学博士学位论文 二二二二二巴二二二二二二巴巴三巴 对偶性质。在号3 . 1 中， 首先给出D C 函数和D C 规划的基本概念及性质; 然后， 将一般形 式的 解型 线 性双层规 划( 3 . 1 . 8 ) 转化为 一 个含均衡约束的规 划( 3 . 1 . 1 3 ) ， 且有:定 理3 . 1 . 1 2 双层规划( 3 . 1 . 8 ) 中，( x , 刃e, 的 充分必要条件为 存在X E 尸使得 ( x , Y , A ) 是单层规划( 3 . 1 . 1 3 ) 的 可行解。进一步， 把含均衡约束的规划( 3 . 1 . 1 3 ) 转化为一个标准形式的D C

12、 规划( 3 . 1 . 1 7 ) :定理3 . 1 . 1 6 ( x , 犷， 厂) 是含均衡约束的规划( 3 . 1 . 1 3 ) 的最优解的充分必要条件 为( x， 犷， d ) 也是单层规划( 3 . 1 . 1 7 ) 的最优解，且两个规划的最优值相等。从而，把解型线性双层规划问题转化为D C 规划问题。在夸3 .2 中， 首先介绍了D C 规划的 共辘对偶的形式及其性质。 然后，利用D C 规划( 3 . 1 . 1 7 ) 的 共扼对偶， 得到了 解型线性双层规划( 3 . 1 . 8 ) 的共辘对偶形式 值 型双层规划( 3 .2 . 1 5 ) ，并给出 该对偶形式的强

13、对偶性质:定理3 .2 . 1 6值型双层规划( 3 .2 . 1 5 ) 的 最优值与解型双层规划( 3 . 1 . 8 ) 的 最优值相 等。由于某些数学规划与其对偶规划之间存在着很好的对偶性质，而且对偶规划 的形式比原规划的形式简单。因此，在求解这些数学规划时，就可以考虑通过对 偶理论把较为复杂的原规划变为较为简单的对偶规划，在求得对偶规划的最优解 后，再利用对偶性质，找到原规划相应的最优解，从而较好的解决原问题。故而，在第四章中，主要讨论几类数学规划问题的根据其对偶理论而设计的 算法。在 4 . 1 中， 讨论了 上层子规划的 约束中 仅有变量非负约束( p = 0 ) 和上层子规 划

14、仅 有单个约束 ( p = 1 ) 的两类特殊的值型线性双层规划的多项式时间算法。在讨论上层子规划的约束中仅有变量非负约束( p = 0 ) 的值型线性双层规划 ( 4 . 1 .9 ) 的 算法时， 首先给出 双层规划( 4 . 1 . 9 ) 与其对偶双 层规划( 4 . 1 . 1 0 ) 的 最优解 之 间的关系:引 理 4 . 1 . 1 1 4 8 若( X , x ) 是双层规划( 4 . 1 . 1 0 ) 的 最优解， 且犷是双层规划 ( 4 . 1 .9 ) 下层子规 划参 变量为x的 最 优解， 则( x， 犷) 为 双层规 划( 4 . 1 . 9 ) 的 最优解。然后

15、， 建立双层规划( 4 . 1 . 1 0 ) 的最优解与线性规划( 4 . 1 . 1 2 ) 的最优解之间的关 系:定 理4 . 1 . 1 3 若A . 是 线 性 规 划( 4 . 1 . 1 2 ) 的 最 优解， 且x = 0 ， 则( A . ， X . ) 是 双 层规 划( 4 . 1 . 1 0 ) 的 最 优 解， 且 线 性 规 划( 4 . 1 . 1 2 ) 的 最 优值 与 双 层 规 划( 4 . 1 . 1 0 ) 的 最 优 值 相 等。 并且， 若线性规划( 4 . 1 . 1 2 ) 无可行解，则双层规划( 4 . 1 . 1 0 ) 无最优解。从 而，

16、 把对 值型线性双层规划( 4 . 1 .9 ) 的 求解转化为对一个线性规划( 4 . 1 . 1 2 ) 的 求解，因此， 双层规划( 4 . 1 . 9 ) 就有多项式时间算法.山东大学博士学位论文在讨 论上 层子 规划仅有 单个 约束 ( p = 1 ) 的 值型线 性双层规划( 4 . 1 . 1 7 ) 的 算 法 时， 先根据 2 .2 中的结论给出 其对偶双 层规划( 4 . 1 . 1 8 ) ， 再根据参数b 的正负取值， 把对双层规划( 4 . 1 . 1 8 ) 的求解分为三种情况处理:当b = 0 时，双层规划( 4 . 1 . 1 8 ) 就可写为线性规划( 4 . 1 .2 0 ) ;当b 0 时， 双层规划( 4 . 1 . 1 8 ) 的 最优值就等于如下至多( m + 1 ) 个线性规划问 题m a xA E s , 全 *