（运筹学与控制论专业论文）一种求解约束优化问题的新罚信赖域算法.pdf

ad i s s e 九a t i o ns u b m i t t e dt o t o n 西iu n i v e r s i t yi nc o n f o 珊i 哆w i t ht h er e q u i r e m e n t sf o r t h ed e g r e eo fm a s t e ro fp h i l o s o p h y an e w p e n a l t yt r u s t r e g i o nm e t h o d f 6 r 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 s ( s u p p o r t e db yt h en a t u r a ls c i e n c ef o u n d a t i o no fc h i n a ， g 陷n tn o 1 0 7 7 11 6 2 ) c a n d i d a t e ：x i n 如y u s t u d e n tn u m b e r ：0 7 2 0l0 2 0 2 5 s c h o o l d e p a n m e n t ：m a t l l e m a t i c sd e p 叭m e n t d i s c i p l i n e ： m a t h e m a t i c s m a j o r ：o p e r a t i o nr e s e a r c h s u p e r v i s o r ：p r o d i n g - g u op u j a n ，2 0 l o 哪8i_哪9 删42 8l哪y 学吖大哪 湃一 冈唧 学位论文版权使用授权书 本人完全了解同济大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：喻 劢矽年多月侈日 同济大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、己公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 懈 劢年岁月弓日 同济人学硕+ 学位论文摘要 摘要 本文主要考虑如何有效地求解约束优化问题，结合信赖域算法和罚函数法的 特点，提出了一种新的算法。 对于一般的约束优化问题，信赖域算法是一种比较有效的方法。b y r d ，p o 、v e n 及我国学者袁亚湘均在这方面做了大量的研究。1 9 8 6 年，b y r d 等人提出了一种 当试探步不接受时计算二阶校正步的信赖域算法。19 9 1 年，袁亚湘和p o 、e l l 合 作给出了p 0 w e l l y u a i l 方法。但是，这些算法由于计算过程中有约束条件存在， 显得比较麻烦，计算成本也比较高。本文的主要工作是在信赖域算法和罚函数算 法的基础上建立一种新的罚信赖域算法。首先，利用厶精确罚函数将约束优化问 题转化为一个无约束优化问题。其次，将罚函数转化为一个含有最大最小值函数 的等价形式，同时，引入两个光滑函数矽( z ，万) 和( 乙万) 去逼近最大最小值函数， 以克服厶精确罚函数的非光滑性，得到原问题的一个光滑的逼近问题，然后再利 用信赖域算法进行求解。为了应对求解此类大规模问题时，信赖域子问题可能出 现病态的情况，本文还引入了n e 叭0 n c g s t e i h a u g 算法，进一步提高了算法的 有效性。 本文的结构如下： 第一章对约束优化问题、信赖域算法及罚函数算法的国内外研究现状作了一 个简单的描述。 第二章给出了一些论述中涉及的重要概念和重要定理。 第三章详细介绍了本文新算法中所用到的新的光滑化技术以及为了解决病 态信赖域子问题所引入的n e w t o n c g s t e i h a u g 算法，并对这种新的罚信赖域算 法作了比较详细的阐述。 第四章对算法的一些收敛性结果进行了证明，同时还对几个不同的算例从不 同的初始点进行数值实验，试验结果表明这种新的罚信赖域算法还是十分有效 的。 第五章为本文的小结部分。 关键词：约束优化问题，罚函数法，信赖域算法，光滑化技术 i nt h i sp a p e r ，w es t u d yh o wt od e a lw i t l lt i l ec o i l 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 e 任e c t i v e l ma n dp r e s e n tan e wp e n a l t y 伽l s tr e g i o nm e t h o df o rt l l e m f o rm e s ep r o b l e m s ，t h et m s tr e g i o na l g o r i t h mi sa ne 旋c t i v em e t h o d b y r d ，p o 、e l l 锄dy u a n1 1 a v ed o n eal o to f r e s e a r c hi nt i l i sa r e a i n1 9 8 6 ，b y r dp r e s e n t e dat m s t r e 西o nm e t l l o dw h i c hs h o u l dc a l c u l a t et h es e c o n d o r d e rc o r r e c t i o ns t 印w h e nt h et e s t s t e pi sn o ta c c e p t e d a n di nl9 9l ，y u 锄锄dp o 、e l lg i v et h ep o 、l l - y u 觚m e t h o d h o w e v e r ，t l l ee x i s t e l l c eo ft i l ec o n s t r a i n t sm a i st l l ec a j c u l a t i o no ft h e s em e t h o d sc o s t h i 曲l y 1 1 1 i sp a p e r sm a i nt 鹳ki st oe s t a b l i s han e we 脆c t i v ea l g o r i t h mb a s e do nt h e t r l 哦r e 西o nm e t l l o d 觚dt h ep e n a l t ) ，鼬c t i o nm e t 王l o d w ec h o o s em e 厶 e x a c t p e n a l t ) rm n c t i o nt 0t r a n s l a t e 也ep r o b l e mi n t oan o n - c o n s 昀i n e dp r o b l e m i l lo r d e rt 0 d e a l 、 ，i t ht l l ed i 伍c u l 够t h a tt 量l e 厶e x a c tp e n a l 够向n c t i o ni sn o n - s m o o t h ，、ec r e a t ea n e ws m o o t l tt e c l l l l o l o g y ，u s i l 培t w os m 砌c t i o n s ， 痧( z ，万) 锄d y ( z ，万) ，t o a p p r o x i m a t ei t t h e nw ec h o o s et n l s tr e g i o nm e t h o dt od e a lw i 血t l l ea p p r o x i m a t i o n p r o b l e m i na d d i t i o n ，w ec h o o s en e w c o n c g s t e i h a u ga l g o r i t h mt 0c o p e 研t ht l l e i l l - c o n d i t i o n e d 仇i s tr e g i o ns u b p r o b i e m s 1 h i sp 印e fi ss 吐眦t l 鹏d 鹤f o l l o 谢n g ： 1 kf i r s tc h l 她西v e sa 晡e fd e s c r i p t i o no ft h e 咖d y0 nt h ec o n 删n e dp r o b l e l i l s ， t i 圮咖s tr e g i o na l g o r i t t l i i l 肌dp e n a l t y 缸l c t i o na l g o r i t h ma th o i l l ca i l da b r o a d t h es e c o n dc h a p t e r 西v e ss o m ei m p o n a 呲c o n c e p t sa i l dt h e o r e m s 1 kt h i r dc h a p t e rd e s c r i b e sm en e ws m o o t ht e c l l l l o l o g yf o rt h ea l g o r i t h m 锄d l e n e w c o n c g s t e i h a u gm e t h o dw h i c hi no r d e rt 0s o l v ct h ei l l 一仃u s tr e g i o ns u b p r o b l e m s t h i ss e c t i o na l s o 西v e st h ed e t a i l so ft h en e wp e n a l t yt r u s tr e 百o nm e t h o d t h ef 0 删lc l l a p t e r 西v e ss e v e r a lc o n v e r g e n c er e s u l t so ft h e2 l l g o r i t l l m ，锄dt l l et e s t r e s u l t si i lt l l e 删m e r i c a le x p e r i m e n t ss h o w st h a to u ra l g o r i t h mi sav e 巧e f j f e c t i v e m e t l l o d 1 1 圮f i f i hc h a p t e ri st h es u m m a 巧s e c t i o n k e yw o r d s ：c o m ；仃a i n e do p 缸n i z a t i o np r o b l e m ，p e n a l 锣觚i o nm 础0 d ，t 1 1 l s tr e 酉o n a l g o r i t l l m ，s m o o m i n gt e c l l i l i q u e 1 4 本文主要工作6 第二章预备知识8 第三章新的罚信赖域算法1 3 3 1 新的光滑化技术1 3 3 2 算法的描述1 8 第四章算法的收敛结果及数值实验2 1 4 1 算法的收敛结果2 1 4 2 数值实验2 3 第五章小结2 7 致谢2 9 参考文献3 0 个人简历在读期间发表的学术论文与研究成果3 4 m 1 1 引言 第一章绪论 在经济社会活动中，人们经常需要处理一些经营管理、生产运输等现实问题， 希望获得一个最佳的解决方案，以最低的成本获得最大的利润。这种如何获得最 佳解决方案的问题，就称为最优化问题。针对最优化问题，如何获得这个最佳解 决方案的方法就是最优化方法。 最优化方法可以追溯到古老的极值问题，而它成为一门独立学科则在2 0 世 纪4 0 年代末，在d a i i t z i g 于1 9 4 7 年提出求解一般线性规划问题的单纯形法后开 始的。如今，随着科学技术的r 益进步和生产经营的日益发展，最优化方法已成 为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管 理、经济管理、国防等各个领域，发挥着越来越重要的作用。 最优化问题的一般形式为 m i n ( x ) s f x 么 ( 1 1 1 ) 这里x r ”称为决策变量，( x ) 称为目标函数，xc 称为约束集或者可行域。 特别地，当约束集x = f 时，原最优化问题被称为无约束最优化问题。否则， 称为约束最优化问题，其形式通常可以表示为： m i n 厂( x ) j j ( x ) = 0 ，f e ， q ( x ) 0 ，f ， ( 1 1 2 ) 这里的e 表示等式约束的指标集，表示不等式约束的指标集，e o ) 表示约束函 数。当目标函数和约束函数均为线性函数时，问题称为线性规划，否则称为非线 性规划。 对于无约束优化问题，目前已经提出了很多算法，比如牛顿法、拟牛顿法、 共轭梯度法等。在解决无约束优化问题时，人们总是希望从当前点出发，寻找一 个能够使目标函数快速下降的方向。从这个角度出发，法国著名数学家c u a c h y 最早提出了最速下降法。牛顿法也是求解无约束优化问题的最古老的算法之一， 它的基本思想是在迭代点以附近用二次函数g o ) = 厂( 玫) + s + s 7 g t s 2 逼近 厂( x ) 。通过不断发展，其改进形式仍然十分有效。但是这种方法也有一个缺点， 就是只能保证算法的局部收敛性，同时又需要计算二阶导数。1 9 5 2 年，h e s t e n e s s 同济人学硕十学位论文一种求解约束优化问题的新罚信赖域算法 和s t i e f e l 为求解线性方程组提出了共轭梯度法，这是一种介于最速下降法和牛顿 法之间的方法，它仅需一阶导数信息，既克服了最速下降法收敛慢的缺点，又避 免了存储和计算牛顿法所需要的二阶导数信息。为了克服牛顿法需要计算二阶偏 导数的缺点，人们还提出了一种拟牛顿法，它利用目标函数值厂( x ) 和一阶导数 g ( 力的信息，构造出目标函数的曲率近似，从而无需再计算二阶导数，同时又 具有收敛速度快的特点。 对于约束优化问题，目i j i 也已经有了不少算法，比如信赖域算法、罚函数算 法、逐步二次规划( s q p 方法) 等。本文重点介绍信赖域算法和罚函数算法，并 在此基础上，介绍一种新的算法。 1 2 信赖域算法 信赖域算法起源于2 0 世纪7 0 年代，当时传统的最优化方法几乎都是线搜索 方法，每次迭代产生一个搜索方向，得到下一个迭代点。但是这种方法常常因为 步长过大而导致失败，特别是对于病态问题。p 0 w e l l 于1 9 7 5 年提出了一种求解 无约束优化问题的信赖域算法，这种算法的基本思想是在每次迭代时强制要求新 迭代点与当前迭代点之间的距离被控制在某一个量以内，也就是要求试探步以 在某一个信赖域之内，每一次迭代时都有一个正数。，满足 | l 以临色 这里的试探步以从某种意义上说，也就是使得+ 反是在以也为中心的广义球 上的一个“最优的”点。同时，信赖域的大小在每一次迭代中逐步调节，如果 当前迭代点被接受则信赖域可以适当扩大，否则适当缩小。 对信赖域算法的研究，一直受到广大研究者的重视，j o 玛en o c e d a l 、觚p p 0 ， s a r t e n a e r 、p o 、e l l 等人都做了大量的工作，我国学者袁亚湘、戴或虹、邓乃扬等 人也取得了可喜的成绩。目前，国内外学者都主要围绕如何有效地解决信赖域子 问题展开研究，研究焦点包括信赖域半径的选取、信赖域算法与一维搜索的结合 等。1 9 9 7 年，s a t e m e r 提出了一种能够自动决定信赖域半径的算法，随后又有很 多学者相应地提出了各自不同的信赖域半径。在信赖域方法和线性搜索方面， j o r g en o c e d a l 和袁亚湘乜1 与1 9 9 1 年首次提出了这种新的计算方法的思想。1 9 9 3 年，邓乃扬d 1 等人又首次提出了一类非单调的信赖域算法。之后，带线搜索的信 赖域算法在众多学者的研究下不断发展。而在其他优化问题的信赖域算法方面， 比如复合非光滑优化问题，f l e t c h e r 于1 9 8 1 年首次给出了一种有效的信赖域算 法。袁亚湘在1 9 8 5 年证明了f l e t c h e r 二阶校正步的信赖域法的超线性收敛性。 对于任何类型的优化问题，都可以构造信赖域算法。它的形式如下： 2 一章绪论 步2计算一个试探步吨，满足0 反l i 0 ，s o ，届 l 属 0 ，o 屈 屈 o ，占0 ，七净1 ； 步2 求解( 1 2 2 ) 得到巩；如果i | 畋l | 0 ，则+ l = 耳+ 矾 否则，故+ l = 吒 步3 如果0 2 5 ，则转步4 ，色_ 色2 ，转步5 ； 步4如果气 0 ，使得对所有满足x r ”和忪一x i i ( x ) ， 则称，为的局部极小点。如果对所有满足x ，x x 和l lx x 厂o ) ，则称j 为的严格局部极小点。 8 第二章预备知识 定义2 4 如果对所有的x r ”，厂( z ) 厂( ，) ，则称，为厂的总体极小点。如果对所 有满足z x 的x 足”，八z ) 八x ) ，则称x 为的严格总体极小点。 在实际操作中，一般可行的方法只是求一个局部极小点( 或严格局部极小 点) ，求解总体极小点是一个相当困难的任务。而且，在很多实际应用中，求局 部极小点往往已经可以满足问题的需求。 在诸多最优化方法中，导数或者梯度的信息也是非常重要的，下面给出梯度 及连续可微的概念。 定义2 5 设厂：r ”专r 为钟上的连续函数，如果 ( 箬) ( x ) 存在且连续，扛l ，刀，则称在x r 一上连续可微，并称 夥( x ) ：【要( 机要( x 圹 为在x 处的梯度。如果厂在开集d 彤中的每一点都连续可微，则称厂在d 中 连续可微，记作厂c 1 ( d ) 。 定义2 6 设：r 斗r 为掣上的连续可微函数，如果 ( 器) 存在且连续，l ，j 聆，则称厂在x r ”上二次连续可微，并称以 咖瑚，= 鼍，1 乞。一( 曲 这与的定义矛盾，从而x 是原问题的一个局部极小点。 另一方面，存在舌 o 和； o ，使得 p ( 力 p ( 功，v i i 工一工i i 万，x 工 。鼻o h 束优化问题的解。从定理2 3 可以看出，只要盯足够大就可以得到原问题的精确 解。基于这一点考虑，本文采用精确罚函数法。 1 2 算法 在本文中我们主要考虑如下的约束优化问题： m 蝉厂( x ) s t c 0 ) = 0 ，f = 1 ，他 ( 3 1 1 ) q ( x ) ；0 ，f = ，气+ 1 ，聊 其中，厂( x ) 和q ( x ) 都是二次连续可微的。对于这个问题，在过去几十年晕已经 有了不少算法，比如g a s 算法 4 和c d e 算法 5 ，而我们考虑用罚函数法将原 约束优化问题转化为无约束问题来求解。在 6 中，作者已经提出了一种用罚函 数法求解等式约束优化问题的方法，其所采用的罚函数为 烈础) _ 八砧+ 壶善z o ) z 百 这是一个非精确罚函数，通常情况下，约束优化问题的足一r 点并不一定是非精 确罚函数的稳定点，因此，在此处我们仍然用上面这个非精确罚函数是不太适宜 的。我们可以考虑用精确罚函数，同时，精确罚函数也能帮助我们在有限步迭代 后得到一个精确解。在本文中，我们选用厶精确罚函数，其形式如下： ( x ) = 厂( x ) + 仃l lc 1 ( d i | l c 一( d = ( c l 一( 曲，巳一( 曲) q ( 曲= q ( nf = l ，他 q 一( 曲= m i n o ，c ( 曲) ，f = + 1 ，历 为了本文的叙述方便，我们考虑将厶罚函数再做一下变形，在厶罚函数两 边同时乘以土，得到 仃 q ( 功= 土弓( x ) = 圭( x ) + | | c 一( d l l l 11 o o 显然，问题 m i l l q ( 力 ( 3 1 2 ) 的最优解必定也是问题 1 3 将原来的非光滑问题再转化为一个光滑问题来求解。在介绍光滑化技术前，首先 将q ( x ) 作进一步的变形： m i n 0 ，q ( x ) ) i = 圭厂( x ) + 艺【麟 o ，q ( x ) ) 一幽 o ，q ( x ) 】一m i n o ，q ( x ) ” i = l ，= + l = 圭似) + 懈 o ，q ( x ) ) 一幽( x ) v ，= l ，t l 从上式可以看到，x = 0 是q ( x ) 的唯一一个间断点，我们只需引入两个连续函数 在x = 0 的一个小领域内逼近最大值函数和最小值函数即可，本文引入了两个连 续的分段函数： 矽( z ，艿) = y ( z ，万) 其中，m = 万与= 南一 o 。 z 一万 一艿 z o o z 万 z 万 z 一6 一万 z o 0 z 万 z 艿 这两个函数具有很好的连续性和连续可微性，且能很好地逼近最大最小值函数， 本文通过以下几个引理进行证明。 引理3 1 1 函数( z ，万) 和少( z ，万) 对于任意z 足都是连续的。 证明：首先证明函数痧( z ，万) 是连续的。 显然，在( ，一司，( 一万，0 ) ，【0 ，万) ，【万，+ ) 四个区间上( z ，万) 1 4 。； m d 卜 d 飞 d 飞 吵 啄 k。闰瑚 + + 力 7 7 7 啪盯一ili盯 x 现 国x 啦 筇一曲 硒 矿 r 加 q一代乞 乃以 憎r p 舻堋 州脚 。防、，ik010 算法 ： ! 毒! 二兰；：o 2 ( e d e 叫) 即在点z = 一万处，函数矽( z ，万) 是连续的 当z 专o 一时， e 。柑+ e m 一2 2 姆1 歹i ：丁 ：_ o 一 2 ( e 6 一e 叼) e 0 + j + e 晰一2 2 ( e 6 一e 面) = 0 + m ( e p 占+ e 占一。一2 ) 即在点z = 0 处，函数矽( z ，万) 是连续的 当z 专万一时， l i i 坠【z + m ( e 。一声+ e 占一2 2 ) 】 = 姆【z + 锝 ，e 占一j + e j 一一2 = d + 专r 2 ( e d e 呻) = 万+ 0 = 艿。 在点z = o 处，函数矽( z ，艿) 也是连续的 因此，矽( z ，万) 对于任意的z r 都是连续的。同理，可以证明对于任 意的z r ，缈( z ，万) 也是连续的。 引理3 1 2 函数矽( z ，万) 和沙( z ，万) 对于任意z r 都是连续可微的。 证明：先证可微性 对于函数矽( z ，艿) ，只需证明在z = 一坑o ，万三个点可微即可。 1 5 = o ：l i l i l 丝盟二塑二鱼：盟 ：一一， z 一( 一万) 即函数矽( z ，万) 在z = 一万处是可微的，由于 l i m 丝：塑二丝! q ：盟 每窨邓+ 等等， ：l i m 型= ! ：! ! !坐：二! ：! ： ：_ o - z o j 计篙) - ( 。+ 等等) “m 竺二玉三互竺：至互! z 矿 z o l i i l l 至! 三：鱼2 二壁! q ：鱼2 l i m 至! 三：变! = 丝! 变：鱼2 z 一f z 一6 ( z + 篙) 一( 6 + 篙) ：。疏! 三二至至互竺二玉巫： ：f z 一6 = l i m 丝翌二生! 鱼：翌 ：_ 扩 z d 所以矽( z ，万) 在点z = 0 ，艿也是可微的，同理可以证明( z ，万) 也是可微 的，并且 ( z ，回= o ， z 一万 m ( e z + 万一e z 一万) ，一万 z 0 1 + m ( e z 书一e 西吃) ，o z 錾理y ( z ，回= m i i l o ，z ) 。 o u 证明：对于任意的z 尺 当z = o 时，( z ，万) = 0 = m a ) 【 o ，z d u 当z 0 时，让万充分小使其满足艿 o ，f o ，七= o ； 步2利用初始迭代点屯的值求解 1 r 得到解工( 吒，名) ； 步3 如果l l ( 瓤吒，反) ) i l l 占，则停止，并且 而+ i = x ( 听，磊) ，吒+ i = l o 吒 七：j i + l ，转步2 。 在算法3 2 1 中一个重要步骤就是在步2 中求解无约束优化问题 而信赖域算法在求解无约束优化问题时是非常有效的，本文在算法的第二步采用 信赖域算法来求解得到x ( 吒，反) 。首先，我们给出这个问题的信赖域子问题 m i n ( d ) = d + 去d t b d s t - | | 圳 ( 3 2 1 ) 其中，是信赖域半径，舀= v 巧( x ，万) ，局= v 2 乃( 万) 。但是，随着迭代次数的 增加，以将变得越来越大，( 3 2 1 ) 也可能成为一个病态的信赖域子问题，这 给算法的有效性带来了一定的困难。为此，我们引入n e w t o n c g - s t e i h a u g 算法， 这是s t e i h a u g 于1 9 8 3 年在文 7 中提出的一种算法，对于解决病态的信赖域子问 题非常有效。其算法可以表述如下： 算法3 2 2 步l 给定s o ，令氤= o ，= ，风= 一，= o 如果忱0 f ，则终止，返回d = 磊， 否则，转入步2 ； 步2 如果p j 耳p ，o ，则终止，寻找f ，使得 d = d ，+ f 乃是m i n ( d ) 的最优解，且满足忪忙，返回d = 嘭+ f 乃 否则，转入步3 ； 步3 步4 步5 令a j = tr j f p 1b k p j ，d | = d | + a i p j 如果i id 川i i 色，则终止，寻找r ，使得 d = 哆+ f 乃满足i i d i | = 。，返回d = 哆+ f 乃 否则，转入步4 ； 令r j “= r j + a j b k p j 如果o 。q i i ，则终止，且返回d = 嘭+ ， 否则，转入步5 ； 令历+ = 矗。，= + 。彳，= f ，乃+ 。= _ 。+ 历+ 。乃 ，：= ，+ l ，转入步2 。 1 9 问题的新罚信赖域算法 + ，= 瓯2 ，并且给定 如果幢如i l 占，则终止里层f o r 循环 否则利用算法3 2 2 求解( 3 2 1 ) 得到t 计算甜耐= ( 暑，瓯) 一( 暑+ 珥，4 ) 啦= 慨( o ) 一他( 巩) p j = a r e d l | p r e d | 如果肛，则令= m a ) 4 ，川z | i 否则，川【l i 以0 ，j i 珥l i