（运筹学与控制论专业论文）无约束最优化问题的一类非精确牛顿法.pdf

摘要 随着科学技术的发展，非线性最优化方法在科学计算和工程分析中起着越来越 重要的作用，它们的实现大多依赖目标函数的一阶或高阶导数及其相关项( 如雅可 比矩阵与向量的乘积等) 的计算。自动微分是计算这些导数项的有效工具，与传统 微分方法相比具有计算成本低和计算精度高的优点。本文介绍了一类非精确牛顿法 以及与自动微分结合的改进的非精确牛顿法的一系列研究成果，建立了它的全局收 敛算法，并从理论上证明了全局收敛性。本文进一步讨论了在自动微分方法基础上 的结构的非精确牛顿算法，并在效率上与改进的非精确牛顿法作了对比分析。本文 还对非精确牛顿法的应用及数值实现做了初步的探讨。 关键词：非线性最优化；非精确牛顿法；自动微分；正向模式；反向模式 北京工业大学理学硕士学位论文 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h es c i e n t i f i ct e c h n o l o g y , n o n l i n e a ro p t i m i z a i t i o nm e t h o d p l a y sam o r ea n dm o r ei m p o r t a n tr o l ei ns c i e n t i f i cc o m p u t a t i o n sa n de n g i n e e r i n ga n a l y s i s f i e l d t h e i ri m p l e m e n t sm o s t l yd e p e n do nd e r i v a t i v e s ( e g g r a d i e n to rh e s s i a n ，a sw e l l a so t h e rm a t r i x - v e c t o rf o r m s ) i nd i f f e r e n tw a y s a u t o m a t i cd i f f e r e n t i a t i o ni sa ne f f i c i e n t t o o lt oc a l c u l a t et h ed i f f e r e n t i a t i o n s i th a st h ea d v a n t a g e so fl o wc o s ta n dh i g ha c c u r a c y c o m p a r e dw i t ht h et r a d i t i o n a ld i f f e r e n t i a t i o nm e t h o d s i nt h i sp a p e r , w ei n t r o d u c et h er e s u i to fa ni n e x a c tn e w t o nm e t h o dw i t ha u t o m a t i cd i f f e r e n t i a t i o n ，e s t a b l i s ha n dp r o v et h e g l o b a lc o n v e r g e n c e t h e nw ei n t r o d u c et h es t r u c t u r e di n e x a c tn e w t o nm e t h o dw i t ha u t o m a t i cd i f f e r e n t i a t i o n ，a n dc o m p a r ei tw i t ht h ei m p r o v e di n e x a c tn e w t o nm e t h o di nt e r m s o ft h e i re f f i c i e n c y l a t e r , w em a k ead i s c u s s i o no nt h ei m p l e m e n t so fi n e x a c tn e w t o n m e t h o da n dn u m e r i c a le x p e r i m e n t s k e y w o r d s ：n o n l i n e a ro p t i m i z a t i o n ；i n e x a c tn e w t o nm e t h o d ；a u t o m a t i cd i f f e r e n t i a t i o n ；f o r w a r dm o d e ；r e v e r s em o d e i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 签名：玉羞日期：边遂：【：墨2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即；学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：韭导师签名：必塑丛啉 第1 章前言 1 1 历史背景 第l 章前言 非线性最优化方法在科学计算和工程分析中起着越来越重要的作用。因 而是科研人员和工程技术人员的关注热点牛顿法是解决非线性最优化中最 有效的算法之一。它的基本思想是利用目标函数的二次泰勒展开，并将其极 小化 考虑无约束优化问题 r a i n ，( z ) ， z 彤，( 1 - 1 ) 其中f ：舻_ r 为二次可微实函数，x k 舻，h e s s e 矩阵v 2 f ( x k ) 正定。我们 在z 七附近用二次泰勒展开近似， 1 f ( x 七+ t ) q ( 七( t ) 一，( 茁七) + v f ( x k ) r t + 去t t v 2 ，( z 七) t ， ( 1 2 ) 其中t = z z 七，g ( 七) ( s ) 为，( z ) 的二次近似。将上式右边极小化，便得 z 岛+ 1 = x k 一【v 2 j p ( z 七) 】一1 v ，( z 七) ，( 1 3 ) 这就是牛顿法迭代公式对于正定二次函数，牛顿法一步即可达到最优解。对 于非二次函数，牛顿法并不能保证经有限次迭代求得最优解，但由于目标函 数在极小点附近近似于二次函数，故当初始点靠近极小点时，牛顿法的收敛 速度一般是很快的，因此这种方法得到了很多人的认可与利用牛顿法中最 主要的工作就是求解牛顿方程。但是，如果精确求解牛顿方程，那么在每一次 迭代中所需的计算量较大，尤其对于维数很大的问题。因此，人们开始考虑用 不精确的方法来求解牛顿方程，即：非精确牛顿法t o i n t 和s t e i h a u g 分别在 1 9 8 1 年和1 9 8 3 年提出了牛顿共轭梯度法 1 2 ，即牛顿方程用共轭梯度法来近 似求解。这样不仅可以求得允许误差范围内的最优解，而且能节省计算量 北京工业大学理学硕士学位论文 之后，人们已经将它发展成为内容十分丰富的使用条件预优共轭梯度技术的 非精确牛顿类算法( n e w t o n p c g 算法) 。大量的数值试验结果表明，它是求解 大型优化问题的最有效方法之一。虽然如此，直到邓乃扬、王兆智1 9 9 8 年的 工作 3 才首次从理论上论证了这类算法与牛顿法相比的有效性，后被英国著 名优化专家d i x o n 称为“邓一王定理” 4 】。随着大量相关研究成果的发表，关 于n e w t o n p c g 类算法的研究越来越深入2 0 0 5 年，邓乃扬、薛毅等利用效率 分析导出了一类新的非精确牛顿法 5 】，使非精确牛顿法的研究更进了一步。 与大多数最优化方法密切相关的是计算函数的一阶乃至高阶导数。目前， 主要有四种不同的计算导数的方法：手写代码、除式微分、符号微分以及自动 微分( 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 ) 具有代码简练、计算精度高及投入人力少等优点。如果我们直接编写导数代 码，这不仅费时，而且极易出错，当问题的规模非常巨大时，单靠人力几乎 是不可能完成的除式微分可以用差商来近似导数，但求解函数的梯度时相 对于计算函数本身具有极高的计算复杂性( 其计算代价依赖于独立变量的数 目) ，而且由于受机器有效精度的限制不可避免的存在截断误差。符号微分一 般基于一些成熟的数学通用软件，如m a t h e m a t i c a , m a p l e ，r e d u c e 等，来准确求 得复杂表达式或函数的导数，但对具有数据相关性的复杂对象模式来说，则 具有很大的局限性。自动微分基于原模式代码依赖机器自动生成数值函数的 导数或微分代码，通过整体分析对象模式的结构特征和数据相关性，通过可 以得到一个合理的与问题本身规模无关的计算时间和空间存储代价。同时， 自动微分针对程序代码分析地求解数值函数的导数，因而它的一个突出优点 是无截断误差，可以准确到机器精度另外，基于自动微分得到的微分模式代 码在变分资料同化、最优化方法、奇异向量与奇异值问题、系统参数辨识、 多学科综合设计以及敏感性分析等领域中有着非常广泛和成功的应用 3 7 】 自动微分方法讨论如何以合理的代价分析地求解数值函数的梯度、j a c o b i 矩阵、更高阶导数和微分，以及多种矩阵一向量乘积形式的微分模式。其基 一2 一 本出发点是：任何程序意义的数值模式，无论多么复杂，总可以分解为一系 列有序的有限数目的基本函数( 如s q r t , s i n ，c o s ，l o g 等) 和基本运算操作( 如加、 减、乘、除、乘方等) 的运算复合。按照链式法则，可以形式地对程序代码做 微分线性化处理，从而达到对整个模式对象做微分处理的目的通常，用来 计算函数的导数有两种不同的基本模式，即正向模式( f o r w o r d m o d e ) 和反向模 式( r e v e r s em o d e ) 正向模式就是按照程序运行的自然顺序自上而下地计算函 数的梯度。而反向模式则是按照与程序运行相反的顺序自下而上地计算函数 的梯度。作为计算科学领域的一个独立分支，目前自动微分研究包括：稀疏 j a c o b i 矩阵及稀疏h e s s e 矩阵，高阶导数求解，奇异微分，并行计算微分，隐式 方程求解，微分代码的评价和优化等系列问题 6 7 。 在实践中，自动微分在许多领域有着极其广泛的应用。数学物理应用中的许多 数值模拟问题都与非线性最优化方法有关，或者最终可以归结为一个非线性最优化 问题来求解运用自动微分方法得到的微分模式代码，通常以合理的代价求解目标 函数的梯度和h e s s e 矩阵，以及向量值函数的雅可比矩阵和各种形式的方向导数。 这些问题包括：系统参数辨识、变分资料同化、多学科最优设计、模式的可预测性 分析等，关于这方面的文献有很多，如 8 1o 】等 自动微分方法最早是由w e n g e r t , r e ( 1 9 6 4 ) 、b e d a , l m ( 1 9 5 9 ) 等人正式提 出，不过那时人们一般普遍认为分析求解函数的导数具有极高的计算代价。随后， l i n n a i n m a ，s ( 1 9 7 0 ) 、w a e n e r , d d ( 1 9 7 5 ) 、k e d e mg ( 1 9 8 0 ) 、b a u r , w ( 1 9 8 2 ) 、 f i s c h e r , h ( 1 9 8 7 ) 等人先后在求解j a c o b i 矩阵的稀疏结构，正向和反向模式的最小 代价实现、导数求解的计算复杂性，以及求解h e s s e 矩阵等方面做过许多重要的工 作直到八十年代，随着计算机技术与软件技术的飞速发展和自动微分基本理论 和方法的逐渐成熟，r a i l ，l b ( 1 9 8 1 ) 、g r i e w a n k , a ( 1 9 8 9 ) 、b i s c h o f , c ( 1 9 9 1 ) 和 c h r i s t i a n s o n ，b ( 2 0 0 0 ) 等人在a d 基本方法、高阶导数分析求解，特别是揭示计算 导数的真实计算代价方面做了系统的工作，并得到极为广泛的应用。在这方面比较 有代表性的文献有 11 1 4 。u w en a u m a n n ( 1 9 9 9 ) 在他最近完成的博士论文 15 】中 一3 一 北京工业大学理学硕士学位论文 用计算图分析方法系统地讨论了基于非增量积分法的导数计算，并提到了基于节点 消去法来寻找最优消去次序等价于一个n p 难解问题。g r i e w a n k ，a ( 2 0 0 0 ) 在他最 近出版的著作e v a l u a t i n gd e r i v a t i v e s 一书中【1 6 ，对目前a d 研究的基本现状以及 a d 基本理论框架结构做了一个非常好的概括和论述。为今后a d 的发展方向及应 用前景提供了大量非常有价值的想法和文献资料，这标志着a d 已经成为一门独立 学科分支，其主要参考文献见【17 1 9 】。 自动微分可以很好地应用于改进最优化算法，文献 2 0 将自动微分应用于改进 5 中提出的新的非精确牛顿法，其基本结论是：包括函数及其导数的计算量在内， 改进的n e w t o n 。p c g 算法与牛顿法的效率比随问题规模的增大而无限增大。而在此 之前的比较结果是：当函数及其导数计算量很小时，会有相应的结论，反之，随问 题规模的增大改进效果越来越不明显。 目前，这类非精确牛顿法的研究一直在局部收敛算法方面，需要建立和研究它 的全局收敛算法；另外，已有的研究是针对一般的最优化问题，而对于特殊结构如 具有某种稀疏结构的最优化问题，如果使用一般的方法求解显然是不经济的，需要 研究针对特殊结构的更加高效的非精确牛顿算法；还有，应该将这类非精确牛顿法 应用到其它理论或实际问题中。 1 2 本文工作概述 本文第二章的内容是自动微分方法及其实现。第三章介绍了有关非精确牛顿法的 研究进展，并建立和研究了它的全局收敛算法。第四章结合自动微分技术讨论了改 进的非精确牛顿算法，并且用具体实例验证了该算法在实际应用中的可行性与优越 性。第五章具体讨论了使用自动微分的结构非精确牛顿法，并在效率上与改进的非 精确牛顿法作了对比，并用数值例子进行了验证最后本文作了总结和展望。 一4 一 第2 章自动微分算法及其实现 第2 章自动微分算法及其实现 2 1 自动微分( a d ) 的两种基本形式 自动微分方法讨论如何以合理的代价分析地求解数值函数的梯度、雅可比矩 阵、更高阶导数和微分，以及多种矩阵一向量乘积形式的微分模式。其基本出发点 是：任何程序意义的数值模式，无论多么复杂，总可以分解为一系列有序的有限数 目的基本函数和基本运算操作的运算复合。按照链式求导法则，可以形式地对程序 代码做微分线性化处理，从而达到对整个模式对象做微分处理的目的。 自动微分方法基于不同的数值需要依赖机器自动形式化地对程序模式代码做一 阶或高阶微分线性化处理。其处理的对象通常是一组具有数据相关性的数值程序模 式，或单个独立子过程或函数，也可以是单个的数值表达式、程序语句、或程序段。 自动微分主要基于这样的思路实现：一个相对独立的程序对象、数值模式、独立子 过程或函数，按照其输入输出关系可被视为一个分段可微的算子，而该算子又可以 按不同粒度、过程或函数划分为一系列最小算子的有序复合重复使用链式求导法 则，可以形式地对程序对象做一阶或高阶微分线性化处理 自动微分包括正向和反向两种基本模式。对于一个给定数值模式，如果我们从 独立变量到中间变量按照程序执行的自然路径求导，就得到正向模式；相反地，如 果我们从依赖变量到中间变量按照与程序执行相反的计算路径反向求导，就得到反 向模式通过正向模式和反向模式来计算雅可比矩阵具有不同的计算代价，当依赖 变量的数目小于独立变量的数目时，运用反向模式往往可以得到较小的计算时间代 价；而当独立变量的数目小于依赖变量的数目时，运用正向模式往往可以得到较小 的计算时间和空间存储代价。 自动微分发展的另一个方面是大量自动微分工具的出现d a v i dj u e d e s 对早期 的微分工具进行了恰当的分类，近年来比较有代表性的系统包括o d y s s e e 系统、 a d i c a d i f o r 系统、t a m c 系统、a d o l c a d o l f 系统和自动微分转换( d f t ) 系统它们分别在处理的程序对象、处理问题的方式和方法、处理问题的要求、并 5 北京工业大学理学硕士学位论文 行及向量支持以及其它有效降低自动微分代价的方法特色等方面而略有差异。这里 提到的许多有效的自动微分算法，如并行实现、结构化、算子重载等，对于降低不 同问题的梯度及方向导数的计算代价有着非常重要的意义 下面我们以求解j a c o b i 矩阵为例来具体说明正向模式和反向模式的实现形式。 对于如下的数值模式 y = f ( x ) ， 其中y 尼”为函数变量集，x r “为自变量集。除有限点外，f 具有一阶连续 导数。 那么求解原函数f ( x ) 的顺序执行的w e n g e r t 表为： t k = x k ，l 尼礼 t k = 妒凫一。( 乃) ， 仡+ 1 七n + p ，入 - 岛 k = 7 k + p 一。+ 南， 1 尼竹1 其中p 为中间变量的个数。 求解j a c o b i 矩阵的正向模式的基本结构为： v t k = v x k ，1 七n v 死2 等v 死n + l 0 ，使得f ( x ) 在水平集l ( z o ) = j zi ，( z ) ，( z o ) ) 上满足 u 丁v 2 ，( z ) u m0u1 1 2 ，v u 彤，z l ( z o ) ， ( 3 8 ) 一1 2 第3 章一类非精确牛顿法及其全局收敛性 假设序列钏v ，( z ) 吣一致小于1 ，则在精确一维搜索下，带步长因子的非精确牛顿 算法( g i n a ) 产生的迭代点列 z 七) 满足： ( 1 ) 当 矿】- 为有穷点列时，对某个k 有v f ( z ) = 0 ( 2 ) 当( 扩) 为无穷点列时， z k ) 收敛到，的唯一极小点z + 证明：( 1 ) 当 z 。 为有穷点列时，由算法的终止性条件可知，其最后一个z + 满足 v ，( 矿) = 0 ，故z + 为，的驻点。 ( 2 ) 当( 扩) 为无穷点列时，则有v f ( x 七) 0 ，但由( 3 - 8 ) 知f ( x ) 为舻上的 严格凸函数，从而其平稳点为总体极小点，且是唯一的。 首先，当执行c f 求解时，由于8 南= 一i v 2 f ( x 七) 】- 1 v f ( x 七) ，故 v f ( m 七) t 8 七= 一v ，( ) t v 2 i ( z 七) 】- 1 v f ( z 七) 0 故8 为下降方向，我们把直接求得的迭代点记作z 乞，由f ( x ) 单调下降可知 z 乞) c g ( x o ) ，且v 2 f ( x k d ) 正定。 接着，根据p c g 方法求得的下降方向s 抖1 为： s 七十1 = 一w 一1 v f ( x 七十1 ) + w 一17 七十1 ，i i r 七十1i l i i v f ( x 七十1 ) 1 1 2 + ， ( 3 9 ) 其中彬= v 2 ，( z 岛) ，e ( 0 ，i 2 p + 1 ) 又因为 v f ( x 七+ 1 ) t s 七+ 1 一v f ( x 七+ 1 ) t w 一1 v f ( x 七+ 1 ) ( 1 一l i v f ( m 惫+ 1 ) 1 1 1 + ) ， ( 3 1 0 ) 根据假设序列 ij v f ( x 知) 吣一致小于1 ，得知 v f ( x 十1 ) t 8 七十1 0 ， ( 3 1 1 ) 从而s 忌+ 1 是下降方向，我们把间接求得的迭代点记作z ；“ 因此，( z ；+ p ) ，( z ；+ 1 ) ，( z 岛) 故知i 不论是执行c f 步，还是p c g 步，f ( x 七) 是单调下降序列， 扩) cg ( x o ) ， 所以 扩) 是有界点列，必有极限点。 1 3 北京工业大学理学硕士学位论文 设是 的极限点，则存在子列 z 。) 所收敛到z + ，这里k 1 是子序列的 指标集。由于 扩 k ac 舻】- ，故- 厂( 茁) k ，c ，( z ) ，从而由厂的连续性可知，对于 k 1 ( 1 ，有 f ( x + ) = ( 2 i r a ) = 。h m ，( z ) = ，+ ( 3 - 1 2 ) 类似地， 扩“ 也是有界点列，故存在子列 z 七) 。收敛到孟+ ，这里是 一十1 ) 的子序列的指标集，并且 于是， 厂( 牙+ ) = f ( 1 i mz + 1 ) = h m ，( z 缸 1 ) = 厂+ ( 3 1 3 ) n u 0尤+ ，( 牙+ ) = f ( x + ) = f + ( 3 1 4 ) 现在用反证法证明v f ( x + ) = 0 假定v f ( x + ) 0 ，则存在入，有 f ( x + + 入s + ) 0 故对于k 鲍，令k _ ，可得 ，( 孟+ ) ( z + + a s + ) 0 ，使得f ( x ) 在水平集l ( x o ) = zf ( x ) f ( x o ) ) 上满足( 3 8 ) ，又 假设序列 l l v f ( x ) 吣一致小于1 ，则在强w o l f e 非精确一维搜索下，带步长因子的 g i n a 算法产生的迭代点列 扩) 满足： ( 1 ) 当 z 2 ) 为有穷点列时，对某个k 有v f ( x 七) 一0 ( 2 ) 当 扩】i 为无穷点列时， 护】i 收敛到，的唯一极小点z 。 证明：( 1 ) 当 矿) 为有穷点列时，由算法的终止性条件可知，其最后一个z + 满足 v f ( x ) = 0 ，故z + 为，的驻点。 ( 2 ) 当 扩 - 为无穷点列时，则有v f ( x 七) 0 ，但由( 3 8 ) 知，( z ) 为研上的 严格凸函数，从而其平稳点为总体极小点，且是唯一的。 首先，当执行c f 求解时，由于s = 一 v 2 ，( 矿) - 1 v 厂( 扩) ，故 v f ( x k ) t 8 七= 一v f ( x 南) t 【v 2 f ( x 南) 1 1 v f ( x ) 0 故s 惫为下降方向，我们把直接求得的迭代点记作z 岛，由，( z ) 单调下降可知 z 各) c l ( x o ) ，且v 2 f ( z 5 ) 正定。 接着，根据p c g 方法求得的下降方向s 抖1 为： s 七+ 1 = 一w 一1 w f ( x 南+ 1 ) + w 一1 r 七+ 1 ，i i r 知+ 10 i i v f ( x 七+ 1 ) 1 1 2 机， ( 3 1 6 ) 其中= v 2 ，( z 岛) ，e ( 0 ，1 2 p + 1 ) y - n 为 v f ( z 知+ 1 ) t s 七十1 一v ，( z 七+ 1 ) t w 一1 v f ( x + 1 ) ( 1 一i v f ( x 惫+ 1 ) 1 1 1 + ) ，( 3 - 1 7 ) 根据假设序列 l l v f ( x 南) 吣一致小于1 ，得知 v f ( z 2 + 1 ) t s 抖1 0 ， 从而s k + 1 是下降方向，我们把间接求得的迭代点记作z ；+ 1 。 1 5 ( 3 - 1 8 ) 北京工业大学理学硕士学位论文 因此， 厂( z ；+ p ) ，( z ；十1 ) 厂( z 乞) 。 故知，不论是执行c f 步，还是p c g 步，厂( ) 是单调下降序列， z 】cl ( 扩) ， 所以 z 七) 是有界点列，必有极限点。 设z + 是 z 七) 的极限点，则存在子列 矿) 硒收敛到矿，这里k l 是子序列的 指标集。由于 z 七) ，cx 凫) ，故f ( x 2 ) 耳，cf ( x 豇) ，从而由厂的连续性可知，对于 k k 1 ，有 ，( z + ) = f ( 1 i mx 2 ) = l i m _ 厂( z 七) = 厂+ ( 3 - 1 9 ) - - - - - o o- - - * o o 类似地，( z 1 】也是有界点列，故存在子列 z k k 。收敛到牙4 ，这里是 z 七+ 1 ) 的子序列的指标集，并且 f ( x 4 ) = ，( 1 i m 扩“) = l i r af ( x 南+ 1 ) = 厂+ ( 3 2 0 ) 拧o o h 一。o 于是， ，( 孟+ ) = ，( z + ) = ，+ ( 3 2 1 ) 现在用反证法证明v 厂( z + ) = 0 假定v f ( x + ) 0 ，则存在入，有 ，( z + + a s + ) f ( x + ) + p v f ( x + ) s + ，( 3 2 2 ) 因为 v f ( x + 1 s + 0 所以，我们有 ，( z + + 入s + ) ，( z + ) ， 和 f ( x 七+ 1 ) = ，( z 七+ 入2 s 南) 故当k 鲍，我们令k _ 。，有 f ( x + ) 一，( z + + 入七s + ) ，( z + ) ，( 3 2 3 ) 这与( 3 - 2 1 ) 矛盾，这证明了v f ( z + ) = 0 ，即z + 是，的驻点 口 1 6 第3 章 一类非精确牛顿法及其全局收敛性 3 3非精确牛顿法全局收敛性的进一步研究 最近，关于非精确牛顿法又有一些新的研究成果，见 2 1 ，下面我们做简单介绍 3 3 1 非单调全局策略的非精确牛顿法 我们选择r ( 0 ，1 ) ，盯( 0 ，1 一叩) ，0 口m 伽 p 僦嚣 1 一a a l l v f ( m 七) i i + 纵时， 步4 1 计算 伽【曲咖入，口m 入】， 步4 2 令入= a 能伽和z 8 懈= 扩+ a s 七 步5 令入知= 入；z 七十1 = 。七+ a k s 七；七= k + 1 3 3 2 非单调全局策略非精确牛顿法的全局收敛性 定理4 ：假设 扩 是由算法2 产生的序列；l i m k 。o oi i v f ( x 七) i l 一 盯 第4 章基于自动微分的改进的非精确牛顿法 第1 步终止试验：利用自动微分算法的第1 ，2 步计算v f ( x ) 如果v f ( x ) = 0 ， 置若x + = x 七。 第2 步转换试验：若k 能被p + 1 整除，转第3 步，否则，转第4 步。 第3 步精确牛顿步( c f ) ： 解牛顿方程：利用自动微分算法计算v 2 ，( z ) ，置 b 七= v 2 ，( z ) ， 利用c h o l e s k y 分解v 2 ，( z “) = l k d k l t 求得牛顿方程( 4 3 ) 的解s 七，置m = 0 转第 5 步 第4 步非精确牛顿步( p c g ) ：对牛顿方程求近似解s 七： 置b 七= b 南，m = m + 1 ，m = b 七，利用算法p c g ( m ，v f ( x ) ，k ，l + f m 2 ”) 求得 第5 步置z 七十1 = 扩+ 8 ，k = k + 1 ，转第一步 文献 2 0 中对使用自动微分的非精确牛顿法与未使用自动微分的非精确牛顿 法在效率上进行了细致的分析，并用大量的数值试验验证了该算法的优越性下面 我们用初等的数值试验对使用自动微分的非精确牛顿法与使用自动微分的精确牛顿 法在实际问题中作了对比。 4 3 使用自动微分的改进非精确牛顿法应用举例 支持向量机中的分类算法可以解决许多实际问题，如文本分类、图像处理等 2 3 - 2 5 ，下面我们将自动微分技术与分类算法结合在一起，建立并研究使用自动微分 的分类算法，然后，用数值试验验证了非精确牛顿法优于精确牛顿法的理论分析 用数学的语言可以把分类问题描述如下 根据给定的训练集t = 【( z 1 ，1 ) ，( 勋，们) ) ( x y ) ，其中x i xc 彤，y i y = 1 ，一1 ) ，i = 1 ，z ，寻找x 舻上的实值函数g ( z ) ，以便用决策函数 2 1 北京工业大学理学硕士学位论文 ，( z ) = s i g n ( 9 ( z ) ) ，推断任一模式z 相对应的y 值求解分类问题，实质上就是找到一 个超平面把钟上的点分成两部分。 当g ( x ) 为线性函数g ( x ) = ( w z ) + b ，其中( 术木) 表示内积计算，w 舻，由 决策函数f ( x ) = s i g n ( g ( x ) ) 确定分类准则时，称这种方法为线性支持向量分类机。 对于训练集t = ( z 1 ，y 1 ) ，( 钆，犰) ) ( x y ) ，其中x i xc 册，玑 y = 1 ，1 ) ，i = 1 ，z ，若存在b r 和正数，使得对所有使y i = 1 的下标i 有 ( w x i ) + b ，而对于所有使y i = - 1 的下标i 有( w 皿) + b 一，则称训练集t 线性可分，同时我们也称相应的分类问题是线性可分的。 对于这种线性可分的问题，一般采用最大间隔法来求解。 1 ) 设已知训练集t = ( z 1 y l ，) ，( 靓，们) ) ( x y ) ，其中兢xc 础，y i y = l ，一1 ) ，i = 1 ，e ； 2 ) 构造并求解对变量w 和b 的最优化问题 m i n i n 。言 ( 4 8 ) 。石l l 训旷， 一一萏) s t y i ( ( w 鼢) + b ) 1 ，i = 1 ，f 求得最优解w + ，b + ； 3 ) 构造分划超平面( w + - z ) + 扩= 0 ，由此求得决策函数f ( x ) = s i g n ( ( w + - z ) 十6 + ) 若训练集丁是线性可分的，则最大间隔法求出的分划超平面唯一，且此分划超 平面能将训练集中的两类点完全正确的分开 4 0 一般来说，训练集并不是严格可分的，当训练集线性不可分时，任何分划超平 面必有错划，因此我们引入一个惩罚参数c 0 ，引入松弛向量e = ( 1 ，e 2 ，旬) t ( 可以构造出描述训练集被错划的程度) ，对于上述训练集，我们把z 个点对应的 x i xcr “写成一个f n 维的矩阵a ，把2 个点对应的y i y = 1 ，一1 】| 写成 一个对角矩阵d ( 其中对角元为1 或一1 ) ，则支持向量机问题表示如下 2 3 】 ， m i n 三矿w + c e t e ， ( 4 9 ) ( ，b ，e ) e r n + l + r n2 。 、 2 2 第4 章 基于自动微分的改进的非精确牛顿法 s t d ( a w e b ) + g e ， 0 经变形，求解原始问题等价于求解如下严格凸二次规划问题 (m黪。(叫tw+bb 22 ) + 壶c t ， ( 叫，e ) r n + 1 + m 、 2 s t d ( a w e 6 ) + e e ， 0 可知问题关于的解应满足 = ( e d ( a w e 6 ) ) + ( 4 - 1 0 ) ( 4 - 1 1 ) 其中( ) + 是单变量函数( ) + = m a x ( o ，z x 把( 4 - 11 ) 代入( 4 1 0 ) 中，就得到无约束最优化问题 骢壶( 矿w + b 2 ) + 扫i ( e d ( a w e 6 ) ) + ) 睡( 4 - 1 2 ) 上述问题是严格凸的无约束最优化问题，它有唯一的最优解，但函数( ) + 是不可微 ( 非光滑) 的，故要建立一个与非光滑无约束问题近似的光滑无约束问题，为此，我 们引入非光滑函数( ) + 的近似函数 p ( x ，a ) = z + 言1 n ( 1 - t - e 一) ( 4 1 3 ) 其中a 0 是参数，显然p 是光滑的，而且当a _ 。时，函数p ( x ，q ) 收敛于( ) + 故式( 4 一1 2 ) 可以近似于如下问题( 光滑支持向量机s s v m ) ( ，罐孙+ ，( 叫 6 ) 2 ( ，锲壶c l i p ( e d ( a w - e b ) ，q ) 岍去( 矿w + b 2 ) ( 4 - 1 4 ) 下面我们先使用牛顿法求解 求解分类问题应用自动微分的牛顿算法 2 3 北京工业大学理学硕士学位论文 1 ) 取初始点( w o ，b o ) r 叶1 ，置i = 1 2 ) 利用自动微分算法的第1 , 2 步，求解中。( 叫，6 t ) ，v 中。( 叫，b i ) 若v o 。( 埘，6 1 ) = 0 ，则停。输出最优解w + ，b + 否则使用自动微分算法的第3 步得到v 2 圣。( 叫，b i ) ，求 解d r ”“，使得： v 2 西。w ，扩) = 一v 西。( 叫，b ) ( 4 1 5 ) 3 ) 选择九r ，求得( w 件1 ，b i + 1 ) = ( w ，b i ) + ) q d ，其中九= m a x 1 ，互1 ，i 1 ，) ， 使得 圣。( ，b i ) 一西口( ( ，b ) + a i d ) 一6 九v 垂口( 叫，b i ) d i 成立( 5 ( 0 ，；) ) 4 ) i = i + 1 ，转2 下面讨论上述算法的计算量设函数垂的计算量为w e ，由文献 1 6 】知，运用 自动微分算法求v 西的计算量w v v 满足 w _ v 西) 4 ， 由文献 1 6 】知，求v 2 西的计算量w v 2 垂) 满足 w v 2 圣) w v o ，v 2 垂】( 6 n + 4 ) w 勺 而采用传统的微分方法求v 西的计算量约为n w 圣， 求v 2 西的计算量约为 h + 1 ) 2 ) 采用c h o l e s k y 分解求解方程组( 4 - 15 ) 的计算量为 = 丢n 3 + 互3 n 2 一百2 扎( 4 - 1 6 ) 故运用自动微分方法每步迭代的计算量 w a = ( ( 6 n + 4 ) w + w 易l t ， ( 4 1 7 ) 运用传统微分方法每步迭代的计算量 ：( 粤半) + w l 脚( 4 - 1 8 ) 2 4 第4 章 基于自动微分的改进的非精确牛顿法 根据方程( 4 一1 4 ) 知 w o = ( 1 + f ) n + 1 2 + 4 l + 3 则我们可以定义改进因子r 为 ( 4 1 9 ) r全一wt：(n瓦2+3-n雨)2万w垂1+fwldlt，(4-20)wa ( 6 n + 4 ) + 既d l t 其中，w l d l r ，在上面已给出。 一般而言f n ，故w e 较大，所以r ( 礼2 + a , o 2 ( 6 n + 4 ) 由上式可以看 出，r 可以作为使用自动微分和传统微分方法的比较指标，即r 越大，表明自动微 分对算法的改进越大。 所给的3 个的实例，都是典型的分类问题我们用新算法( 使用自动微分的分 类算法) 来求解这些问题 例1 1 9 9 0 年统计了7 6 8 个超过2 1 岁的印第安比马女人的怀孕次数、年龄等8 项指标，患有糖尿病的记为1 ，没有患病的记为一1 。他们要根据这些指标对该地区 的女人只检查这些指标就来确定此人是否患有糖尿病。 例2 人们统计了美国波士顿市的住宅群情况给出了5 0 6 个郊区的犯罪率、空 气指数等十三项指标，达到指定标准的记为1 ，没有达到标准的记为- l 。他们希望 根据这些指标对住宅群的好坏进行评估 例3 现实生活中，乳腺癌患者与一定的指标有关，人们统计了1 9 8 个人的胆固 醇、年龄等3 5 项有关的指标，患病的记为1 ，没有患病的记为- 1 他们希望根据 这些临床的资料，对新来的病人只检查这些指标就推断这个人是否患病。 根据前面给出的优化模型，来解决上述三个分类问题。使用自动微分的牛顿算 法求出了分隔两类点的超平面，即求出了w + ，b + ，得到了决策函数。试验的终止准 则为0v 西0 2 l