『运筹OR帷幄』转载

作者：柚子优化

本文转载自公众号 柚子优化

编者按

Professor M.J.D. Powell, …, one whose contributions to the subject are unsurpassed.

——Roger Fletcher, Practical Methods of Optimisation, Ed.

数学家Michael James David Powell（1936.07.29-2015.04.19）是优化领域的奠基者之一。Powell生前是剑桥大学的教授。作为计算数学的先驱之一，他的主要研究方向为优化方法与理论、数值分析和逼近论。他获得过许多荣誉和称号。其中，在1982年，他获得了首届George B. Dantzig Prize，这个奖项被誉为优化领域的最高荣誉。这和Powell获得的伦敦数学会（LMS）的 Naylor Prize and Lectureship (1983) 以及 Senior Whitehead Prize (1999)、英国应用数学学会（IMA）的Catherine Richards Prize (2007) 等其他重量级奖项都有力地说明了他在计算数学领域的非凡影响力。他还是英国皇家学会会士、美国国家科学院外籍院士和澳大利亚科学院通讯院士。

图1：Powell照片

一、早期生活

1936年7月29日，Powell出生于英国伦敦。Powell 幼年时父亲William大多数时间都在服兵役，因而他的母亲Beatrice主要负责照顾Powell。Beatrice对Powell的教育很上心。七岁时，Powell 进入了Farnham 的Frensham Heights公学。那时候Powell 对数学的兴趣正值萌芽之际，他在家中常常通过数学游戏消磨时间。七年后，Powell转学到了Eastbourne学院，这是一所相对传统的公立学校。在Eastbourne，数学老师Paul Hirst发现了Powell在数学方面的天赋，并不断地鼓励和引导Powell。这是Powell 在日后从事数学研究和数学教育工作的源动力。多年以后回顾Powell在Eastbourne学院的这段时光，人们惊奇地发现，包括Powell在内的三位著名的数值分析领域的专家（另外两位分别是加州大学伯克利分校的Beresford Parlett和布拉德福德大学的Peter Graves-Morris）竟同时在此学习[1-3]。看来那段时间的Eastbourne学院，称得上是“数值分析的摇篮”了。

1956年，Powell在英国皇家炮兵部队完成服役后，获得了剑桥大学Peterhouse学院提供的奖学金。他在两年内完成了剑桥大学数学学部的本科学习，第三年完成了数值分析与计算的学位（Diploma）课程学习。在本科结业考试中，Powell因重感冒发挥失常，只得到了“优良”的成绩，这与他平时表现本应得的“优秀”差了一个等级。他因此受到了打击，毕业后没有继续从事学术工作，而是关注于工业界更为关心的数值计算方向。当然，这只是一种可能的原因。另一个可能的原因是Powell小时候得过脑炎，而有谣言说这种疾病的后遗症会使其大脑在十几岁时退化。然而，所谓的“退化的大脑”却在未来几十年内计算数学的史书上大放异彩，这铁的事实正是对那些可笑的谣言最好的回击。在剑桥大学求学期间，Powell和Caroline Henderson相识，并于1959年完婚，二人执手一生直至Powell去世。

二、优化工作

1959年至1976年，Powell在位于Harwell的英国原子能研究所的数值分析小组工作，他所在的部门是理论物理分部。他的工作是进行数值分析的基础研究、编写计算机程序，为研究所其他研究人员提供最有效的算法。著名的优化专家Roger Fletcher也曾在这个小组工作、与Powell共事过。

尽管Powell早期的工作主要关注原子物理和化学中的计算，他却阴差阳错地因为对优化领域奠基性的贡献而声名远扬。他不仅证明了许多重要的理论结果，而且对设计新的有效的数值方法以及用Fortran编程实现算法等都有深刻的见解。事实上，Powell一直保持着亲自编写、调试程序的习惯。他编写的程序数据结构精妙、几乎在程序的执行效率上达到极致。无怪后辈的优化学者称他写的Fortran优化程序是“宝藏”。国际著名数值计算软件库Harwell中关于优化和数值逼近方面的软件很多都是Powell 编写的，涉及的优化方法包括最小二乘、共轭梯度法、拟牛顿方法、逐步二次规划方法、无导数方法等。本文第五部分还将更详细地介绍Powell关于无导数方法软件的工作。

