（运筹学与控制论专业论文）求解p非线性互补问题的非内点光滑算法.pdf

中文摘要 互补问题是一类非常重要的优化同题，它在工程、经济、交通平衡以及运筹学中 都有着广泛的应用经过几十年的努力，互补问题的研究得到了极大的发展，产生了 很多种有效的求解方法光滑化算法是一种有效的方法，该方法用n c p 函数把非线性 互补问题转化为非光滑方程组，然后引入光滑参数将非光滑方程组光滑化，最后通过 牛顿型算法求解光滑方程组，从而得到非线性互补问题的解 本文第章概述了互补问题的各种形式及其在工程、经济、运筹学等领域的应用；第 二章介绍了求解互补问题的几种主要方法；第三章针对文 3 0 】中给出的求解单调n c p 的非内点光滑算法，将其拓展到类更广的问题只n c p 上( 只n c p 包含单调n c p 作 为其特例) 并在不另加任何条件的情况下得到了算法的全局收敛性质，且证明了由算 法得到的互补问题的解是一个极大互补解 关键词；n c p 函数；只非线性互补问题；非内点光滑算法；极大互补解 a b s t r a c t u o m p 上e m e n t 甜i 锣p r o b l e m sa r ea l li m p o r t a n tb r a n c hi nt h em a t h e m a t i c a l p r o g r 锄 m l n gf i e l d a n dt h e yh a v ew i d ea p p l i c a t i o n si nm a n yf i e l d ss u c ha se n 舀n e e r i n g ，盼 n o m l c s t r 棚ce q u i l i b r i u mp r o b l e ma n do p e r a t i o n sr e s e a r c h c o m p l 锄e n t 撕协p r o b - l e m 8n a 、吧b e e nd e v e l o p e de x t e n s i v e l ya n dt h e r e h a v ed e v e l o p e dm a n ym m l e r i c a lm e t h - o d sf o rt h e m s m o o t h i n ga l g o r i t h mi so n eo ft h em o s te f f e c t i v em 砒o d s ；t h e m a i n 1 d e ao ft h i sm e t h o da 8f o l l o w ：f i r s tr e f o r m u l a t et h e c o m p l e m e n t a r i t yp r o b l 锄釉an o n - 锄0 0 t he q u a t i o n ，t h e na p p r o x i m a t et h en o n s m o o t he q u a t i o nb ya 硒埘o f 锄o o t h e q u a t i o ni n v o l v i n gas m o o t h i n gp a r a m e t e r ， s m o o t he q u a t i o n s f i n a l l yu s en e w t o nm e t h o dt o8 0 l v et h e 。l h 嘲sm a 沁】yd e a l sw 扣ht h ei l o n i n t e r o r - p o i n ts m o o t h i n g 以鲥t h m hc h a p t e ro n e ，d i f f e r e n tf o r m u l a t i o n so fc o m p l e m e n t a r i t yp r o b l e m s 甜e i i l t r o d u c e d ，a l n dt h e i r c a r l o 瑚a p p l i c a t i o n si ne n g i n e e r i n g ，e c o n o m i c sa n do p e r a t i o n sr 圈e a r 出a r ed 裙c r i b e d b r l e h y s 0 m ee x i s t i n ga l g o r i t h mf o rc o m p l e m e n t a r i t yp r o b l e m sa r ed 姻c r i b e di nc h 玲 t e r i 、w 0 i nc h a p t e rt h r e e ，t h en o n - i n t e r i o r - p o i n t s m o o t h i n ga l g o r i t h mf o rm o n o t o n e n c pp r o p o s e di n 【3 0 】i se x t e n d e dt os o l v i n gt h e p n c p , w l l i c hc o n t a i 璐m o n o t o n en c p a u sas p e c l a lc 嬲e ，a n di t sg l o b a l l yc o n v e r g e n c e i so b t a i n e dw i t h o u ta n ya d m t i o n 砒c o n d i t l o n m o r e o v e r ，t h es o l u t i o no b t a i n e db yt h ea l g o r i t h mi sp r o v e dt ob e8m a 对m 越l v c o m p l e m e n t a r ys o l u t i o no ft h ep , n c e 。 k e yw o r d s ：n c pf u n c t i o n ；只n o n l i n e a rc o m p l e m e n t a r i t y p r o b l e m ；n o n - i n t e r i o r - d o i n t s m o o t h i n ga l g o r i t h m ；m a x i m a l l yc o m p l e m e n t a r ys o l u t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的研究成 果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发表或撰写过的 研究成果，也不包含为获得天津大学或其他教育机构的学位或证书而使用过的材 料与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示了谢意 学位论文作者签名：彳杀南支 签字日期：2 p 多年2 月“日 学位论文版权使用授权书 本学位论文作者完全了解天津大学有关保留、使用学位论文的规定特授权 天津大学可以将学位论文的全部或部分内容编入有关数据库进行检索，并采用影 印、缩印或扫描等复制手段保存、汇编以供查阅和借阅同意学校向国家有关部门或 机构送交论文的复印件和磁盘 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：手釜南良 签字日期：2 。口；年1 2 - 月f 日 导师签名：c 蠢矗彤鸯导师签名：c 企i 辩 签字日期：谢年l 月“日 第一章互补问题 第一章互补问题 互补河题最显著的特点就是包含互补性条件； z 0 ，8 0 ，z 1s = 0 即要求两个( 或多个) 非负量的积为0 ，这里的非负量可以是数量也可以是向量 早在1 9 3 9 年k a r u s h 研究带不等式约束的连续变量非线性规划的最优性条件时就 提出了互补的概念，但直到1 9 6 3 年h o w s o n 把一个双矩阵对策的n a s h 平衡点问 题转化为一个线性互补问题，互补问题才得到人们足够的注意，对互补问题的研 究才真正开始了随后非线性互补问题也被提出。之后c o t t l e 和d a n t z i g 把线性 规划问题、二次规划问题和双矩阵对策问题统一表述为线性互补问题，一系列的 突破性工作激发起人们对互补问题研究的高潮经过几十年的研究，互补问题的 理论和算法都得到了极大的发展而趋于成熟 1 1 互补问题的分类 1 1 1 线性互补问题 在各种互补问题中，最简单的，也是研究最深入、应用最广泛的一类问题要 数线性互补问题( l c p ) 了，因此被称为运筹学中的一类基本问题线性互补问题 的一般形式为： 给定矩阵m 驴孙，q 舻，求z 舻，s 舻满足： s = m z + q ，z 0 ，8 o rz 丁s = 0 ( 1 1 ) 通常用符号l c p ( m ，q ) 来表示一个线性互补问题线性互补问题的名称来源于 ( 1 1 ) 中的互补性条件t , t 8 = 0 ，它要求问题的解满足条件：，s 1 ) 中至少有一个 量为0 ，其中i = 1 ，2 ，扎每一个( 翰，岛) 称为一个互补对 下面是一些本文中要用到的与矩阵相关的概念 定义1 1矩阵m 舻煳，z = 1 ，2 ，礼) ， 1 若对任意z 舻，且z 0 ，存在i z 满足： 】 第一章互补问题 筑0 ，且x i ( m x ) t 0 ， 则称m 为岛矩阵； 2 若对任意z 舻，且o 0 ，存在i z 满足t 戤o ，且x i ( m x ) t 0 ， 则称m 为p 矩阵； 3 若存在非负数下。对任意z 舻，满足t ( 1 + r ) x i ( m x ) i + x i ( m x ) l 0 ， i e l + ( 霉) i e i 一( o ) 其中4 ( z ) = 【i z ：x i ( m x ) i o ) ，l ( z ) = t z ：鳓( m z ) t o ) ，则称m 为只 矩阵 若m 为半定矩阵，则l c p ( m ，q ) 称为单调l c p ；若m 为r 矩阵；则l c p ( m ，q ) 称为p o l c p ；若m 为只矩阵，则l c p ( m , q ) 称为只l c p 对标准线性互补问题( 1 1 ) 作一些扩展，就可以得到多种不同的线性互补问 题下面，我们简要地介绍其中的几种 混合线性互补问题( m l c p ) ；给定a 咿黼，b 舻m ，d 妒黼， e 妒m ，c 舻，舻，求z 驴，y 舻，s 舻，满足t i a 秒+ b x + c = 0 ， d + 眈+ ，= s ， ( 1 2 ) l z 0 ，s 0 ，x t s = 0 这个问题是由一个l c p 和一个关于无约束变量y 的线性方程组组成的混合问 题同时含有等式约束与不等式约束的二次规划问题的最优性必要条件就是一 个形如( 1 2 ) 的m l c p ( 1 2 ) 式中，若a 为非奇异矩阵，则y = - a - 1 ( b x + c ) ( 1 2 ) 可表示为标准线性互补问题l c p ( e d a b ，一d a _ 1 c ) 水平线性互补问题( h l c p ) ；给定n 舻姗，m 渺肌。q 卯，求 z 舻，s 舻，使下式成立， 尬+ 8 + 口_ 0 ( 1 3 ) l z 0 ，s o ，x t $ = o 、7 当n = i 时，式( 1 3 ) 就是一个标准的线性互补问题；若为非奇异矩阵，( 1 3 ) 式等价与线性互补问题l c p ( - n m ：一_ 口) 第一章互补问题 垂直线性互补问题( v l c p ) t 给定t 【1 ，2 ，n ，佻为正整数且m = n i _ - - 1 佻，m 舻煳，q 妒，且 m = m 1 ，j 炉】r ，口= f q l ，剌 矿跪帆x n ，矿蹰，t = l ，2 ，礼 求z 舻，使之满足( 1 4 ) 式： m t m x + q 芝0 ，z 0 ，觋( 1 - i ( 埘$ + 一) j ) = o t = 1 ，2 ，n ( 1 4 ) j = l 显然，若对每一个i 都有佻= 1 ，则上述v l c p 就是标准l c p 一般线性互补问题( g l c p ) ；给定a 妒加，b 妒肌，c 妒d 且 q 孑p ，求z 乳n ， s 蹰礼，z 蹰：d ，使得： 血+ b s + c z = q ，( z ，s ，z ) 0 ，x t 8 = 0 1 1 2 非线性互补问题 非线性互补问题( n c p ) 的标准形式为t 给定非线性函数，：舻_ 舻，求 o 咿，s 舻，满足下式。 s = ，( z ) ，z 0 ，s 0 ，z t s = 0 ( 1 5 ) 显然当函数f ：咿_ 舻为仿射函数m x + q 时，( 1 5 ) 式就退化成标准线性 互补问题l c p ( m ，q ) ，因此非线性互补问题可以看作是线性互补问题的非线性扩 展 下面是几个非线性互补问题中常用到的与函数相关的定义： 定义1 2设函数f ：舻_ 舻， 1 若对于任意的z ，y kc 舻，都有 ( z y ) 丁( ，( z ) 一，( 可) ) 0 ， 则称函数，为k 上的单调函数； 2 若对于任意的z ，y kc 舻，z y ，都存在i 1 ，2 ，n ) ，满足： ( 魏一玑) ( 五( z ) 一五( 可) ) 0 ， 则称函数，为上的户函数； 3 第一章互补问题 3 若对于任意的，y kc 舻。z y ，都存在t 1 ，2 ，n ) ，满足： ( 甄一玑) ( ( z ) 一五( 可) ) 之0 ， 则称函数，为k 上的昂函数； 4 若存在一个非负数1 - ，对于任意的z ，y kc 舻，满足： ( 1 + 7 ) 芝二( 私一玑) ( ( z ) 一 ( y ) ) + ( 戤一弘) ( ( z ) 一 ( 可) ) 0 ， i e i + ( 。，v ) i j 一( 君，v ) 其中， 4 ( z ，y ) = t 1 ，2 ，n ) ：( 一佻) ( ( z ) 一 ( 秒) ) o ) ； l ( z ，y ) = 1 ，2 ，几 ( z ，可) 则称函数，为k 上的只函数 显然，若r = 0 ，则只函数就是单调函数，即单调函数是只函数的一个特 例倒如函数，( z ) = ( x l 一5 x 2 ，勉) t 是只函数但不是单调函数 在n c p ( 1 5 ) 中，若函数，是单调函数，则称n c p 为单调n c p ；若函数，是 昂函数，则称n c p 为p o n c p ；若函数，是只函数，则称n c p 为p o n c p 标准非线性互补问题n c p ( 1 5 ) 的形式便于理论上的分析。但由实际问题 归结出的模型更多的是混和互补问题( m c p ) ：即：给定函数，：舻_ 舻， 2 蹰u o 。) 竹，t 验uo o n ，且2 t 正，求z 舻， 加舻。秒舻，满足 下式： ， i s c x ) 一t l ，+ t ，= 0 ，i z f 0 ，伽0 ，( z 1 ) t w = 0 ， ( 1 6 ) i u z 0 ，口0 ，( 缸一z ) t t = 0 注意在上述定义中，当：= 一o 。，u = o 。时，混和互补问题m c p ( 1 6 ) 就是方程 ，( z ) = 0 ；而当f = 0 ，u = o o 时，混和互补问题m c p ( 1 6 ) 就是标准非线性互补 问题n c p ( 1 5 ) 标准非线性互补问题和混和互补问题都是另一类更广贬的问题变分不等式 问题( p ) 的特例变分不等式v i ( k ，s ) 的定义；给定函数，：舻一舻， 仍kc 舻，求矿k 满足： ( 可一z ) 丁i ( x ) 0 ，对vy k ( 1 7 ) 在y i ( g ，) 的定义中，当k = z i z o ) 时，( 1 7 ) 式就退化为非线性互补问题( 1 5 ) 式；当集合七为矩形即k ：= 1 - i ：l t i ，啦】( 其中： 一o 。如 0 中的一条路径来降低，s 到0 其中的路径为下面的含参 数系统的解集： 占= m x + q x ( 8 i = p ，t = 1 ，2 ，n( 2 1 ) z 0 ，s 0 ， 上式中每给定一个p ，就会产生一个路径上的点从初始点( z o ，s o ) 开始，取不 同的p 就会得到一个沿着上述路径的迭代点列 ( 矿，s 七) 每次迭代通过下面的 方程来计算： x - i 奄s m k 临a x k - s k - m k x k - q 第二章求解互补问题的算法 其中胪和x 。是两个对角矩阵，它们的对角元分别为t 链= s ，磁= 砖，且 触= ( 扩) t s 七n 实际上这个方程是把牛顿法应用到( 2 1 ) 式得到的 下一个迭代点( + 1 ，s 七+ 1 ) 定义为： ( x k + 1 ，s 七+ 1 ) = ( ，8 七) + q 七( ，a s 七) ， 其中q 的选取应保证迭代点离路径不会太远 内点法的一个缺点是它的起始点必须是一个严格可行点，即初始点( x o ，s o ) 必须满足8 0 = m 一+ q ，且( 护，8 0 ) 0 要找到这样一个初始点并不总是一件容 易的事情，其难度与求解l c p 本身相同 内点法不仅可以求解线性互补问题，也可以求解非线性互补问题 2 2求解n c p 的算法 本节介绍几种求解n c p 的方法，为了讨论的方便，我们只考虑标准n c p ( 1 5 ) 2 2 1 序列l c p 算法 序列l c p 法是通过求解一系列的l c p 来求解n c p 的方法，这类方法通过 产生一系列迭代点 ) 来逼近n c p 的解迭代点列中，z 1 是l c p ( m 鬼，q 七) 的 解，其中舻，矿的选取要使得在处l c p ( m k ，q 七) 逼近n c p 基于舻，矿的 取法不同，会产生不同的算法，如牛顿法、拟牛顿法、投影法等不同算法中 m 七，矿的取法见【8 】这里只考虑牛顿法，相应的m ，口j c 取法为m 七= v f ( z 七) ， q 七= ，( ) 一m k x k 实际上这里的，七( z ) ：- - - m k x 七+ q 七是函数，的一阶泰勒逼近 j o s e p h y ( 9 】) 已证明在n c p 的解矿的领域内，由这种方法产生的迭代点列二次 收敛于矿如同用牛顿法求解非线性方程组一样，需要使用一种策略来扩大算 法收敛的区域用牛顿法求解非线性方程时使用了后退线性搜索的策略，即每 步都沿着牛顿方向d 七= 一+ 1 一妒搜索，以确保每次迭代都能使价值函数充分地 下降但是这种策略用在n c p 上却很不成功，主要原因在于对有目的选取的价 值函数，牛顿方向不能保证是其下降方向 r a l p h ( f 1 0 ) 给出一种不用牛顿方向的后退策略即沿着连接一与l c p ( m 七，q 七) 的解的一条逐段线性路径作搜索使用这种搜索方法的牛顿序列l c p 算法是全 局收敛的 1 2 第二章求解互补问题的算法 2 2 2 光滑型算法 借助n c p 函数可以将n c p ( 1 5 ) 重构为等价的非线性方程组这里的所说的 n c p 函数定义为t 设函数西：铲_ 乳，若咖( a ，b ) = 0 净口0 ，b 0 ，a b = 0 ，则称 函数西是一个n c p 函数例如函数 西( 口，b ) = m i n a ，6 就是一个最简单的n c p 函数 n c p 函数的作用是可以把互补问题重构为只含一个等式的问题，从而把复 杂的问题归结为求解方程组的问题解方程组是我们熟悉的，有多种方法可以使 用，例如人们熟知的牛顿型算法 对任意给定的n c p 函数咖，定义函数圣：舻一渺如下； 垂( z ) = ( z t ， ( z ) ) ： ( z n ，厶( z ) ) ( 2 2 ) 则矿是非线性互补问题n c p ( 1 5 ) 的解的充要条件为它是西( z ) = 0 的解( 【1 1 1 ) n c p 函数有很多种，选用不同的n c p 函数就会得到不同的方程组若n c p 函数是连续可微的，则圣也是连续可微的，这种情况下就可以用经典的牛顿 型算法解方程组圣( z ) = 0 若n c p 函数咖不可微，则圣也不可微，从而不能直 接使用牛顿法来求解方程组圣( z ) = 0 这时需要使用光滑化方法来处理，即先 用n c p 函数将互补问题重构为一个非光滑的方程组，然后用带参数( 称为光滑参 数) 的光滑方程组近似这个非光滑方程组，最后再用牛顿型算法求解含参数的光 滑方程组在一定的假设下，并通过对光滑参数进行适当的控制，这个光滑方程 组的解收敛于互补问题的解 基于可微n c p 函数的方程组有一个缺点：它在n c p ( 1 5 ) 的退化解矿处 ( n c p ( 1 5 ) 的退化解是指对某些下标i 有= 五( 矿) = 0 ) 的雅克比矩阵是奇异 的，从而使牛顿型算法的快速局部收敛性不再具备而且，对于可微的n c p 函 数都存在这种雅克比矩阵的奇异性所以在实际计算中，可微n c p 函数使用的 并不多，一般都采用不可微的n c p 函数 下面具体描述一下光滑化算法的过程这里我们考虑问题n c p ( 1 5 ) ，n c p 函 数取为( n ，b ) = m i n a ，吣，显然在a = b 上不可微为了方便讨论，将n c p ( 1 5 ) 写成如下形式：求向量( z ，s ) 舻铲，使得 1 3 第二章求解互补问题的算法 ( i ) s m ) = o ， ( 2 3 ) ( i i ) z 0 ，s20 ，x t s = 0 、 其中，：舻_ 渺是一个非线性函数 根据n c p 函数( o ，b ) = m i = a ，6 ) ，用方程组圣( z ，s ) = 0 来代替n c p ( 2 3 ) 中 的条件( i i ) 设函数日为： 脚，= s - f ( = 眨4 ， 其中圣( z ，s ) = ( 咖( z 1 ，s 1 ) ，咖( ，s n ) ) t 舻，( z t ，8 1 ) = m i n z t ，吼 0 = 1 ，佗) 则( 矿，s ) 满足互补问题( 2 4 ) 当且仅当( 矿，矿) 是方程组 日( z ，s ) = 0( 2 5 ) 的解 由于函数( n ，b ) = m i a ，6 ) 在a = b 上不可微，故方程组( 2 5 ) 是非光滑的 为能够使用标准牛顿型算法求解( 2 5 ) ，下面考虑将( 2 5 ) 光滑化近似 对不可微n c p 函数( a ，b ) = m i n a ，h 在a = b ，可以使用几种不同的光滑 化方法，这里用c h k s ( c h e n - h a r k e r - k a n z o w - s m a l e ) 光滑函数 钆( q ，b ) = 去( o + b v f ( a - - b ) 2 - 4 - 4 t 2 ) ( 2 6 ) 来逼近它对函数h 定义中圣( z ，s ) 酌每一个分量函数曲( 翰，s i ) ( t = 1 ，2 ，n ) 都 用相应的光滑近似函数钆，s t ) = ( 瓤- 4 - s 一匿= i 严f 砰) 来代替，则有： 脚；= 愀孙 防7 ， 其中钆( z ，s ) = ( 钆( z l ，s 1 ) ，札( z n ，8 n ) ) t 形相应地有如下光滑方程组 - i ( z ，s ) = 0 ( 2 8 ) 在算法的迭代过程中，使光滑参数p o ，则用牛顿法求解方程组( 2 8 ) 得 到的点列( ，s p ) 收敛于方程组( 2 5 ) 的解( 矿，s ) ，从而求得互补问题n c p ( 1 5 ) 的解 与内点法不同，光滑化算法的初始点不必要求是内点，因此光滑化算法也常 被称为非内点算法另外，光滑化算法也可以求解线性互补问题 第二章求解互补问题的算法 2 3n c p 函数与光滑函数 n c p 函数与光滑函数是光滑化算法的核心之一文献中已经给出了多种 n c p 函数以及光滑函数 上一节给出了n c p 函数的定义，即：噼一驼，若 ( d ，b ) = 0 错n 0 ，b 0 ，o h = 0 ， 则函数为n c p 函数下面是几个常见的n c p 函数； ( n ，b ) = m i n t , , ，6 ) ， 咖( o ，b ) = 、面丽一n b ， ( a ，6 ) = 去曲2 o ，n + 6 ) - 口6 ， ( d ，6 ) = ( 口一6 ) 2 一口i 口j b l b l 1 9 7 6 年，m a n g a s a x i a n ( 【1 2 ) 提出并证明了n 维非线性互补问题( 1 5 ) 完全等 价于求解一个含有n 个未知数的由n 个方程组成的非线性方程组实际上，求解 互补问题的方程组方法正是基于这项工作下面给出该定理的叙述和证明 定理2 1设函数0 为实数域验上的严格递增实函数，即口 b 寺兮9 ( 口) o c b ) ；并满足0 ( 0 ) = 0 则z 是互补问题( 1 5 ) 的解的充要条件是 e ( i h ( z ) 一兢j ) 一口( 五( z ) ) 一p ( 盈) = 0 ，i = 1 ，2 ，死( 2 9 ) 证明：必要性若z 是互补问题( 1 5 ) 的解，则对每个i = 1 ，2 ，扎，或 者龟= 0 ，或者 ( z ) = 0 如果筑= 0 ，则口( 1 五( z ) 一戤f ) 一口( 五( z ) ) 一o ( x i ) = p ( 五( z ) ) 一p ( ( z ) ) 一0 = 0 ；如果 ( z ) = 0 ，贝00 ( i a ( z ) 一戤i ) 一口( ) ) 一口( 戤) = o ( x i ) 一0 一o ( x i ) = 0 充分性设z 满足方程( 2 9 ) ，证明其满足互补问题( 1 5 ) 中的三个式子 ( a ) 为证明f ( x ) 0 ，用反证法，即假设对某些i = 1 ，2 ，扎， ( z ) i 鼢一 0 ) i = 甄一 ( z ) 这与五( z ) 0 如果五( z ) 盈，则 o ( i f , ( z ) 一魏i ) = 口( 五( z ) 一甄) 1 是算法3 1 中给定的常数则对所有的k 了有) ； ( i v ) 序列 胀) 非负且单调递减； ( v ) 血皿女二i i h ( z 2 ) l i = 0 且l i m 七一+ 肛七= 0 证明：( i ) 我们分两步来证明算法适定性s ( a ) 首先来证明s t e p2 中的方程可解易见对任意的( p ，z ，s ) 雌+ x 舻x 舻， 日7 ( z ) = 10o 0 - f 7 ( z ) j d ( z ) + zd ( z ) e ( z ) 其中，表示钆x 礼单位矩阵， d ( z ) ：= v i 戈 一2 ( 盈一s ) 2 + 4 p ：i z ， d ( z ) ：= d i a g 1 + p 一( z t 一& ) 、( 而一s i ) 2 + 4 p ：i z ) ， e ( z ) ：= d i a g 1 + 0 ， 1 9 第三章一个求解只n c p 的非内点光滑算法 旧南l d ( 名)e ( z ) l 是非奇异的( 见【3 5 】，引理4 1 ) ，进而对任意的名跪1 + 加，当弘 0 时日，( 名) 是非 奇异矩阵由s t e p2 中的等式可得到 ： p 七+ 1 = 弘七+ x a # k = ( 1 一a k ) k + a k o z ) l l h ( z 七) 0 0 ， 这表明对所有的k 歹，都有风 0 从而s t e p2 中的方程可解 ( b ) 下面来证明s t e p3 中的线性搜索准则是适定的令r ( z 七) ：= h ( z 七+ a x z 七) 一 h ( z 七) 一a h ( ) a z k 则由s t e p2 中的方程可得 i i h ( z k + q ) l i = i i r ( z k ) + h ( z 七) + a h z 七) i i r ( z 奄) | l + 【1 一a ( 1 1 卢) l l h ( z k ) 1 1 注意到对任意的z 跪1 + 加，当p 0 时日是连续可微的，从而对所有的七3 ， 有l i r ( z b l l = d ) ，这就表明s t e p3 中的线性搜索准则是适定的 结合( a ) 和( b ) 可知( i ) 成立 ( i i ) 显然序列 l l h ( z 七) 盼是非负的，由s t e p3 中的线性搜索不难得到序列 h h ( z 七) l | ) 单调递减 ( i i i ) 由初始点的取法知z 0 ( p ) 假设对某个z 了，有= ( 肌，一，8 。) ( 卢) ，则 肌+ l 一( 1 卢) 1 1 日( + 1 ) 0 = ( 1 一) 胁+ a , ( 1 f 1 ) l h ( z 2 ) 一( 1 , 8 ) i l i - t ( z 1 ) ( 1 s 9 ) ( 1 l h ( z t ) l i - i i h ( z 2 + 1 ) 1 1 ) 0 结合( i i ) 的结论则有卢p f + 1 i i h ( z l + 1 ) 1 1 从而对所有的k 了有( 卢) ( i v ) 由( i ) 的证明过程可知序列 p l | c ) 非负，结合( i i i ) 和( i ) 的证明过程，可 得对任意七了。 p 七+ 1 = ( 1 一a 七) p 七十入k ( 1 d ) l l g ( z 七) i | ( 1 一a 七) p 七+ 入七弘k = p 七， 这表明序列 弘k ) 单调递减 ( v ) 为证明( v ) ，首先来证明下面的结论： 第三章一个求解只n c p 的非内点光滑算法 ( r o ) ，是一个连续的只函数，假设口 0 和厨 0 是两个标量且口 乒则 对所有的p 陋，厕，有l i m l l ( 霉。) 1 1 i i h ( z ) i i = 0 0 下面用反证法来证明( r 0 ) ；假设( r 0 ) 不成立则存在一个无界序列z 七= ( 肌，矿，驴) ) 满足对所有的k 了，肌呛，翻且 l l h ( z ) l l 有界，由h 的定义有 j i h ( z 七) 1 1 2 = p ；+ i j s 七一，( z 七) 1 1 2 + l i 圣( z 七) + p 七z 七1 1 2 ， 从而，8 七- f ( x 七) ) 和【西( ) + 凤矿) 有界对所有k 了，令夕( 矿，矿) ：= s 七一f ( x 七) ， 则 9 ( 扩，s 七) ) 有界且扩= ，( 矿) + g ( x 奄，驴) 由于序列 ( 铲，8 k ) ) 无界，则或者 扩) 无界或者矿无界现在假设 矿) 无 界来导出一个矛盾，是连续的只函数，则由【4 l 】中引理1 可知存在一个子序 列，不失一般性将其记为 扩) ，和如满足或者域_ 0 0 且 厶( 矿) ) 有下界，或 者磙_ 一0 0 且 五。( 一) ) 有上界注意到 9 ( 矿，s 七) ) 有界且对每一个七了， 矿= f ( x 七) + g ( 9 ，s 七) ，从而有或者磕一0 0 且 s 乏) 有下界，或者一一o 。且 ) 有上界所以由磙一。有 + ( 1 2 ) p k z 乞_ 0 0 且s 乞+ ( 1 2 ) p 七_ 0 0 ， 由磙一- - 0 0 有 + ( 1 2 ) p 七_ - - 0 0 且+ ( 1 2 ) p 詹_ - - 0 0 进一步，由函数咖的性质( 如令参( e ，口，6 ) ：= a + b 一 石= 丽，其中( ，a ，b ) 铲， 令害和手是两个标量且满足拿 专假设序列( ( 七，口奄，泸) ) 满足( i ) 对所有的k 歹， 舌 0 由i i 亨( z + ) i l 0 有l i m k - + k = 0 从而对充分大的k ，步长 轧：= k 6 不满足s t e p3 中线性搜索准则，即对任意充分大的七，有 1 日( + k ) 0 【1 一口( 1 1 p ) 氟 l l h c z 七) 1 1 ， 这表明 遐丛坠掣剑 一口( 1 - 1 i p ) l l h ( z k ) 1 1 由m 0 可知h ( z ) 在点z 处连续可微令k _ o o ，则由上面的不等式可得 蹁h 他懈押( 1 1 i t ) i i h ) 1 1 另外，将s t e p2 中等式的两边取极限可得h 7 ( 矿) 矿= 一日( 矿) t - l l z l l h ( z 。) l i e o ，这 表明- 1 + 1 , 6 + o ( 1 1 p ) 0 这与卢 1 ，且盯( 0 ，1 ) 矛盾所以，h ( z ) = 0 进而，由h ( z ) 的定义有纵一0 至此，结论( i ) - ( v ) 全部得证 口 引理3 2对任意的( p ，n ，b ，c ) 跪+ + 跄乳驼，有 咖( p ，a ，b ) = c 营口一c 2 o ，b c 2 o ，且( 口一c 2 ) ( 勺一c 2 ) = p 证明：首先证明( p ，n ，的= 0 仁专a 0 ，b 0 ，且曲= p ： 一方面( p ，口，b ) = 0 ，即a + b v ( a - b ) 2 - t - 4 # = 0 得( o + 6 ) 2 = ( 口一6 ) 2 + 4 p ，展 开得p = a b ，又a b = p 0 且n + b 0 ，所以口 0 ，b 0 ； 。 令一方面a 0 ，6 0 ，且a b = p ，则 a + b 一、( 口一6 ) 2 + 4 p = n + b 一、( n + 6 ) 2 = a + b 一( n + b ) = 咖( p ，n ，b