《基于增广lagrange函数的rqp方法》由会员分享，可在线阅读，更多相关《基于增广lagrange函数的rqp方法（8页珍藏版）》请在金锄头文库上搜索。
1、基于增广L a g r a n g e 函数的R Q P方法 王秀国薛毅 北京s业大学 应用 数址学 院.北京 1 0 0 0 2 2 摘要 R Q P方法 是由B a r t h o l o m e w - B i g g s 等人发展 起来 的 解决非线 性规划的一种方法. 即将 增 广L a g r a n g e 函 致的局部 极小 点的 一阶 优 化 条件 转化为一 个非 线 性系 统. 本文 提 供了 一种通 过求解建立在增广L a g r a n g e 函数基础上的二次规划子阿 题得到搜索方向， 从而解决约束优 化问 题的新的算法， 它避免了罚因 子趋向于无穷的不利因素. 井利
2、用F le t c h e r 精确罚函 数作 为价值函数， 并引进其近似方向 导数， 以遵免计算二阶导数 又 本文证明了此种算法的全局收 敛性和局部超线性收敛性.同时提供了一些数值结果私 关 僻I R Q P 方 法 ， 约 束 优 化 间 题 ， 精 ， 罚 嗽巍 收 她汤 部 触酗她 R e c u r s i v e Q u a d r a t i c P r o g r a mmi n g Me t h o d s B a s e d o n t h e A u g me n t e d L a g r a n g i a n WA N G X i u g u o C o l l e
3、 g e o f A p p l i e d M a t h e m a l i c a n d Physic., B e ij i n g XUE Yi P o l y t e c h n i c U n i v e r s i t y , B e 示n _g 1 0 0 0 2 2 Ab s t r a c t R e c u r s i v e q u a d r a t i c p r o g r a m mi n g i s a f a m i l y o f t e c h n i q u e s d e v e l o p d b y B a r t h o l o m e s
4、v - B i g g s a n d o t h e r a u t h o r s f o r s o l v i n g n o n l i n e a r p r o g r a m m in g p r o b le m s . T h e f a s t - o r d e r o p t i m a l i t y c o n d i t i o n s f o r a l o c al m i n i m i z e s o f t h e a u g m e n t e d L a g r a n g i a n a r e t r a n s f o r m e d i n
5、 t o a n o n l i n e a r s y s t e m . T h i s p a p e r d e s c r ib e s a n e w m e t h o d f o r c o n s t r a i n e d o p t i m i z a t io n w h i c h o b t a i n s i t s s e a r c h d i r e c t i o n s f r o m a q u a d r a t i c p r o g r a m m i n g s u b p r o b l e m b a s e d o n t h e w e
6、 l l - k n o w n a u g m e n t e d L a g r a n g i a n f u n c t i o n . I t a v o id s t h e p e n al t y p a r a m e t e r t e n d i n g t o i n f i n i t y . We e m p l o y t h e F l e t .c h e r s e x a c t p e n a l t y f u n c t i o n a s a me r i t f u n c t i o n a n d t h e u s e o f a n a
7、p p r o x i m a t e d i r e c t i o n al d e r i v e t i v e o f t h e f u n c t i o n t h a t a v o i d s t h e n e e d t o e v a l u a t e t h e s e c o n d o r d e r d e r i v a t i v e s o f t h e p r o b l e m f u n c t i o n s . We p r o v e t h a t t h e a l g o r i t h m p o s s e s s e s g
8、l o b al a n d s u p e r l i n e a r c o n v e r g e n c e p r o p e r t y i e s . A t t h e s a m e t i m e n u me r i c al r e s u l t s a r e r e p o r t e d ， 国 家自 然科学基金第1 9 9 7 1 0 0 8 号 1I 基于增广 L a g r a n g e函 数的R Q P方法 8 2 7 K e y w o r d s : R Q P m e t h o d s , c o n s t r a i n e d o p t
9、 i m iz a t i o n p r o b l e m , e x a c t p e n a l t y f u n c t io n g l o b a l a n d s u p e r l i n e a r c o n v e r g e n c e . 引盲 朴lin亡 nS 对于等式约束规划问题 c ( 二 _ ( 1 . 1 ) 其中了 : 尺 ” 叶尺R斗 在本文中，利用增广 R. L a g r a n g e 函数 。 (二 ) 一 ， (二 ) + ， (二 ) + 1+ 2 0 IC (二 ).(1 .2 ) 其 中A 是 最 优 解: = 二 时 相 应 的
10、L a g r a n g e 乘 子叉 的 一 个 近 似， 是 罚 因 子 ，卜日 是 指 2 - 范数. 提出一个新的算法， 希望通过求解( 1 .2 ) 的极小点且使得。 不趋向于无穷来解 决等 式约束 优化间 题( 1 . 1 )在算 法中 利用F le t c h e r 精确 罚函 数作为价值函 数， 并引 进其 近似方向 导数.而且如果算法得到的序列 ， 、 王 入 * 有界， 罚因子也是有界的. 2 与 P ( x , A ) 的极小点有关的一个二次规划子问题 o f 幻是二次连续可徽的; D c ( 二 ) T =7 c , ( 二 ) ， 7 C 2 ( 二 ) ， ,
11、v e m ( x ) 1 对 一 切x Q R ” 均 为 列 满 秩 =f 二 ) + A T C ( 二 ) . 则 增广L a g r a n g e 函 数( 1 .2 ) 可 记为 =-幻 于是 D s P( 二 . A ) O -P( a ) P (一 ” = L (x ,A ) 普 ，Ic 回 已 =? 二 L ( x , A ) + o A ( x ) T C ( x ) , = V ,2 , L (二 ， J) + ， 党 c ; (x ) n c ; (a ) + ， ， (二 )A (x )T , (2l)洲 B (x , a ) = V 2- L ( 二 a ) +
12、。 艺C y ( x ) ,7 2 C , (x ) , 由牛顿法得 c 呈 z Pk ( x r , 4) ( x * 十 ， 一 二 、 ) 记A k =A ( x k ) , B k =B ( x k , A k ) 。 、 =c ( x k ) , 心二 =- 0 . P, ( x k , A k ) . : 、 + ， 一: *由( 2 . 2 ) 式得 B k d k + P k A k e k + Q k A , A l d , + C s L ( x k , A k ) 二( 2 .3 ) 轰 一万 只厂喻 甲一一 ， 8 2 8 王秀国薛毅 假 定B k 是 可 逆 的 ，(
13、 2 .3 ) 两 端 分 别 左 乘六 叮盯 得 ( 9k 。 : “ ) 。 、 一A T v 扣(X k 叉 、 卜叮笃伙h C k 例幽 八 T d kk = 一 。 * + 竺 其中 ( I + A k B g iA k) rkQ k一 、 B k IV , L (%k , A k) + Ck 将 ( 2 . 4 ) 代人( 2 3 ) 得 四洲 V , L ( 二 、 , A k ) +B k d k +A k r k =0 * =一 B k 1 ( A k r k + V , L ( 二 、 , k ) ) 易 看出 ， 如 果: k , d k 分别由( 2 .5 ) , (
14、2 .7 ) 式算出， 那么d k 也满 足( 2 .3 ) 式， 如果B k 以 某种 法 则矫 正， 易 证d k 是与 罚函 数P(二 . 初有关的一 个拟 牛顿方向 . 而且从( 2 .4 ) ;( 2 .6 ) 式中 可以看出d k , r 4 满足等式约束二次规划 ( Q P 2 . 8 ) 告 d T B k d k + V a L (x k , A k ) T d t A d 、 二 一 二十 0 ( 2 8 ) 的一阶优化条件 特别地，r k . 正好是 ( Q P 2 .8 ) 的L a g r a n g e 乘子， 而且其一个重要的 特 别之处在于L a g r a n
15、 g e 乘子和罚因子出 现在可行域的表达式中.很显然，如果假定B 、 正 定， 则对任意的， 、 。 ， 即使A 、 不是满秩的，由( 2 .5 ) , ( 2 . 7 ) 式得出的: k , d k 也是唯一确 定的. 因此二次规划 ( Q P 2 . 8 ) 的 可解性与A 、 的秩无关. 另外易看出 对于( 2 . 7 ) 式计算的 搜 索 方 向d k 间 题( I . 1 ) 的 约 束 条 件C ( 二 ) = 。 在。十 心处 的 一 阶 近 似 为e k + A 和 、 = 斋 ， 为使搜索方向d k 趋于可行域，二 、 斗二是必要的， 所以 在一些情况下，( Q P 2 .
16、 8 ) 是很难 精确求解的.为此我们 希望在新的 算法中， 避免。 、 、二来解决二次规划子问题. 现在考虑矩阵B , 如果， =x . A =A , 则。 ( 封=。 且此时由( 2 .1 ) 式定义的B等于 L a g r a n g e 函 数在i 处的I l e s s e i 、 阵.由 于B中包含着约束函数和目 标函数的二阶导数， 因 此在可 行的 算法中 ， 我们 都希 望 避免计 算B . 在( 2 .3 ) , (2 .5 ) , ( 2 .6 ) , ( 2 .7 ) 和( 2 .8 ) 式中 的B 可以 用? r , L 的只包含f 和c 的一阶导数的一个近似来代替， 且强使其是正定的， 各结 论仍成立.一个合适的关于B的迭代方法将在后文中给出. 3 基于增广L a g r a n g e 函数的R Q P算法 令( 川=一 川x