1950年代，彼时非线性优化主要关注于无约束优化问题，方法也局限于牛顿法和最速下降法。一些企业则对高度非线性的函数极值问题产生了浓厚的兴趣，这直接催生出了一些最初的无导数优化方法。在研究这类方法时，Powell提出了共轭方向的概念，后人称为Powell's method。这一思想启发了学者利用共轭方向的性质构造有效的算法，比如后来著名的共轭梯度法。他还研究了非线性最小二乘的数据拟合问题，包括无导数方法 [4-6] 和可用于高斯-牛顿法收敛性证明的折线步方法 (Dog leg method) [7,8]。Powell学术中最重要的贡献之一DFP拟牛顿方法是源于他1962年在利兹大学参加的一场学术会议。当时，他原计划报告无导数优化方法的相关内容，但临时改变主意，介绍了Bill Davidon在1959年提出的变尺度拟牛顿法。在会议上他与Roger Fletcher交流了彼此关于Davidon的工作的看法和最新进展，两人合作完成了一篇论文 [9]，从数学上整理了Davidon的工作，并在理论上加以完善。这项工作在当时大大提高了计算的效率。后人用三个人的首字母指代该工作，这便是第一个拟牛顿方法（DFP方法）的由来（图2是DFP三位作者的合影）。但是，论文的发表过程并非一帆风顺，而是首次投稿后遭到了拒稿。这段小插曲让这项开创性的工作显得更加弥足珍贵。或许，这段轶事也能够激励当前的研究者，被拒稿的工作未必不值一文，反而可能是沧海遗珠呢。

图2：从左到右依次为Davidon, Fletcher, Powell (DFP)

1969年，Powell又做出了一项对优化领域具有深远影响的理论工作。彼时求解约束优化问题通常是通过罚函数将约束函数罚到目标函数上，从而求解转化后的无约束优化问题。Powell在求解等式约束问题时发现，把约束函数做一定的平移，可以使罚函数更快速地求解。由于平移的思想与拉格朗日乘子联系紧密，该罚函数也可以看作是对问题的拉格朗日函数为目标函数的Courant罚函数形式，Powell提出的方法被人们称为增广拉格朗日罚函数方法。这一概念直至今日仍在福泽后人。我们目前熟知的交替迭代乘子法 (Alternating Directions Method of Multipliers , ADMM) 本质上就是运用交替迭代方法求解问题的增广拉格朗日罚函数。

1970年代，优化领域的研究热点转向非二次目标函数的无约束优化方法的理论性质。Powell依然是其中的领军人物。对于拟牛顿方法，他首先证明了DFP方法对于一致凸函数在精确线搜索框架下的收敛性结果 [13]，之后证明了BFGS方法对于凸函数在Wolfe线搜索框架下的收敛性。后者的结果后来又被推广到除了DFP方法外所有Broyden族方法。这些工作到目前为止仍然是拟牛顿方法最重要的收敛性结果。他的开创性的收敛性证明技巧令许多研究者叹为观止。此外，Powell还推导出了对称化的Broyden秩一公式，即PSB拟牛顿修正公式 [8]。除了证明收敛性结果，Powell还擅长针对数学命题举出反例。例如，他设计了一个精妙的反例，说明早期的交替方向法可能不收敛 [11]；他构造过反例说明共轭梯度法有可能失败[57]，他给出有趣的例子使得著名的内点算法在特殊情形下效率非常低[37]。

1976年，剑桥大学应用数学和理论物理系将Powell聘任为应用数值分析John Humphrey Plummer教授。重返剑桥大学，Powell已经成为国际优化界的引领者之一。

此后Powell的一项重要工作是针对逐步二次规划方法 (Sequential Quadratic Programming, SQP)。在SQP方法的收敛性理论分析和算法实现方面，Powell发表了几篇重量级的论文 [17,18]。该方法因此迅速成为国际优化领域的研究热点。逐步二次规划方法的根本想法是对约束优化问题的一阶最优性条件应用近似的牛顿法。在每步迭代过程中求解以拉格朗日函数的二阶近似展开为目标函数、以原约束的线性化近似为约束条件的二次规划问题。最妙的是，求解这个子问题不仅仅可以改进、更新原问题的解，还可以得到原问题拉格朗日乘子的近似值。在理论上，SQP方法也保持了牛顿法具有的局部快速收敛速度。Powell在SQP方法更新Hessian矩阵的问题上提出了部分更新、保持凸性的更新方式，使得子问题的求解效率大大提高。SQP方法的思想迄今为止仍是求解非线性约束优化问题的最根本思想。

