（化工过程机械专业论文）大规模过程动态优化算法研究.pdf

浙江大学硕士学位论文 摘要 过程的动态模拟和动态优化在近二十年来愈来愈得到过程系统工程研究者 的关注。实际过程的动态性决定了必须建立过程的动态模型，动态优化技术的运 用对提高系统效率、降低能耗、合理利用资源及提高经济效益等方面均具有重要 意义。 最常用的动态优化算法是基于非线性规划的序贯算法和联立算法。序贯算法 具有寻优变量少，是可行路径法，可利用现有过程模拟软件等优点，但它不能处 理状态变量的路径约束。联立算法可以处理状态变量的路径约束，仅在最优点处 求解一次模型方程，其缺点是寻优变量多，产生非常大的非线性规划问题，需要 特殊的求解策略和数学处理。最近提出了一种结合两种算法特点的拟序贯算法。 一方面，与联立算法一样离散全部变量，控制变量离散为时间单元内的分段常量 函数，状态变量使用正交配置法进行离散，将状态变量的路径约束加于配置点上。 另一方面，与序贯算法一样在每次迭代时求解模型方程，使得生成的非线性规划 问题只包含控制变量与不等式约束，从而大大减小了优化问题的规模。 非线性规划的s q p 算法处理不等式约束有积极集法和障碍内点法两种。积极 集法效率与有效不等式约束相关，当有效不等式约束数目增加时，积极集法效率 明显下降，而障碍内点法效率与有效不等式约束数目无关。因此为了适应大规模 动态优化问题大量不等式约束的需要，本文在研究基于积极集s q p 的拟序贯算 法和非线性规划的障碍内点法的基础上，提出了基于障碍内点法的拟序贯算法。 本文主要内容包括： l 建立了内点拟序贯算法的算法结构。内点拟序贯算法将优化过程分为模 拟层和优化计算层双层。在模拟层中使用正交配置法离散变量并求解离 散模型方程，消除等式约束和状态变量，减小n l p 优化问题的规模。在 优化计算层中使用障碍内点法处理非线性优化问题。 2在算法结构研究的基础上，使用科学计算语言f o r t r a n 实现了内点拟 序贯算法。为了提高算法的效率，需要考虑j a c o b i a n 矩阵的稀疏结构。 为了算法尽可能自主实现，除了第三方免费的大规模稀疏线性方程组求 解器，算法完全自主编写，不依赖于任何商业数学库。 浙江大学硕士学位论文 3使用编程实现的内点拟序贯算法进行实例优化。首先使用一个二维 r o s e n b r o c k 函数优化问题比较了基于积极集s q p 的拟序贯算法、基于内 点法的联立算法和基于内点法的拟序贯算法的收敛路径，由该问题可以 看出内点拟序贯算法在一些问题中的优势。然后通过小规模的管式反应 器平行反应控制问题、中等规模的连续搅拌反应器最优控制问题以及大 规模的热集成精馏系统最优控制问题三个动态优化问题验证了算法效率 和稳定性。优化实例表明内点拟序贯算法可以快速有效的求解大规模动 态优化问题。 最后对全文研究工作进行了总结，并提出了存在的一些问题和将来的研究方 关键词：动态过程优化，拟序贯算法，障碍内点法，求解路径 i i i 浙江大学硕士学位论文 a b s t r a c t i n t e r e s ti nd y n a m i cs i m u l a t i o na n do p t i m i z a t i o nh a si n c r e a s e ds i g n i f i c a n t l y d u r i n gt h e l a s tt w od e c a d e s r e a lw o r l dp r o c e s s r e q u i r e sd y n a m i cm o d e l i n g a p p l i c a t i o no fd y n a m i co p t i m i z a t i o nh a sr e m a r k a b l ee f f e c to ni m p r o v e m e n to fs y s t e m e f f i c i e n c y , r e d u c t i o no fe n e r g yw a s t e ，r e a s o n a b l eu s eo fr e s o u r c ea n di m p r o v e m e n to f e c o n o m yp r o f i t t h em o s tc o m m o na n de f f i c i e n td y n a m i co p t i m i z a t i o na p p r o a c h e sa r es e q u e n t i a l a p p r o a c ha n ds i m u l t a n e o u sa p p r o a c hb a s e do nn o n l i n e a rp r o g r a m m i n g s e q u e n t i a l a p p r o a c h e x i s t i n g h a sl e s so p t i m i z a t i o nv a r i a b l e s ，i saf e a s i b l ep a t ha p p r o a c ha n dc a nu s e p r o c e s ss i m u l a t i o ns o f t w a r e b u ts e q u e n t i a la p p r o a c hc a n n o td e a l w i t h p r o b l e m s 、析t hs t a t ev a r i a b l e sp a t hc o n s t r a i n t s s i m u l t a n e o u sa p p r o a c hc a nd e a lw i t h s t a t ev a r i a b l e sp a t hc o n s t r a i n t sa n do n l ys o l v e sm o d e le q u a t i o n sa to p t i m a lp o i n t ，b u t i t g e n e r a t e s a l a r g en o n l i n e a rp r o g r a m m i n gp r o b l e mw h i c hr e q u i r e ss p e c i a l d e c o m p o s i t i o nt e c h n i q u e r e c e n t l yaq u a s i s e q u e n t i a la p p r o a c hw h i c hc o m b i n e st h e c h a r a c t e r i s t i co fb o t ha p p r o a c h e sw a sp r e s e n t e d o no n eh a n d ，q u a s i s e q u e n t i a l a p p r o a c hd i s c r e t i z e sa l lv a r i a b l e s c o n t r o lv a r i a b l e sa l ed i s c r e t i z e da sp i e c e w i s e c o n s t a n ta n ds t a t ev a r i a b l e sa r ed i s c r e t i z e dw i t hc o l l o c a t i o nm e t h o d ，a n ds t a t e v a r i a b l e sp a t hc o n s t r a i n t sa r ea d d e do nc o l l o c a t i o np o i n t s o nt h eo t h e rh a n d ， q u a s i - s e q u e n t i a la p p r o a c hs o l v e sm o d e le q u a t i o n sa te a c hi t e r a t i o n ，e l i m i n a t e sm o d e l e q u a t i o n sa n ds t a t ev a r i a b l e sw h i c hm a k e sn o n l i n e a rp r o g r a m m i n gp r o b l e mi n c l u d i n g o n l yc o n t r o lv a r i a b l e sa n di n e q u a l i t yc o n s t r a i n t s s e q u e n t i a lq u a d r a t i cp r o g r a m m i n gf o rn o n l i n e a rp r o g r a m m i n gh a st w om e t h o d s t od e a lw i t hi n e q u a l i t yc o n s t r a i n t s ，a c t i v es e tm e t h o da n db a r r i e rm e t h o d e f f i c i e n c y o fa c t i v es e tm e t h o dr e l i e so nn u m b e ro fa c t i v ei n e q u a l i t yc o n s t r a i n t s ，a n dd r o p s s i g n i f i c a n t l yw i t hi n c r e a s i n go fa c t i v ei n e q u a l i t yc o n s t r a i n t sw h i l ee f f i c i e n c yo f b a r r i e rm e t h o di si n d e p e n d e n tw i t ha c t i v ei n e q u a l i t yc o n s t r a i n t s 。l a r g e s c a l ed y n a m i c p r o c e s so p t i m i z a t i o np r o b l e mu s u a l l yh a sm a n y a c t i v e i n e q u a l i t yc o n s t r a i n t s ， t h e r e f o r ei n t h i sp a p e ra ni n t e r i o r - p o i n tq u a s i s e q u e n t i a la p p r o a c hw a sp r e s e n t e d m a i nw o r ki nt h i sp a p e ri n c l u d e s ： i v 浙江大学硕士学位论文 1d e t a i la p p r o a c hs t r u c 饥1 r ew a s g i v e n i n t e r i o r - p o i n tq u a s i - s e q u e n t i a la p p r o a c h a p p l i e st w ol a y e r ss t r a t e g yc a l l e ds i m u l a t i o nl a y e ra n do p t i m i z a t i o nl a y e r i n s i m u l a t i o nl a y e rd y n a m i cp r o b l e mi sd i s c r e t i z e da n dm o d e le q u a t i o n sa r e s o l v e dt oe l i m i n a t es t a t ev a r i a b l e s i no p t i m i z a t i o nl a y e ra l li n t e r i o r - p o i n t m e t h o di sa p p l i e dt os o l v en o n l i n e a rp r o g r a m m i n gp r o b l e mf r o ms i m u l a t i o n l a y e r 2b a s e do na p p r o a c hs t r u c t u r e ，as o f t w a r ep a c k a g ew a sc o d e dt oi m p l e m e n t i n t e r i o r - p o i n tq u a s i - s e q u e n t i a la p p r o a c hw i t hf o r t r a n s p a r s es t r u c t u r eo f j a c o b i a nm a t r i xw a sc o n s i d e r e dt oi m p r o v ee f f i c i e n c yo fp a c k a g e e x c e p tf o r f r e e t h i r d - p a r t ys p a r s e l i n e a r e q u a t i o n ss o l v e r , p a c k a g e w a sc o d e d i n d e p e n d e n t l yf r o ma n yc o m m e r c i a lp a c k a g e 3t h ep a c k a g ew a su s e dt oo p t i m i z ed i f f e r e n tp r o b l e m st ot e s ti t se f f i c i e n c y f i r s t l yat w o - d i m e n s i o nr o s e n b r o c kp r o b l e mw a sp r e s e n t e dt oc o m p a r et h e i t e r a t i o np a t ho fd i f f e r e n to p t i m i z a t i o na p p r o a c h e s t h e nas m a l l - s c a l e t u b u l a rr e a c t i o np r o b l e m ，am i d d l e - s c a l ec s t rp r o b l e ma n dal a r g e - s c a l e d i s t i l l a t i o ns y s t e mo p t i m a lc o n t r o lp r o b l e mw e r ep r e s e n t e dt ov a l i d a t et h e e f f i c i e n c ya n ds t a b i l i t yo ft h ep a c k a g e c o n c l u s i o nc o u l db ed r a w nt h a t i n t e r i o r - p o i n tq u a s i s e q u e n t i a la p p r o a c h c a ns o l v e l a r g e s c a l ed y n a m i c o p t i m i z a t i o np r o b l e m s ，e s p e c i a l l yo p t i m a lc o n t r o lp r o b l e m s t h ep a p e ri sc o n c l u d e dw i t has u m m a r y , e x i s t i n gp r o b l e m sa n dp r o s p e c to ff u t u r e r e s e a r c h e s k e y w o r d s ：d y n a m i co p t i m i z a t i o n ，q u a s i - s e q u e n t i a la p p r o a c h ，i n t e r i o r - p o i n tm e t h o d ， s o l u t i o np a t h v 浙江大学研究生学位论文独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成 果，也不包含为获得逝姿盘堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位敝储虢珲雠签字嗍瑚年弓月i r 学位论文版权使用授权书 本学位论文作者完全了解逝姿态茔有权保留并向国家有关部门或机构送交本 论文的复印件和磁盘，允许论文被查阅和借阅。本人授权逝、江盘堂可以将学位论文的 全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：评耐性 签字同期：】力口年3 月，同 导师签名： 矿 钒站簪 签字h 期：厶睥月i 同 浙江大学硕士学位论文 致谢 在论文完成之际，首先衷心感谢导师洪伟荣老师。在攻读硕士学位期间，洪 老师在科研和生活方面给了我极大的关心。动态优化算法研究是比较新的研究课 题，需要比较高的数值计算基础和计算机编程能力。洪老师耐心指导在优化算法 完全没有经验的我，指明研究方向，帮助我制订了详细的计划，使我能顺利的掌 握优化技术并顺利完成论文。他渊博的专业知识、质朴的生活作风、平易近人的 处事方式等都给我带来了深刻的影响，感谢两年半时间内洪老师给我的帮助和指 导。 同时还要感谢实验室的吴荣仁老师和宣海军老师，是你们共同给我创造这样 好的实验室环境。感谢实验室的师兄师弟师妹们，他们是：金江明、王彦、叶林、 童仲尧、何庆、陆晓、林乐新、丁志伟、李娟娟、刘璐璐、周忠彭，和你们的共 同学习和生活很快乐。 感谢我的女朋友张召翠，谢谢你给予我的支持和鼓励，用你的关怀与呵护伴 我同行。感谢我的家人，二十几年来支持着我的学业和生活。 浙江大学硕士学位论文 1 1 课题研究背景 第一章绪论 优化技术是研究和解决如何从所有可能的方案中寻找最优方案的技术。优化 技术目前已经成为过程系统工程的重要研究方向，已经从仅仅的学术研究意义进 化到对工业产生重大影响的技术。近年随着应用优化技术解决问题的领域不断扩 大，解决问题的深度不断深化，优化技术广泛应用于农业、国防、交通、金融、 化工、能源和通讯等许多领域。在生命科学、材料科学、环境科学、结构力学和 控制论等科学研究领域也得到广泛应用。国内外的应用实践表明，在同样条件下， 经过优化技术的运用处理，对系统效率的提高、能耗的降低、资源的合理利用及 经济效益的提高等均有显著的效果，而且随着处理对象规模的增大，这种效果更 加显著。这对整个国民经济的各个领域来说，其应用前景无疑是巨大的。因此， 近年来优化方法的研究和应用倍受科技界和工业界的重视。 过程的动态模拟和过程动态优化在近二十年来愈来愈得到过程系统工程研 究者的关注。由于稳态过程只是相对的、暂时的，实际过程中总是存在各种各样 的波动、干扰以及条件的变化。因而过程的动态变化是必然的、经常发生的。常 见问题可以归纳为： 1 计划内的变更，如原料批次变化、高负荷生产或减负荷操作、设备的定 期切换等。 2 事物本身的不稳定性，如同一批原料性质上的差异和波动、冷却水温度 随季节的变化、随生产时间的增加而引起的催化剂活性降低、设备的结 垢等。 3 意外事故、设备故障、人为的误操作等。 4 装置的开停车。 以上种种波动和干扰的存在，都会引起原有的稳态过程和平衡发生破坏，而 使系统向着新的平衡发展。此时就不是稳态模型所能表达了，而必须建立过程的 动态模型，用动态模拟和优化技术来解决过程的设计和操作。砚代化的工业生产 要求实现整个过程的经济效益最大化，这就要求在给定的约束条件( 如产品质量 和指标、设备处理能力、公用工程限制等) 下，按照实时的生产数据，求出各有 浙江大学硕七学位论文 关工艺和操作参数的最佳匹配，并随时实施优化控制。这些问题都向传统的生产 管理、操作和控制提出了新的挑战。因此随着过程动态模拟技术、数值计算和计 算机硬件的发展，过程动态优化技术便应运而生了。 1 2 技术现状 1 2 1 动态优化算法 动态优化算法近几十年在国际上得到了广泛关注和重视，取得了很大进步和 发展1 1 。目前动态优化算法主要可以分为间接方法、基于动态规划方法和直接方 法三种。 间接方法为早期的求解方法，它注重于求解经典的变分条件来得到最优，又 称为变分法，其基础为庞特里亚金极大值原理的一阶最优条件。变分法适用于求 解无约束动态优化问题，而对于有约束的动态优化问题，约束条件为变分法的求 解过程引入更多的乘子及相应的互补条件，从而不可避免的带来耗时巨大的组合 问题。变分法只适用于小规模的问题。 迭代动态规划方法将时间区域分解为多个时间区间，控制变量表示为时间区 间上的分段常数函数或线性函数。迭代动态规划方法通过寻找控制变量序列使得 目标函数最小。一旦找到最优的控制变量序列，则缩紧时间区间，再次进行动态 规划寻优。在反复进行这一过程中，前一步迭代的最优控制变量信息被充分利用 以寻找当前迭代的最优控制变量序列。由于计算效率的问题，动态规划方法也仅 适用于小规模问题。 直接方法通过一定程度的离散将原动态优化问题转化为非线性优化问题。按 照离散程度的不同，直接方法可以分为序贯算法和联立算法。现代过程工业的一 个重要特点是向大型化发展，过程系统特别是化工过程系统模型高度复杂、高度 非线性以及存在复杂的约束条件，其优化问题离散化后得到的n l p 优化问题都 属于带约束的大规模强非线性的优化问题，用间接方法和迭代动态规划方法很难 求解如此大规模优化问题。由于直接方法将动态问题离散为n l p 问题，可以采 用高效的n l p 算法求解，具有较高的计算效率，所以近十年动态优化算法的研 究主要集中在序贯算法和联立算法上，接下来将着重介绍序贯算法和联立算法的 算法结构。 浙江大学硕士学位论文 1 2 1 1 序贯算法 序贯算法【2 】【3 1 将变量划分为控制变量和状态变量，只有控制变量在时间区域 内进行离散，因此序贯算法又被称为部分离散算法。将时间区域划分为多个时间 单元，控制变量表示为时间单元内的分段常量函数、线性函数或者多项式函数。 序贯算法在给定的初始条件和离散控制变量条件下，在每一步n l p 迭代中均需 要使用d a e 求解器求解d a e 系统得到目标函数值，再通过n l p 求解器得到最 佳控制变量的解。由于d a e 系统的求解消除了状态变量和等式约束，使得问题 仅仅包含控制变量，动态优化问题中通常状态变量数目远远大于控制变量数目， 因此状态变量的消除大大减小了问题的规模。 由于在每次优化迭代中，都要求解过程状态方程，即是说d a e 系统总是得 到满足的，状态变量都有明确的物理意义，所以它是一种可行路径法。同时这种 方法又被称为双层算法，把过程模拟称为内层，把优化层称为外层，外层的n l p 优化完全不涉及内层的过程模拟，不需要知道d a e 系统模型。 序贯算法的优点在于其过程模拟和优化计算的双层结构。过程模拟可利用现 有的过程模拟软件，易于工程技术人员的理解和掌握。而优化计算层中不需要考 虑过程系统模型。另外由于序贯算法是可行路径法，因此其每步迭代都是满足 d a e 模型的，也正因为d a e 系统的求解将优化规模大大减小，在n l p 优化中 不需要求解一个大规模的问题。 序贯算法的缺点在于由于状态变量没有包含在n l p 优化层中，基于这种算 法的优化方法不能处理状态变量的路径约束。因此许多序贯算法在处理不等式约 束时，将不等式约束作为惩罚项加到目标函数中，或者通过一个端点约束使它直 接等于零。f e e h e r y 和b a r t o n 曾提出一种可以处理状态变量路径约束的序贯算法 4 1 。这种算法把不等式路径约束问题转化为离散连续混合动态优化问题，在寻优 过程中会遇到不同的微分阶数，需要求解高阶d a e 方程。这种高阶d a e 方程 需要用虚拟导数方法来求解，并且对一些问题还需要二阶灵敏度的信息，所以这 种算法存在很大局限性。序贯算法的另一个缺点是，d a e 系统模拟可能会耗时 很长，甚至在遇到不稳定模型时，对于控制变量输入得不到状态变量的值而导致 优化进程无法继续而终止。 1 2 1 2 联立算法 浙江大学硕士学位论文 近十年来，动态优化算法的研究领域主要偏重于联立算法【5 】【6 】，其主要代表 人物是美国卡内基梅隆大学的b i e g l e r 教授【7 1 。他所领导的研究小组近十年发表 了多篇有关动态优化算法及其在非线性模型预测控制、参数估计、数据调理和过 程综合等方面的应用文章。联立算法离散所有状态变量和控制变量，因此联立算 法又称为完全离散算法，产生的大规模n l p 问题通常由s q p 算法进行求解。将 时间区域划分为有限时间单元，状态变量和控制变量通常使用正交配置法离散。 联立算法将d a e 系统结合到优化问题中，d a e 系统仅在最优解处求解一次，而 在非线性优化迭代过程中不必满足，因此又被称为不可行路径法。由于联立算法 无需求解d a e 系统，由此可以避免许多不必要的中间计算步骤，省去额外的数 值计算时间。 联立算法的最大优点在于将控制变量作为优化变量，因此联立算法处理带有 状态变量路径约束的动态优化问题比较容易。同时由于优化迭代过程中无需求解 模型方程，因此对于不稳定的模型具有很大优势。 联立算法的不足一方面体现在其离散后产生的大规模n l p 问题，通常需要 特殊的分解技术和复杂的数学处理【8 儿9 1 。针对这一问题，b i e g l e r 教授等提出了简 约s q p 算法【1 0 】，它充分利用了d a e 系统j a c o b i a n 矩阵的稀疏结构和优化问题的 块对角结构，将问题的规模减小到与序贯算法相当的水平。另一方面，由于它是 一种不可行路径算法，其中间的优化结果是不可用的，使其在在线优化中的应用 受到了局限。 1 2 1 3 拟序贯算法 在综合研究序贯算法和联立算法优缺点的基础上，最近提出了一种结合两种 算法特点的拟序贯算法【1 1 1 。一方面和联立算法相同，通常采用正交配置法将状态 变量和控制变量全部进行离散，将d a e 系统转化为代数方程组，将不等式约束 加于配置点上。由于状态变量的路径约束在每个配置点上都得到满足，因此说拟 序贯算法结合了联立算法的优点，克服了序贯算法处理状态变量路径约束困难的 缺点。另一方面，拟序贯算法又和序贯算法相同，将变量划分为控制变量和状态 变量，在每次n l p 迭代中都要求解离散模型方程，消除等式约束和状态变量， 从而生成一个小规模的优化问题，保留了序贯算法的这个优点。拟序贯算法的详 细描述将在第二章中给出。 4 浙江大学硕士学位论文 1 2 2n l p 算法 直接方法通过部分离散或全部离散将原动态优化问题转化为n l p 问题，需 要使用n l p 优化算法进行求解，目前最重要的n l p 优化算法为s q p 算法且s q p 算法已被证明优化时需要最少的函数估计次数【1 2 】。s q p 算法通过k k t 系统的牛 顿或拟牛顿搜索方向迭代从而寻找满足k k t 条件的最优解。s q p 算法通常可以 根据以下特性进行分类： 1 根据对不等式约束处理方式的不同可以分为积极集法和障碍内点法 0 3 1 1 4 】。研究表明当有效不等式约束很多时，障碍内点法相对于积极集法 具有优势，相反当有效不等式约束很少或者已知的情况下，积极集法将 会更加有效。 2 根据确保全局收敛性算法的不同可以分为一维搜索和信赖域算法【”】。信 赖域算法具有更好的全局收敛特性，尤其适用于病态的n l p 问题。一维 搜索对于非病态问题更加有效，并且实际应用中实时优化通常都是非病 态的。最近f l e t c h e r 和l e y f f e r 提出了一种过滤一维搜索算法【1 6 】【17 1 ，相较 于基于传统价值函数的一维搜索更加有效。 3 另外二阶导数信息的提供方法也可以分为几种，精确二阶导数可以保证 优化效率，但是需要更多精力给出，于是出现了二阶h e s s i a n 矩阵的 b f g s t l 8 】和l - b f g s t 2 0 】【2 1 1 等更新算法，可以提供h e s s i a n 矩阵的估计值 且保证h e s s i a n 矩阵的正定性。另外也可以通过自动微分工具等求得一 阶和二阶导数信息。 目前基于s q p 算法实现的求解器主要包括i p o p t 2 2 1 、k n i t r o t 2 3 1 、s n o p t ， r s q p 、l o q o 等，不同的求解器在处理不等式约束、全局收敛算法以及h e s s i a n 矩阵的提供方法等方面不尽相同，但是从求解器的发展来看，最新求解器逐渐采 用障碍内点法来代替积极集法来处理不等式约束。 除了基于牛顿方向的s q p 算法，还有基于其它导数方向的n l p 算法，如求 解器l a n c e l o t 、m i n o s 等均为此类算法。通常此类算法相对于s q p 算法需 要更多的函数和导数信息估计次数，但是将此类算法与建模语言相结合，如 g a m s t 2 4 、c u t e i ：z 5 1 和a m p l t 2 6 等，在这些平台上函数和导数信息估计非常高效， 因此此类算法也很有效。 浙江大学硕士学位论文 与以上各种基于导数信息的算法不同，还有一类不需要导数信息的现代优化 算法，如模拟退火算法、遗传算法、神经网络算法、蚁群算法【2 7 1 等。该类算法 实现比较容易，并且具有比较好的全局收敛性。但是现代优化算法只适用于无约 束优化或者说只有简单边界约束的优化问题，并且现代优化算法的计算时间随着 优化变量的增加显著增加，通过并行运算可以改善这种情况，但是总体来说现代 优化算法只适用于小变量问题。 接下来将着重介绍联立算法的简约空间s q p 算法和障碍内点法。n l p 优化 问题的典型模型如下： r a i n ，f ( x ) ( 1 1 a ) x e r “ 、 s i c ( x ) = 0( 1 - l b ) x 0 ( 1 - l c ) 其中式( 1 1a ) 为目标函数，式( 1 1 b ) 为等式约柬，不等式约束通过添加松弛变量转 化为等式约束，式( 1 1 c ) 为变量的边界约束。 1 2 2 1 简约空间s q p 算法 在第k 次迭代中，通过求解以下二次规划子问题得到搜索方向d k ： 珊v f ( x 。) 以+ 三以( 1 - 2 a ) s j c ( x t ) + 4 d k = 0 ( 1 - 2 b ) z t + d 女0( 1 - 2 c ) 求解问题( 1 2 ) ，将变量分解为m 独立变量和，2 一m 非独立变量，矩阵彳分块 表述如下： 彳；= bn 。】 ( 1 3 ) 式中矩阵c 七为约束对非独立变量的导数矩阵，通过一系列的列变换也即非独立 变量的选择，可以保证q 为非奇异矩阵。简约空间s q p 算法将搜索方向分解到 程空间和零空间上，分别定义零空间和程空间的基矩阵为： 绫= 一c ；尺。= 三 c ，一4 ， 搜索方向可以表达为： 浙江大学硕士学位论文 d k = r k d r + q k d q ( 1 5 ) 矩阵绕满足t g = 0 ，因此它是么；的一个零空间基矩阵。程空间的搜索方向可 以通过求解下面方程得到： d 凡= 一g 1 缸 零空间的搜索方向则由如下简约q p 子问题得到： m 俐i n 一。 ( 簖既+ 醇哌r 以) 7 + 三1 嘭v f n r w 。一t - 。) 噍 s j x 女+ r t d r + q d q 0 1 2 2 2 障碍内点s q p 算法 ( 1 - 6 ) ( 1 7 a ) ( 1 7 b ) 障碍内点法使用对数障碍项代替不等式约束，并将障碍项添加到目标函数 中，则原问题( 1 1 ) 转化为： r a 础i n 。吼( x ) = m ) 一乏1 n x ， r 1 - 8 a ) f 1 - 8 b ) 其中k t 为障碍系数，且为一递减序列。障碍法通过求解一系列障碍问题( 1 - 8 ) 来 得到原问题( 1 1 ) 的解。由障碍问题( 1 8 ) 的k k t 条件可得： w ( x ) + 4 五一z = 0 c ( x ) = 0 x z e a e = 0 ( 1 - 9 a ) f 1 9 b ) ( 1 9 c ) 其中v ( x ) 为目标函数的导数，a 为等式约束的j a c o b i a n 矩阵。五和z 分别为等 式约束和不等式边界约束的拉格朗日乘子。x 和z 均为对角矩阵，对角线元素 为x 和z 4 使用牛顿法求解式( 1 9 ) 非线性系统，线性化( 1 7 9 ) 得到第k 次迭代搜索方向 浙江大学硕士学位论文 雕羽= 町誊气 m 呐 睨奢倦h 砜篙4 1 m 其中。= x i l z 。不等式约束乘子的搜索方向为： = 版1 e - - z 。一。 ( 1 - 1 2 ) 1 3 本文研究内容 年来，国外有关动态优化算法的研究蓬勃发展，己有成熟的商业软件，如g p r o m s 浙江大学硕士学位论文 求解器等。 3 实例验证内点拟序贯算法的有效性。首先使用不同方法优化一个数学问 题，对搜索路径进行比较。其次分别通过一个中小规模的管式反应器平 行反应控制问题以及连续搅拌反应器和热集成精馏系统两个大规模最优 控制问题来验证算法效率和稳定性。 4 最后对金文研究工作进行总结并且提出了有待改进之处和未来的研究方 向。 浙江大学硕士学位论文 第二章基于内点法的拟序贯算法 在研究基于积极集s q p 算法的拟序贯算法和内点法的基础上，本章提出了基 于内点法的拟序贯算法，并详细描述其算法结构。内点拟序贯算法同样将优化过 程分为模拟层和优化计算层双层，模拟层中使用正交配置法离散变量并求解离散 模型方程，优化计算层中改用障碍内点法处理不等式约束，以适应大规模不等式 约束问题的要求。 本章讨论的约束动态优化问题的一般性模型如下： m i n ，、缈( z ( ，) ，“( f ) ，f ) ( 2 1a ) s a t ( z ( ，) ，z ( ，) ，“( ，) ，f ) = 0 z ( o ) = z 0 2 n i ms z ( f ) z m a x ( 2 一l b ) ( 2 一l c ) ( 2 1 d ) “m j l l u ( t ) “一 ( 2 - 1 e ) 其中反力与材( 力分别为状态变量与控制变量。式( 2 1 a ) 2 优化目标函数，式( 2 1 b ) 定义了动态优化问题的d a e 模型，式( 2 1 c ) 为状态变量的初始值，式( 2 1 d ) - 与式 ( 2 1 e ) 分别定义了状态变量与控制变量的边界约束。值得注意的是，任何不等式 约束都通过添加松弛变量转化为等式约束并添加到式( 2 1 b ) 的d a e 系统中，松弛 变量添加到控制变量中。 2 1 模拟层 动态优化问题( 2 1 ) 首先经过模拟层将状态变量与控制变量全部离散，将动态 优化问题转化为非线性优化问题。同时和序贯算法一样在每次迭代时求解离散 d a e 系统，对于给定的控制变量输入求得状态变量值以及灵敏度信息，消除状 态变量和等式约束，从而达到减小非线性优化问题规模的目的。 2 1 1 变量离散 从1 9 7 7 + 年提出使用正交配置法进行数值求解微分方程以来，正交配置法【2 8 】 在优化及其它数值计算领域得到了广泛的应用。与其它数值方法，如一阶欧拉近 似方法、龙格库塔法相比，正交配置法具有上机前处理量小、内存占用量少、 1 0 浙江大学硕士学位论文 结果精度高等优点。 拟序贯算法为完全离散算法，即控制变量和状态变量全部离散。将时间区域 分为n l 个时间单元，控制变量表示为每一时间单元内的常量函数或者线性函数， 状态变量采用正交配置法进行离散，通常采用三点配置法，在每一时间单元内有 三个状态变量配置点以及一个初值点。通过将前一时间单元中最后一个配置点的 值赋给下一时间单元初始点的值来保证时间单元之间的连续性。状态变量的三点 正交配置法表示为下图： t oz 1 17 0 z l - i ? 3 ：z l , oz 1 , 2 z 【? 3 。z l + l i o z l + l i 3 ：z t + 2 , 00 图2 - 1 三点正交配置法 状态变量代数项与微分项在每一时间单元内配置点处的值可以表示为： 3 z l ( ，) = 粤( 儿， i = 0 ，3 ；l = 1 ，n l ；( 2 - 2 ) 掣= 删d g j 矿( t t , , ) 锄圳，3 ；m ，n l ； ( 2 - 3 ) 其中粤，( ，。) 与竺d t 盟在以拉格朗日多项式为基的三点正交配置法中分别为： 班心) = ：一= d t 一1 2 0 6 0 3 0 6 0 1 3 3 3 3 3 3 1 1 6 3 9 7 8 2 0 9 1 6 3 9 7 9 o 2 1 1 6 9 3 0 1 6 3 9 7 8 0 7 2 7 4 8 7 5 0 ( 2 4 ) ( 2 5 ) 原动态优化问题( 2 1 ) 通过状态变量的三点正交配置离散以及控制变量的分 段离散转化为如下非线性优化问题： m ，i n 伊( z ，u ) ( 2 - 6 a ) z e r ”“e 一时 、 s 手 f ( z ，“) = 0 ( 2 6 b ) z 1 o = ( 2 - 6 c ) 4 影k ， 甜 钟珊扒d 掺心如肼 3 5 l b 5 c ；一l 浙江大学硕士学位论文 乙i 。z 乙a x ( 2 6 d ) i n u “ ( 2 6 e ) 其中z 与u 分别为离散状态变量和控制变量。式( 2 6 b ) 为离散d a l e 系统，式( 2 6 c ) 为离散状态变量初值，即第一时间单元状态变量初值。式( 2 6 d ) - 与式( 2 6 e ) 分别为 状态变量和控制变量边界约束。正是由于拟序贯算法将原动态边界约束加于状态 变量配置点上形成点约束，拟序贯算法才具有易于处理状态变量边界约束的优 占 n 、 2 1 2 模拟计算 原动态优化问题通过将控制变量离散为时间单元内的常量函数以及在每个 时间单元内使用三点正交配置法离散状态变量转化为非线性优化问题，同时原非 线性微分代数方程组的d a e 系统也转化为非线性代数方程组。模拟计算在已知 控制变量输入的情况下，通过求解非线性方程组得到状态变量值。模拟计算并不 是求解一次规模为尺肌的大型非线性方程组，而是按时间单元逐次进行计算，在 每个时间单元内求解小规模非线性方程组。给定第一个时间单元状态变量的初 值，求解模型方程得到第一个时间单元配置点处的状态变量值。然后将第一个时 间单元最后一个配置点的值作为第二时间单元状态变量的初值，以此类推完成整 个模拟计算过程。 每个时间单元的模型方程可以表示为： c ( z i j “，) = 0 j = 1 ，n l ；i = 1 ，3( 2 7 a ) z ，o = z o ，= 1 ( 2 7 b ) z ，o = z ，- 1 3 ，= 2 ，n l( 2 - 7 c ) 勿，与u 1 分别为每个时间单元内的状态变量与控制变量，和i 分别为时间单元编 号和配置点编号。式( 2 7 a ) 为每个时间单元内的离散非线性方程组，式( 2 7 b ) 为状 态变量初值，亦即式( 2 6 c ) ，式( 2 7 c ) 为单元间的连接方程，即前一单元的最后一 个配置点作为后一单元状态变量的初值。 非线性方程组( 2 7 ) f f 寸求解方法有很多种类，最基本的是牛顿迭代法。牛顿迭 代法的基本思想是通过泰勒级数展开对非线性方程进行近似的线性化。使用k 表 浙江大学硕士学位论文 示第k 次优化层迭代，使用船表示模型方程的第触次牛顿迭代。模型方程经过 泰勒级数线性化后，第船步牛顿迭代方向为： 止船= 一( 害) 一c ( z k k ，h k ) = 一c 一1 ( z k k , l l k ) c ( z 船，站。)( 2 8 ) u z 其中c ( z 胁，“。) 是模型方程对状态变量的一阶导数矩阵，称为状态变量的j a c o b i a n 矩阵。牛顿迭代法通过z 船+ 。= + 应肚进行更新，直至达到收敛条件得到状态变 量的解。 在实际的大规模优化问题中，非线性方程组的维数通常很大，并且状态变量 的j a c o b i a n 矩阵非常稀疏。在迭代方向计算时如果直接进行求逆运算将会消耗大 量时间，通常可以利用j a c o b i a n 矩阵的稀疏结构求解线性方程组o c o ca z 船= 一c ( z 敞，u k )( 2 9 )一、船= 一般， ) ( 2 _ 9 ) 叱 目前已经有很多成熟的稀疏线性方程组求解器，如h s l 的m a 2 7 、m a 2 8 和m a 5 7 求解器、m u m p s 和p a r d i s o 等。在利用这些稀疏求解器时，需要给出左端 j a