（系统工程专业论文）自动微分算法研究及其在过程系统优化中的应用.pdf

浙江大学硕士学位论文 摘要 在流程工业自动化系统中，优化起着非常重要的作用，如何提高优化的求解 速度和精度是一个意义重大且富有挑战性的研究课题。而在优化计算过程中，导 数是至关重要的信息，因为它代表了寻优过程的搜索方向。同时，导数求解的耗 时在整个优化时间中往往占有很大的比重，尤其是在对大规模复杂计算流程进行 优化时，求导耗时往往成为提高优化效率的瓶颈。由此，寻找一种精确又快速的 求导算法是提高优化计算效率最有效的途径，这也是本文工作的重点所在。 遥过研究当前热门的自动微分求导算法，并将其应用于精馏塔灵敏度分析过 程，以及应用于本文建立的乙烯生产流程脱丙烷和脱丁烷塔的联塔模型的优化计 算过程，再与传统的差分法和稀疏差分法进行比较，分析求导算法的不同对优化 效率的影响。 本文的研究工作包括以下几个方面： 1 简要介绍过程系统优化的重要性，通过分析求导和优化的关系，强调求 导在优化计算中的重要性。并介绍自动微分算法的发展和应用、基本原 理和自动微分算法的发展。再着重分析和比较自动微分算法的两种实现 方式：基于操作符重载和基于编译原理，并同传统的差分法和稀疏差分 法进行比较分析，找寻最可行有效的求导算法。 2 对乙烯生产流程中两个重要的单元脱丙烷塔和脱丁烷塔，采用开放方程 法在m a t l a b 平台建立联塔数学模型，并对联塔模型进行模拟计算， 将计算结果同a s p e n 流程模拟结果进行比较，以验证模型的合理性。 3 实例分析自动微分算法在精馏塔优化计算的灵敏度分析中的应用，包括 将其应用于灵敏度分析过程，以及灵敏度的并行计算过程。 4 实例分析自动微分算法在过程系统优化计算中的应用，包括将自动微分 应用于乙烯生产流程的脱丁烷单塔以及联塔的优化计算中，并比较和分 析其对优化效率的影响。 l i i 浙江大学碗l 学位论文 t h i sp a g ei sl e f tb l a n ki n t e n t i o n a l l y 浙江大学硕士学位论文 a b s t r a c t p r o c e s ss y s t e m so p t i m i z a t i o np l a y sas i g n i f i c a n tr o l ei nt h ef i e l do fp r o c e s s s y s t e m se n g i n e e r i n g a n d h o wt o i m p r o v et h ee f f i c i e n c y a n da c c u r a c yo f o p t i m i z a t i o ni sab i gc h a l l e n g ef o rt o d a y sr e s e a r c h e r s s i n c et h en u m e r i c a ld e r i v a t i v e r e p r e s e n t st h es e a r c hd i r e c t i o no fo p t i m i z a t i o np r o c e s s ，i t s t h ek e yi n f o r m a t i o nf o r o p t i m i z a t i o n b e s i d e s ，d e r i v a t i v ec a l c u l a t i o ni sa l w a y st h em o s tt i m e c o n s u m i n gp a r t o ft h ew h o l eo p t i m i z a t i o np r o c e s s ，e s p e c i a l l yf o rt h el a r g e - s c a l ep r o b l e m s t h e r e f o r e ， a p p l y i n ga l la c c u r a t ea n de f f i c i e n t d e r i v a t i v ec a l c u l a t i o nw a yt oo p t i m i z a t i o ni so f g r e a ti m p o r t a n c ef o rt h ei m p r o v e m e n to fo p t i m i z a t i o ne f f i c i e n c y a u t o m a t i cd i f f e r e n t i a t i o n ，ap r o m i s i n gd i f f e r e n t i a t i o na l g o r i t h m ，w h i c hh a sb e e n d e v e l o p e dr a p i d l yi nr e c e n tt w e n t yy e a r s ，i si n v e s t i g a t e di nt h et h e s i s a n da u t o m a t i c d i f f e r e n t i a t i o ni sa p p l i e dt ot h es e n s i t i v i t ya n a l y s i sp r o b l e mo fd i s t i l l a t i o nc o l u m n o p t i m i z a t i o n ，a sw e l la st h eo p t i m i z a t i o np r o b l e mo ft h em u l t i d i s t i l l a t i o nc o l u m n s m o d e lo fd e p r o p a n i z e ra n dd e b u t a n i z e ri ne t h y l e n ep l a n t f i n a l l yt h ec a l c u l a t i o n r e s u l t sa n de f f i c i e n c ya r ea n a l y z e da n dc o m p a r e dw i t ht h et r a d i t i o n a lf i n i t ed i f f e r e n c e a n ds p a r s ef i n i t ed i f f e r e n c e t h em a i nc o n t r i b u t i o n si n c l u d et h ef o l l o w i n ga s p e c t s ： 1 t h ei m p o r t a n c eo fn u m e r i c a ld e r i v a t i v ef o ro p t i m i z a t i o ni ss t u d i e db y a n a l y z i n gt h er e l a t i o n s h i po fd e r i v a t i v ee v a l u a t i o na n do p t i m i z a t i o n a n dt h e d e v e l o p m e n ta n da p p l i c a t i o n so fa u t o m a t i cd i f f e r e n t i a t i o na l g o r i t h mi nr e c e n t y e a r sa r ei n t r o d u c e d ，a sw e l la st h eb a s i ca l g o r i t h mi sd i s c u s s e d a n dt w o i m p l e m e n t a t i o nw a y s o fa u t o m a t i cd i f f e r e n t i a t i o nb a s e do ns o u r c e t r a n s f o r m a t i o na n do p e r a t o ro v e r l o a d i n ga r ef u l l yi n v e s t i g a t e da n dc o m p a r e d w i t ht h et r a d i t i o n a lm e t h o d so ff i n i t ed i f f e r e n c ea n ds p a r s ef i n i t ed i f f e r e n c e 2 e q u a t i o no r i e n t e dm e t h o d i s a p p l i e dt o t h em u l t i - c o l u m n sm o d e l i n go f d e p r o p a n i z e ra n dd e b u t a n i z e ri ne t h y l e n ep l a n tb a s e d o nf i r s tp r i n c i p l e s a n d t h es i m u l a t i o nr e s u l to ft h eb u i l tm o d e li sp r o v e dc o r r e c ta f t e rc o m p a r i n g w i t ht h er e s u l to fa s p e np l u s ，ap r o f e s s i o n a la n dc o m m e r c i a ls i m u l a t i o n s o f t w a r e 3 t h ea p p l i c a t i o no fa u t o m a t i cd i f f e r e n t i a t i o ni ns e n s i t i v i t ya n a l y s i so f d i s t i l l a t i o nc o l u m no p t i m i z a t i o ni sd i s c u s s e d ，i n c l u d i n ga p p t y i n gi tt ot h e v 浙江大学硕士学位论文 s e n s i t i v i t ya n a l y s i sp r o b l e mo fd i s t i l l a t i o nc o l u m no p t i m i z a t i o n ，a sw e l la s t h ec o r r e s p o n d i n gp a r a l l e ls e n s i t i v i t ya n a l y s i sp r o c e s s 4 t h ea p p l i c a t i o no f a u t o m a t i cd i f f e r e n t i a t i o nj np r o c e s ss y s t e m so p t i m i z a t i o ni s f u l l yi n v e s t i g a t e d ，s u c ha sa p p l y i n gi tt ot h eo p t i m i z a t i o np r o b l e mo ft h e m u l t i d i s t i l l a t i o nc o l u m n sm o d e lo fd e p r o p a n i z e ra n dd e b u t a n i z e ri ne t h y l e n e p l a n t ，a sw e l la st h eo p t i m i z a t i o np r o b l e mo fs i n g l ed e b u t a n i z e rm o d e l t h e i n f l u e n c eo fd i f f e r e n td e r i v a t i v ee v a l u a t i o n w a y s t ot h ee f f i c i e n to f o p t i m i z a t i o ni sa n a l y z e da n dc o m p a r e dt h r o u g ht h ea p p l i c a t i o n s 本文工作得到国家重点基础研究发展规划项目( 9 7 3 项目，n o 2 0 0 2 c b 3 1 2 2 0 0 ) “复杂生产制造过程实时智能控制与优化理论和方法 研究”和国家自然科学基金项目( n o 2 0 2 7 6 0 6 2 ) “基于自动微分算法的 化工过程系统优化”资助。 致谢 首先我要感谢我的导师邵之江教授对我的学习和研究给予的帮助和指导。邵 老师在研究的思路和方向上常给予我关键性的指导和提点，帮我解决研究过程中 遇到的困难，督促我不断努力上进，他求真的科学态度和踏实的工作作风永远值 得我学习。对邵老师的耐心指导、悉心调教，在此致以崇高的敬意和真挚的谢意! 感谢系统所陈曦老师在过程系统模拟与优化方面给予我的支持和帮助，和他 的热情关怀和鼓励。感谢钱积新老师、王惹老师、赵均老师、梁军老师、赵豫红 老师、周立芳老师对我的关心和帮助! 感谢李翔师兄，李翔师兄在自动微分方面做了大量的工作，在他离校前，对 我热心帮助，悉心指导，将自动微分的知识和工作倾囊相授。李翔师兄出色的工 作为我今天自动微分的研究奠定了坚实的基础。还要感谢张仲广师兄，在张师兄 的热心帮助下，我才能完成关于并行计算的研究，再次表示感谢! 感谢9 7 3 课题组的江爱朋师兄、方学毅师兄、耿大钊、吴嫒嫒、张正江、李 吴和邵泉敏，感谢他们在我研究过程中给予的支持和帮助。还要感谢4 1 3 实验室 的姚莉、黄婉平、沈倩、陈圆、高枫、王赓、蒋维、吕晶华、金盂合、施健等同 学在生活上给予的关心和照顾，我会十分怀念我们共同营造出来的融洽温馨学习 和生活氛围。同样要感谢朝夕相处的室友对我的关心和照顾。 最后，我要感谢我的家人，特别是我的父母。在我研究生期间，他们经常从 千里之外打来电话询问情况，给予鼓励，使我能一直饱含热情的工作。他们无私 的关怀将永远是我学习和工作的动力。 谨以此文献给所有关心和帮助过我的人。 郑小青 2 0 0 6 年3 月4 目 求是园 浙江大学硕士学位论文 第一章绪论 摘要：本章简要介绍过程系统优化的重要性，强调求导方法在其中的意义，并介绑当前热门 的自动微分算法的发展和应用，基本原理，自动微分算法的发展和改进，其中义包括符号白 动微分算法的提出，相应的工具箱x a d m a t 的开发以及面向模块的自动微分方法的提出。 再详细阐述了本文的研究内容，为下文第二章到第五章的研究工作做好铺垫。 1 1 过程系统优化计算 现代工业生产过程的一个重要特点是大型化和复杂化( 钱积新等，1 9 9 7 ， 1 9 9 8 ) ，只有具备较高的自动化和计算机水平才能满足生产过程的各种需求，使 得企业提高经济效益，于是出现了综合自动化系统c i p s ，它包括过程控制层， 过程优化层，最优调度层和计划决策层，其中过程优化处于过程控制和最优调度 两层之间，起着桥梁的作用，是企业增效的核心所在。尤其是在市场竞争激烈、 企业不断追求更高利润和效益的今天，优化已经从纯学术的理论发展成为能对工 业起到巨大推动作用的技术力量，成为工业企业保持竞争力的主要技术手段 ( b i e g l e ra n dg r o s s m a r m ，2 0 0 2 ) 。 国外实时优化技术的应用表明，对于一般的过程系统采用实时优化技术可以 使经济效益提高3 以上( l a u k s 等，1 9 9 2 ；徐用懋，杨尔辅，2 0 0 1 ) ，采用优化 技术的投资费用一般可以在o 5 2 年收回成本。对于在国民经济中占主导地位的 流程工业，3 以上的效益提高意味着极高的经济回报。 除了经济效益的提高，过程系统优化还具有以下作用f 江爱朋，2 0 0 5 ) ： 通过优化减少原材料、人力和能源等的消耗，提高生产资料的利用水平，使 得生产资料得到更加合理的利用，从而降低生产成本。通过优化使得生产各个环 节得到改善，使得设备利用率和产品收率等得到提高，从而提高整体的生产效率， 增加企业的利润率。通过过程设计优化得到最合理的设计模式，从而以最有效、 最节省的模式对系统进行设计，减少设备投资。通过对系统的模拟和优化，可以 了解在不同工况下的系统性能，并对危险工况进行分析，尽量加以避免，增强安 全性。通过优化控制，使得产品质量保持连续一致。通过优化使得系统的启停操 作更加经济和安全，通过模拟与优化确定系统的瓶颈问题所在，有利于系统的改 善。 浙江大学硕士学位论文 而在优化方法和技术方面，目前，可以直接或者通过技术改造来求解大规模 优化命题的算法主要有序列线性规划算法、罚函数和障碍函数算法、增广拉格朗 f 1 函数算法、广义简约梯度算法、内点方法、序列二次规划算法和序列凸规划算 法( s c h i t t k o w s k i ，2 0 0 3 ) 。其中序列二次规划算法( 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 g ， s q p ) 是目前应用最为广泛、最为有效的非线性优化算法，国外许多学者，包括 v a s a n t h a r a j a ns ( 1 9 8 8 ，1 9 9 0 ) 、s c h u l z ( 1 9 9 6 ) 、n i c k e lr h ( 1 9 8 9 ) 、b o g g s ( 1 9 9 5 ， 2 0 0 0 ) ，都对s q p 或改进过的r s q p 进行了深入的研究和探讨。总的来说，s q p 算法具有以下优点：强大的非线性处理能力；非常适用于约束优化问题求解；采 用拟牛顿方法计算搜索方向，不需要二阶导数信息；不需要初始可行解；具有快 速收敛性甚至超线性收敛性；稳定性好，鲁棒性强。 在优化技术的软件开发和应用方面，国外大型流程工业公司不仅开发了许多 优秀的流程模拟与优化软件，而且将大规模在线优化技术应用于生产过程，取得 了非常显著的成果。仅在石油化工领域，国外已有2 0 多家软件公司相继推出了 在石油化工过程专用和通用的流程模拟软件6 0 多种，优化软件3 0 余种，其应用 领域涉及天然气加工、原油蒸馏和分馏、催化裂化、加氨、溶剂脱蜡、减粘、延 迟焦化、硫回收、乙烯装置、合成氨、p e t ( 聚酯) 、苯乙烯、氯乙烯单体、用能 组合、炼厂装置及整体等f 江爱朋，2 0 0 5 ) 。 其中，流程软件开发公司a s p e nt e c h 走在前列，开发优秀的流程模拟和优 化软件a s p e np l u s ，将其用于石油、化工、制药等领域的稳态过程系统模拟与优 化。a s p e np l u s 包含序贯模块和开放式方程两种过程系统建模方式，并可以采用 序列二次规划s q p 法进行模拟和优化计算，s q p 方法在其中具有很好的鲁棒性， 能快速、灵活的进行模拟计算和优化求解。 1 2 优化与求导 当前的许多优化算法的求解计算都是要基于模型的一阶和二阶的导数信息 的，比如非线性规划的s q p 算法，为了构造二次规划子问题，需要求出原问题 的一阶和二阶导数信息。 这些优化算法离不开求导的原因在于，它们本质上都是基于牛顿法或拟牛顿 法的寻优思路，其优化过程的实质是寻找函数在自变量的可行域内的最小或最大 浙江大学硕士学位论文 值，而牛顿法的实质就是通过探求函数和自变量之间的动态变化关系来找到这个 最小或最大值。我们知道，一阶导数描述的恰恰就是函数关于自变量的变化率， 同时二阶导数反映了一阶导数关于自变量的变化率；这两者的信息综合起来就可 以反映函数和自变量之间的这种动态关系。在拟牛顿法中，二阶导数信息用其它 的方法来近似，从而避免了求取二阶导数带来的诸多数值计算问题。牛顿法和拟 牛顿法对导数信息的利用，从本质上说是对模型信息的利用，是优化算法合理而 自然的选择( 李翔，2 0 0 3 ) 。 尤其在复杂的过程工业中，所建立的系统优化问题常常带有大量的等式或者 不等式约束，采用借助于导数信息的优化算法，能相对快速地收敛，找到最优解。 因此，基于严格机理模型和导数计算的优化算法仍是过程系统优化的主流方法， 而本文过程系统优化将采用的s q p 方法就是其中最有效的一种算法。 由于导数信息要用于构造优化的搜索方向，所以优化中的求导算法的精确性 是很重要的。而且，求导所用的时间占整个优化时间的比重非常高，w o l b e r t 等 ( 1 9 9 4 ) 指出至少在某些流程优化中，求导计算是过程优化中最为耗时的一步。因 此寻找到一种精确又高效的求导算法对优化而言是至关重要的。 综上所述，求导问题是过程系统优化不可避免的重要问题。差分法( f i n i t e d i f f e r e n c e ，f d ) 和自动微分法( a u t o m a t i cd i f f e r e n t i a t i o i l ，a d ) 是当前两种主要的求 导算法。差分法实际上是将模型看作“黑箱函数”，仅根据其输入和输出之间的 关系来逼近导数，由于差分法的实现十分方便，再加上改进过的稀疏差分法求解 速度相对比较快，从而使它成为流程模拟和优化计算中历史最悠久、应用最广泛 的方法。但是差分法不可忽视的一个弱点是，它求得的是不精确的、存在截断误 差的导数信息。而自动微分是近二十年多来才发展迅速的精确的求导算法，能求 出相当于计算机精度的导数信息，但如何提高自动微分的求解效率和可行性，提 升它在流程优化计算中的可适用性是当前一个热门的研究课题，也将是本文着重 研究的方向。 1 3 自动微分求导技术 自动微分方法源自于2 0 世纪7 0 年代末，b e r ts p e e t p e r m i n g 提出的种新的 求导思路，他直接用算法来分析目标函数的结构从而自动地生成计算导数的代 浙江大学颇十学位论文 值，而牛顿法的实质就是通过探求函数和自变量之问的动态变化关系来找到这个 最小或最大值。我们知道，一阶导数描述的恰恰就是函数关于自变量的变化率， 同时二阶导数反映了一阶导数关十自变量的变化率；这两者的信息综合起来就司 以反映函数和自变量之刚的这种动态关系。在拟牛顿法中，二阶导数信息用其它 的方法来近似，从而避免了求取二阶导数带柬的诸多数值计算问题。牛顿法和拟 牛顿法对导数信息的利用，从本质上说是对模型信息的利用，是优化算法合理而 自然的选择( 李翔，2 0 0 3 ) 。 尤其在复杂的过程工业中，所建立的系统优化问题常常带有大量的等式或者 不等式约束，采用借助于导数信息的优化算法能相对快速地收敛，找到最优解。 因此，基于严格机理模型和导数计算的优化算法仍是过程系统优化的主流方法， 而本文过程系统优化将采用的s q p 方法就是其中最有效的一种算法。 由于导数信息要用于构造优化的搜索方向，所以优化中的求导算法的精确性 是根重要的。而且，求导所用的时间占整个优化时间的比重非常高，w o l b e r t 等 ( 1 9 9 4 ) 指出至少在某些流程优化中，求导计算是过程优化中最为耗时的一步。因 此寻找到一种精确又高效的求导算法对优化而吉是至关重要的。 综上所述，求导问题是过程系统优化不可避免的重要问题。差分法( f i n i t e d i f f e r e n c e ，f d ) 和自动微分法( a u l o m a t i cd i f f e r e n t i a t i o n 。a d ) 是当前两种主要的求 导算法。差分法实际上足将模型看作“黑箱函数”仅根据其输入和输出之删的 关系来逼近导数，由于差分法的实现十分方便，再加上改进过的稀疏差分法求解 速度相刘比较快，从而使它成为流程模拟和优化计算中历史最悠久、应用最广泛 的方法。但是差分法不可忽视的一个弱点是，它求得的是不精确的、存在截断误 差的导数信息。而自动微分是近二十年多来才发展迅速的精确的求导算法，能求 出相当于计算机精度的导数信息，但如何提高自动微分的求解效率和可行性，提 升它在流程优化计算中的可适用性是当前一个热门的研究课题，也将是本文着重 研究的方向。 1 3 自动微分求导技术 自动微分方法源自于2 0 世纪7 0 年代末，b e r ls p e e l p e n n i n g 提出的一种新的 求导思路，他直接用算法来分析目标函数的结构从而自动地乍成计算导数的代 求导思路，他直接用算法来分析目标函数的结构从而自动地生成计算导数的代 浙江大学硕士学位论文 码，2 0 多年这种思路得到了不断的完善，逐渐形成了现在的较成熟的自动微分 算法( a u t o m a t i cd i f f e r e n t i a t i o n ，a d ) 。德国亚琛技术大学( a a c h e nu n i v e r s i t yo f t e c h n o l o g y ) 的研究小组对自动微分做出了如下的定义： 自动微分是机械地运用链式求导法则对计算机程序形式的函数求导的一组 技术。自动微分利用了这样的事实，即无论描述函数的计算机程序有多么的复杂， 它本质上都是执行一系列的元代数运算或元函数运算( 比如指数函数) 。通过对这 些元运算迭代地运用链式求导法则，计算机可以自动地和精确地得到目标函数的 任意阶导数。 】3 1 自动微分的发展和应用 虽然一般认为自动微分源自于b e r ts p e e l p e n n i n g 的求导思路，但事实上早在 二十世纪五十年代，自动微分算法就已经开始萌芽。比如，1 9 5 9 年，l m b 。d a 等人发表文章“基于b e s m 机器的自动微分编程”mm b e d a 等，1 9 5 9 ) 。该文 章被认为是自动微分领域最早的研究。 而近二十年来，自动微分以其独特优势蓬勃发展，研究成果层出不穷。比如， b i s c h o f ( 1 9 9 2 ，1 9 9 4 ，1 9 9 7 ) ，c o l e m a n ( 1 9 9 6 ) ，g r i e w a n k ( 1 9 9 1 ) ，i r i ( 1 9 9 1 ) ， j u e d e s ( 1 9 9 1 ) 都对自动微分进行了研究，并发表了文章。 图1 1 显示了二十世纪自动微分的研究论文和其它出版物的情况，从中可以 对自动微分的历史发展趋势有一个直观的了解。 图1 1 二十世纪自动微分的出版物统计 注：横坐标为年份，纵坐标为相应年份的出版物情况 4 浙江大学硕士学位论文 而自动微分的应用非常广泛，在物理、化学、环境、电力、医学、气象、航 空航天等领域中都得以应用，并取得了卓越的成果和丰富的经验。从被应用对象 所形成的数学问题的类型的角度，自动微分的应用可以分为四个方面： 1 单纯的微分计算，比如用于曲率计算，t a y l o r 展开等。 2 数值分析和求解领域，比如将自动微分应用于常微分方程的计算过程， 或者微分代数混和方程的求解过程，又或者用于离散化的偏微分方程 的求取过程，有利于得到精确的计算结果。 3 灵敏度分析领域。当模型存在不确定性参数，或者扰动的时候，可以 将自动微分方法引入以定量分析扰动或不确定性参数对模型的影响， 即模型对其扰动或不确定参数的灵敏度。 。 4 非线性优化领域。在无约束或有约束的非线性优化中，需要提供 j a c o b i a n 矩阵信息以确定优化算法的搜索方向，自动微分是不同于传统 差分法的非常好的选择。 尤其第四方面，自动微分在优化计算领域的应用是本文关注的重点，而纵观 国内外的研究情况，自动微分在该领域成功应用的实例也是层出不穷。 b i s e h o f 等( 2 0 0 1 ) 将自动微分应用于化学领域中子散射的参数拟合，中子散射 是要研究固体或液体的分子动态。从数学的角度，该参数拟合问题展后形成的是 一个无约束的优化问题。前向自动微分方法被应用于求解目标函数的导数信息， 并将其用于改进过的高斯一牛顿法中，结果显示，这比原来的基于差分法的拟牛 顿方法更精确、更可靠。 b i i c k e r 等( 2 0 0 2 ) 同样对上述参数拟合问题进行研究，对3 5 0 0 行基于 f o r t r a n 7 7 语言的目标函数代码用自动微分工具a d i f o r 进行求导，该自动微 分方法在参数拟合中的应用，极大地显示出其在精确和效率方面的高效性，并且 通过一种接口改进( i n t e r f a c ec o n t r a c t i o n ) 策略的实施，更进一步地提高这种基于自 动微分的参数拟合的计算效率。 l a u r e n th a s c o t 等( 2 0 0 3 ) 将自动微分应用于一个实际的三维最优设计问题 中，将超声波飞行器的音爆作为目标函数，通过优化计算实现目标函数最小。 k u m a r 将自动微分的后向求导模式应用于该问题的求导计算中，并通过调用自动 微分工具t a p e n a d e 进行求解，计算结果证明了这种自动微分应用方法的成功。 j o n ggk i m 等( 2 0 0 3 ) 将自动微分集成于多相、多组分、非等温的流程模拟器 浙江人学硕士学位论文 t o u g h 2 中，并在t o u g h 2 的e c 0 2 模块的模拟计算过程中，应用自动微分方 法进行求导计算，同传统的差分法比较发现，自动微分单次求解j a c o b i a n 矩阵的 效率整整改进了2 8 。 d e r y ab ，o z y u r t 等( 2 0 0 4 ) 将自动微分应用于大规模的动态优化过程。我们知 道，无论是化工还是生物工程领域，动态优化问题的求解比较困难，也因此受到 越来越多的关注。动态优化问题可以通过常微分方程或微分代数混合方程进行描 述，优化求解过程中需要对目标函数或者约束方程进行一阶甚至二阶的导数计 算，非常耗时。为改善这种情况，o z y u r t 提出一种新方法，应用自动微分将该动 态优化问题转化为定向二阶伴随系统( d i r e c t i o n a ls e c o n do r d e ra d j o i n ts y s t e m ) 再进 行求解，并通过实例测试，证明了这种基于自动微分和伴随系统理论的在解决大 规模动态优化问题中的有效性。 除了上述在各领域中的成功应用，自动微分还被集成到专业的数学软件或优 化软件中，用于其中的求导计算。比如： b i s c h o f 等( 2 0 0 1 ) 将自动微分应用到通用有限元软件包s e p r a n 中，使 该软件包的功能从单纯的对对象的模拟扩展到可以对对象模型进行求 导。在此，自动微分处理的问题不是简单的程序文件，而是共有大约8 0 万行f o r t r a n7 7 代码、含有超过3 0 0 0 个子程序的软件包。对于一个 典型的问题，自动微分需要将约4 0 万行模型计算代码转换为约6 0 万行 的模型求导代码。通过一些标准测试问题的实验，可以看到对于 s e p r a n 描述的模型，自动微分比差分具有更高的效率、精确性和可靠 性f 李翔，2 0 0 3 ) 。 t o l s m a 等( 2 0 0 1 ) 将自动微分技术集成在通用的动态建模和仿真工具 d a e p a c k 中，极大地提高其在求解微分方程中的效率和可靠性。 d a e p a c k 在化工动力学计算、燃烧过程模拟和优化等问题中取得了极 大的成功( 李翔，2 0 0 3 ) 。 自动微分算法被集成于建模语言和平台a m p l 以及g a m s 中，通过调 用自动微分引擎来计算a m p l 或g a m s 平台下优化或模拟计算所需的 导数信息，为其平台下的各种优化求解器提供了一种精确可靠的求导算 法，也因此极大地扩展了自动微分的应用。 自动微分算法被加入到专业的优化软件包g a l a h a d 中。g a l a h a d 浙江人学碗士学位论文 是基于f o r t r a n 9 0 的大规模优化计算软件包，可以求解无约束优化问 题、二次规划问题、约束优化问题以及非线性最小二乘问题。自动微分 算法的加入使得用户在优化求解过程中多了一种更可靠、可精确的求导 算法的选择。 n e o s ( n e t w o r ke n a b l e do p t i m i z a t i o ns y s t e m ) 服务器5 0 版中，集成了三 种自动微分工具：基于f o r t r a n 7 7 语言的a d i f o r ，基于a n s ic 语 言的a d l c ，以及基于c 语言的a d o l c 。可见自动微分的优势已被广 泛接受。 基于m a t l a b 平台的自动微分工具m a d 被应用于t o m l a b 公司丌发 的专业优化软件t o m l a b 中，并为用户提供了三种自动微分求导方式： m a d 、稀疏m a d 以及压缩m a d ，详细阐述见第二章。 1 3 2 自动微分基本原理 自动微分的基本原理如下：无论函数有多复杂、其形式如何、是否含有子程 序，每个函数都可以写成一系列的基本的元函数，比如加、减、乘、除和s 1 n 等的组合，若对这些基本的元函数求偏导数，并用链式求导法则对偏导数按规律 进行累积，就可以计算出与机器精确度相当的求导结果( 李翔等，2 0 0 1 ) 。 考虑标量函数y = ( x ) ，f ：r ”一矗，有如下关系： f o r i = + 1 , n 十2 胛+ p x ，= ，( x a j j i( 1 1 ) e n d y 2 x n + d 其中，j ic 1 , 2 ，i 一1 ) ，v f = m + l ，行+ 2 ”，聆十p 上述( 1 1 ) 所示的关系恰恰表明了将原函数表示成若干个基本元函数的组合 的过程：对于含”独立变量t ，x ：，z 。的函数y = ，( 工) ，设置p 个中间变量 x n + lx 。，x 。，并将其表示成基本元函数。以。，六+ ，最后一项t + ，就是 因变量y = 厂( z ) = 厶+ ，。 比如函数y = s i n ( x i + x 2 ) + e x p ( 3 * x ，) ，其独立变量为，工：屯 ，设置中间 c o s x 浙江大学碗上学位论文 变量f x 。，j ，氏，z ，x 8 ，x ，_ 。 ，并将其表示成相应元函数 厶，疋，无，7 ， ， ，z 。 。 工4 = 厶= x 1 + 工2 j 5 = ；= 3 x x 6 = 五= c o s x 】 x 7 = 厶= s i n x 4 x 8 = 以= e x p ( x 5 ) x 9 2 五2 x 7 - t - x 8 因变量：y = r i o = 必。 再对每个元函数 厶， ，兀， ，以，五，一。) 求偏导数，并按式( 1 2 ) 的链式关系， 对求得的元偏导数进行累积。 立：监监监监；蚯监 两砘k 阮豌。阮屯 要：娑要墼姿 ( 1 z ) 政k 嵋瓯阮 ”7 a y ：监监监亟 鸭砘弧氓两 用如下关系图1 2 表示各元函数的组合及其偏导的过程： 圈1 2 关系图 注：各有向连线上的表达式为相应的元函数的偏导数，各节点表示独立变量或元函数。 浙江大学顶十学位论文 由该图，并根据上述的链式求导关系就可以最终得到精确的导数结果 砂砂砂 两咄阮。 而自动微分算法在计算机内部实现方式有两种：前向模式和后懒( t o l s m a a n db a r t o n ，1 9 9 8 ) ，分别见图1 3 和图1 4 。 f o r w a r d ( y ，v ，x ) 1 f o ri _ l t on 2 可x 。：e ? 3 e n d 4 f o r i 一i l + 1t o n + p 5 x 1 卜f 。b i l 耐j s 吣善誓j *u 7 e n d 8 - y 七- x h n 9 、y 七- 飞x 。 图1 3 前向算法模式 r e v e r s e ( ，v y , x ) 1 f o ri n + lt o n 十p 2 ，x 。卜，一k j j 3 。x i 1 0 4 e n d 5 y - 工。+ 。 6 善。一1 7 f o ri 卜lt o n 8 t - 0 9 e n d l o f o r i - n + p d o w n t on + tb y 1 - ，i = i + 誓i w 以 1 2 e n d 1 3 f o ri - - 1t on 1 4 砂。_ t 】5 e n d 图1 4 后向算法模式 前向模式算法是一个正向累积得过程，对于p 个中间变量按链式求偏导规 则，v x l = ， j i 吼，正向直接地求其梯度，最终得到函数y 的梯度v r 厂。而 后向模式算法就不像前向模式那么直接简单，它分两步：首先是正向地计算d 个中间变量= z ( j ，) ，t ，再是反向地从第n + p 硕至n + l 项累积中间变量地 梯度i = i + 誓i 。这里，i = 妻。比较两种模式的梯度运算删可以看出， 后向模式不像前向模式那样需要重复地累积计算梯度，它的梯度x y 和计算函数 f 的计算量比率与独立变量的个数n 无关。另外，它的时间复杂度方面比其他方 浙江大学钡士学位论文 法都来得更加有利，但同时它需要增加更大的存储空问。 比较前向模式和后向模式的计算效率，若n 为自变量个数，则前向模式算法 汁算导数的时间不超过计算原函数时间的3 月倍，而后向模式算法计算导数的时 间不超过计算原函数时间的3 倍，但是后向模式由于需要存储中间计算结果， 其存储空间比前向模式算法多o + p ) ( t o l s m a a n db a r t o n ，1 9 9 8 ) 。在计算机软硬 件告诉发展的今天，存储空间并不是个问题，因此后向模式以其时间复杂度相 对较低的优势更获得青睐。 1 3 _ 3 符号自动微分算法和x a d m a t 自动微分虽然能求精确的数值导数值，但无法求导数的解析表达式。试想如 果能生成导数解析表达式，优化计算时只需调用这个文件求导即可，这样就会极 大地提高求导和优化的效率。但是靠手工求解表达式显然是不可行的，李翔( 2 0 0 3 年) 在自动微分的基础上提出符号自动微分方法，可以求解对象函数的导数解析 表达式。 符号自动微分算法借用了自动微分对对象函数的拆解分析方法，可以对子程 序形式的函数求导。其求导原理如下( 李翔，2 0 0 3 ) ： 对于一般的自动微分的求导过程，在执行时并不将自变量的数值代入，而是 将自变量作为符号代入。之后，在每一步运算中并不是做数值计算，而是做符号 计算，这样得到的中间变量都是符号表达式的形式。最后得到的求导结果就不是 函数在某一个点处的数值导数，而是该函数的导数的符号表达式。 以y ：掣为例，分析符号自动微分算法，并与自动微分进行比较。设 【而x 2 ) x i = l ，。2 = 2 。 普通的自动微分算法的计算图如图1 5 所示。 浙江大学硕士学位论文 图1 5 自动微分计算圉 其求导过程为： 立生：!一12十fln2)x4x2=1-21n2 3 x 42 、1 64 老7 1 拶1 + ( _ 2 ) x 4 x l 1 - 2 1 n 2 而符号自动微分算法下的计算图如图1 6 所示。 n i n ( x l x 2 ) ( x l x 2 ) 2 。滗l _ a ( x 。x 2 )务k j ) 2 l 石咫：，2 图1 6 符号自动微分计算图 ( 1 3 ) f 1 4 1 其求导过程为， 普2 志去氇+ - 瞒l n ( 划x 2 ) x 2 x 2x x 2 - 等笋 m ， 妾2 高去酗十掣x 2 x x 2 x x , - 等笋s ， 可以看到，符号自动微分的结果和符号微分法的计算流程是一致的，并且得 黎 1 浙江人学硕士学位沦文 到的在求导点五= 1 ，x 2 = 2 的数值结果是一样的，证明符号自动微分求导的l f 确 性。 而且这种符号自动微分生成导数表达式的过程是一次性的，优化计算可以反 复调用生成的导数表达式以求取所需的导数信息，这样就避免了像自动微分那样 重复求导的过程，极大地节省计算时间。 相对地，符号自动微分也有其不可避免的缺点。尤其对于复杂模型，生成导 数表达式的时间会非常长，生成的导数表达式非常冗长，而且对计算机存储空间 的要求也非常高。 为实现这种符号自动微分过程，李翔( 2 0 0 3 ) 基于自动微分工具a d m a t ，开 发了扩展的自动微分工具x a d m a t ( e x t e n d e d a d m a t ) 。 符号自动微分的实现基于两个条件：一是自动微分工具a d m a t ，- 2 是 m a t l a b 符号运算工具箱。为了实现符号微分和自动微分在计算流程上的“同 步”，需要对a d m a t 进行修改，使其在自动微分数值计算的同时添加符号计算， 以生成符号表达式，从而实现符号自动微分的功能，完成x a d m a t 的开发。 1 3 4 面向模块的混合自动微分 为更好地利用模型信息，李翔( 2 0 0 3 ) 提出面向模块的混合自动微分方法，将 模型分割成不同的模块，对每个模块采用最适合的求导算法，包括自动微分、符 号自动微分和差分法。再对各予模块之间进行连接，累积得到整个模型的导数信 息。 相对于传统的自动微分算法，面向模块的自动微分有三个优点：它可以更加 充分地利用模型的稀疏性；可以方便地把外部的导数计算模块纳入整个算法的框 架中来；可以为各个模块选择最好的求导算法。将这种面向模块的自动微分方法 按以下4 步应用于过程系统优化过程，以提高整个优化过程的效率( 李翔，2 0 0 3 ) ： 1 ) 将过程模型分解为一系列的子模块，并为每个子模块确定最佳的求导算 法。 2 ) 对于需要用符号自动微分求