（运筹学与控制论专业论文）互补问题的有效算法研究.pdf

摘要 摘要 本文主娶 项 开 究求解互补问 题的有效算法。从 2 0世纪 6 0年代互补问题的 提出到现 在，尤其是最近2 0 多年来，互补问题发展非常迅速。并且出 现了 各种形式的互补问 题。 互补问题被广泛地应用于工程、 经济和 运筹学中。 对互补问 题的研究可以 分为 理论和算 法。 前者主要研究问 题解的 存在性 、 唯一性、 稳定性以 及灵敏度分析等性质。 后者 集中 研究 如 何构造有效算 法及 其理 论 分析。 本文旨 在 有效算 法方面的 研究。 第一章概述了 互补问 题的 各种形式及其在工程、 经济和运筹学中的 应用，同时分 类介绍了求解互补问题的几种主要算法， 并将作者的工作穿插在相关算法里 做了 简要介 绍。 第二章首先介绍了信息论中的嫡、最大墒原理、最小叉嫡原理。然后针对带不等 式 约 束 的 非 线 性 规 划问 题 ， 给 出 一 个l a g r a n g e 正 则 化 ( 摄 动) 方 法， 该 方 法 有 效 地 克 服了 线性l a g r a n g e 函 数难 于 在对 偶 变量空间 直接 求解的困 难。 文中 分别以s h a n n o n 嫡 函数和 k u ll b a c k叉墒函数作为摄动函 数， 导出 其对偶函 数分别是原问 题的指数罚函数 和指数乘 子罚函 数。 这 样就在l a g r a n g e 摄动和指数罚函 数之间 搭 起了 一 座桥梁。 然后 文中把这种方法应用到 有限 维极大极小问 题的一个等价非线性规划问 题，得到了 相 应的 光滑函 数， 且与用最大嫡原则 和最小叉嫡原则得到的 凝聚函 数相同。 由于求解线性互补问 题的内 点 法可以 看作是线性规划原一 对偶内点法的一个自 然推 广，在第三章开头首先 介绍了内 点法。 然后， 基于极大极小问 题的 均衡作用， 构造了 一 个新的效益函数( 势函数) ，并以 其梯度为零代替一般内点法中的互补条件方程。 鉴于该 效益函数是非光滑的，不便于操作， 使用前一章给出 光滑函数做了光滑处理， 而得到的 光滑效益函数是一个凸函 数。 与一般内 点 法中的 摄动互补条件相比， 其最优性 条件 含有 一组中心化参数。这组参数利 用上一个迭代点的信息对当前步向中心路径进行调整， 文 中称之为自 调整作用。 基于这组方程， 文中建立了一个求解线性互补的不可行内点算法， 并分析了 它的多项式复杂度。 数值结果表明 参数起到了自 调整作用。 第四 章细化了c h e n - x i u求解线性互补问 题的一步非内 点延拓算法，并 且推广到非 线性互补问 题。 得到了 与c h e n - x i u 同样的全局线性收敛， 推广了c h e n - x i u 的 局部 超线 性收敛i ii 局部二次收敛。 在一定意义下，光滑化函数是延拓算法的核心。本章尝试用叉 嫡函 数来光滑化极小化 n c p函数。 建立了 一个求解单调线性互补问 题的非内点延拓算 法。 其数值结果非常好， 部分的好于文中提到的不可行路m 民 踪算法。 在这一章的 最后， 把 m i d ( . ) 函 数重新表 述， 并 用 s h a n n o n墒函 数光滑化。 文中讨论了 得到的光滑函 数的 性质，给出一个求解一类混合互补问题的非内点预估一 校正延拓算法，并分析了其全局 收敛性。 基于非线性互补问 题的一个等价不动点格式， 第五章分别用 s h a n n o n嫡函数和 k u l l b a c k 嫡函 数光滑化m a x 函 数。 文中 分别给出了两个迭代 算法， 并与p a u l t s e n g 的 外梯度投影法进行了 数值比 较。 在内点法中， 采用不同的 代数等价路径形成了 通向 最优解的不同 轨迹。 虽然 f a n g - p u t h e n p u re , t u n c e l - t o d d , w r i g h t 等都 认识到这个问 题的 重要性， 但.9 a i 7t 方 面的 i 大连理工大学博士论文 作还很少。 讨论了 基于对数变换的 代数等价路径， 并 构造了 一个不 可行的大步长路t 踪算法，并 分析了 它的复杂度， 而且数值结果也是令人 满 意的。与此同 时， 分析了 该方 法与p e n g等人 近期 工作的 联系， 发现 因 ; 补条件 的 右 端可 表 示 成 嫡函 数的负 梯度。 并且 证明，由p e n g 等人提出 的自 正 则 邻 近度 量函 数 方 法 ( 缩 减了 大步 长路 有 劲良 踪 算法的 复 杂度) ，也可以 通过等价代数变换得到。 第七章通过计算验证了文中 提出的几个算法。首先， 对文中 提出的不可行路经跟 踪算法3 . 3 、 算法6 . 1 与z h a n g y i n 的 不 可行路 经 跟踪 算 法进 行了 数值比 较。 其次， 给 出了 第四 章中 用k u l l b a c k 叉嫡光滑化n c p 函数的一个非内 点延拓算法4 . 2 的 数值结果。 最后， 对基于s h a n n o n 嫡光滑 化和k u l l b a c k 叉 嫡光滑 化的 迭 代算法与p a u l t s e n g 的 外 梯度法进行了 数值比 较。 最后， 作者总结了全文，并对下一步的研究工作做了 展望。 关键词: 互补问题、 内点法、 延拓算法、 中 心路径、 代数等价路径、 光滑化、 s h a n n o n 嫡、 k u l l b a c k 又 嫡、 最大 嫡原理、 最小 叉 嫡原理。 ab s t r a c t ab s t r a c t t h e p a p e r d e a l s w i t h t h e s t u d y o f e ff i c i e n t a lg o r i th m s f o r c o m p le m e n t a r it y p ro b le m s ( c p s ) . c p s h a v e b e e n d e v e l o p e d v e ry q u i c k l y s i n c e t h e y a p p e a r e d i n t h e 6 0 s la s t c e n t u ry , e s p e c i a lly t h e re c e n t t w o d e c a d e s . ma n y f o r m u l a t i o n s o f t h e m w e re p ro p o s e d a n d w id e l y u s e d i n e n g i n e e r in g , e c o n o m ic s a n d o p e r a t i o n s re s e a r c h . r o u g h l y s p e a k i n g , t h e s tu d y o f c p s c a n b e c las s i fi e d in t o t w o c l a s s e s : t h e o ry a n d a lg o r it h m s . t h e f o r me r i s d e v o t e d to t h e e x i s t e n c e , u n iq u e n e s s , s ta b ili t y a n d s e n s i t iv it y a n a ly s i s o f t h e s o lu t io n s , w h i l e t h e la tt e r i s in t e n d e d to s o lv e t h e p ro b le m s e ff i c i e n t ly , t o g e t h e r w it h t h e t h e o re t ic a l a n a ly s i s o f t h e a l g o r it h m s . d iff e r e n t f o r m u l a t io n s o f c p s二 i n t r o d u c e d in c h a p t e r o n e , a l o n g w it h v a ri o u s a p p li c a ti o n s i n e n g in e e r in g , e c o n o m i c s a n d o p e r a t io n s re s e a r c h . s o m e a l g o r i t h m s f o r c p s a re d e s c r ib e d . me a n w h il e , t h e t h e s i s w o r k i s o u t li n e d b r i e fl y . c h a p t e r t w o in tr o d u c e s t h e c o n c e p t o f e n t ro p y i n i n f o r m a ti o n th e o ry , m a x im u m e n tro p y p r i n c ip l e , a n d m i n im u m c ro s s - e n t ro p y p r in c i p l e . i t i s d i ff i c u lt t o a n a ly t i c a l ly s o l v e t h e in e q u a li t y c o n s tr a in e d n l p s in t h e d u a l s p a c e , d u e t o t h e l in e a r l a g r a n g i a n . a p e r tu r b e d ( re g u l a r i z e d ) l a g r a n 乡 a n a p p r o a c h i s p ro p o s e d , w h ic h p r o v id e s a n a n a ly t ic s o l u ti o n o f t h e d u a l v a ri a b le s i n t e r m s o f p r im a l v a r i a b l e s . t h e a p p l ic a t i o n s o f s h a n n o n e n t r o p y a n d k u l l b a c k s c r o s s - e n t ro p y as p e r tu r b a ti o n s a r e d i s c u s s e d . 琦m a x i m iz in g t h e p e r tu r b e d l a g r a n g i a n s in d u a l s p a c e , w e o b t a in t h e e x p o n e n ti a l p e n a lt y fu n c t io n a n d e x p o n e n ti a l m u lti p l i e r p e n a lt y fu n c ti o n , r e s p e c ti v e ly , f o r i n e q u a li t y c o n s t r a in e d n l p s . t h u s , a b ri d g e i s b u i l t b e t w e e n t h e l a g ra n g e p e r b u a ti o n m e t h o d s a n d t h e e x p o n e n ti a l p e n a lt y m e t h o d s . t h e n t h e p e rt u r b a ti o n m e t h o d s a re u s e d t o a n e q u i v a l e n t n l p p ro b l e m o f m in m a x p ro b le m s a n d th e r e s u lt e d s m o o t h f u n c ti o n s a re j u s t a g g r e g a t e f u n c ti o n s o b t a in e d b y m a x i m u m e n t ro p y p r in c ip l e a n d m in im u m c r o s s - e n t ro p y p r i n c ip le , r e s p e c ti v e ly . c h a p t e r t h re e in t r o d u c e s t h e d e v e l o p m e n t o f in t e ri o r - p o in t m e t h o d s f o r l in e a r p ro g r a m s f ir s t s in c e t h e in t e r i o r - p o i n t m e t h o d s f o r l c p s c a n b e l o o k e d as a n a t u r a l e x t e n s io n o f p ri m a l- d u a l i n t e ri o r - p o i n t m e t h o d s f o r l p s . a n e w m e ri t f u n c ti o n ( p o t e n ti a l f u n c t i o n ) i s c o n s t r u c t e d i n c h a p t e r t h re e , b a s e d o n t h e b a l a n c e d e ff e c t o f t h e m in - m a x p ro b l e m . b e c a u s e o f t h e n o n - s m o o t h n e s s , s h a n n o n e n t ro p y is u s e d t o s m o o t h t h e m e ri t fu n c t io n . t h e r e s u lt e d s m o o t h m e ri t f u n c ti o n i s c o n v e x a n d it s o p t i m a l c o n d iti o n s c o n ta in a s e t o f e x tr a p a r a m e t e r s , c o m p a r e d w it h t h e u s u a l p e rt u r b e d c o m p l e m e n t a ri t y c o n d iti o n s . t h e s e t o f p a r a m e te r s i s u p d a t e d b y u s in g t h e in f o r m a ti o n o f t h e l as t it e r a t io n a n d b r in g s a b o u t t h e c e n t e r i n g e ff e c t t o w a r d s t h e c e n t ra l p a th , w h i c h w as c a lle d t h e s e l f - a d j u s t i n g e ff e c t . a n i n f e a s i b le p a th - f o ll o w in g a l g o ri th m i s c o n s tr u c te d , a n d i t s p o ly n o m i a l c o m p le x it y i s a n a l y z e d . n u m e ri c a l t e s t s s h o w th e s e l f - a d j u s ti n g e ff e c t o f th e p a r a me t e r s . t h e o n e - s t e p n o n - in t e ri o r c o n t in u a ti o n m e t h o d o f c h e n a n d mu f o r l c p s i s re f i n e d in c h a p t e r f o u r . i t i s e x t e n d e d t o n l p s . t h e c o n t r o l p a r a m e t e r i s re p la c e d b y t h e s m o o t h in g p a r a m e t e r in t h e p e r t u r b a t io n t e r m o f n e w t o n s t e p . t h e c o n v e r g e n c e o f t h e re fi n e d n o n - in t e r i o r 大连理_ 大学博十论文 c o n t in u a t i o n m e t h o d f o r n c p s i s a n a ly z e d , th e s a m e g lo b a l l in e a r c o n v e r g e n c e a s c h e n - x i u s is o b t a in e d . l o c a l ly q u a d r a t ic c o n v e r g e n c e i s a l s o o b ta i n e d , c o m p a r e d w it h t h e lo c a l ly s u p e r l in e a r c o n v e n g e n c e o f c h e n - x i u s . s m o o t h in g f u n c t io n s , i n s o m e s e n s e , a r e t h e c e n t e r in c o n t in u a t io n m e th o d s . k u l lb a c k s c r o s s -e n t ro p y f u n c t io n i s t r i e d t o s m o o t h t h e m i n i m a l n c p - fu n c t i o n a n d a n o n - in t e ri o r c o n t in u a t i o n m e th o d i s c o n s t r u c t e d f o r l c p s . it s n u m e r i c a l p e r f o r m a n c e i s v e ry g o o d , e v e n b e t te r p a r t l y t h a n t h e in f e a s ib le p a t h - f o l l o w in g m e t h o d s in c h a p te r t h r e e a n d c h a p t e r s i x . a t la s t o f t h e c h a p t e r , t h e m i d ( ) f u n c t io n i s re f o r m u l a t e d . s h a n n o n e n t r o p y f u n c t io n i s u s e d t o s m o o t h in g it . a n o n - in t e r i o r p r e d i c t o r -c o r r e c t o r c o n t in u a t io n m e th o d is b u i lt f o r a c l a s s o f m i x e d c o m p le m e n t a ri t y p ro b le m s . i t s g lo b a l c o n v e r g e n c e i s a n a ly z e d . s h a n n o n e n t ro p y a n d k u ll b a c k s c r o s s - e n t ro p y a re u s e d t o s m o o t h t h e m a x f u n c t i o n r e s p e c t iv e ly i n a f ix e d - p o in t f o r m u la t io n o f n c p s in c h a p t e r f o u r . t w o it e r a t io n m e t h o d s a re c o n s t r u c t e d a n d t h e a l g o r it h m s a r e c o m p a r e d w it h e x t ra g r a d i e n t p ro j e c t i o n m e t h o d o f t s e n g . i n in t e ri o r - p o i n t m e t h o d s , d i ff e r e n t 咧e c t o ri e s t o t h e o p t im a l s e t a re f o r m e d fr o m d i ff e re n t a lg e b r a i c a l ly e q u i v a l e n t p a t h s . a lt h o u g h f a n g - p u th e n p u r a , t u n c e l - t o d d , w r i g h t e tc h a v e re a li z e d t h e i m p o r t a n c e o f a l g e b r a i c a l ly e q u iv a l e n t t r a n s f o r ma t io n s , li t tl e w o r k h a s b e e n d o n e i n t h i s a s p e c t . p e n g e t a l re d u c e d t h e p o ly n o m i a l c o m p le x i t y o f la r g e - s t e p p a t h - f o ll o w in g m e t h o d , b a s e d o n t h e i r s e l f - re g u l a r p ro x im it y f u n c t i o n . i t i s d i s c o v e re d t h a t t h e n e w to n d i r e c t i o n o f p e n g e t a l c a n b e o b t a in e d fr o m a n a lg e b r a i c a ll y e q u i v a le n t p a th . w e d i s c u s s t h e lo g a ri t h m i c tr a n s f o r m a t io n a n d c o n s t r u c t a n i n f e a s ib le l a r g e - s te p p a t h - f o ll o w in g a l g o ri t h m . t h e p o ly n o m i a l c o m p l e x it y i s a n a ly z e d a n d t h e n u m e ri c a l r e s u l t s f o r s o m e t e s t p ro b l e m s a re v e r y e n c o u r a g i n g . t h e a l g o ri t h m s p ro p o s e d in t h e th e s is a re t e s te d i n c h a p t e r s e v e n . f ir s t ly , t h e i n f e a s ib le p a t h - f o ll o w i n g a lg o ri t h m 3 .3 a n d a l g o ri t h m 6 . 1 a re c o m p a re d w i th t h e i n f e a s ib le p a t h - f o ll o w in g a l g o ri t h m o f z h a n g y in . s e c o n d l y , t h e n o n - in t e ri o r c o n t i n u a t io n a lg o ri th m 4 .2 i s te s t e d . l a s tl y , t h e i t e r a t io n m e t h o d s b a s e d o n t h e s h a n n o n e n t ro p y s m o o t h in g a n d k u ll b a c k s c ro s s - e n t ro p y s m o o t h in g a re c o m p a r e d w it h t h e e x t r a g r a d ie n t p ro j e c t i o n m e t h o d o f p a u l t s e n g f in a l ly , t h e a u th o r s u m s u p t h e re s e a r c h e ff o r ts in t h e s is a n d g i v e s p r o s p e c ts o f t h e f u r th e r r e s e a r c h i n t h e fi e l d s . k e y w o r d s 二 c o m p l e m e n t a ri t y p ro b le m , i n t e r i o r - p o i n t m e th o d , c o n t in u a t io n m e t h o d , t h e c e n t r a l p a t h , a l g e b r a i c a ll y e q u i v a l e n t p a t h , s m o o t h i n g , s h a n n o n e n t ro p y , k u l l b a c k s c ro s s - e n t r o p y , m a x i m u m e n t r o p y p r in c i p l e , a n d m i n im u m c ro s s - e n t ro p y p r i n c ip l e . 第一章绪论 第一章绪论 互补问 题最显著的 特点就是存在互补对( 1 . 1 ) 式: x l o s ? 。 ， 厂s = 0 .( 1 . 1 ) 早在 1 9 3 9 年k a r u s h 研究带不等式约束的连续变量非线性规划的最优性条件时就提 出了互补的概念，然而直到1 9 6 3 年h o w s o n 把一个双矩阵对策的n a s h 平衡点问 题转化 为 一 个线性互补问题，互补问 题才引起州 门 的注意，互补问 题的研究才显得重要。1 9 6 4 年c o t tl e 提出了 非 线性互补问 题。1 9 6 8 年c o tt l e 和d a n t z ig 把线性规划问 题、二 次规 划 和双矩阵对策问题统一表述为线性互补问 题，这项突破性的工作激发了互补问题研究的 高潮。经过近四十年的研究，互补问题的理论与算法己 趋于成熟，而其在工程、经济和 运筹学中的广泛应用使其成为数学规划领域中一门内容非常丰富的学利。 此综述性的 文 献 1 - 8 j 介 绍了 关于互补问 题的 基本理论、 算法及其 应用。 本文主要研究求解互补问题的算法， 特别是适于求解大型互补问题的算法。在本 章里，首先介绍了互补问题的各种不同形式及其在运筹学和各类工程问题中的应用，然 后对求解互补问题的各种算法分门别类地做了介绍，本文作者在互补问 题算法方面的研 究工作被穿插进相关算法综述中做了简略介绍，最后一节对本文工作做了简短概述。 1 . 1互补问 题的 类型 丝 丝 -f l * lpj m r ( l c p ( m ; q ) 是 互 补 问 题 中 最 简 单 的 ， 也 是 应 用 最 广 泛 、 研 究 最 为 深入的 一 类问 题， 它被看作是运筹学中的一类基本问题。 线性互补问题一般司以 表述为 给定m二 r n x n ， q e r ， 求二 e r , s r 满足: s =y l k + q , x o , s _ 0 , x f s 二 0 ( 1 2 ) 其中:x 为原变量，s 为互补变量。 线性互补问 题稍 作扩展便得 到9 9 o n it -ff * a g ( m l c p ) ，即; 给定a e r n , b e r x x m ， c e r , d e r n r ， f e r 和 b e r ， 求x e r ，y e r , s e r . 满足: a y+ b x + c =0 勿 + e x 十 f一 : 二 0 x o , s ? o , x t s 二 0 ( 1 3 ) r!、j!、 大连理_ 二 大学博士论文 ( 1 .3 ) 式 中 ， 若a 为 非 奇 异 矩 阵 ， 则 y = - a - 1 ( b x + c ) ， ( 1 .3 ) 式 可 进 一 步 表 述 为 线 性 互 补 问 题 l c p ( e 一 d ,4 - b , f 一 d a - c ) o 线性互补问 题的另一个扩展就是丛王 些丝互处卫题( h l c p ) ， 即: 给定n二 fl -, me r 和 q e 尸，求x e r , s c- r ， 使 得 ( 1 .4 ) 式 成 立。 m x + n s 十 q = 0 x o , s _ o , x t : 二 0 ( 1 . 4 ) 若n= 1 时， ( 1 .4 ) 式就是标 准的 线性互补问 题: 若n为 非奇异 矩阵， 则 ( 1 .4 ) 式等价 于 线 性 互 补 问 题 l c p ( - n - m , - n q ) 。 线性互补问题的另一个扩展就是垂 ( v l c p ) , a ll :给定 me r m x n q e r ， 且 、 = im i, ,m n i t , 、 一 、 ， ，、 了 . ( 1 . 5 ) m r m , n ， q e r ,e =1 , 2 , - - - , n ( 1 .6 ) 求x e r ， 满足 ( 1 .7 ) 式: m x + q ? 0 , x ? o , x i(fl 箕 ( m x + q ) ) = 0 . i = 1 , 2 ， 二 ， n ( 1 . 7 ) 上述线性互补问题的扩展都是线性的，下面我们将给出 线性互补问题的非线性 扩展。 韭 些丝 旦处 立 亚 题(n c p ) 是 线 性互 补问 题的 非 线 性 扩展中 最 直 接也是 最 重要的 一 类，即: 给定函数f: r - - r ， 求x e r , s e r ，满足( 1 .8 ) 式: s 一 f ( x ) , x : o s : o , x t s = 0 .( 1 名 ) 很显然， 当函 数f ( 二 ) 为 仿 射函 数怂十 q 时， ( 1 .8 ) 式就 退 化为 线 性互补问 题 l c p ( m, q 非线性互补问题可以扩展到混合互补问题( mc p ) ，即:给定函数f: r - - r i 。 r 。 一 二 ” ， 、 。 r v c o ， 且i 4 , ( x 一 p ) t w = 0 u 一 x _ 0 , v 0 , ( u 一 x ) r v = 0 了1十1!、 当 l = - 0 0 , 。 二 ， 时 ， 则 混 合 互 补 问 题 ( 1 .9 ) 式 就 是 方 程 组f ( x ) 二 0 a 当 1 = 0 , u ( 1 . 9 ) =丈 ， 则 混合互补问 题( 1 .9 ) 式就是非线 性互补问 题。 变 发 工 签武v i ( k , 玛可 以 看 作 是 非 线 性 互 补 问 题 、 以 及 混 合 互 补 问 题 的 更 进 一 步 的 扩 展， 即 : 给定 函 数f : r -4r 0。; 6 ke r ， 求x e k满 足 ( 1 . 1 0 ) 式: f ( x ; ) t 。一 : ) ? 0 ， 对v y e k . ( 1 . 1 0 ) 当 k 二 、 卜 ? 0 时 ， ( 1 .1 0 ) 式 退 化 为 非 线 性 互 补 问 题 ( 1 .8 ) 式 。 另 外 当 集 合 k 为 矩 形 k := 1 1 几 j l; , u j ( 其 中 : 一 co : 1 0 ， 则 有 f ( x ) t ( 二 一 对 _ 0 , 则称f 在集合k上是 丛婆 调的; 大连理_ 大学博十论文 3 .若对于任意的 x , y e k, f 满 足: r f ( x ) 一 二 ( ， )了 ( x 一 y ) 0 , 则称 f在集合k上是的: 4 若对于 任意的 x , y e k， 存 在a 0 ， 使 得f 满 足: f ( x ) 一 f ( y ) 了 ( x 一 y ) : a 1ix 一 ， 112 . 则称 f在集合k上是的; 5 .若对于任意的x e k ， 存 在向 量尸e k， 使得f 满 足: l i m r c k .ll= il-f ( x ) t ( x 一 二 “ )/ 11x 11= 称f 关于 集合k 是 强 剑的; 6 .若对于 任意的x , y rz k , x x y , f 满足: m a x f , ( xi) 一 f ( y ) ( x : 一 y t) 0 ， 则 称f 为 集合k 上的p 一 函 数: 7 若对于任意的x , y e k , f 满足: m a x f , ( x ) 一 f , ( y ) (x , 一 、 ) ? 0 ， 则 称f 为 集 合k 上 的p o 一 函 数; 8 .若对于任意的x , y e k ， 存在a 0 ， 使得f 满足: m a x f ( x ) 一 f ( y ) ( x ， 一 ， ， ) a llx 一 y llz 称f 为 集合k上的一 致 p 一 函数; 9 .若对于 任 意的: e r ， 在 集 合k 上 ，f ( x ) = m x 十 4 ， 且 : ( 1 + z ) y 、 二 (, ) x r ( m x ) , + l r ds /* (x ) ( m x ) ; ? 0 , ， 期: 十 ( x 卜 i x , ( m . 工 0 , 一 ( 小 卜 ( m x ) , _ 0 , 厂s = 0 ( 1 . 1 3 ) !12、!、 显然，( 1 . 1 3 ) 式是一个混合线性互补问 题( m l c p ) o 考虑二次规划 m i n 生 二 厂 q ly 十 。 t x ( 1 . 1 4 ) s .t . a x = b , x _住 其最优性条件为: : = q - 一 a t y 十 。 a x =6 x ? o , s o , x t s = 0 ( 1 . 1 5 ) ( 1 巧 ) 式也是一个混合线性互补问 题口 考虑带不等式约束条件的非线性规划: m in f x s .t . 9 ( 二 ) 三 。 ( 1 . 1 b ) 其中f: r - r r , g : r - r 为凸 函 数且n ? 二。 其l a r g a n g e 函数为: l ( x , u ) 一 f ( x ) + u r g ( x )( 1 . 1 7 ) 且其最优性条件 o f ( 二 ) 一 v g ( x ) 7 : ， 七 0 , - g ( 二 ) 七 0 , u=0 u r g ( x ) 二 0 护ijll 是一个混合互补问 题。 对于一般的非线性规划问题: 大连理_ 1 _ 大学博士论文 m in f ( x ) s .t . h ( x ) = 0 , 9 ( 二 ) r , g : r - -) r , h : r - 尸为 凸 函 数 且 。 m , n -a ( 。 其 l a g r a n g 。 函 数为: l ( x , u , v ) 一 f ( x ) 一 u t h ( x ) + v t g ( x ) ， ( 1 . 1 9 ) f ( x ,u ,v ) 一 o x l ( x , u , v ) - 0 l ( x , u , v ) - 0 l ( x , u , v x :! s x e r ” 一、 ( x ) :- 0 ,h ( x ) 二 0 ,u :一 u e r ) ; v := v c r iz : 。 ， ( 1 . 2 0 ) 由 于 f : r - - r , g : r -+r , h : r - - r l 都 是 凸 函 数 ， 则 非 线 性 规 划 ( 1 . 1 8 ) 式 满 足一 阶约束规范，从而下面的鞍点条件成立: l ( x . ,u ,v ) l ( x * ,u . ,v i ) : l ( x ,u ,v ) 其中 : ( x , u , v ) e k:二 x x u x v 。 从 1 5 可 知， 非 线 性 规 划问 题 ( 1 . 1 8 ) 式 可以 转 化 为一 个 变 分不 等 式问 题v i ( k , f ) ， 其中k , f 如 上 所 述。 鞍点问 题中的一个重要情形就是扩展的线性一 二次规划问 题 2 。设. y , y 均为多 胞 形，令k:= xx y，则 k := x x y ，则扩展的线性一 二次规划问题为: l (x ,y ) 一 合 x tp x + p tx - x t ry + q t， 一 合 y tq y ( 1 .2 1 ) 1 . 3互补问题在工程和经济中的应用 互补问题在工程和经济领域中的应用非常广泛，其中一个重要原因就是系统平衡 的概念等同于互补的概念。力学中的弹塑性分析问题、接触问题、蠕变问题、土力学 问 题、 复合材料断裂问 题、 润滑力学问 题等都可以 转化为 互补问 题来求解 1 6 - 2 1 下 面我们将简单地介绍互补问题在接触力学问题、交通平衡问题、最有控制问题、经济 问题和对策模型中的应用。 1 . 3 . 1 . 互补问题在摩擦接触问题中的应用 在一 个三维刚体摩擦接触模型中，刚体与几个相互间由有限个节点连接的机械手发 第一章绪论 生 接 触， 接 触 力 服 从c o u lo m b 摩 擦定 律 设 在 某 一 时 刻， 接 触 模 型 中 含 有n个 接 触 点 ， 其 中 包 括 滚 动 接 触 点 和 滑 动 接 触 点 。 设 集 合 r 和s 为 1 , 2 , . , n ,. 的 两 个 不 相 交 的 子 集 ， 分 别代表滚动接触点集和滑动接触点 集。 给定一组外力， 这里用下标n , t , o分别表示 加速度与接触力的法向及切平面内两个互相垂直方向的分量。对待求的所有接触点 ， 2 . . . . . n _ 处 的 线 性 加 速 度 ( a m , a a , a , ) 和 接 触 力 ( q 。 、 几几 ) 需 满 足 运 动 加 速 度 约 束 条 s i g n o ri n i 非 穿 透 条 件 和c o u l o m b 摩 擦定 律。 特别 地， 令 只 := ( 、 处 . ， a :一 ( a a ) ,_ , ， a , := ( a l , ， :一 ( 汽 ) :泣 ， ， c :一 ( 、 ): . c :一 ( c -j - i 则运动约束条件表述为如下线性方程组: 分十一| 瓦人铸.瓦 广lles!.esl + lles.j cn吼co 尸.llesll a 一一 .!十! an气气 尸leeeel :矩阵a和向量b 为给定的数据。 s i g n o r in i 非穿透条 件将保证法向加速度是非负的， 而法向 接触力不能是拉伸力。 =l、中 林件其 则加速