（控制科学与工程专业论文）大规模优化理论及算法研究.pdf

浙江大学博士后科研工作报告 摘要 摘要 大规模优化理论与算法是工业过程在线优化中的关键技术，也是当前国际 上关注的热点之，为数学和工业自动化中的前沿学科。博士后研究工作在分 析流程工业过程在线优化和大规模优化中存在的理论及技术难题的基础上，以 实际流程工业过程为背景，提出了五个有效和实用的数值方法，) 惧体是： 对一般非线性约束优化问题提出了一个修改增广l a g r a n g e 乘子法，方法采 用乘子法的思想，将所有等式约束和不等式约束都纳入增广l a g r a n g e 函数中， 而上下界约束并不纳入增广l a g r a n g e 函数中，即在每次迭代中求解一个界约束 的优化子问题，而非无约束优化子问题，方法克服了修改障碍函数法处理等式 约束时的不足，文中详细讨论了方法的结构、迭代步骤、罚参数修正方案及收 敛准则等，而且进行了一定数量的数值试验并与修改障碍函数法作了数值比较。 对大规模界约束极小化问题给出了两个数值方法：有效集截断牛顿法和子 空间截断牛顿法。有效集截断牛顿法基于个确定最优解处有效集的有效技巧 以及截断牛顿法，在每次迭代中产生可行迭代点，方法允许快速修改工作集， 极大地提高了一般有效集策略的效率，截断牛顿法只确定自由变量空问中的搜 索方向，而非自由变量空间中的搜索方向只需通过简单的计算得到，由于使用 了高效的有效集策略和截断牛顿方向，该方法特别适合于大规模界约束问题的 求解；子空间截断牛顿法基于截断牛顿法和投影梯度法，它产生的迭代点也是 可行点，每次迭代的搜索方向由三部分组成：一个为非有效变量所在子空间的 截断牛顿方向，另外两个为有效变量所在子空间的梯度和修正梯度方向，截断 牛顿方向的使用使得方法有比子空间有限内存拟牛顿法更高的计算效率。文中 证明了这两个方法的整体收敛性，并对它们就一类大规模问题与子空间有限内 存拟牛顿法进行了数值比较。 针对凸二次规划问题的结构特点，提出了两个不同类型的内点算法：一个 是势下降内点算法，对任意初始点，算法产生的迭代点列有界，且其任何聚点 均是所求二次规划问题的最优解，即算法具有全局收敛性质。另一个是预估校 正内点算法，它已被证明等价于1 阶扰动复合牛顿法，算法属于不可行内点法， 它对初始点的选取只有非负性要求，没有可行性要求，更没有严格可行性的要 求，从而使用非常方便。对上面所给的两个内点算法均进行了相当数量的数值 体收敛性，数值试验。 浙江大学博士后科研工作报告摘要 a b s t r a c t t h e t h e o r ya n da l g o r i t h m sf o rl a r g e s c a l eo p t i m i z a t i o na r ep i v o t a lt e c h n i q u e so f o n l i n eo p t i m i z a t i o n i ni n d u s t r ya n df r o n t a ls u b j e c ti nm a t h e m a t i c sa n di n d u s t r i a la u t o m a t i o nb a s e do na n a l y z i n gt h et h e o r y a n dt e c h n i c a lp r o b l e m si no n l i n ea n dl a r g e - s c a l eo p t i m i z a t i o n s ，t h i sp o s t d o c t o r a lr e p o r tp r o p o s e sf i v e l e f f e c t i v ea n d p r a c t i c a ln u m e r i c a la l g o r i t h m s t h e ya r ea sf o l l o w s ： am o d i f i e d a u g m e n t e dl a g r a n g em u l t i p l i e r m e t h o d ，w h i c ho v e r c o m e st h e s h o r t c o m i n g s o f m o d i f i e db a r r i e rf u n c t i o nm e t h o di nd e a l i n gw i t he q u a l i t yc o n s t r a i n t s ，i sp r o p o s e df o rg e n e r a ln o n l i n e a r o p t i m i z a t i o n t h el a g r a n g ef u n c t i o nc o n t a i n st h ep e n a l t yt e r m so ne q u a l i t ya n di n e q u a l i t yc o n s t r a i n t s a n dt h em e t h o ds o l v e sas e r i e so fb o u n dc o n s 仃a i n e ds u b - p r o b l e m si n s t e a do fas e r i e so fu n c o n s t r a i n e d s u b - p r o b l e m s t h es t r u c t u r eo ft h em e t h o d ，t h es t e p so fi t e r a t i o n ，t h eu p d a t i n gs c h e m e so np a r a m e t e r s a n dt h ec o n v e r g e n c ec r i t e r i aa r ed i s c u s s e di nd e t a i l ac o n s i d e r a b l en u m b e ro fn u m e r i c a le x p e r i m e n t a n dc o m p a r i s o n sw i t ht h ep e r f o r m a n c eo f m o d i f i e db a r r i e rf u n c t i o nm e t h o da r em a d e t w on u m e r i c a la l g o t i t h m sf o rl a r g e - s c a l eb o u n dc o n s t r a i n e dm i n i m i z a t i o n0 3 ei n t r o d u c e d t h ef i r s t o n ei st h ea c t i v es e tt r u n c a t e d - n e w t o na l g o r i t h m ，w h i c hi sb a s e do na l le f f i c i e n ti d e n t i f i c a t i o nt e c h n i q u e o fa c t i v es e ta tt h es o l u t i o na n do nat r u n c a t e d - n e w t o nm e t h o d t h ea l g o r i t h mg e n e r a t e sf e a s i b l e i t e r a t e s ，p e r m i t sf a s tc h a n g e si nt h ew o r k i n gs e ta te a c hi t e r a t i o na n di sv e r ys u i t a b l ef o rl a r g e s c a l e b o u n dc o n s t r a i n e dm i n i m i z a t i o na se m p l o y i n gt h ee f f i c i e n ta c t i v es e tt e c h n i q u ea n dt r u n c a t e d n e w t o n d i r e c t i o nt h es e c o n dn u m e r i c a l a l g o r i t h m i st h e s u b s p a c et r u n c a t e d - n e w t o na l g o r i t h mt h a t a l s o g e n e r a t e sf e a s i b l ei t e r a t e sa n d ，c o m p a r ew i t ht h es u b s p a e el i m i t e dm e m o r yq u a s i - n e w t o na l g o r i t h m ， 。 h a sh i g h e rn u m e r i c a le f f i c i e n c ya su s i n gt r u n c a t e d - n e w t o nd k e c f i o n ，t h es e a r c hd i r e c t i o nc o n s i s t so f t h r e ep a r t s ，w h i c ha r e t h et r u n c a t e d - n e w t o nd i r e c t i o ni nt h es u b s p a c es p a n n e d b yi n a c t i v ev a r i a b l e sa n d t h es u b s p a c eg r a d i e n ta n dm o d i f i e dg r a d i e n td i r e c t i o n si nt h es p a c es p a n n e db ya c t i v ev a r i a b l e s i nt h i s r e p o r t ，t h eg l o b a lc o n v e r g e n c eo ft h ea b o v et w oa l g o r i t h m si sa n a l y z e da n dn u m e r i c a lc o m p a r i s o n s w i t ht h ep e r f o r m a n c eo fs u b s p a c el i m i t e dm e m o r yq u a s i - n e w t o na l g o r i t h mo nas e to fl a r g e - s c a l e p r o b l e m s a r em a d e c o n s i d e r i n gt h es t r u c t u r ec h a r a c t e r i s t i c so fc o n v e xq u a d r a t i cp r o g r a m m i n gp r o b l e m ，w ed e v e l o p t w od i f f e r e n tk i n d so fi n t e r i o r - p o i n t a l g o r i t h m s t h e y a r et h e p o t e n t i a l r e d u c t i o n i n t e r i o r - p o i n t a l g o r i t h ma n d t h ep r e d i c t o r - c o r r e c t o ri n t e r i o r - p o i n ta l g o r i t h m i ti sp r o v e dt h a tf o ra n yi n i t i a lp o i n t ，t h e s e q u e n c eg e n e r a t e db y t h e p o t e n t i a l r e d u c t i o n i n t e r i o r - p o i n ta l g o r i t h m i sb o u n d e da n dt h a t a n y a c c u m u l a t i o no ft h ei t e r a t i v e s e q u e n c e i sas o l u t i o no ft h eq u a d r a t i cp r o g r a m m i n gp r o b l e m t h e p r e d i c t o r - c o r r e c t o ri n t e r i o r - p o i n ta l g o r i t h m ，w h i c hi sp r o v e dt ob ee q u i v a l e n tt oa l e v e l - 1 p e r t u r b e d 。 c o m p o s i t e n e w t o nm e t h o d ，b e l o n g st oi n f e a s i b l e i n t e r i o r - p o i n ta l g o r i t h m s a n d o n l yr e q u i r e s n o n n e g a t i v ei n i t i a lp o i n ti n s t e a do fs t r i c t l yf e a s i b l ei n i t i a lp o i n t f o re a c hi n t e r i o r - p o i n ta l g o r i t h m ，w e h a v em a d eac o n s i d e r a b l en u m b e ro f n u m e r i c a l e x p e r i m e n t s ，w h i c hs h o w t h es t a b i l i t ya n de f f e c t i v e n e s s o f t h e p r o p o s e da l g o r i t h m sf o r c o n v e x q u a d r a t i cp r o g r a m m i n gp r o b l e m s k e y w o r d s ：t h e o r ya n da l g o r i t h m s f o r l a r g e s c a l eo p t i m i z a t i o n ；o n l i n eo p t i m i z a t i o n ；m o d i f i e d a u g m e n t e dl a g r a n g em u l t i p l i e rm e t h o d s ；a c t i v es e tt r u n c a t e d - n e w t o na l g o r i t h m ；s u b s p a c et r u n c a t e d - n e w t o na l g o r i t h m ；p o t e n t i a lr e d u c t i o n i n t e r i o r - p o i n ta l g o r i t h m ；p r e d i c t o r - c o r r e c t o ri n t e r i o r - p o i n t a l g o r i t h m ；g l o b a lc o n v e r g e n c e ；n u m e r i c a le x p e r i m e n t ， 浙江大学博士后科研工作报告第1 页第一章前言 第一章前言 摘要本章叙述了大规模优化方法的研究背景，分析了当前国内外对大规 模优化方法的研究现状及发展趋势，并对整个科研工作报告中的主要工作作了 概要的描述。 关键词 大规模优化方法：研究背量：研究现状：发展趋势：主要工作。 第一节研究背景 优化是在多种( 有限种或无限种) 决策中挑选最好决策的问题。它广泛应用于 工业、农业、国防、工程、交通、金融、化工、能源、通信等许多领域，如在资 源利用、结构设计、调度管理、后勤供应等许多领域中产生了巨大的经济效益和 社会效益。优化在结构力学、生命科学、材料科学、环境科学、控制论等其他科 学研究领域也有广泛应用。优化作为人们一个强有力的思想方法，已迅速发展成 为一门重要的应用数学学科，并且与分析、几何、代数、概率及计算机科学、系 统科学、自动化等有密切联系，同时相互促进。国内外的应用实践表明，在同 样条件下，经过优化技术的处理，对系统效率的提高、能耗的降低、资源的合理 利用及经济效益的提高等均有显著的效果，而且随着处理对象规模的增大，这种 效果也更加显著。这对国民经济的各个领域来说，其应用前景无疑是巨大的。近 些年来，大规模优化方法的研究和应用倍受重视。 随着生产的迅速发展，大规模工程问题的优化计算越来越成为人们急需解 决的迫切问题。在工业界，激烈的市场竞争和多变的市场需求使得现代工业正逐 步向大型化和自动化方向发展，安全、平稳、优质和高效正越来越成为企业生产 所追求的目标。工业自动化是实现这一目标的基本条件和重要保证。工厂装置规 模的不断扩大使得生产操作和装置运行的好坏与工厂经济效益的关系更加密切， 从而对工业过程自动化提出了更高的要求。其着眼点从基础控制发展到先进控 制，进而发展到在整个企业范围内集成市场供应、能源与原材料价格、人事、财 务、设各、库存及过程操作现状等信息来优化管理与控制生产，以实现企业的生 产过程综合自动化。当前，人们已从基于离散工业的计算机集成制造系统c i m s 浙江大学博士后科研工作报告第2 页第一章前言 与基于连续工业的计算机集成生产系统c i p s 认识到，仅靠单纯提高个别生产装 置的控制与优化以及只寻求局部最优的生产模式已远远不能适应现代工业的生产 要求，只有对整个工段、车间乃至全厂进行先进控制及在线优化才是当今企业技 术进步和持续发展的最佳选择。 人们习惯上将众多的工业过程分为流程工业和离散制造业两大类。在流程 工业领域，基于严格机理模型的开放式方程建模与优化已成为国际上公认的主流 技术方向。据报道，全球流程工业的年产值超过5 万亿美元，其中仅化i f t j 石油 化工部分就超过1 万2 于亿美元。中国石油化工总公司所属的炼油厂，原油加工 能力约为1 6 亿吨，6 7 套常减压装置的年产值约为1 2 0 0 亿人民币，6 5 套催化裂 化装置年产值约9 9 3 亿人民币，仅此两个装置的年产值就达2 0 0 0 多亿人民币。 实现企业的综合自动化( 从设计优化、运行优化到最优计划) 可给企业带来占总 产值1 5 - 2 0 的效益提升。许多流程工业系统工程公司和各大科研机构纷纷投入 大量的人力物力对系统的建模与优化进行深入细致的研究，企图取得突破性的进 展。然而基于严格机理模型所得到的优化命题往往具有方程数多、变量维数高、 非线性强，这使得相关变量的存储、计算及命题的求解都相当困难。比如，一个 典型的流程工业系统全联立方程的维数通常在上万甚至数十万之多，这其中包含 了所有的单元模型方程、物性计算方程、流程联接方程，求解如此庞大的优化命 题本身就已相当困难，更难以到工业现场实施在线应用。常规的优化算法面对这 。 样的大型问题已无能为力，无论是在计算速度、收敛性、初值敏感性等方面都远 不能满足现代工业的要求。因此，针对化工应用中的大规模优化闯题的特点开发 池相应的算法已成为现代化工发展的一个重要方面。 不仅工业界存在大规模优化问题，在国民经济的各个领域中也存在着相当 多的涉及因素多t 规模大、难度高和影响广的优化命题，如运输中的最优调度、 生产流程的最优编排、资源的最优分配、农作物的合理布局、工程的最优设计以 及国土的最优开发等等，所有这些问题的解决也必须有一个强有力的大规模优化 工具来进行求解。且在这类大规模优化命题中，绝大部分都是关系到国计民生的 重大问题。如建筑工程设计领域中坝体断面的优化设计、水利优化设计、水库畜 洪量的最优设计等都是一些变量维数高、非线性强且不易求解的优化命题。此类 问题不仅仅是经济效益的最大化，而是关系到人民生命财产，涉及千家万户的问 题，如果得不到很好的解决，不仅不能防灾和减灾，而且还可能带来灾难性后果。 又如在空中交通管制中，用优化模型对全国或区域空中交通流量管制进行优化建 模与调度，不仅可以为充分利用空域资源、减缓大量飞行流量需求与有效空域资 源的矛盾提供科学的决策支持，而且可为航空公司的运营产生可观的经济效益， 这类问题通常具有几万到几十万个变量和约束方程。 浙江大学博士后科研工作报告第3 页第一章前言 发展大规模优化算法是解决上述问题的关键。近几年来，国内外尤其是国 外在此方面的研究日渐活跃。经过一些科学工作者的努力，目前国际上已出现了 几种适合于中等规模乃至大规模问题求解的优化算法，随着这些算法的出现及成 功应用，大规模优化算法的研究和工程实施成为学术界和工业界的研究热点。因 此，从工业挖潜增效的目标出发，开发具有通用性的可为各行各业作为技术借鉴 的大规模优化算法是十分有意义的。 第二节国内外研究现状和发展趋势 大规模优化命题的主要特征是变量维数高、非线性性强从而求解困难，要 想解决这类问题，仅靠计算机性能的提高是不可能的，另外，随着命题维数的增 加，误差的累积效应越明显，这进一步增加了命题的求解难度。因此，如何在现 有技术水平上，降低命题的存储需求和误差累积效应的影响，提高问题的求解效 率，是目前亟待解决的关键问题。 序列二次规划算法通过将原问题转化为一系列二次规划予问题的求解来获 得原问题的最优解，它对l a g r a n g e 函数取二次近似，从而提高了二次规划子问 题的近似程度，对非线性较强的优化问题也能较好地进行计算，同时它在优化过 程中所需的函数计算次数较少，且在一定条件下具有超线性收敛性，因而是公认 的、适合于中小规模优化问题求解的非常有效的算法之一，在流程工业系统优化 尤其在化工过程系统优化中得到了大量应用。但方法中二次规划子问题是通过对 原问题的约束条件进行线性近似得到的，因此有可能出现矛盾的约束而导致二次 规划子问题无解，使计算中断，这样就不能满足在线优化系统的要求。同时，在 求解大规模问题时，为了得n - 次规划子问题需计算原问题l a g r a n g e 函数的 h e s s i a n 矩阵，计算量非常大，而且对如此规模的h e s s i a n 阵，由于计算误差的 影响，很难保证其正定性，从而不能保证所得二次规划子问题有唯一解，也有可 能使二次规划子问题无解而使求解过程中断。因此，如何避免算法中断或在中断 时如何设法继续计算以及如何处理h e s s i a n 矩阵的更新和如何保证其正定性已成 为各种序列二次规划算法的主要目标。 目前，国内外针对序列二次规划算法的研究主要集中在简约空间序列二次规 划算法、稀疏全空间序列二次规划算法和内点序列二次规划算法。其目的是为了 降低高维矩阵的存储需求和相应的庞大计算量。简约空间序列二次规划算法针对 流程工业过程特别是化工过程中优化命题变量数非常大、状态方程非常多，但决 策变量并不多，即问题自由度不大的特点，利用空间分解技术，设法将问题分解， 浙江大学博士后科研工作报告第4 页第一幸前言 使二次规划子问题中仅含决策变量，从而避免了对系列大规模二次规划子问题 的求解，降低了相关矩阵的存储要求，进而大大减少了问题的求解时间。在此方 面已有许多学者作了大量工作，提出了不同的分解策略，如标准正交基分解、一 交基分角翠和坐标基分解等。但在实际问题中，现有的分解策略不仅实现困难，而 且难以保证所得二次规划子问题中二阶矩阵的正定性。 稀疏全空问序列_ - = 次规划算法利用流程工业过程系统优化命题普遍具有稀 疏性的特点，采用稀疏矩阵存储及计算技术来达到降低存储、减少计算的目的， 并最终降低优化命题的计算时间。其求解过程在所有变量的全空间中进行，对命 题的自由度大小无限制，目前已有学者在此方面进行过深入研究，提出了一些算 法，然而这些算法过于复杂或仅适于某类特殊命题，难以通用化。 事实上，序列二次规划算法在利用问题特殊结构时的主要障碍之是对其 二次规划子问题中不等式约束的有效处理，目前大部分通用二次规划程序采用的 有效集策略的计算复杂性随问题规模的增大而呈指数型上升，这使得整个序列二 次规划算法的效率随之降低。而内点法具有计算量、迭代次数受不等式约束影响 极小的优点，所以近几年出现了内点序列二次规划算法，它在序列二次规划算法 的框架下结合了内点法技巧，从而克服了有效集策略的不足，对具有大量不等式 约束的命题求解提供了巨大潜力。然而该方法的缺点是每次迭代必须从可行点开 始，对大规模问题，寻找初始可行点较困难，由此带来的计算代价也相当大。随 后出现了从不可行点开始搜索的新的内点法，即不可行内点法，这一学术思想正 引起人们的广泛关注。 另一类适于大规模不等式约束优化问题的算法是修改障碍函数法，它是在 经典的逻辑障碍函数法的基础上产生的，具有有限收敛性，且障碍参数不必在迭 代中趋于零。实践表明，这一方法对仅有不等式约束的问题是非常有效的，但也 存在一些问题，有待进一步探讨。首先，约束以罚函数的形式集成于目标函数中， 约束方程的尺度自然地会影响算法的收敛性。因此，约束方程的尺度对该方法非 常重要，过小的尺度会导致约束条件过晚地起作用，从而使迭代次数增加，而过 大的尺度由于需要逐渐降低目标函数，也会增加迭代次数。如何选择合适的尺度 是一个需要研究的问题。其次，该方法存在的另一个问题是它目前只能求解不等 式约束的命题，对于等式约束只能化为两个不等式约束( 大于或小于) 来处理。 这样增加了方程个数，并且两个几乎矛盾的不等式约束也使得约束方程的条件数 增大，造成命题求解困难。而工业中优化模型往往因各种平衡条件具有很多等式 约束，因此如何修改此方法，使之能够在有等式约束的条件下运行，也是应当解 决的问题。 浙江大学博士后科研工作报告第5 页第一章前言 解决大规模优化命题的另一个思路则是采用并行优化技术。传统的并行处 理系统主要有多向量处理系统、基于共享存储的多处理机系统和基于分布存储的 大规模并行处理系统。这些系统大多十分昂贵，其应用受到很大的限制。近年来 颇受人们瞩目的机群系统利用高速通用网络将一组工作站或p c 机按某种结构连 接起来，在并行程序设计和可视化人机交互集成开发环境支持下，统一调度，协 调处理以实现高效的并行计算。因其丌发周期短、可扩展性好、性能价格比高、 投资风险小等特点，机群系统这新的分布式并行计算模式已成为当前研究的热 点。 在并行算法的研究上，函数求值、矩阵计算的并行化算法比较多，也比较 成熟。但是大规模系统优化算法的并行化却刚刚开始，目前研究很多的优化方法 通常只是优化计算中某个步骤的并行化，如在梯度计算中引入矩阵的并行乘法， 这些都只是局部的并行，而缺乏一种从总体结构上分解开的大规模优化算法的并 行。如何在当前企业承受能力有限的情形下，采用个人计算机机群系统的分布式 并行计算技术为大规模的工业生产过程提供一个扩展性好、易于实现的解决方案 是一个值得深入研究的问题。 总的来说，对于大规模非线性优化问题，目前国外的研究相对较多，而国 内的研究还非常薄弱，许多领域还是一片空白，真正富有成效的研究成果也并不 多见。国内从事约束优化算法研究的以中科院的席少霖教授、赵凤治教授、袁亚 湘教授、韩继业教授等为代表，对算法的改进和理论分析进行了很多有益的探讨。 清华大学的陈丙珍教授等对序列二次规划算法的变量标度化问题、二次规划的相 容性问题以及优化在化工过程系统中的应用等也做过很深入细致的研究。近年 来，浙江大学工业控制技术研究所在钱积新教授的带领下已在大规模非线性优化 算法、并行优化技术以及工业过程的在线优化等方面的研究上取得了相当的进 展，作出了大量系统和卓有成效的研究工作。 第三节主要工作 适于大规模不等式约束优化问题的修改障碍函数法，在经典的逻辑障碍函 数法的基础上产生，具有有限收敛性，且障碍参数不必在迭代中趋于零，对仅有 不等式约束的问题是非常有效的，但是约束以罚函数的形式集成于目标函数中， 不合适的约束方程尺度会导致迭代次数增加，影响算法的收敛性，而且该方法目 前只能求解不等式约束的命题，对于等式约束只能化为两个不等式约束( 大于或 小于) 来处理，这样两个几乎矛盾的不等式约束也使得约束方程的条件数增大， 浙江大学博士后科研工作报告第6 页第一章前言 造成命题求解困难。因此，针对实际工业中优化模型往往因各种平衡条件具有很 多等式约束的特点，根据修改障碍函数法的思想，提出能够有效处理带等式约束 的非线性优化问题的罚函数法是本文第二章的主要工作。 在第二章中，我们对一般的非线性约束优化问题提出了一个修改增广 l a g r a n g e 乘子法，其中罚函数的构造采用乘子法的方法，将所有等式约束和不 等式约束都纳入增广l a g r a n g e 函数中，而上下界约束并不纳入增广l a g r a n g e 函 - 数中，即在每次迭代中求解一个界约束的优化子问题，从而与通常的罚函数法不 同，这里形成的是一系列界约束优化子问题，而非一系列无约束优化子问题。我 们详细讨论了方法的结构、迭代步骤、罚参数修正方案及收敛准则等，关于界约 束子问题的求解，我们首先用求解无约束优化问题的截断牛顿法求解增广 l a g r a n g e 函数的无约束极小化问题得到截断牛顿方向，然后根据界约束条件对 所得截断牛顿方向进行修正得到搜索方向，再利用一个修改的线搜索技巧得到搜 索步长，产生下一个迭代点后继续迭代求解，直到某个终止准则满足为止，最后 在章末进行了一定数量的数值试验并与修改障碍函数法作了数值比较。 第三章给出一个求解大规模界约束极小化问题的有效集截断牛顿法，该方 法基于一个确定最优解处有效集的有效技巧以及截断牛顿法，在每次迭代中产生 的迭代点均为可行点。在计算搜索方向时，算法首先启用一个估计技巧来估计哪 个界约束是最优解处的有效约束，这一估计技巧允许快速修改工作集并保持搜索 1 方向的部分分量固定，然后在对应的自由变量空间中利用修正的截断牛顿法确定 搜索方向对应于自由变量的分量，而搜索方向对应于非自由变量的分量只需通过 简单的计算得到，搜索步长利用a r m i j o 非精确线搜索确定。由于使用高效的有 效集策略和截断牛顿方向，所给方法将特别适合于大规模界约束问题的求解。同 时我们证明了方法的整体收敛性，并就类大规模问题对所给的方法和 7 6 中的 子空间有限内存拟牛顿法进行了数值比较。 第四章给出了求解大规模非线性界约束极小化问题的另一个算法：子空间 截断牛顿法。该方法基于截断牛顿法，它利用截断牛顿法修正非有效约束所对应 的变量，而有效集所对应的变量用投影梯度法进行修正。方法产生的迭代点均为 。 可行点，搜索方向由三部分组成：一个为非有效变量所在的子空间截断牛顿方向， 另外两个为由有效变量所在的子空间梯度和修正梯度方向。梯度搜索和截断牛顿 法的使用都将使得我们的子空间截断牛顿法特别适合于大规模界约束极小化问题 的求解，方法的整体收敛性在文中得到了证明，同样就一组大规模优化问题对所 给算法和 7 6 中的子空间有限内存拟牛顿法进行了数值比较，所得结果相当理 想。 浙江大学博士后科研工作报告第7 页第一章前言 第五章叙述序列二次规划方法的提出背景以及各种序列二次规划方法的区 别，并对目前研究较多的几种典型序列二次规划方法的思想进行了概述，最后分 析了内点序列二次规划法目前的状况、优缺点以及求解二次子问题的预估校正内 点算法。 针对凸二次舰划问题的结构特点，在第六、七两章中提出两个不同类型的 内点算法。在第六章中提出一个求解凸二次规划问题的势下降内点算法，在该方 法的每次迭代中，首先求解一个线性方程组以得到搜索方向，然后沿此搜索方向， 利用a r m i j o 非精确线搜索技巧进行线搜索，同时使一个势函数的值减少。我们 证明了对任意初始点，由算法产生的迭代点列是有界的，且该迭代点列的任何聚 点均是所求二次规划问题的最优解，即算法具有全局收敛性质。最后，我们就 组二次规划问题对所给算法进行了数值试验，数值试验结果进一步表明所给算法 对凸二次规划问题是稳定和有效的。 在第七章中提出了一个求解凸二次规划问题的预估校正内点算法，算法属 于不可行内点方法，它对初始点的选取只有非负性要求，没有可行性要求，更没 有严格可行性的要求，证明了所提算法等价于1 阶段的扰动复合牛顿法。最后对 所给算法进行了数值试验，给出了一些数值试验结果。 浙江大学博士后科研工作报告第8 页 第二章修改增广l a g r a n g e 束子法 第二章求解大规模优化问题的 修改增广l a g r a n g e 乘子法 摘要在这章中我们研究求解大规模非线性约束优化问题的修改增广 l a g r a n g e 秉子法。详细探讨了所给方法的迭代步骤其基本步骤包括个外层 迭代和一个内层迭代l a g r a n g e 秉子和不周的罚参敦在外层迭代中修正在内 层迭代中皿求解一个非线性的界约束优化子问题。所给方法黛成7 3 算法程序 m a l m m ，并以一粪规模由小到大的非筑性约束优化问题进行了数值试验所 得数值结果表明所给方法对大规模约束优化问题是稳定和有效的。 关键词：修改增广l a g r a n g e 秉子法：大规模非线性约束优化：数值试验。 第一节引言 在流程工业领域，基于严格机理模型的开放式方程建模与优化已成为国际 上公认的主流技术方向。化学工程中的最优化方法要求能够求解几百到数千个 变量和约束的非线性问题。目前，使用最广泛的方法都基于线性化技巧，如广 义简约梯度法【1 5 ，1 7 ，1 0 8 】，序列二次规划法【5 ，2 8 ，1 1 0 及修改障碍函数法 【8 7 ，1 1 4 ，1 1 5 等。这些基于线性化技巧的方法当应用于全空间时，它们能求解的 问题的变量数不大，而当用于简约空间时，它们能求解自由度不大的大规模问 题。同时，基于有效集策略的序列二次规划法对包含大量不等式约束和界约束 的问题的求解效率相当低。而修改障碍函数法将原约束优化问题的求解转化对 一 一系列无约束问题的求解，与古典障碍函数法的渐进收敛性不同，该方法具有 有限收敛性且其罚参数不必在迭代过程中趋于零，它能有效求解大规模约束优 化问蹶。然而，与其他障碍法一样，修改障碍函数法在求解带等式约束的优化 问题时遇到了严重的困难，因为这类方法都将等式约束化为两个相反的不等式 约束来处理，从而很难满足方法对问题所有不等式约束的可行域具有严格内部 的要求。 浙江大学博士后科研工作报告第9 页 第二章修改增广l a g r a n g e 乘子法 本章将给出求解大规模非线性最优化问题的一个修改增广l a g r a n g e 乘子 法。所求约束非线性规划问题的一般形式如下： m i n f ( x ) s t c i ( x ) = 0 ，i = 1 2 ，m ， c i ( z ) 0 ，f 2 m 。+ 1 一，” ，x “ r 2 f 2 ( 2 f 2 其中，和“是中的两个已知向量，不等式，x “按向量的分量耿大小。 如果没有界约束( 2 4 ) ，问题( 2 1 ) 一( 2 3 ) 的求解可用增广l a g r a n g e 乘子法。对 给定的l a g r a n g e 乘子向量兄和罚参数向量口，增广l a g r a n g e 乘子法第k 步所 求的罚子问题是： m i n j p ( x ，兄，盯 )f 2 5 1 其中p ( x ，兄，盯) 是增广l a g r a n g e 罚函数： p ( x , 2 ，盯) 2 ，( x ) 一【 c ，( x ) 一 盯，( c i ( x ) ) 2 】一e ( x ，旯，盯) ( 2 6 ) 只( x ，五，= 丑c ，( x ) 一三q ( q ( z ) ) 2 ， ；枷， 如果 一口，q ( 石) 0 否则 对无约束极小化子问题( 2 5 ) 的求解，通常可采用梯度法、b f g s 拟牛顿法、或牛 顿法等方法。在大规模极小化优化方法中，截断牛顿法是最有效的算法之一 8 9 ，9 6 】，它利用一个低存储和低计算量的方法去近似牛顿方向，具有很强的收 敛性质且其渐进收敛率可由使用者设定为线性与二次之间的任何值。我们将在 下面详细讨论截断牛顿法并对该方法进行修改以利于大规模界约束极小化问题 的求解。 + 如果在约束非线性最优化问题中存在简单界约束( 2 4 ) ，上面的增广l a g r a n g e 乘子法需要进行修改。在修改障碍函数法中，简单界约束( 2 4 ) 被化为两个一般的 不等式约束x f2 0 和 一x2 0 ，这极大地增加了l a g r a n g e 乘子和罚参数的个数。 为此，我们提出另一种修正方法来处理带简单界约束的优化问题( 2 1 ) ( 2 4 ) 。在 第k 步，假设已知l a g r a n g e 乘子向量五和罚参数向量盯，与增广l a g r a n g e 乘 子法求解子问题( 2 5 ) 不同，我们求解如下界约束子问题： ( 2 7 ) “x 1 ，其叶 帜x ) 0 2 =辱鬲画 称为可行性度量，o 1 且通常取f = ； 方案2 盯： ( 21 2 ) ? 如果k x “1 ) l 水( x k ) l ，i = i ，以，或 i r n i n c x k + 1 ) ，o ) l - 1 且通常取y = 1 0 或y = 1 0 0 。 同时注意到，在上面的修正方案中，在当前的可行性度量比用户所需求的 误差s 小时，限制罚参数盯增大个毫无意义的倍数是非常有用的，在这种情况 下，它不会影响整个方法收敛准则的最终有效程度。在修改增广l a g r a n g e 乘子 法中，用户可以对罚参数向量。引进一个保护机制，即一个严格上界o - ，以阻 止该向量取不切实际的很大数值。 2 3收敛准则 注意到修改增广l a g r a n g e 乘子法所产生的迭代序列 x ) 满足原问题( 2 1 ) ( 2 4 ) 的界约束，即，x h ，k = 1 , 2 ，我们可以按( 2 1 2 ) 式定义可行性度量 1 i 石( x ) l l ：。对用户给定的容许误差s ，修改增广l a g r a n g e 乘子法的终止准则是： 浙江大学博士后科研工作报告第1 3 页 第二章修改增广l a g r a n g e 乘子法 如果慨x “) 1 f ：f ，则x “1 是原问题( 2 1 ) 一( 2 4 ) 的近似解 其中x “1 是第k 个界约束极小化子问题( 2 7 ) 的解。 第三节方法的内层迭代 对于第k 个界约束极小化子问题( 2 7 ) 的求解，可以采用基于投影的方法 ( 8 8 1 、拟牛顿方法【8 3 】或信赖域方法【l1 9 1 等，在这里我们将采用另外的方法来求 解界约束极小化子问题( 2 7 ) 。由于截断牛顿法是求解无约束优化问题的非常有 效的方法之一，且不需存储矩阵，它特别适合于求解大规模无约束优化问题， 因此我们将对截断牛顿法加以改进以适于对界约束极小化子问题( 2 7 1 的求解( 详 见第三、四章) 。 在牛顿法中，为了极小化无约束函数f ( x ) ，第女次迭代的搜索方向d 通过 求解如下牛顿方程得到： v 2 f ( x ) d = 一w ( x ) 这使得牛顿法的计算量太大而无法成为求解大规模优化问题的实用方法。截断 牛顿法采用共轭梯度法来近似求解牛顿方程以得到搜索方向，其中共轭梯度法 的求解过程在得到了一个近似解时终止( 截断) 。截断牛顿法以两层迭代的结构 形式实现，其中外层迭代确定搜索步长，内层迭代确定搜索方向。为了求解函 数f ( x ) 在界约束( 2 4 ) 的极小值点，我们需要对截断牛顿法进行适当的改进使之 成为求解如下问题的有效和稳定的数值方法： 这些改进包括对截断牛顿法所得搜索方向d 的修正 非 ： 以及对非精确线搜索的修正，通常的非精确线搜索是在区间( 0 ，l 】上取得搜索 步长，这里我们对非精确线搜索的修正是指在区间( o ，簖) 内确定搜索步长， 其中： t z o k = r a i n 卜n t 簪：钟删+ t t t - - x i k ：小。， ， d” = 或o i， df = ， x 。 果则如否 浙江大学博士后科研工作报告第1 4 页 第二章修改增广l a g r a n g e 乘子法 内层迭代的收敛准则采用p y t l a k 【8 8 1 + nv a s s i l i a d i se ta 1 4 】求解界约束极小 化问题的终止准则，即： f x 一p r o j c r 一v f ( x ) ) - “， 是对第个界约束极小化子问题求解的容许误差，它根据用户所需的求解精 度s 按如下规则加以确定： 吼= m a x e - ，1 0 一 ，r = 这种误差确定规则对丌始的几个界约束极小化子问题的求解精度要求较松，随 着整个算法的迭代进行，对往后的界约束极小化子问题的求解精度要求越来越 强，这样既可以减少整个算法的计算量，又可以节省整个问题的求解时间。关 f 截断牛顿法的改进详见第三、四两章。 第四节数值试验 为了表明由所给修改增广l a g r a n g e 乘子法得到的算法m a l m m 求解约束优 化问题的有效性，我们用选自h o c k s c h i t t k o w s k i 【1 1 7 和v a s s i l i a d i s e ta 1 1 1 4 中的一组问题对算法进行了数值试验。算法程序用m a t l a b5