翩线性规划问题昀基孑新核函数昀内点算法 渤海大学数理学院吕佳佳 [摘要]原始一对偶内点算法是求解线性规划问题和非线性规划问题的重要方法。在本文中,给出了一个新的核函数。基于这个核函数可以构造出一个解线性规划问题的原始一对偶内点算法,并计算出了这个算法的一个理论迭代界。 [关键词]线性规划核函数原始一对偶内点算法大小步校正法理论迭代边界 1、内点算法
内点算法是一种在问题可行域内部生成趋近于问题最优解的点列的方法,它是解决线性规划问题的众多算法中最有效的算法之一。而在各种内点法中,原始一对偶内点算法的实用性更强。线性规划问题的原始一对偶内点算法是由T o d d和Y e 以及 A i d e d 等人首先提出的。 考虑线性规划问题的标准形式
1+ 。在按照前面所给出的步骤求出迭代边界前,我们先给出两个重 要引理。
弓 I理3 . 1设函数 ( 5 ): ( O,+∞)一( 1,+∞)是 ( )的反函数,其中 £> 1,则有
√ I _干了 ( ) 1+ 数,令
( 3 _ 3 )
( L P )m i n{ c x: A z= b, ≥ 0}, 其对偶问题可表示为
引理3 . 2设函数p:[ o,+∞)一( o, 1】是一吉 (£ )在( o, l】上的反函 f。:[ O,+∞)一( O, 1]是一 6 ( )在( O, 1]上的反函数,则有 f D ( )≥p ( 2+ 2 s ) ( 3 . 4 ) 现在我们开始求算法的迭代边界,我们设为计算过程中求得的 ( )的值的一个上界。
( L D )m a x{ b y: A y+ s= f, ≥ 0}, 其中AE R m x n ( r a n k ( A )= ), b E R , f E R”, Y E R , s i f r”。 不失一般性,知求解 ( L P )和( L D )的一个最优解等价于求解下面的 系统 Ax= b. z 0
A y+s=c, ≥O x s= 0
( 1 . 1 )
由于一 ( f )= 1+吉,所以我们可求出其反函数为 — 彳。 因此,根据引理得
即( L P )和( L D )的K— K— T系统。原始对偶内点算法的基本思想是
用参数方程 x s=/ l e{>o )替代( 1 . 1 )中的第三个方程,然后用牛顿法解 如
下系统 Ax= b0≥0
p ( s )去 由此,求得
( 3 . 5 )
A v+ 一c . ≥O
( 1 . 2 )
厂≤一 ( ( ) )
一筹
其中 >O, e一( 1, 1,…, 1 )。如果内点条件成立,则对于固定的
> o,系统( 1 . 2 )有唯一解( z ( ) , ( ), 5 ( ) )。我们称 - z ( )为( L P )的 中心,称I ( ), ( ) )为问题( L D )的/ J一中心。当一0时,一中心 一
根据引理 3 . 1知,函数 ( )的反函数满足、『 r干 i ( )≤1+ 。 因此,忽略掉自变量 v有
的集合产生一条由原始点到原始一对偶解的中心路径。原始一对偶内点算法的运算过程就是沿着中心路径逼近最优解的过程。 2、预备知识
所以根据 ( )吉 ( ( ( v ) ) ),我们得到
核函数在内点法的发展过程中占据着重要的地位。近年来白延琴教授等人采用由核函数构造的障碍函数作为原始对偶内点算法的 搜索方向。下面我们给出核函数的定义。
厕一南一 1] 由于 0≥ r≥1,因而
一
( 3 _ ) ( 3 _ 8 ) ( 3 9 ) .
定义设单变量函数: ( O,∞)一[ 0, o o )是二次可微的,如果满足下 列条件:
厂 一嬖 一—— 根据 =一———
( 1 )= ( 1 ):o; (£ )> O;
( 2 . 1 ) ( 2 . 2 )
2 5 ( 1+√ 1— 1 ( ),可以得出和 y的值 ,
≤ \/
{ ( )= l i r n (£ )=。。; 格凸的函数。
( 2 3 )
j——
),=百
1
则我们称其为核函数。根据( 2 . 1 )和( 2 . 2 )我们知 ( )是非负且严 白延琴教授在文献[ 5 1中列出求解算法迭代边界的步骤。在给出新 的核函数后,我们就可以按照其所列的步骤计算出新的迭代边界,步骤如下 . ,
2 5 ( 1+√而 ) 根据 ( 1 )= 4,我们看 2 f+ ≤ T因此,迭代边界为 ( 3 1 O )
S t e p 1解方程一 (£ )=,得到一吉 ( )的反函数l D ( ),其中 t f( 0, 1]。
s t e p 2根据不等式 _厂 ) 一 满
足
,计算 ( )的减少量。
l o g詈< 5 0 ( 1+ 边界为 厂 3、
)
(+ ) 詈 ( 3 .… o ( ),所以迭代
计算大步校正法,设 r=O ( n ),=@ ( 1 ),则
s t e p 3解方程 ( f )=s,得到 ( )的反函数 ( s ),其中£ 1。
S t e p 4根据 ( )≥ 1 ( ( ( ) ) )导出 : ( )的一个下界。 S t e p 5根据S t e p 3和S t e p 4的结果得到常数/, 2和7,其中7 E( o, 1], ,、
O『 l l 0 g詈。 / / 、
_厂 ≤一 ( )卜
接着我们计算小步校正法,设 r: o ( 1 ), :@ f{l,所以迭代边 f f三1 1
界为o ( ) l。 g詈。 参考文献 l 1 I To d d M T a n d Ye Y. A c e n t e r e d p r o j e c t i v e a l g o i r t h m f o r l i n e a r l 2 l Mo n t e i r o R . a nd Ad 1 e r I .I n t e r i o r po i n t p a t h -f o n o wi nR p i- r ma l—d u a l a l g o it r h ms .P a r t l: Li n e a r p r o ra g m mi n g,M a t h e ma t i c a l Pr o ra g m— mi n g, 1 9 8 9, 4 4: 2 7 -4 1 .
s t印 6根据 。 一
){ I,计算 。关于 )的唯
上界。
p r o g r a mmi n g[ P] Ma t h e ma t i c s o f Op e r a t i o n s Re s e a r c h, 1 9 9 0, 1 5: 5 0 8— 5 2 9
s t e p 7根据 l。 g詈导出迭代总数的一个上界。 S t e p 8计算大小步校正法的迭代边界。 3、基于新核函数的内点法的算法分析在本节中,我们给出一个新的核函数
( ):£ 一 1+ (÷一 l 它的三阶导数为
( 3 . 1
1 3 J B a i, Y., E l G h a mi, M., a n d Ro o s, c. A n e w e ic f i e n t l a r g e - u p d a t e p i r ma l— d u l a i n
t e r i o r - p o i n t me出o d b a s e d o n a i f n i t e b a r i r e r 1 1 j . S I A M f o u ma l o n Op i r mi z a t i o n, 2 0 0 2, 1 3 ( 2 ): 7 6 6 - 7 8 2 . 1 4 l B a i, Y., RO O S, C. a n d E 1 Gh a mi, M. A p i r ma l—d u a 1 i n t e r i o r - p o i n t me t ho d f o r 1 i ne a r o p t i mi z a t i o n b a s e d o n a n e w pr o x i mi t V f u nc t i o n』 T 1 . oD— t i mi z a i r o n Me t h o d s a n d S o f t wa r e, 2 0 0 2, 1 7 ( 6 ): 9 8 5 -1 0 0 8 . 【 5 l Ba i Y Q, E 1 Gh a mi, M, a n d RO O S . C. A c o mp a r a t i v e s t u d y o f k e r - n e 1 f u n c t i o n s or f pr i ma l-d u a 1 i n t e r i o r -p o i nt a l g o it r hms i n 1 i n e a r o p t i mi z a -
( ): 2£一丢一 1, ( f )=导+ 2, (£ )=一导
( 3 . 2 )
我们定义 (£ )=£ 一 1+ V b ( t ),其中 (£ )={一 t,则一 G( t ):
t i o n j 1】 S I A M 1 o u r n a l o n Op t i mi z a t i o n, 2 0 0 4, 1 5 0): 1 0 1— 1 2 8 .

单调线性互补问题基于新的核函数的大步校正内点算法_专业资料。提出了单调线性互补问题基于新的核函数的大步校正内点算法.这个核函数是强凸的,而且它既不是自正则...
基于指数型核函数的线性规划原始对偶内点算法_专业资料。给出线性规划原始对偶内... 解线性规划问题的基于新... 1人阅读 1页 0.50 论线性规划的原始一...
基于一个新的核函数,为一类...( 水平线性互补 问题基于核 函数的内点算法 陈华平 ;王胜 文 ( 六盘 水师 ...
在算法的分析中,引入了一个有限核函数取代经典的对数障碍函数从而导出新的可行步,并且证明了算法的迭代复杂性与目前已知最好的线性互补问题的不可行性内点算法的...
解线性规划问题的基于新... 暂无评价 1页 0.50 基于指数型核函数的...吮 竺 为什么在线性规划的内点 算法 中要将目标函 数非 线性刁 堵丁柱 吴...
基于核函数求解线性互补问题的不可行内点算法_数学_自然科学_专业资料 暂无评价
一种求解非线性整数规划问题的填充函数算法_专业资料。在本文中,对于求解非线性整数规划的问题,提出了一个新的填充函数和相应的算法,该函数只有一个参数,具有较好...
求解整数线性规划问题的一种新算法_专业资料。提出了一种求解整数线性规划问题的新方法。利用流动等值面技术的原单纯形方法,从初始整数可行解出发,逐步寻找下一个...
解灰色非线性规划问题的随机搜索算法_信息与通信_工程科技_专业资料 暂无评价
非线性规划问题的函数逼近算法与收敛性_理学_高等教育_教育专区。非线性规划... 解非线性两层规划问题的... 10页 免费 基于核函数的Camshift算... 11页 ...
热门文档