（计算数学专业论文）变分不等式的一些应用.pdf

目录 f i r lflil i tii i iti i i iiii 17 2 7 9 9 9 摘要 i i a b s t r a c ti i i 第一章绪论 1 1 1自由竞争的代价 1 1 2 连续化方法 2 1 3 分裂可行性问题 3 1 4 预备知识 5 1 5 本文结构 8 第二章校正的p r i c eo f a n a r c h y 界限 9 2 1 引言 9 2 2 最佳界限 1 0 2 3 两种界限的差异 1 3 第三章连续化方法的应用及改进1 4 3 1 引言 1 4 3 2 问题分析 1 5 3 3 新的算法 1 8 3 4 收敛性分析 1 9 3 5 数值实验 2 1 第四章非线性分裂可行性问题2 6 4 1 引言 2 6 4 2 问题分析 2 7 4 3 自适应投影梯度法 2 9 4 4 收敛性分析 3 1 4 5 数值实验3 5 第五章结论4 0 参考文献4 1 附录攻读硕士学位期间的研究成果4 5 致谢4 6 摘要 摘要 变分不等式问题是指，在非空闭凸集q 舻上找一点z ，使得 ( z z + ) t ，( z + ) 0 ，v z q ， 其中厂为形一r 他的一个线性的或非线性的映射变分不等式问题的数学理论最 初应用于解决均衡问题，在此模型中，函数来自对应势能的一阶变分，因此在命名 时叫作变分不等式问题变分不等式问题在数学规划，交通规划，网络经济，最优决 策以及区域科学等诸多领域都有广泛应用，本文主要研究变分不等式问题的几个 简单应用 首先，本文考虑一个自由竞争状态下用户均衡与系统最优两种情况下系统总费 用比率的界限问题p e r a k i s 通过考虑一个不可分，非对称且非线性的价值函数，定 义并给出了一个费用比率的界限我们通过分析原最优化问题的最优性条件，得到 了一个比p e r a k i s 给出的界限更为准确的界限 其次本文考虑一个带非凸约束的最优化问题采用g o l u b 和l i a o 连续化求 解主特征值问题的思想，我们将带非凸约束的最优化问题转化为一个带凸约束的 最优化问题然后构造动力系统建立连续化方法，并且借助于求解变分不等式问题 的自适应方法，设计出一个新的求解该问题的离散化方法 最后，本文考虑一类推广的分裂可行性问题，称之为非线性分裂可行性问题 通过分析与之等价的最优化问题，在其目标函数的梯度函数满足l i p s c h i t z 连续性 条件下，我们借助于z h a n g ，h a n 和l i 提出的自适应投影梯度法求解多集分裂可 行性问题的构造思想，设计出一个自适应投影梯度法来求解非线性分裂可行性问 题，并给出收敛性分析和数值实验 关键词：变分不等式，混乱的代价，连续化方法，非线性分裂可行性问题 第一章绪论 在本章，我们首先提出本文将要考虑的三个问题；然后，引入变分不等式问题， 给出求解变分不等式问题的预备知识；最后，给出本文结构 1 1 自由竞争的代价 在过去的2 0 余年里，有限维的变分不等式v i ( f i n i t e d i m e n s i o n a lv a r i a t i o n a l i n e q u a l i t y ) 和非线性互补问题n c p ( n o n l i n e a rc o m p l e m e n t a r i t yp r o b l e m ) 理论取 得了迅猛发展，交通网络均衡模型作为其应用的对象，对变分不等式理论的发展 起了很大的推动作用同时交通网络均衡模型也得到了多方位的发展经济学家 k n i g h t 1 7 】( 1 9 2 4 ) 最早用“均衡”一词来表达交通流形态，w a r d r o p 【3 2 】( 1 9 5 2 ) 提出 了两个著名的出行者路径选择行为准则，由此推出了用户均衡( u s e re q u i l i b r i u m ) 和系统最优( s y s t e mo p t i m u m ) 的概念，b e c k m a n n 等【3 】( 1 9 5 6 ) 的工作使得交通 网络数学均衡分析成为可能，p e r a k i s 【2 2 ，2 3 】也在交通控制管理方面也做出了很多 贡献 我们知道在实际的非合作博弈中，无论是在经济上还是在交通上系统效率都不 可能达到全效，因此很多学者都试图量化n a u s h 均衡问题的效率损失k o u t s o u p i a s 与p a p a d i m i t r i o n 【1 8 】在负载平衡博弈中首次量化了用户均衡的效率损失，他们用 “自由竞争状态下的代价”来刻画效率的损失程度后来，r o u g h g a r d e n 和t a r d o s ( 2 5 ，2 6 】与k o u t s o u p i a s 【2 7 ，2 8 】进一步考虑了该问题，接着人们又在资源分配，交 通和网络流量中研究该问题，并从可分的，对称的，线性的价值函数推广到不可分 的，非对称的，非线性的情况 最近，p e r a k i s 【2 2 1 考虑一个依赖于每一个竞争者策略的不可分的，非对称的， 非线性的价值函数，给出了一个用户均衡与系统最优两种情况下系统总费用比率 的一个界限在【2 2 】中，p e r a k i s 对系统最优的集中问题考虑极小化问题： m i n x r f ( z ) ，( 1 1 1 ) 正k 、一 、 。 对用户均衡的分散问题考虑变分不等式问题：找z u k ，使得对所有的z k 有 ( z z u ) r f ( x u ) 0 ，( 1 1 2 ) 1 第一章绪论 记与为系统最优问题( 1 1 1 ) 与用户均衡问题( 1 1 2 ) 的解，用a = z f ( ) = m 茹i k n x t f ( z ) 表示系统最优时的总费用，g = z t f ( z u ) 表示用户均衡时 的总费用在f 连续可微并满足j a c o b i a n 相似性【3 1 】，且对所有的z k 都有 x t f ( o ) 0 时，p e r a k i s 得到结论： 岳 悫”l ， 扯， p e r a k i s 是通过求解一个二元约束最优化问题得到界限( i i 3 ) 的，然而此界限并不 是最佳的，本文的第一个t 作就是重新分析求解界限( 1 1 3 ) 的原始最优化模型，得 1 2 连续化方法 愁1 2 由于问题( 1 2 1 ) 是极小化单位球面上的一个二次函数，其可行域的非凸性增加了 问题的求解难度2 0 0 6 年g o l u b 和l i a o 【1 2 】引入连续化方法来求解该问题，他们 这里k 是a 的一个极大特征值事实上，由实舒尔定理可知，a 的所有特征值都 是实的，且存在一个正交矩阵u = ( u 1 ，u 2 ，u n ) ，与一个对角矩阵a ，使得 a = u a u t ，( 1 2 3 ) 根据参考文献【1 1 】中推论2 3 2 ，有 。m 、a x 九l = i l g l l 2 i i a l l l ，0 2 4 ) 第一章绪论 从而可以选取c = i i a l l l + 1 满足( 1 2 2 ) ，这样问题( 1 2 1 ) 可以等价地转化为如下 最优化问题 lr a i n x t a x c x t x x e r ” ( 1 2 5 ) 【s t x t x 1 问题( 1 2 5 ) 与问题( 1 2 1 ) 的不同之处在于虽然其目标函数是严格凹的，但其可 行域却是一个简单的球，是一个闭凸集，这使得问题( 1 2 5 ) 在一定程度上比问题 ( 1 2 1 ) 更易于求解为求解问题( 1 2 5 ) ，g o l u b 和l i a o 构造了一个动力系统 掣：一卜忍( z m ) ) 】， ( 1 2 6 ) 这里f ( x ) = ( a c s ) x ，q - - - z r i x t z 1 ) 然后，g o l u b 和l i a o 通过o d e 函 数o d e 4 5 连续地求解了动力系统( 1 2 6 ) ，成功地得n - yi ；- j 题( 1 2 5 ) 的解 g o l u b 和l i a o 考虑的是求解一个对称正定矩阵的主特征值问题然而在很多 实际应用中，如图像恢复【2 0 】，信号处理【1 1 ，网络信息安全【1 9 】，数据谱分析( 2 1 】 等，往往要求得到的解是非负的( 只有非负的解才有意义) 这就要求我们考虑带非 负约束的最优化问题( 1 2 1 ) ，即 ( 1 2 7 ) 本文中我们考虑一个带非负约束的最优化问题( 1 2 7 ) 同样采用连续化方法 的思想，构造动力系统连续地加以求解，并且构造新的算法来提高求解效率，然后 通过数值实验加以验证 1 3 分裂可行性问题 可行性问题是一类重要的数学规划问题，很多最优化问题都可以看成可行性问 题例如，线性规划问题 m i n c t x la x = b ，z o ) ，( 1 3 1 ) 这里a r m 黼记 u = m 帅 z = o 缸 归 。1 而 八1 ， z 肛局 l一删时 第一章绪论 问题( 1 3 1 ) 可转化成找一点u 4 ，使得 矿c ，c = u im u + q = 0 ，n u o 】，( 1 3 2 ) 其中 m = ( 三一拿t ) ，= ( 舌g ) ，6 = ( 三) 问题( 1 3 2 ) 即是一个可行性问题 分裂可行性问题是凸可行性问题的一种，即，给定两个非空闭凸集cc 形与 q r 仇，以及a r m 期，找一个点矿满足 z + c 使得a x + q ( 1 3 3 ) 分裂可行性问题即是从一个闭凸集中找一个点，使其在经过线性变换后属于另一 个集合当c 为一族闭凸集的交集，q 为另一族闭凸集的交集时，问题( 1 3 3 ) 就称 为多集分裂可行性问题，即找一点z + 满足 a x + q ：= nq ， ( 1 3 4 ) j = l 这里闭凸集g 形，i = 1 ，t ，q 冬，j = 1 ，7 ，a r m 黼 分裂可行性问题以及多集分裂可行性问题有着广泛的应用背景，如医学上的调 强放射治疗反问题【8 】，图像重构及信号处理【5 】等目前，求解分裂可行性问题的 方法很多，最典型的方法之一就是投影法从1 9 9 4 年c e n s o r 和e l f v i n g 【6 】首次提 出分裂可行性问题，并利用投影法加以求解，到2 0 0 9 年z h a n g ，h a n 和l i 【3 5 】提 出的自适应投影法求解多集分裂可行性问题，投影法求解分裂可行性问题的应用 范围越来越广，效果也越来越好 分裂可行性问题或多集分裂可行性问题中的映射是线性的，在某些复杂问题 中，往往模型中涉及的映射是非线性的另一方面，所有的投影算法都要求所涉及 到的集合是“简单的”才能有效求解，而实际中所涉及的集合往往是复杂的( 如人体 器官通常并不规则) 对这种“复杂的”集合的情况，一个简单的思想是通过某种转 换，将其转化为“简单的”集合的情况，从而得到的分裂可行性问题就成为了一个非 线性分裂可行性问题 4 得使a 。n 龇 = d 护 第一章绪论 本文中，我们考虑非线性分裂可行性i ；1 题类似于投影法求解分裂可行性问题， 我们也利用投影映射将非线性分裂可行性问题转化为与之等价的最优化问题，并且 在适当的条件下构造自适应投影梯度算法，最后通过数值实验验证算法的有效性 下面我们给出本文将要用到的一些预备知识 1 4 预备知识 本节，我们给出一些基本概念和性质 变分不等式问题是指，在非空闭凸集q r n 上找一点x + ，使得 ( z z + ) r ，( z + ) 0 ，v z q ，( 1 4 1 ) 其中，为舻_ 舻的一个线性的或非线性的映射我们把变分不等式问题( 1 4 1 ) 记作v i ( f l ，厂) v i ( f 2 ，f ) 问题包括互补问题( 当q = 僻时) 与方程组问题( 当 q = r n 时) 等，它在数学规划，交通规划，网络经济，最优决策以及区域科学等诸多 领域都有广泛应用，见参考文献【9 】等 忙l i = 伍表示z 的2 。范数，r ( ) 表示到q 上的投影映射，即 玮( z ) = a r g m i n 恬一z y q ) ( 1 4 2 ) 当q 是非负卦限( z 胛i z o ) 时，有 ( 坼执：卜 辄p0 10 ， 否则； 当q 是一个盒子 z r n a z b ，a ，b 研 i 时，有 io ， 若戤 0 ) 时，有 一裂g 。i i ” 根据投影映射的定义( 1 4 2 ) ，投影映射具有如下重要性质： 第一章绪论 引理1 4 1 若qs p 为一非空闭凸集，r ( ) 为册到q 上的投影映射，则 对任意z ，y r n ，任意z q ，有 【o ) x s 2 禽p a 【z ) = z ； ( 6 ) ( x 一昂( z ) ) t ( z p q ( z ) ) 0 ； ( c ) 1 f p , ( x ) 一玮( 耖) i | 2 ( z 一可) 丁( r ( z ) 一r ( 可) ) ； ( d ) i i 玮( z ) z l l 2 i l z 一名0 2 一l i 局( z ) 一z i l 2 ； ( e ) | l f b ( z ) 一f h ( 秒) 0 j l z 一暑； ( ，) i i r ( z ) 一p , ( y ) 1 1 2 i i z 一可j j 2 一i l 忍( z ) 一z + y p , ( y ) 1 1 2 证明：见参考文献【9 】 下面给出几个重要的引理 ( 1 4 3 ) ( 1 4 4 ) ( 1 4 5 ) ( 1 4 6 ) ( 1 4 7 ) ( 1 4 8 ) 口 引理1 4 2 对任意p 0 ，矿q 是变分不等式问题v i ( q ，) 的解的充分必 要条件是 x = r ( z 一卢，( z + ) ) ( 1 4 9 ) 证明：见参考文献【9 】 口 由以上引理知，解变分不等式问题( 1 4 1 ) 等价于求解l ；- j 题( 1 4 9 ) 记 e ( z ，卢) = 2 一昂( z p ，( z ) ) 根据以上定义及引理1 4 2 ，易知e ( z + ，p ) = 0 我们有如下结论 引理1 4 3 解v i ( q ，厂) 问题等价于找e ( z ，p ) 的一个零点 证明：见参考文献【9 ，3 6 】 口 由以上引理可知，e ( z ，p ) 评价了点z 与解矿之间的远离程度对于评价函数 e ( z ，p ) ，有如下单调性性质 引理1 4 4 对任意z 肝，任意声 p 0 ，有如下关系式成立 愀z ，z ) i i 愀z ，z ) l l ， ( 1 4 1 0 ) 与 訾掣螳掣 ( 1 4 1 1 ) a 6 第一章绪论 证明：见参考文献【3 6 】 口 以下两个引理都是数学分析中的基本结论，在后面的收敛性分析中将会用到 引理1 4 5 设 亿) 怨1 为一非负数列，且对所有的k ，亿( 0 ，1 ) 如果 h ( 1 一亿) 0 ，则有 南= 1 ( i ) 仉 0 ， n ( 1 + 入r ) 0 ，使得f 满足 ( z 一秒) r ( ，( z ) 一，( 秒) ) i l ，( z ) 一f ( y ) 1 1 2 ，v z ，y 1 2 ；( 1 4 1 4 ) ( d ) 称，在q 上是l i p s c h i t z 连续的，且l i p s c h i t z 系数为l 0 ，如果，满足 i f 厂( z ) 一( u ) l i l l | z y i | ，v x ，y g t ；( 1 4 1 5 ) 根据以上定义可知，余强制函数是单调的，但不一定严格单调或强单调；反之， 强单调的l i p s c h i t z 函数一定是余强制的 7 + 丢，则z ：= 砑1 ，。；= t c a a ，目标函数的最优值为c 2 a 2 2 ( a 一1 ) 从而由p e r a k i s 定义的p r i c eo fa n a r c h y 界限为 譬，南 若孑； ( 2 忱) 蚓震”1 ，万 协1 2 ， 这里瓯与g 分别表示用户均衡与系统最优情况下的系统总费用 p e r a k i s 的结论是k o u t s o u p i a s 和p a p a d i m i t r i o n 【1 8 】与r o u g h g a r d e n 和t a r d o s 【2 5 】从可分的，对称的，线性情况到不可分的，非对称的，非线性情况的开创性工作 的一个推广p e r a k i s 的分析结合了一些当前的最优化理论成果，如内点算法，半定 9 第二章校正的p r i c eo fa n a r c h y 界限 例2 1 1 假设c 2 = 3 ，a = 2 ，易知c 2 丢，根据p e r a k i s 的结论，问题( 2 1 1 ) 的解为 驴上2 a ：三，铲譬：3 ， z 15 5 石，z 2 。t23 ， 把上式代入问题( 2 1 1 ) ，得目标函数的最优值为c 2 a 2 2 ( a 一1 ) = 1 0 下面我们再取z l = 0 2 7 ，x 2 = 2 7 8 ，这是可行的，然而此时我们得问题( 2 1 1 ) 的目标函数值为9 9 1 3 一 i i i l 九 肋 、，1护一4 一 一 勉 zz 第二章 校正的p r i c eo fa n a r c h y 界限 定理2 2 1 最优化问题( 2 1 1 ) 的解为： ( 1 ) 当a = 1 时，雨 ( i ) 若c 2 2 ，则z ；= 鲁，z ；：1 ，目标函数的最优值为广= 砑4 ； ( i i ) 若c 2 2 ，则z ：= 三，z = 譬，目标函数的最优值为广= c 2 ； ( 2 ) 当a 1 时，有 ( i ) 若c 2 丢一杀，则z = 譬，z ；= 1 ，目标函数的最优值为广= 而4 ； ( i i ) 若c 2 丢一叁测俨耥，铲剿，目标函数的最优值 为，+ = 硒i 再4 a ( a 可- 1 丽) 2 ，这里口：= 厄丽 证明：对任何c 2 1 ，a 1 ，取z l = 击，z 2 = c 2 a 关于问题( 2 1 1 ) 是可行的，且 目标函数值为 ，= 2 【1 + ( c 2 a 一1 ) 】 。，这说明从互补 性条件 2 屉可得x l x 2 ：譬 。2 2 。2 ， 2 了 l 厶厶1 z j 下面分两种情况分别考虑： 情况一：约束条件( 2 2 4 ) 是积极的，即x 2 = 1 由( 2 2 1 2 ) 可得x l = 寻以及目标 函数值广= 了二刍，考虑到约束条件( 2 2 5 ) 一( 2 2 6 ) ，仅当筹 1 ，当 c 2 丢一万4 时解为z ；= 筹，z ；= 1 ，目标函数的最优值，+ = 百厕4 ；否则，有 如( 2 2 2 0 ) 所示的z ：与x 2 ，( 2 2 2 1 ) 所示的f + 口 1 2 第二章 校正的p r i c eo fa n a r c h y 界限 2 3 两种界限的差异 通过以上分析，我们得到了由( 2 1 2 ) 定义的p r i c eo fa n a r c h y “最佳”界限，即 我们得到的界限要比p e r a k i sf 2 2 】给出的小为更直观地看出差异，我们对固定 c 2 = 3 ( 将目标函数看成关于a 的函数) 与固定a = 2 ( 将目标函数看成关于c 2 的 函数) 两种情况，分别计算p e r a k i s 的界限与新的界限，并将前者与后者的差的变化 情况画图如下 8 c 竺 g 五 图2 3 1 ：c 2 = 3 ，新的界限与p e r a k i s 的界限之间的差异 图2 3 2 ：a = 2 ，新的界限与p e r a k i s 的界限之间的差异 1 3 第三章连续化方法的应用及改进 5 3 1 引言 给定一个对称矩阵a 舻黼，考虑最优化问题 i m i nz t a x 蚝碑 ( 3 1 1 ) i s t z t z = 1 因上述最优化问题的约束条件是x t x = 1 ，从而问题( 3 1 1 ) 也等价于 f z r a 碑i n x t a z + q z r z ( 3 1 2 ) is t x t z = 1 ， 这里q 可以为任意实常数记b = a + q ，则问题( 3 1 2 ) 可写成如下形式 fm i nz t b z 【s t x t x = 1 这与原始最优化问题( 3 1 1 ) 具有相同的形式由q 的任意性，存在足够大的a ， 使得b 是一个实对称正定矩阵不失一般性，下而我们假设问题( 3 1 1 ) 中的a 为 一个实对称正定矩阵 注意到问题( 3 1 1 ) 的可行域是单位球面的一部分，其非凸性增加了问题的求 解难度为将其转化为一个相对容易求解的最优化问题，我们先选取一个常数c ，使 得 c h + 1 ( 3 1 3 ) 由于a 对称正定，由推论2 3 2 1 1 ，有 m a x ni 入t i = i i a i l 2 i i a l l l ( 3 1 4 ) 因此，可选取c = 悄1 1 1 + 1 ( 这也是后面数值实验中选取的默认值) 选定好c 后，我 们重新构造如下最优化问题 f 勰，血一n ( 3 1 5 ) 【s t x t z 1 第三章连续化方法的应用及改进 不难看出问题( 3 1 5 ) 与问题( 3 1 1 ) 是等价的，其不同之处在于问题( 3 1 5 ) 的目 标函数是严格凹的，但可行域是单位球的一部分，其凸性使得问题( 3 1 5 ) 在一定程 度上比问题( 3 1 1 ) 易于求解 下面我们引入连续化方法求解问题( 3 1 5 ) ，对问题( 3 1 5 ) 作如下分析 3 2 问题分析 考虑变分不等式问题( 1 4 1 ) ，记f ( x ) = ( a c i ) x ，i h 2 = 扛冗华lx t x 1 ) 1 则问题( 3 1 5 ) 等价于找一点x + q ，使得 ( z z + ) r f ( x + ) o ，v x q ( 3 2 1 ) 由引理1 4 3 ，求解问题( 3 2 1 ) 等价于找如下方程的一个零点 e ( z ，p ) = x r ( z p ，( z ) ) ，( 3 2 2 ) 这里p 为任意正常数另外，为便于讨论，记 e ( z ) = z 一户h ( z 一厂( z ) ) ( 3 2 3 ) 我们考虑用g o l u b 和l i a o 【1 2 】中提出的连续化方法来求解问题( 3 1 5 ) 连续化方 法包括两个部分：一个评价函数( 下有界的) 和一个动力系统，这里要求评价函数 随动力系统单调非增 我们取问题( 3 1 5 ) 的目标函数作为评价函数： f ( x ) = x t a x c x t x ，( 3 2 4 ) 记其梯度函数为厂 ) ，并构造动力系统： 掣= 一陋一r ( z _ ，( 姗 ( 3 2 - 5 ) 下面我们给出结论，当动力系统( 3 2 5 ) 具有非空极限点集时，以上动力系统的任一 极限点都是问题( 3 1 5 ) 的一个稳定点 引理3 2 1 假设评价函数f ( x ) 连续可微，其梯度函数f ( x ) 是l i p s c h i t z 连 续的，q 为一个有界闭凸集，且初始点x o q ，则动力系统( 3 2 5 ) 的轨迹是一个非 空极限点集 】5 第三章连续化方法的应用及改进 证明：由于动力系统( 3 2 5 ) 的右边在p 内连续，根据c a u c h y - p e a n o 定理，该动 力系统的解z ( ) 存在，且z ( t = t o ) = x o 口 定理3 2 1 对任意x ( t = t o ) = x o 兄华，动力系统( 3 2 5 ) 有一个唯一解 z ( ) ，且在【t o ，+ o 。】内，x ( t = t o ) = x o 证明：由引理3 2 1 ，动力系统( 3 2 5 ) 存在一个解z ( t ) ，且x ( t = t o ) = x o 根据这 个解，我们定义 e ( z ( ) ) = l i z ( t ) 一r ( z ( t ) ) | 1 2 则e ( 。( t ) ) 表示了z ( ) 到q 的距离的平方，由参考文献【2 】第4 章定理1 7 ，有 掣_ _ 2 ( 雄) 一晰) ) t 如) 由于q 是一个闭凸集，令z ：= r ( z 一，( z ) ) ，代入投影映射基本不等式( 1 4 4 ) ，得 ( 茁一r ( z ) ) t ( 玮( z 一，( 茁) ) 一r ( z ) ) 0 ， 整理后得 ( z 一玮( z ) ) t e ( x ) i i z p q ( x ) 1 1 2 从而当zgq 时， 气掣= _ 2 ( 邢) 一r ( 删) t 批) ) - 2 i 卜r ( 珊 0 ，使得 俐脚i ，耽咄刁， 则有 h ( t ) = 0 ，v t 【t o ，刁 证明：见参考文献【2 9 口 根据以上引理，可以将t 推j 1 。到+ o o 下面给出动力系统( 3 2 5 ) 的解的收敛 性结果 定理3 2 2 对任意跏q ，记x ( t ) 为动力系统( 3 2 5 ) 的解，且z ( t = t o ) = z o ， 则有 ( i ) 若e ( x o ) = 0 ，则x ( t ) = 0 ，v t t o ； ( i i ) 若e ( x 0 ) 0 ，则1 i 珊e ( z ( 亡) ) = 0 c + 十 证明：( i ) 记 h ( t ) = i l e ( x ( t ) ) 1 1 2 应用参考文献 2 】第4 章定理1 7 ，有 阱2 陋啪t 辨2 i 酢汁 取m = 2 ，则引理3 2 2 的条件满足，从而命题( i ) 成立 ( i i ) 由于z o q ，由定理3 2 1 可知叠q ，v t t o 令z ：= z 一，( z ) ，z ：。， 代人投影映射基本不等式( 1 4 4 ) ，得 ( e ( z ) 一，( z ) ) t e ( z ) 0 由( 3 2 3 ) ，( 3 2 4 ) ，( 3 2 5 ) 及以上不等式，有 1 d f ( 广x ) = 一m 几( z ) 一i i e ( z ) i l z o ，幻 第三章 连续化方法的应用及改进 再由l a s a l l e 不变集合定理( 参考文献 3 0 】定理3 4 ) 与上式，得 1 i 理e ( z ( t ) ) = 0 t _ + 定理证毕口 有了动力系统的收敛性结果，我们可以直接利用m a t l a b 中的o d e 函数求 解动力系统( 3 2 5 ) ，例如o d e 4 5 ( 这也是g o l u b 和l i a o 【1 2 】所选择的函数) 考虑到我们常用的迭代法求解最优化问题的有效性，下面我们提出把动力系统 ( 3 2 5 ) 离散化，用经典的数值方法一e u l e r 方法迭代求解 3 3 新的算法 通过上一节分析可知，为求解最优化问题( 3 1 1 ) ，我们可借助于构造一个评价 函数和一个动力系统来连续化求解通过( 3 1 3 ) 式c 的选择，评价函数是一致凹 的，且模为1 ，这一性质确保了动力系统( 3 2 5 ) 的收敛性，在此基础上，我们构造含 参数的动力系统如下 掣= 一k r ( x - - 明砒 ( 3 3 1 ) 不难看出，对任何卢1 以上动力系统总是收敛在数值实验中，参数p 对算法的 效率往往有着很大影响，下面我们先将动力系统( 3 3 1 ) 离散化，每步自适应地调节 参数迭代求解我们用e u l e r 方法求解以上动力系统，即在时刻t ，我们通过如下迭 代格式产生下一时刻最优解逼近， x ( t + h ) = z ( t ) 一h e ( x ( t ) ，p ( t ) ) ， 这里h 为时间步长，卢( ) 为通过某一准则自适应确定的参数 f u k u s h i m a 【1 0 提出的解强单调变分不等式问题的方法，h e 【1 4 】提出的求解 单调线性互补问题及凸二次规划问题的方法，以及后来h a n 和l o 【1 3 】推出的求解 余强制非线性变分不等式问题的方法，都是采用以上迭代格式本文与他们的不同 之处在于： 考虑的是一个非凸的优化问题； 在算法中引入自适应策略，在数值实验中，很大程度地提高了算法的效率 算法3 3 1 】8 第三章连续化方法的应用及改进 s 0 给定一非负数列 r ( t ) ) ，满足e7 ( ) 0 ，令t ：= t o ； s 1 如果i l e ( x ( t ) ) l i e ，停止迭代；否则，转到s 2 ； s 2 找最小的正整数i k ，使得z ( t + h ) = 沙，y ，及 满足 x ( t + h ) = 茁( t ) 一h e ( x ( t ) ，p ( t ) ) ， ( 3 3 2 ) f ( x ( t + ) ) f ( z ( ) ) 一耶 + ) ， ( ) ) t e ( z ( t ) ，z ( t + 九) ) ； ( 3 3 3 ) s 3 如果 f ( z ( + ) ) f ( z ( t ) ) 一0 7 h f l ( t + ) 厂( z ( ) ) t e ( z ( t ) ，z ( t + 危) ) ，( 3 3 4 ) 则，y = ( 1 + 7 ( + h ) ) f l ( t + 危) ，否则，y = p ( t ) ； s 4 令t ：= t + h ，转到s 1 口 该算法的思想是通过在e u l e r 方法中引入自适应参数，离散地求解动力系统 ( 3 2 5 ) 以提高求解效率，下面我们给出算法3 3 1 的收敛性证明 3 4 收敛性分析 首先考虑以上算法中的参数搜索步s 2 ，由于我们在每次迭代中添加了自适应 选择参数这一过程，因此，我们提出的算法首先在每次迭代中选择参数z ( t + h ) 的 自适应步要求能在有限步终止，为此，我们有如下结论 引理3 4 1 在算法3 3 1 中，对任何t ，寻找参数z ( t + h ) 的自适应步s 2 都能 在有限步终止，并且，存在一个正实数风i n ，使得对所有t 0 ，有z ( t ) 风i 。 0 证明：根据算法3 3 1 步s 3 ，对所有t ，有p ( + 危) ( 1 + 丁( t ) ) p ( ) ，因为7 - ( ) + o o ，由引理1 4 6 ，有 ( 1 + 下( ) ) 0 ，使得对所有t ，有7 k ，且p ( t ) o ，且r 南1 ，根据引理1 4 4 ，有 l i e ( 碱z ( t + h ) ) 怆南( 。) ，俐n ( 3 删 联合( 3 4 4 ) 一( 3 4 6 ) ，得 可赢( z ) ，p ( ) ) 旷f ( z ( ) ) 一f ( z ( t ) 一h e ( z ( ) ，p ( + 九) ) ) ， 对上式两边同时连加，得 篆志忙似巩俐旷”似m 2 。 因为h ( 0 ，1 ) ，且 羡志针， 缸( 1 + 7 - ( t + ) ) 2 一一 有 1 i me ( z ( t ) ) = 0 根据引理1 4 3 ，命题成立 ， 口 3 5 数值实验 本小节，我们用两个例子来检验新提出的算法3 3 1 ，并与g o l u b 和l i a o 【1 2 】 所采用的o d e 函数做比较，验证新算法的有效性所有的实验都是在m a t l a b 7 0 1 的运行环境下，记号i t e r 与s e c 分别表示迭代次数和运行的c p u 时间 ( 单位：秒) 在下面的数值实验中，我们选取的停机准则均为 l i e ( x ) l l 。， 其中= 1 0 一由于算法3 3 1 中s 2 步确定参数会在有限步终止，我们选择调整因 子7 为一常数，如果迭代点z ( t + h ) 满足( 3 3 4 ) ，选择调整因子7 = 1 0 ，并且总共 调整次数不超过1 0 0 次；否则，7 = 0 o d e 函数选择g o l u b 和l i a o 1 2 】中采用的 o d e 4 5 ，所有实验中均设置r e l t o l = 1 0 一，a b s t o l = 1 0 一 2 1 第三章连续化方法的应用及改进 例3 5 1 类似于【1 2 中例1 的构造方法，我们按以下步骤构造矩阵： 1 选择一对角矩阵 人= d i a g ( 2 ，3 ，4 ，l e 一2 ，1 ，1 ) 酽黼； 2 利用m a t l a b 随机生成矩阵b 舻黼，并对b 进行q r 分解旧，捌= g r ( b ) ； 3 记a = q t a q ，则a 为一实对称正定矩阵，且a 的最小特征值为1 e 一2 令札= e n ，这里表示n 维实向量( 1 ，1 ，1 ) t ，我们取跏= 志作为初始 点，显然z o q 并且取c 一5 ，t o = 0 ，y = 7 0 = 1 ，p = 0 6 ，h = o 0 5 选择1 1 从 1 0 0 到5 0 0 0 之间，分别比较两种方法的结果如下 图2 5 1 分别画出n = 1 0 0 0 和n = 5 0 0 0 两种情况下动力系统解的部分分量的收 敛性变化情况，其中x 代表g o l u b 和l i a o 1 2 】中采用的o d e 4 5 部分分量求解 的变化情况，y 代表本文新提出的算法3 3 1 对应分量求解的变化情况 第三章 连续化方法的应用及改进 c o m p a r i s o n1 ：n = l0 0 0 c o m p a r i s o n2 ：n = 5 0 0 0 图3 5 1 ：新算法与o d e 解例1 对比 2 0 0 6 4 3 0 第三章连续化方法的应用及改进 从上图不难看出，两种方法都能得到相同的解，然而新提出的算法3 3 1 求出的 解能在相对较短的时间内趋于稳定，要比o d e 函数o d e 4 5 求解效率高为更进一 步的比较，我们把不同1 2 的取值下两种算法的结果对比列表如下 表1 例3 5 1 n1 0 05 0 01 0