之后Powell的工作主要集中在建立优化算法的收敛性理论和开发求解非线性问题的稳健、高效的无导数优化算法软件两方面。从1984年开始直至2015年他的最后一篇论文，Powell在信赖域方法的全局收敛性方面做出了一系列开疆拓土的工作 [25-29]。信赖域方法是独立于线搜索方法的优化算法框架，其主要思想是在局部近似求解复杂的非线性问题，克服了线搜索方法对于搜索方向和步长依赖不均的缺点，同时具有全局收敛性和局部的超线性收敛速度。在无导数优化算法方面，Powell基于信赖域算法框架，通过若干个点的函数值构造了多项式插值模型，不断改进在目标函数模型中构造Hessian矩阵的方法，从而提高算法效率。针对这个系列工作，他发表了关于运用无导数方法求解无约束、界约束和线性约束优化问题的多篇著名论文和报告[27,28,31-36]。基于这些算法，他还开发了一系列的相关软件，具体将在第五部分详细介绍。

尽管Powell一生从未写过一本优化领域的书籍，但他给后世留下了多篇综述文章[18,41-47]。这些文章为一代又一代的年轻学者开启了优化领域的大门。多年后再读他的文章，其中的丰富信息和深刻见解仍让人深受启发。

除了优化领域，Powell在逼近论方面也做出了很多影响深远的工作，特别是在一元和多元多项式样条逼近方面，包括提出了开创性的径向基函数概念（收敛性、快速算法、Krylov空间方法、薄板样条）、有理函数、l_1-逼近、最佳Chebyshev逼近和凸逼近等。

三、个人生活

1976年Powell被聘为剑桥大学应用数学与理论物理系的教授，他也考虑过在本科时所就读的Peterhouse学院兼任学院的院士，但可惜未如愿。不久后，一路之隔的Pembroke学院向他抛出了橄榄枝。Powell本人很喜欢Pembroke学院的友好氛围，午餐后在Pembroke的草坪上打滚球成为了他的一项生活日常。

在剑桥大学期间，Powell习惯于一个人在办公室推导公式或编写程序，他不喜欢与人应酬、谈论家常。但他办公室的大门永远为他的学生、访问学者、博士后等来与他讨论科研问题的人敞开。他永远会耐心地与学生们讨论问题、批阅学生的文章。这些Powell课题组内的成员也常常造访他家，在每个节日，他们都作为Powell家庭的编外成员出席。作为导师和合作者，Powell培养出了很多优秀科研人才，例如优化领域的领军式人物Phillip Toint、袁亚湘都曾访问他或师出他的门下，逼近论领域的专家Martin Buhmann也是Powell的座下弟子。有趣的是，尽管Powell培养出了不少博士生，他本人却没有博士学位。直到1979年，剑桥大学授予了他一个理学荣誉博士学位，以表彰他的杰出工作。

Powell不喜欢做行政事务和与科研无关的琐事，但他却花费大量时间和精力创办了学术期刊《IMA Journal of Numerical Analysis》。他接受论文的唯一标准是质量和相关性，这也使《IMA Journal of Numerical Analysis》在短时间内成为国际数值分析领域的重要期刊之一。

中国有古语“天将降大任于斯人也，必先苦其心志”。这句话用在Powell身上也不为过。1983年7月，Powell的儿子David于法国骑摩托车旅行时在一场车祸中丧生。白发人送黑发人，Powell度过了一段痛苦、煎熬的时光。为了纪念生前在巴斯大学数学系读书的儿子，Powell在巴斯大学设立了数值分析学生奖。

Powell个人喜好体育运动，其中曲棍球是他的心头好。他年轻时是剑桥大学曲棍球队的队员。他还曾参加过夜间驾驶拉力赛，桥牌亦是他消磨时间的好方式。后来Powell迷上了打高尔夫球，2005年他还成为了所在的高尔夫俱乐部球队队长。Powell也很喜欢登山，几乎每年都要带着课题组的学生远足、爬山。

2014年，Powell被查出患有食道癌。他没有接收化疗等治疗，而是选择保持清醒的头脑整理自己的论文、程序等资料。2015年4月19日清晨，Powell悄然去世了，优化领域的一代巨星陨落。

四、与中国的联系

