文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 数学 > 解线性规划问题的基于新核函数的内点算法
侵权投诉

解线性规划问题的基于新核函数的内点算法

翩线性规划问题昀基孑新核函数昀内点算法 渤海大学数理学院吕佳佳 [摘要]原始一对偶内点算法是求解线性规划问题和非线性规划问题的重要方法。在本文中,给出了一个新的核函数。基于这个核函数可以构造出一个解线性规划问题的原始一对偶内点算法,并计算出了这个算法的一个理论迭代界。 [关键词]线性规划核函数原始一对偶内点算法大小步校正法理论迭代边界 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页

你可能喜欢

  • 核函数
  • 高中线性规划问题
  • 规划管理措施
  • 规划设计说明
  • 规划局
  • 核反应

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email