（运筹学与控制论专业论文）求解约束问题的一类乘子罚函数法.pdf

摘要 本文提出爿：分析一种解决约束最优化问题的修改的桊子罚函数法。与经典罚函 数相比较，修改的罚函数法是连续可微的，消除了五1 罚函数的不可微性。在此基础 上，文章在修改的罚丞数里号l 入拉揍朗强黍子，这榉修改的罚爱数渡不但瀵涂了厶 锾醋数静不冒徽性，同时，遗过校东拉格馥鹜乘子，也避免了要求参数憨予无穷大 静缺点。 本文是按如下方式组织的：第一章为绪论部分；第二章介绍本文收敛往理论所 需甏的最优性条件和基本的假设条件；第三章给出修改的罚函数的定义和憔质，修 改的罚函数的收敛理论，并且给出两个算法模型及其计算结果；第四章引入拉格朗 日乘子，讨论乘子罚函数法；第五章将等式约束问题的乘子法推广到一般约束问题； 最质是附录内容，给出本文所用的数值实验例子。 关键词；最优化，约束忧镬：l 、嗣题，修改豹罚函数法，黍子法。 j 寒工业大学理学壤士学枝论文 a b s t r 鑫c t w ep r e s e n ta 1 1 da n a l y z eam o d m e dm u l t i p l i e rp e n a l t y 胁c t i o nm e t l l o df o r s o l v i n gc o n s t r a i n e do p t i m i z a t i o np r o b l e m s c o m p a r e d 谢t 1 1 厶e x a c tp e n a l t y 如n c t i o n ，妣m o d i f i e dm m t i p l i e rp e n a l t y 矗m c t i o ni ss e q u e n t i a la n dd i 凰r e n t i a b l 。 殛sm e t h o d 勰o i d s 娃艟i n d i & r c n t i 如i i 睁o f t 王l e 矗p c n 西t y 如n c t i o n u n d e rt h e e o n d 主t i 鳜s ，w ei n 把r l a 蟠t km o d i 五e dm u 糙p i i e rp e n a l t y 如n c t i o n 谢畦1l a g r a n g e 撼u l t i p l i 粥t 躯s ，熬s 掰e 耄h o d 鑫。to 珏 y8 v o 遗s 氇ei 盛熟r 。蛹辐i i 毋o f 锤e 五 p e n 鲢锣魅瑶畦o n s o u ta l s o8 i d s 蛙辑f e 幽o f 蹦v i 端p 躲匝e e rt o 十o 。b y u p d a t i n gl a 掣a 1 1 9 em u l t i p l i e f s t h i sp a p e ri so r g a n i z e da sf o l l o 、 隅i nc t 磕l p t e rl ，也eb a c k g r o u n da n dt h em 铵i n r e s u l t so f t h i sp 印e r 鼬eg i v e n t h eg e n e m ip r o g r 甜n r n i n gp r o b l e ma n d 血eb a s i c 聪s u i 芏j 窜i o 糙黼d e rw h i 穗o u rc o 船v e f g e n c er e s u l t sh o l da r ei n 仕o d u c e di nc h a p t e r2 t h cd e 蠡n 嫩o no f 也em 。d i 蠡e d 秽魏a l t y 是轻c 专至。鞋w 撼馥。糙m e 重量轮d 主sb a s 舞。建i s i n t r o d u c e di nc h a p t e r3 ，、状a l s op r e s e 呲也ec o n v e r g e n c er e s u h so f t h em e 牺d 越l d t w oa l g o r i m m sa i l ds o m ea s p e c t sc o n c e r n i n gt h ep r a c t i c a li m p l e m e n t a t i o n i nc h a p t e r 碎，w ei r 她r l a r d 协em o d i 五e dp e n a l t y 如l c t i o nw i t l ll a g r a n g em u l t i p l i e r st od i s c u s st l l e 斑糠t 量p l i e rp e 越袅l 锣f 瀛c i 。nm e 墩。d t h em u l t i p l i e rp e n 蠢移触c 娃。拄r n e 铂o do f c o n s 侄a i n e do p l i 噬z a t i 。珏p b 王蝴sw 热e q 髓l 主t yc 。毪s 娩溉si s 。x t e 盎d e dt o 妇g e 建e 蕊 c o n s t r a i n e do p t i m i z a t i o np r o b l e m si nc h a p t e r5 a n di n 饿e a p p e n 出x ，t h ec o n s t r a 量】d p r o b l e m sw es 0 1 v e da r ep r e s e n t e d k e y w o r d s ：o p t 溉i z a t i o n ，e o n s t r a i 魏e do 越i m i z a t i o n 转出l e 糖，m o d 菠聪p e 建菇锣蠡避c i 。n ， m u l t i p l i e rm e t l l o d 1 1 独创性声明 本人声臻辑呈交携谂文是我令人在导辉摇舅下逡行懿繇究工 乍及敬得酾磷 究成果。尽我所知，除了文中特别加以标淀积致落鲍蜓方终，论文中不包含葵魅 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书筛使用过的材料。与我一同工作的间志对本研究所做的任何贡献均 己在论文中作了葫确的说明并表示了谢意。 签名；蠢亟亟日期：型61 曼笪 关于论文使用授权的说明 本人宠全了解l e 京工渡大学有关缳餐、镬建学位论文黪勰定，鄯：学捩窍权 保髓送交论文的复印件，允许论文被凌阅和借阅；学校可以公布论女的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 僳密的论文在解密后应遵守此规定) 签名：垄鱼垫导簿签名扭雠塑i ：奎梦 1 。1 背景知识 第一章绪论 最优化理论与方法是一门应用性很强的年轻学科。最优化，就是在复杂环境 中遇到的许多可能的决策中，挑选“最好”的决策的科学。它研究某些数学上定 义的问题的最优解，即对于给出的实际问题，从众多的方案中选出最优方案。 本世纪3 0 年代末，由于军事和工业生产发展的需要，人们提出了一些不能 用古典微分法和变分法解决的问题。1 9 4 7 年d a n t z i g 提出求解一般线性规划问 题的单纯形法之后，在许多学者和广大科技工作者的共同努力下，最优化逐渐发 展成为一门独立的学科。现在，解线性规划、非线性规划以及随机规划、非光滑 规划、多目标规划、几何规划、整数规划等各种最优化问题的理论的研究发展迅 速，新方法不断出现，实际应用日益广泛。在电子计算机的推动下，最优化理论 与方法在经济计划、工程设计、生产管理、交通运输等方面得到了广泛应用，成 为。门十分活跃的学科。 数学规划是最优化理论的一个重要分支。数学规划，是指对 个变量对单目 标( 或多目标) 函数求极大( 或极小) 。而这些变量也可能受到某些条件( 等式 方程或不等式方程) 的限制。其数学表达式为： m i n 厂( x ) ，x r 1 ， s c ，( x ) = o ，i e = 1 ，2 ，f ，( 1 1 ) c i ( x ) 兰o ，f = ，+ 1 ，+ 2 ，- - ，+ 晰 ， 这里1 i l i n 表示求极小，5 f ；j “自阳甜f o 意思是受限制于，x 是n 维向量，其分量 为耳，墨，在问题( 11 ) 中称，( x ) 为目标函数，称q ( x ) = o ，( fs e ) q 0 ) o ( i e ，) 为约束条件a 若求极大，可以将目标函数写成n d n ( 一，( x ) ) ，若不等式约 束q 0 ) o 可毗写成一c f ( z ) so 。 在问题( 1 1 ) 中，若厂( x ) 、q o ) ( f e e u ，) 均为线性函数，则得到的规划称 为线性规划，其般表达式为 为线性规划，其般表达式为 j b 京工业大学理学硕士学位论文 m i n ，( x ) = c 7 x ，x r ”， s q ( x ) = 并一缸= o ，f 暑= 1 ，2 ，z ，( 1 2 ) q ( x ) = x 一包o ，f ，= f + l ，+ 2 ，z + 州) ， 在问题( 1 1 ) 中，若，( 句、q ( x ) ( f e u j ) 中之一是非线性函数，刚称为非 线瞧规划。 藩问题的一般表达式为 烹撩篙i ， n 。) s r 。，( x ) = o ，f = 1 ，2 ，z ， 、7 称为等式约束闽题。 若去掉婀题f l ，1 ) 的约束条件，则褥到 m i n ，( x ) ，x l 量r “，( 1 4 ) 称为无约束最优化问题。因此，也称问题( 1 1 ) 为约柬最优化问题。 现代醛攀、经济黯工程麓许多麓运毒羧予稳盔终采菲线犍蔑麓麓蘧的全筠焉 优解的计算技术。约束非线性规划问题已广泛涉及到许多重溪的邻域，其中包招 经济模垄，龛憨，溺络与运输，数字集成设计，图像处理，纯学工程设计与羧制： 分子生物学，环境工程及军枣科学等等。在过去的几十年闻，由于约束非线性却 划在许多都域的重要应用，蕻理论和方法已得到了缎大的发展。 鼠前，常忍的求鼹约束优化阕鼹有两类方法。一类是剥爆约束l 、罐题本身靛憾 质，赢接求解约束问题，例如有效集法。另一类方法是将约束问题转化为系芽 无约寒阉题，逶过求解一系列无约象最铙纯阉题，米褥型鲶索邂题瓣爱挠麓。蘧 类方法称为序列无约束极小化方法( s e q u e r i c a lu n c o n s t r a i n e dm i n i m i z a t i o n l e c 弧i q u 8 ) 。本文中将要讨论豹惩稳函数法灏乘子法靛属予居耱方法。 晟早的罚函数( p e n a l t yf u n c t i o n ) 法是由c o u r a n t 在1 9 4 3 年提出来的，其基 本葱惩是：对不满足约束条件的点进行惩罚，通过求解多个罚函数的极小得到美 束问题的最优解。 对于约柬规划问题( 1 1 ) 的罚函数是指利用目标函数厂( x ) 和约荣函数c ( x ) 繇秘造静虽基有“鬟性覆”粒函数 2 尹x ) = 爹( ，( 冀) ，。x ) ) l 。5 ) 所谓“罚性质”，即要求对所有( 1 1 ) 的可行点均有p ( x ) = 厂( x ) ；而且当约束条 件破坏很大时有p ( x ) 远大于，( x ) 。为了精确地描述约束条件被破坏的程度，我 倪建义约寒遗反度函数c + ( x ) = f + e ) ，毋( x 灯如下 4 + ( x ) = q ( x ) ，f e = 1 ，2 ，z ) ；( 1 6 ) ( x ) 一m 飘 o ，茁) ，f g j = f + l ，f + 掰 我们定义集合 c = c l c r ”，q 篇o ，f e ；q o ，f j ( 1 7 ) 由定义，x 是可行点当凰仅当c ( x ) e c 。不难看出，对任何爿矗”都有 ( 锼= 魏r 奴x ) ，g ) ( 1 8 ) 上式右端的从点到集合的距离的定义如下： 蕊嚣( 墨r ) = r 嫩n 毪x y l l ：歹y ； ( 1 9 ) 正由于上式，我们称c ( 叶( 算) 是约束违反度阐数。 在一羧陵况下，爨函数可表示为嚣舔涵数与一项与c x ) 有关酌“罚项”之 和，即 尹= ，盖) + 女( 。q x ) ) e ) 罚项 ( c ( + ( x ) ) 是定义在尺”上的函数。它满足 磊( o ) o ( 1 ，1 1 ) i 毂矗( c ) = 惝 ( 1 1 2 ) 最旱静蠲露数是e o 珏r 张t 弱滋数，它定义魏下 p ( z ) = 厂( x ) 叫( 州 ( 1 1 3 ) 显然，l 。1 3 ) 是( 1 i 。) 敬磊扣) = 秽嘲；豹特殊情形。搴实上对艘4 中任饼范数戳 及任何口 o ，函数自( 。) = 盯4 都满足( 1 1 1 ) 和( 1 1 2 ) 。于是一类罚酯数可由下 式定义： p ( x ) 盥，( x ) + 拶i q ( x ) ( 1 1 4 ) 其中盯 o 楚罚因子，鼎 o 以及嗣是r 斑c p 的菜一范数。罚韵数( 1 1 0 ) 的另两个 特殊情形是 # ( x ) = ，( z ) + 仃i l 。( x ) | l ， ( 1 1 5 ) 只( x ) = 厂( x ) + ( x 壮 ( 1 1 6 ) 它们被分别称为厶罚函数和瓦罚函数。 罚璐数般与某个罚参数有关。热果当罚参数取大予蒺个较大歪数黪僮( 或 者取大予零旦小于某个小正数的德) 时，对应的罚闷题的极小点与暇约囊闻题的 极小点之间存在某种精确的对应关系，则称对应的罚函数为精确罚激数，否则被 称为非精确罚函数。 对等式约束问题，常用的罚函数为厶罚函数，厶罚函数定义如下： p ( 驴) = ，( x ) + 到e 删： = ，( x ) + 等妻瞰x ) 2 ( 1 1 7 ) 关于厶罚函数有下列定理： 定理1 1 设善是约束越题( 1 ，3 ) 蛇全鼹最锉解，惩嚣辫子 递增越予螂， 若_ j c 2 是镯函数夕( 矗啄) 的全届群，刚 x 缸 的任一聚点必怒约泶问越( 1 1 7 ) 的全 局样。 证鞠：冤文献 1 定理i i 1 2 证螭。 鑫定瑾荔知，与镄函数法静优点是将约束闯题化成一系别无约束问题，可 用求解无约束问题的算法得到约荣问题的最优解。但是厶罚函数要求罚因子趋 于无穷大，当惩罚因子吼充分大后，函数_ p ( x ，) 邋常怒一个病态函数，即其 h e s s e 矩阵v ( 黾，嚷) 的条件数非常大，迭绘无约束问题的求姆带来了圈难。 由z 8 n g w i l l 最早提出懿磊壤礁爨蹑数法鸯教地解决了这一不足。毛精确弱 函数的好处之一是露透过求舞有隈令无绞索润遂寒精确求解一约束饶讫阔题。 厶糖臻鼷丞数定义为： 第| 章鳞论 咖( x ，盯) = ，( x ) 十盯i l c ( x ) l ( 1 1 8 ) = ，( z ) + g 瞰善) | ，= 1 对于厶精确罚函数有下列定理： 定理1 2 设x + 是约束问题( 1 。3 ) 的局部最优解，a 是相应躲l a g r a n g e 黍子。 如果二盼充分条传满足，且匹 睁虹，则x 是( 1 。1 8 ) 蛇局部严接极小点。 芷明：照文献 2 】定理7 。3 。l 涯骥。 惠她定爨可以番蹬，只要露玎 p 轧，粼只翥求籁一个无终隶傀纯滴题 篓爹垂 麓仃) 帮可褥裂阚遂( i 一3 ) 静最伉解，那么这样虢避免了如罚黼数中由于要 求黼因子趋予无穷大胼带来的无约束闯题计算上的豳难。但是这样也带来了新的 淹壤，崮于( i ，1 8 ) 楚一个不可徽涵数，扶祷一些收敛较快的利掰导数的方法不能 蹇接曩寒求解。且在实际计算时，宙予它鹃不可徽毪雨使算法产生所谓的 “m a r o t o s 效敷”，扶愿产生隰止快速爨罄收敛懿现象，嚣魏在蜜际计算中连裁不 可行的。 所以，很自然的一转想法是能不畿将j # 光辫函数使之光、媾化，搜褥凝构造的 函数是连续可微的，且构造这个函数所需的参数只要求充分大而避免趋予无穷 大。若能这样的话，既究成了有约束问题向无约束问题的过渡，又避免了求解无 约束问题可能出现的困难。本文提出的新的罚函数方法就是基于这样的出发点提 出的。 飞。2 阍题的提出 考虑下列不等式约束问题： 卿，( x ) ， j f 。( x ) 墨o ( 1 ，1 9 ) ( 其中，( x ) ：呻霆及x ) = ( c t ( x ) ，乞( x ) r ：f 峙垮为连续爵镦溺数) 罚函数( 1 。l ? ) 可推广到不等式约寒润趱： p ) = 饰) + 帮q ( 销 = 巾) + 詈静 2 ( 1 z 0 ) 其中 c 卜( x ) * ( c + ( x ) ，c ( x ) y ， c ! + ( 工) = m a ) ( o ，乞( x ) ) ，j - l ，耽 ( 1 2 1 ) 其中c ( + 扛) 为约束造反度函数。 对于不等戏约束最优化问题，最卷用的罚函数是利用搬巨数红) + = m a x 冀，o 来构造的( 其中x 是实数) 。作为一个罚函数，当f 充分大时，在一定祭馋下， ( 1 2 0 ) 的局部最优点是问题( 1 1 9 ) 的局部最优点( 见文献 3 卜一 5 ) 。懊显然的， 加函数是不可微的，它的不可微性为计算带来困难。注意到( x ) + = 掰( j ，炒，其 中搿( y ) 是由下式定义的阶梯函数 甜：1 1 ，矿x o ， 、7 l o ，矿善o 琵又默l 副，l 7 ，l 8 学，俘褥捌嬲s i g 辩o i d 添数 s b 搿) 2 石，g o 作为阶梯函数掰( x ) 的一个近l 戥。于是搬函数( x ) + 可蠢s i g 辩。i d 溪数懿积分 x ) + = m 双 薯o * p ( 墨瑾) 。s ( 弘8 ) 毒= 茗+ 去l 。g l e 一) ， 采近似。 对于函数p ( 并，嫂) ，硝 o 来说，我们淀意到它具商下列基本性质( 见文献 9 ) 。 l 对任何正整数，p ( t 掰) 是2 次连续可微的。并且，p ( 一掰) 2 五茹和 矿b 小南 2 p f 石，甜) 在盅上是严格凸函数 6 3 p ( 戈，a ) ( 工) + ，v 七r a 肾，a ) 一( x ) + ) = p ( 吩) = 等 5 艘p ( 础) 一( 工) + = o ，v a ，o 6 熙p ( 五口) = ( x ) + ，觇胄 7 p ( z ，口) ( o ，c 。) ，觇r ，o ，o 对x ( o ，。) ，反函数p 。1 是有定义的 8 p ( z ，a ) p ( x ，芦) ，v a 卢，工r 因此在文献 9 中，作者用p ( z ，口) 来近似加函数( z ) + ，为不等式约束最优化 问题提出一个光滑近似罚函数，得出了很好的性质。但是由于p ( z ，口) 中的e 一项 而导致在实际运算中容易发生上溢出现象，所以又带来新的问题。 另外，文献 1 0 基于文献 9 ，为等式约束问题的不可微精确罚函数提出了 一个新的近似函数，具体形式定义如下： 尸( z ，“，a ) = 厂( x ) + 盯薹 昙，。s ( e 一“q 扛+ e 。q 扛) ，a ，。 ( 1 2 2 ) 这个修改的罚函数，消除了l 罚函数的不可微性，完成了约束问题向无约束问题 的过渡，避免了因惩罚因子趋于无穷大而带来的求解无约束问题时可能出现的困 难。但是由于修改的罚函数中的e “。( 。) + e “，项，所以此篇文献还是没能很好地 解决文献 9 中提出的罚函数容易产生上溢出的问题。 受这两篇文献的启发，我们考虑能否寻找出一种新的等式约束问题的不可微 精确罚函数的近似函数，使之既可以消除l 罚函数的不可微性，又能解决文献 1 0 中在计算过程中容易产生上溢出的问题。 注意到罚函数中( 墨盯) 是利用绝对值函数来构造的，又 i z i 剖p ( x ，口) ；工2 + a 2( 1 2 3 ) 因此我们考虑利用绝对值函数酬的近似函数p b ，a ) 为等式约束问题提出一个新 的近似罚函数。 7 北寰王业大学理学颈士学挝论文 1 ，3 算法的基本思想与文章结构 对于等式约束优化问题，最常用的罚阉数越厶罚函数，但厶罚函数要求惩 罚闳子趋于+ 。，这给无约束问题的求解带来很大困难；厶糖确罚函数虽然很好 地解决了这一问题，只需求解有限个无约束问题即可求得原来有约束间题的最优 解，但由于l 精确罚函数是不可微的，这同样给无约束问题的求解带来困难。因 此我们考虑用一个连续可微的函数来近似不可微的l 罚函数，消除其不可微性， 既完成脊约束问题向无约束问蹶的过渡，又可避免因惩罚因子趋于无穷大而带来 的求解光约束闰题时可能出现的困难。 本文结稿辩下，在| 9 蠹器一牵给斑定瑷涯翡所需酌最优毪条伟帮基本假设， 在燕三豢绘出修改毁罚函数躲定义及性震，势讨论修滚爨羁函数法熬牧敛理论， 给出两个迭代算法以及实验结果；第四章对修改的罚溺数进行进一步的改进，讨 论相应的乘子罚函数法；篇五章将等式约束问题的乘子法推广到一般约束问题； 最蘑是附录内容，给出本文中所用韵数值实验例子。 8 l 。，垒鎏耋些璧塑薹笙鏊，。，。，一 第二章最优性条件和基本假设 2 1 最优性条件和基本假设 考虑如下一般的约束优化l 司越 m i n 厂( z ) ，z 五“， “ q ( x ) = o ，f e = 1 ，2 ，f ) ， ( 1 1 ) c ：( 工) 玉o ，f j = 2 + 1 ，f + 2 ，2 + m ) ， 定义2 1称线性独立约束条件( 简称为( l i c q ) ) 在x r ”处成立，如果 对约束函数c g ) 有v q g l f e 是线性独立的。 定义2 2称在x r ”处m a n g a s a r i a n f r 。n c v i t z 约束条件( 简称为 ( m f c q ) ) 成立，如果存在一个z r “使得 v c 。( x ) 7 三 o 。 定理2 5 设x 毫是并且严辏互 条，f 牛在该点成立，懿菜阔题囊1 ) 翡髫标 函数，帮终束滠数c 在x + 的一个领域内二阶连续可徽，且二阶充分谶条件 = v ：上a + ) z o( 2 11 ) 1 n 纂2 章簸撬性条转和蒸本嫒设 碱r “，z o ，v c f ( x + ) 7 孑= o ，f 毫互( 2 1 2 ) 在b ，0 ) 处满足，莉z + 难( 1 1 ) 的一个严格局部极小点。 定理2 + 6浚蠢为一正宠矩辫，嚣为与叠同除虢经一对称矩阵，掰芒r ，粥 存在掰。，o ，使德当材，膨。时，器+ 础也是正定短阵。 诞明：设对 o ，嚣+ 删都不是正寇矩咚。则歉其“，蠢# 0 蠖褥 矗( 暑+ 捌) g ；d 蒯谢_ 矗 h ，慨r 。 4 * 学扫0 ，搿) 一蛳= p ，掰) = 怫 5 _ 。投p g ，口) 一h = o 。 6 基銎p 扛，g ) = x ，搬g r 。 1 2 7 p g ，删) s ( o ，。0 ) ，帆r 。对x ( o ，。) ，反函数p - 1 是有定义的。 8 。p e ，掰) p g ，x v b l 眵l ，盖g 冀。 我们到蠲函数目熬返像丞数多( x ，搿) 为润麓( 1 。3 ) 提爨一个毅懿透经光潜罚 函数虫爨下： p ( 聃，拶) ：，十f 妻f 届丽虿)( 3 i ) 并研究它的性质。 3 2 函数p g ，口，盯) 的一照基本性质 弓| 理3 2 p 墨搿，d ) 秘性淡为 1 对任意强定的甜，只疆m x 蜃g ) ，扣l ，聊是次连续可微的，刚 p g ，d ，d ) 是次连续可微的。如果厂0 l 0 ) ，f = 1 ，m 是二阶连续可微的，则 v z p g ，g ，亨) 2w b ) + 仃善器且 v 妒) 矧弛) 十仃芝塑型脚盟业擘掣幽 6 1 ( q 2 ( x ) + 扩) i 2 。若，e ) ，g 。g x f 。l ，雕楚凸麟数，则p ( x ，d ，搿) 墩是凸通数。 3 p e ，莎，g ) e ，盯) ，vx 式”。 4 鬻i ( 尹e ，盯，甜) 一审g ，仃势= 聊净i 。 5 墓盈p o ，盯，口) = 也0 ，盯) 6 ，如果l 口；l b ：! ，则p g ，盯，掰，) p g ，盯，d ：) ，任意x g 屁”。 j b 京工业大学理学硕士学位论文 3 3 定理及其证明 假设。下列假设条件成立。 假设a 任意，盯露+ ，p ( x ，皿。) 的全局最优解是农一个有界集合中。 定理3 。l 若後设矗戏立量吲仃一o ，x + 是瀚题( 1 。3 的全蜀鼗饶解，a + 是 相废的l a 掣a n g e 黎予，如暴二阶充分条件满足，且，娅+ 畦，则当拶充分大时， 集合 丸，。) 的任何聚点膏都是问题( 1 3 ) 的解。 证： 设x 是问题( 1 3 ) 的全局最优解。由于戈是集食扛。 的聚点，则存 在每。；翡一个子疼捌备。 满足 l 受心一 但魑p 仁，曝) 的全局最优解，因此有 ，( t ) t p ( 故，吼) g p 扛+ ，吼，嚷) g 厂( z ) + 卅1 i( 3 2 ) 令露一。，有，转) 岳，；。 现在证明量是可行的。如果量不可季亍，则一定存谯一个攒标f 使褥c ； ) 辨。因 此由( 3 2 ) 有 ，仁。) + d 。c ；2 0 。) + 口2c p b 。，a + ，盯+ ) 茧，( 工) + 州吒1 i ( 3 3 ) 觚蕊 ，眩) + 嚷又丽妄，每j + 蹦哝k 3 。4 令一。，因为有h 口一o ，所以( 3 4 ) 的左边趋向+ 。而右边是有上界的，这 是一个矛盾。 霾照，童是可行翡。 又因为冀是阅题( 1 3 ) 的全局最优解，鼹此有，( 芏) s ，圣) ，艇娃 ，( 并+ ) = ，( 量) 。 1 4 缘合戳上，我们筇遭该怒理藏立。证毕e 引理3 3 假设0 ) 煅一连续函数序列且，e ) 是一个连续函数，五g ) 致收敛到，g ) 。若靠是旮白局部极小点且“_ x + ，则x + 是，g ) 的局部最小 点。相反，如暴x + 是，6 ) 严格最小点，赠存在的菊部最小点缸。 使雩罄 x h 寸x + 。 证赘既文献 蜘孳| 理2 1 。 定理3 2 假设x 是问题( 1 3 ) 的严格极小点，五为相应的拉格朗日乘子， 如果二阶充分条件满足，且盯 肛+ k ，则当盯充分大且h 斗。时，存在 p ( 善，颤拶) 驰局部极小点靠。，满足吒，岭蔗+ 。 证明：根据 2 中的定理7 ，3 1 ，我们知道当盯充分大时，x 是由( 1 1 8 ) 定义 懿辔( 长盯) 麓届辞投小点。 对于个固定的盯，由引理3 2 ( 4 ) ，我们知道p ( x ，a ，仃) 一致收敛到国( x ，1 仃) ， 根据引理3 - 3 ，必存在p ( x ，口，秽) 的局部檄小点，满足，呻z + 。证毕。 定理3 3 缀设陬| 斗。基壤是p 0 ，a ) 鲍髑部极小点，则 豹经俺聚 点都是o g ，盯) 的局部极小点。 歪赘：囊雩| 瑾3 - 2 ( 4 ) 缮，对于霞定的仃，尹( x ，捞，仃) 一致牧敛弼国( 五仃) ， 又坼是p ( x ，盯) 的局部极小点，则当七呻o 。时，由引理3 。3 知， 的任何聚 点都是中( x ，盯) 的局部极小点。 3 。4 两个算法模壁 在本繁绘基嚣个冀法模型。 算法3 1 中要求吼斗m ，l 吼l 呻o ，且f i 砷o 。 算法3 1 步1 ：给定初值，q 0 ，s o ， o ，时 1 ，七= 1 ； 步2 ：令女= 兜+ 1 ，以心一，作为初值，鳃下列无约束最优化问题 翟多p 6 ，冁，口* ) 3 5 ) 缛到簸优点瓢； 步3 ：如果e 地s ，则停，否则令吼。= 嚷m 熹，1 + ，l = 1 t 场，转 步2 。 由定理3 1 并注意到1 嚷岭o ( 膏一。) ，有 定理3 4 假设k 由算法3 。l 产生显x + 是溉 懿一个聚点。热采定理3 1 孛黪螽传满足，剐善+ 是阕霆( 1 。3 ) 全爨辍夺患。 现在给密另乡 一个舞法。 在算法3 ，2 中，给定q ，鲞可行被较环辩，港翔仃值， 吼j _ o 且k i 吼一o 。 算法3 2 步1 给出初 誊，q o ，饼l o ，m 1 ，s o ，膏= 1 ： 步2 令觅= 尼十l ，阁x 。作为初值，解下列无约柬最优化问题 巴势尸0 ，盘e ，盯t ) ( 3 。6 ) 、+ 7 、7 得到摄优点磁； 步3 鲡聚 c x 灞。，剐蒋，否辅令p 。i 。扛； 步4 如桊陋( 靠) 乳 肛( 一。) 甩，转步5 ；否痢= 吼，转步2 ； 步5 仃= 吼m ，转步2 。 对算法3 2 ，有下列定理： 定理3 5 设假设a 成立并且问题( 1 1 3 ) 的可行域非空n 如果k l 啼o ，则由 算法3 2 产生的序列扛。 中的任何聚点都是问题( 1 。3 ) 的是艘点。 第3 章光滑化方法 证设是 k ) 的一个极限点，则存在k ) 的一个子序列( 为了简单，假 定该子序列就是k 本身) ，使得 x k 争曼，七手 首先证明章是口 行的。 假设童不可行。与定理3 1 一样，我们有一个指标f 满足 c ， ) o ， 并且 ，g 。) + c c f 2 ( ) + ，仁) + 肌c k l 口。l( 3 7 ) 这里i 是一可行解。 令女_ o 。， 因为i i 寸o ，l 吼1 斗o ，故上式左边趋于+ 。，而右边有上界，这 是一个矛盾。因此量是可行的。 因为札是尸( x ，吼，听) 的极小点，有 v 帆善持c 胁。 铷m 烈告坼 在上式中令七_ 。，有 故曼是问题( 1 3 ) 的艇丁点。 3 5 数值实验 v ，( i ) + v q ) = o( 3 1 3 ) f _ 1 以下给出算法3 1 和算法3 2 的计算结果。 实验例子见附录等式约束问题部分。 j 京工娅夫学壤学硪士学毽论文 袭3 1 检骏问题、缎数与约束个数 问题维数约寒令数 1 1 0 0 9 8 2 1 0 09 3 3 l o o 2 4 l o o9 8 5 1 0 09 6 6 9 9 4 9 7 1 0 04 8 1 0 09 8 9 。1 0 06 1 0 。l o o 9 8 1 1 9 86 4 1 2 9 77 2 1 3 9 86 4 1 4 9 8 6 4 1 5 9 77 2 1 6 +9 77 2 l 亨孕7 7 2 1 8 。0 7 7 2 l 第3 颦光撵化方法 表3 2 算法3 j 的计算结聚 问题 n in fn g 盘盯 ，( x ) 1 l7 9 61 2 116 7 5 6 5 7 e 0 11 2 76 2 i 98 3 8o 。0 1 5 6 2 5 蝣 2 6 2 8 8 5 3 。1 4 3 4 0 5 5 9 70 。0 0 0 1 2 2 0 75 8 56 8 9 ? 7 器 4 1 0 l1 3 1 1 1 96 2 8 5o 0 0 0 l1 0 0 0 0 02 7 2 4 3 7 5 l3 6 8 51 5 0 l415 3 2 6 6 e 0 0 5 为 88 7 3 89 5 20 0 0 7 8 1 2 51 66 0 3 6 9 2 7 。32 7 88 譬0 2 50 0 0 0 9 5 8 6 3 8 82 4 2 1 65 0 s 8o 5o 0 2 7 4 6 莲? 9 39 6 31 1 20 2 5l0 0 0 01 6 6 7 4 3 1 0 97 2 3 88 4 0o 0 0 3 9 0 6 2 52 83 4 ，7 5 3 8 1 1 l3 6 58 3 2 8 4 5 8 4 e 0 1l 1 2 。g4 9 5 6 5 60 。g 0 3 9 0 6 2 52 8 1 2 。i l l 7 1 3 2 l1 8 4 8 4 61 2 2 4 3o 。0 2 57 8 0 8 0 。6 0 4 8 1 4 1 01 8 6 6 71 7 1 7 0 0 0 1 9 5 3 1 35 11 0 7 8 3 5 1 5 l3 1 7 8 1 5 0 1 4 7 3 5 1 8 7 e 0 0 7 1 s ，l2 0 75 9 4 6 3 1 6 3 e 0 1 2 1 7 2 21 3 5 8 6 鑫8 9 4 9o ，9 1 2 52 ? 1 3 7 1 s 4 1 8 1 65 3 1 0 33 6 0 6 o 。0 0 1 5 6 2 51 0 2 吐1 1 5 1 7 l 总和 2 3 65 8 7 8 2 04 5 1 8 7 闫麓静求解采黼m 毗l a b 6 5 ，算法3 。】中参数取德为q = 1 ，1 q i = 1 m = 2 ， s = l 。一，算法的终止准刘为9 c ( 稚) 弛1 0 。在计算无约束问题骝p g ，吼，吼) 时，采焉的是b f g s 薄法，无约束问题的终止准则为0 v p ( 五，吼) k9 1 0 ，在求 j 豪王韭大掌理学磺士学证论文 解无约束问题极小时，一维搜索方法是简单后退准则。 计簿结槊为问题4 没有达到终止准则的要求。 表3 3 算法3 2 的计薄结果 闻题秘王n f n g 盘仃 ，( 石) l 。21 8 1 51 8 l0 51 0 01 3 3 9 2 9 e e 1 3 2 。唾6 8 8 s1 0 0 80 。1 2 55 02 。6 8 7 7 3 。l l2 4 2 7 3 4 2 0 0 0 0 9 7 6 5 s 35 e1 4 1 6 8 3 4 。1 0 11 6 3 5 0 9 07 8 1 6 6o 。0 6 2 52 0 04 7 7 。? 5 5 5 1 0 12 0 1 0 91 8 1 80 。0 0 0 13 2 0 0o 6 9 5 1 7 7 6 1 19 4 1 2 6 7 3 1 4 o 11 36 0 3 7 l l 7 17 lbl5 0o 0 2 4 0 4 7 7 8 l7 8 51 4 95 0o 0 2 7 4 6 4 7 9 57 3 19 1o 0 6 2 55 0o + o 0 0 4 6 6 8 3 8 1 0 87 0 6 5 25 3 1 80 i2 53 4 9 2 3 3 i l l2 2 _ 莲97 1 45 03 7 0 0 3 9 e 0 0 9 1 2 。l o l4 9 2 7 22 哇3 20 。g o l8 0 03 4 。? 3 3 3 1 3 ，1 8 4 4 3 8 3 3 1 7 9 o 。0 0 0 1 9 5 3 1 3s 02 6 8 。s 1 3 1 4 1 0 l1 4 4 0 5 5 99 9 2 4 6o 。0 6 2 55 04 9 2 。8 1 5 1 0 12 2 8 7 1 69 2 5 6 61 61 3l 。1 3 5 0 l 1 6 l 7 6 1 1 3 6 15 02 6 0 2 5 2 e 一0 1 2 1 7 1 8 9 1 1 3 36 7 0 20 0 0 0 3 9 0 6 2 55 01 3 7 1 4 5 1 8 1 4 5 7 4 1 5 4 1 4 6 o o 0 0 7 8 1 2 55 01 1 5 1 6 4 总和 6 0 03 7 4 7 1 8 03 0 3 5 1 2 淘题静求解采甭擀a t l 曲8 5 ，算法3 2 中参数取德为q 一5 0 ，i 甜1 = 1 ，m 一2 第3 章光滑纯方法 s 一1 旷4 ，算法的终止准则为i l c ( 兆s l o 。在计算无约束问题墨势p b ，吸) 时，采用的是b f g s 算法，无约京问题的终止准则为| | v p 毒，吼) 虬s l o ，在求 鼹无约寒阅越极小时，一缎搜索方法是筵单基退准剿。 计算结果为问题4 、5 、1 2 、1 4 、1 5 没鸯达到收敛要求。 比较算法3 1 和算法3 2 ，可以发现算法3 + l 比算法3 。2 更为有效一些。 3 6 本章小结 在这一章里，我们讨谂了绝对篷涵数翻静近戗凝数争墨搿) 懿性爱，戳_ | 魄给 出了修改款爨函数戆定义，骚交了修泼静爨涵数法懿枝敛理论，绘懑了褥个薪费 算法模型，共绘出了这鼹令算法的数馕实验结祭。 通过实黢结果，我们着如算法3 1 要比算法3 。2 灼效果更好一魑，傻是算法 3 1 也存在不足之处。因为算法3 。1 中要求纯一+ m ，孬这在实际计算中，容易 产生病态，从嚣造成诗冀上靛不可行。因此，我囊考惠摄l a g r a n g o 乘予弓| 入修 改的罚黻数的惩罚项中，对修改的罚黼数进行邀一步鲍讨论。 北京工业大学理学硕士学位论文 第四章乘子罚函数法 4 。1 乘子法的基本思想 罚函数法适用范围较广，它的优点是将约束问题化成一系列无约束问题，可 用求解无约束问题的算法褥到约束问题的最伐解。本文修改的罚爨数楚连续微 熬，湾除了l 精臻罚函数静不霹徽性，数鬣实骏证髑修敬静罚溺数是方便有效的。 但由算法3 1 知，修改的罚函数法需要惩罚因子盯；越于无穷大时，才可使求罚 函数极夺勰求解爨阚趣等价。两当惩弱舀子充分大酎，函数p ( x ，啄) 通常 是一个病态函数，即其h e s s e 矩阵v ：p x 哝，吼的条件数非常大，我们知道， h e s s e 矩黪条 牛数躲大小是求解无终寒闳题匿难程度豹重簧标志。为巍服这缺 点，我艇考虑在修滚瓣疆器数中弓l 入拉格勰匿乘予，讨论乘予罚涵数。 其祓法是将拉格蘸匿莱予弓l 入罚函数法的惩罚项中，躐者说将惩罚项弓j 入拉 格鞠酗函数中，阻试图通邋调整拉格朗目乘子，避免罚函数法中出现的病态现象。 增广拉格朗日乘子法把惩罚数和拉格朗曰函数结台起来，构造一个新的函数 增广挝格朗日函数，通过求解该函数的无约束极小点来获得原约束问题的解。 4 2 改进罚函数的设想 对于等式约束问题 m m ，( x ) ，x 薯r “， s f q0 ) = o ，扣1 ，2 ， 提 赶的修改罚函数为 p o 鸬盯) ：o ) + 口羔f 佰两万1 0 1 ) ( 42 ) 设x 蔻( 4 1 ) 的全局解，考察x + 是否为无约束问题( 4 2 ) 的全局解( 局部解) 。 j p ( x ，盛，盯) 农盖处的梯度为 2 2 v x p 。，甜，盯) = w g ) + 玎喜辫2 v ，g + ) 在通常的意义下，v ，b ) 喾o ，也就是说，x + 不是问题( 4 2 ) 的全局( 局部) 解， 因此不能期漫选择一个固定的仃，求解一个无约束问题得到约束河题的最优解。 现在基然提篷一个阍题：是否疼在这撵瓣函数痧( x ，饼) ，使褥x 埝好蹙无 约泶问题 m 谊 妒b ，d ，d )( 4 3 ) 的全局或裁辩解，以翘望求鳃一个秃约束游题褥到绞衷藏熬的最俊解，这撵霹大 大提高算法效率。 匿茏约窳润逶静二酚充分条俘，若薛毅萨f 墨葶，搿 在x 4 处满足 v ：妒s ，口) = o ， v ：g 鸬盯) 正定， 则z 是无约束问题( 4 3 ) 的严格局部解。 秘4 ) ( 4 、5 ) 现在褥逡满是条 牛( 4 ，4 ) 秘0 。5 ) 豹函数庐( 孔盯，群) 。 我们知道l a 黜l g e 函数 0 ，五) = 厂g ) + _ c g ) ( 4 6 ) 在秘，z ) 楚豹梯疫等于o ，鄂么l a g r a n g e 溺数三0 ，五) 在b + ，z ) 处怒否满足祭件 5 ) 呢? 一般 毒况下是不溅是鲍。国鲍寒阏题蕊二除充分条臀霹皴：毛a 蓼黼g e 函数的h e s s e 矩阵在x 处只有切空间上正定，即 d v ：三b + ，弦 o ，v d m ， ( 4 7 ) 萁中 m = 矧d 7 v c b ) = o ， 并不能保证在整个空间上v ：+ ，) 正定。 事实上，l a g r 馘g e 函数在矗方嗣上二输方向导数夫子o ， ( 4 。8 ) 雨在酾线的法向方 向v c 0 ) 上，二阶方向导数小于o 。为了使构造的函数在法向方向上二阶方向导 数大于o ，仍然使用锶函数法的基本思想，农法向方向上挺以惩援，也就是谨， 当x 离开矗方离时，裙e o ) o 时，辩l a g r a n 辨薛数撩潋惩弱，这样得到函数 妒) = ，( x ) m e ) + 嘻( 瓶万万) 可以期望，当仃充分大时，蠢v ：g