Powell 与中国数学界有千丝万缕的联系。中国改革开放之后，在70年代后期我国学术界逐步恢复与国际同行的联系。作为中科院和英国皇家学会的交流项目，华罗庚要去剑桥大学访问，出面邀请他的正是Powell。华罗庚在推广优选法期间写的小册子《优选学》还引用了Powell 关于DFP方法的文章 [9]。1982年3月，Powell应华罗庚和冯康的联合邀请访问了北京、西安等地，并在中科院计算中心、中科院应用数学所、西安交通大学等学校讲学交流。这次访华，Powell不仅把当时国际最前端的优化方法和技术（如逐步二次规划方法、信赖域等）介绍给国内优化界，还亲自面试了当时冯康的硕士生袁亚湘、并同意其跟随自己到剑桥大学攻读博士学位。袁亚湘博士毕业后回国工作，也把最新的优化研究方法带回了国，为国内优化领域的发展带来了新的生机。

80年代初，西安交通大学的葛人溥教授曾作为访问学者到剑桥大学访问Powell。1983年，两人在期刊Mathematical Programming上发表过关于拟牛顿矩阵收敛性结果分析的合作工作[55]。这也是我国大陆学者在该著名刊物上发表的最早的文章之一。中科院计算中心王慧娟和戴彧虹、上海交通大学范金燕也先后作为访问学者访问过Powell。从1982年开始，Powell 多次来中国参加学术会议和作学术报告。他1996年、2006年先后参加了在北京举行的庆祝他60周岁和70周岁的国际学术会议，2003年、2011年先后在桂林和厦门参加了第4届和第8届国际数值优化与数值代数会议。2011年退休之后，Powell每年都到香港城市大学短期访问工作几个月。

可以说，Powell与中国优化领域的关系源远流长。2016年，Powell去世后的第二年，他的学生袁亚湘还在北京举办了一场纪念Powell诞辰80周年的国际学术会议。Powell去世后，他编写的无导数优化求解器一直由袁亚湘的学生张在坤的团队维护。

图3：Powell与中国学生袁亚湘及其部分徒子、徒孙合影

五、无导数优化软件

在第二部分“优化工作”中我们曾提到，无导数优化算法是 Powell 始终关注的一个课题。他在 1964年提出的共轭方向法就是一个无导数算法。这是 Powell 在优化领域发表的第二项工作 (第一项是 1963 年发表的 DFP算法)，也是引用量第二的工作 (第一也是 DFP 算法)。20 世纪 80 年代，Powell向国际数学及统计程序库 (IMSL) 提供了 TOLMIN算法；这个算法需要目标函数的导数，但 IMSL 的用户并不希望计算导数，因此 IMSL调用TOLMIN时首先用有限差分逼近了导数。这显然违背了Powell的本意，也成为他进一步研究无导数算法的重要原因之一[56]。

与此同时，Westland Helicopters公司请Powell帮其解决一个四维的约束优化问题，Powell因此构造了COBYLA 算法，并于1994年发表[32]。该算法用线性函数插值逼近目标函数和约束函数，不需要任何导数信息即可求解一般的非线性约束问题。但线性模型的逼近精度较低，Powell此后把注意力转向了使用二次插值模型的无导数算法，先后设计了UOBYQA (2002，无约束问题)，NEWUOA(2006，无约束问题)，BOBYQA (2009，界约束问题)，LINCOA (2013，线性约束问题)等一系列无导数算法。可以想象，假若 Powell仍在世，他下一步的工作很有可能是基于二次插值模型求解一般非线性约束问题的无导数算法。可惜这一切在2015年戛然而止，只能成为永远的遗憾。

不过，Powell的四个基于二次模型的算法加上基于线性模型的COBYLA正好涵盖了所有类型的非线性优化问题。而且，Powell对这五个算法都编写了极为细致的代码，给我们留下了五个堪称艺术品的无导数优化求解器。它们一直是无导数优化领域公认的算法标杆，在科学工程领域有广泛应用。只不过，Powell 编写这些求解器用的是Fortran语言（Fortran 77）。而目前算法的研究和实践更多基于较易用的MATLAB、Python、Julia、R等语言。香港理工大学的张在坤和他的学生Tom M. Ragonneau编写的PDFO (Powell's Derivative-Free Optimization solvers，) 软件致力于为Powell的无导数优化求解器提供跨平台的调用接口。使用 PDFO 目前的版本，Linux/Mac/Windows用户可在MATLAB和Python直接调用Powell的无导数优化求解器。

参考文献

[1] M. D. Buhmann, R. Fletcher, A. Iserles, and Ph. L. Toint. Michael James David Powell. 29 July 1936–19 April 2015. Biographical Memoirs of Fellows of the Royal Society, volume 64, pages 341-366, 2018.

[2] An Interview with M. J. D. Powell by Luís Nunes Vicente,