一个修正的罚函数方法.pdf

2 0 0 4 年 1 2 月 De 5 2 0 0 4 应用数学与计算数学学报 CoMM oN AP PL MA TH AND COMPUT 第 1 8 卷第 2 期 Vo 1 1 8 NO 2 一 个修正的罚函数方法 高圣国 姚奕荣 上海大学数学系 上海 2 0 0 4 3 6 摘要 本文通过给出的一个修正的罚函数 把约束非线性规划问题转化为无约束非 线性规划问题 我们讨论了原问题与相应的罚问题局部最优解和全局最优解之间的关系 并给出了乘子参数和罚参数与迭代点之间的关系 最后给出了一个简单算法 数值试验表 明算法是有效的 关键词 非线性规划 K K T乘子 罚函数方法 1 引 言 考虑如下的非线性规划问题 m i n I x s t z R g i x 0 i 1 2 m 其中 和g i i 1 2 m是二次连续可微函数 假设 z 具有下面的性质 I 所以存在一个有界闭箱 使得 i n t X包含 的全局极小点 本文中我们考虑上面 问题的等价问题 P m i n s t S z X g i x 0 i 1 2 m 引入函数 r t t t 0 t 上 t 一 1 t 0 由此 我们构造修正的罚函数 得罚问题如下 m i n p 九 加 本文 2 0 0 4 年 4 月 2 O日收到 维普资讯 应用数学与计算数学学报 这里 P 0 t 0 i 1 2 m 我们用 G 和 L 分别表示问题 的全局极小点和局部极小点 本文给出的修正的罚函数与文 1 所研究的函数不同 我们首先用比较初等的方 法研究了原问题和相应的罚问题的全局最优解的近似等价性 然后证明在满足二阶 充分条件 罚参数足够大时 原问题的局部极小值点是相应的罚问题的严格局部极小 值点 此外我们还给出了原问题的 K K T乘子和罚函数中的参数间的关系 最后 我 们给出了一个简单的算法 两个算例表明所给方法是有效的 2 主要结论 下面我们证明主要的定理 定理 2 1若 G P c i n t X G P e B O 1 c i n t X 其中 0 B O 1 R Il训 0 1 2 m 这 里 0 7 7 mi n s B e 1 G P B e 1 一f x G P 0 E 1 0 9 如 如 x s m i n 1 m a x g 1 9 2 g m Ax e 所有 X有 lf x l M 那么 对任意 X G P e B O 1 Q x 入 P 0 S G P e B O 1 总 有f x f x 成立 因为s G P e B 8 1 是紧集 f x 连续 所以存在E 1 0 且 E 1 0 使得 S E I B 8 1 G P E B 8 1 时 成立f x f x 此外 m a x g 1 g 2 x g m 是连续函数 且 s e l B 8 1 是紧集 所以成 立 B m a x g 1 9 2 9 m g i o X i o 0 下面把 分为两种情况 1 S e i B O 1 G P e B O 1 时 一m Q x 入 p l A i O s g t i l m f x 一 入 1 f x f x A i cp P g t i 1 Q x 入 p 2 X S e i B O 1 这时 是不可行点 从而 m a x g l x g m g j x 9 如 如 0 维普资讯 2 期 高圣国 姚奕荣 一个修正的罚函数方法 8 1 Q p i p 一M 一 1 一 M一 叼 A j a t p 9 未 一 M一叼 M i o p g Q x p 所以在定理的条件满足时 对所有 X G P e B O 1 成立 Q P 0 则存在正数 使得当c 时 P c Q是正定的 定理2 3 若 i P n i n t X 并且一阶和二阶最优性充分条件在 成立 K K T乘 子 i 1 m 严格互补 即Y Y R y T V g i x 0 Y 0 E I x 时 一 0 且 0 i I x 贝 4 令 t 入 i 1 2 m i E I x 当P充分大时 Q 证明 因为 Q p 鲁 p Q x p v f z p g i x V g i 又因 0 i I x 0 1 所以 并且 Q x p v f z p i E I x v f z 0 i E I x m Q x p 九 p g i x V p T g i 1 Q x p g i p o v g i V g T i E I x i E I x 因为 f x g i x 在 y y T V g x 0 y 0 上是正定的 i E I x 1 V g i x T g i x 是半正定的 0 2 0 i I x 由引理可知 当P 充分 大时 Q x P 正定 所以 是Q x P 的严格局部极小点 即 Q 定理 2 4如果 G Q A p n i n t X G P P和 0 i 1 2 m满足定 理2 1 的条件 并且vg i t I x 线性无关 则v f z p 圭 i EI z 1 这里 九 p 圭 p 是 P 的近似的K K T点 证明 根据定理2 1 有G Q A p C G P e B O 1 当P 和 i i 1 2 m满足定理 2 1 的条件 充分小时 则有 G P 使得 忙 一 ll 且 v f z p V f x 9 i p V g i x 9 p g i x 记 1 2 一 m p 0 当i 时 圭 圭0 当 i I x 时 g i x 0 所以I x 因为X G p n 所以 k i n t X m Q p V f z p 九 p 0 i 1 维普资讯 2 期 高圣国 姚奕荣 一个修i E ff 罚函数方法 8 3 当i 时 1 和容许误差 E 1 E 2 1 计算f X 0 V Q 0 A o p 如果 lV Q 0 A o P l E 1 停止 第2 步 求Q 一 1 P 的极小值点 计算f X k V Q 一 1 p 第3 步 如果 l V Q P l E 1 或 lIx k 一 1 ll E 2 停止 否则 一 1 p g i x k 1 2 m 1 P P 返回第2 步 例1 ra i n y x i 2 l 一 2 z l z 2 2 z l 一 6 z 2 s t X l 2 2 一Xl 2 z 2 2 Xl 2 0 这里 g l X l 2 2 9 2 z 一 X l 2 z 2 2 X 1 x 2 lO X i 2 1 2 g 1 鲁 g 2 表 1相关的计算数据 z 1 z 2 VQ z p p 1 2 z Q z 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 4 0 8 6 8 5 4 0 4 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 3 2 2 0 0 0 0 4 5 5 9 1 3 4 1 0 7 9 2 9 8 0 1 1 9 6 2 4 2 3 0 5 7 3 0 5 0 4 0 4 0 0 0 0 4 3 2 8 2 5 0 6 5 0 3 6 4 7 1 6 9 7 9 8 7 3 9 8 6 3 6 2 0 7 9 9 8 9 1 1 2 0 0 0 5 2 3 0 6 8 9 0 2 0 4 0 8 0 4 0 0 4 2 9 0 8 1 0 4 8 1 8 3 0 7 1 9 9 8 3 9 7 3 6 5 4 7 7 3 0 7 9 9 9 2 7 1 2 0 0 0 7 3 3 1 1 2 2 7 6 0 4 1 2 1 2 0 0 4 2 9 0 6 1 0 3 5 6 1 5 4 7 2 0 0 0 0 0 7 3 2 2 2 4 3 维普资讯 8 4 应用数学与计算数学学报 l 8 卷 根据表 l 终止点是 z 0 7 9 9 9 2 7 1 2 0 0 0 7 3 的最优点是 0 8 1 2 函数值为 一 7 2 例2 m i n f x 2 x 2 x l 一2 x 1 z 2 4 x 1 s t X l 5 x 2 5 2 z i z 2 0 这里 g l z X l 5 x 2 5 g 2 x 2 x 一z 2 函数值是 x 一 7 2 0 0 0 0 0 事实上目标函数 一 6 x2 Xl X 2 0 z X z 1 x 2 10 X i 3 i l 2 9 l 9 2 表 2相关的计算数据 1 z 2 Q z P p 1 2 f x Q 0 0 4 0 0 0 0 0 0 9 0 0 0 0 0 2 3 0 8 7 4 8 0 1 4 0 0 0 0 1 0 0 0 0 0 0 0 8 0 0 0 0 0 5 7 8 0 0 0 0 6 3 0 7 7 7 2 1 0 5 9 2 9 2 6 0 8 8 1 2 8 5 1 0 1 9 5 0 7 0 1 4 9 8 0 0 0 9 7 2 5 7 7 0 6 8 4 3 4 9 6 4 4 8 0 3 9 6 5 6 7 4 2 6 2 0 6 5 8 8 6 3 0 8 6 8 2 0 9 0 5 5 6 3 9 8 0 1 6 0 2 8 6 0 9 7 2 3 8 8 0 6 4 9 2 3 3 6 6 1 2 9 9 3 6 6 1 3 O 8 8 3 0 6 5 8 8 6 6 0 8 6 8 2 0 8 0 5 5 6 3 0 0 0 1 7 1 5 0 6 0 9 7 2 3 5 9 0 6 4 9 2 3 1 6 6 1 2 9 9 7 6 6 1 3 0 8 9 根据表 2 终止点是 z 0 6 5 8 8 6 6 0 8 6 8 2 0 8 函数值是 f x 6 6 1 2 9 9 7 事实上目 标函数的 最优点是 0 6 5 8 8 7 2 0 8 6 8 2 2 6 函数值为 一 6 6 1 3 0 8 6 参 考 文 献 l 1 R P o l y a k Mo d i fi e d B a r r ie r F u n c t i o n s T h e o r y a n d M e t h o d s Ma t h P r o g r a mm in g 1 9 9 2 5 4 1 7 7 2 2 2 f 2 1 K Ar r o w L Hu r w i c z H U z a w a S t u d i e s o n L i n e ar and N o n h n e ar P r o g r a mmi n g S t anf o r d Un i v e r s i t y P r e s s S t a n for d CA 1 9 5 8 3 G D i P il l o L G r ip p o E x a c t p e n a l t y m e t h o d A l g o r i t h m s fo r c o n t in u o u s o p t im i z a t i o n E S p e d i c a t o Kl u we r Ac a d e mi c Pu b l i s h e r s Ne t h e r l an d s 1 9 9 4 2 0 9 2 5 3 B u r k e A n e x act p e n a l i z a t i o n o f c o n s t r a i n e d o p t i mi z a t i o n s I A M J C o n t r o l and O p t i m i z a t i o n 1 9 9 1 2 9 9 6 8 9 9 8 5 15 Mo k h t ar S B a z ara a H D S h e r a li C M S h e t t y N o n li n e ar P r o gra m m i n g s e c o n d e d i t io n J o h n W i l e y S o n s l n c 1 9 9 3 A M o d i fi e d Pe n a l t y M e t h o d Ga o S h e n g g u o Ya o Yi r o n g D e p a r t me n t o f Ma t h e ma t i c s S h a n g h a i U n i v e r s i t y S h a n g h a i 2 0 o 4 3 6 A bs t r ac t I n t h i s p a p e r a mo d i fi e d p e n a l t y f u n c t i o n me t h o d i s g i y e n wi t h wh i c h a c o n s t r a i n e d n o n h n e a r p r o gra mmi n g p r o b l e m i S c o n v e ne d i n t o a n u n c o n s t r a i n e d p r o b l e m Wle d