（应用数学专业论文）一类不可微优化算法及在线性分类问题中的应用.pdf

论文题目：一类不可微优化算法及在线性分类问题中的应用 专业：应用数学 硕士生：郑颖春( 签名) 盗翘盘 指导教! j 币：王雪峰( 签名) 窆勉 摘要 介绍了不可微优化理论与算法的发展历史、研究意义及应用领域，分析了现有不可 微优化算法的研究现状。提出了紧凸集的外接长方体的概念，构造了一个次微分集的外 接长方体，在此基础上给出了一类求解无约束不可微优化算法，它与已有的不可微优化 算法不同，搜索方向的确定不需要计算次微分集及任何次梯度元，也不需要求解任何二 次规划，只需计算2 门个方向导数，并且给出了算法收敛性的证明。通过引进二阶方向 导数的概念，证明了几个积分中值定理，并由此证明了算法在一定条件下具有线性收敛 性。针对极大值函数的特点，给出了极大值函数的g 一次梯度的计算方法，从而得到了 一类求解极小极大问题的算法，并且证明了该算法的收敛性。对两类函数进行数值实验， 并与已有的不可微优化算法进行比较，数值结果表明，算法是可行且有效的，并具有大 范围收敛的特点，和已有的不可微优化算法相比，算法具有收敛速度快、迭代次数少的 优点，尤其对具有严格不可微点的函数和极小极大问题，算法具有更明显的优势。最后 将线性分类问题转换为一类无约束最优化问题，并给出了一种计算次梯度元的数值方 法，从而可以利用次梯度型算法求解线性分类问题。算例表明，用不可微优化算法求线 性回归方程，具有简单实用的特点。 关键词：不可微优化；极小极大；次梯度；线性分类 论文类型：理论研究 s u b j e c t ：ac l a s so fa l g o r i t h mf o rn o n d i f f e n r e n t i a b l eo p t i m i z a t i o n a n dt h ea p p l i c a t i o nf o rl i n e a rc l a s s i f i c a t i o n s p e c i a l t y ：a p p l i e dm a t h e m a t i c s n a m e ：z h e n gy i n g c h u n i n s t r u c t o r ：w a n gx u e f e n g a b s t r a c t ( s i g n a t u r e ) j 血粤显孚纵 ( s i g n a t ur e ) t h i st h e s i si n t r o d u c e st h en o n d i f f e n r e n t i a b l eo p t i m i z a t i o nt h e o r ya n da l g o r i t h m ， i n c l u d i n gh i s t o r yo ft h ed e v e l o p m e n t ，r e s e a r c hs i g n i f i c a t i o n ，a p p l i c a t i o na r e a sa n ds t u d ys t a t u s q u o p r o p o s et h ec o n c e p to fc i r c u m s c r i b ec u b o i di nt h eb i c o m p a c tc o n v e xs e ta n dc o n s t r u c ta c i r c u m s c r i b ec u b o i di nas u b d i f f e r e n t i a b l es e t o nt h i sb a s i sac l a s so fn o n d i f f e n r e n t i a b l e o p t i m i z a t i o na l g o r i t h mi sg i v e nt os o l v et h eu n c o n s t r a i n e dp r o b l e m n l ea l g o r i t h mi sd i f f e r e n t f r o mt h ec u r r e n tm e t h o d s t h es u r ef o rs e a r c hd i r e c t i o nd on o t r e q u i r e c a l c u l a t e s u b d i f f e r e n t i a b l es e ta n da n yo r d e rs u b g r a d i e n t ，a n ds o l v ea n yt w o - o r d e rp r o g r a m m i n g i t s i m p l yc o m p u t e s2 nd i r e c t i o n a ld e r i v a t i v e s n ec o n v e r g e n c eo ft h ea l g o r i t h mi sa l s op r o o f n l ep a p e rp r o v e ss e v e r a li n t e g r a lm e d i a nt h e o r e m sa n dt h el i n e a rc o n v e r g e n c eo ft h e a l g o r i t h mu n d e rc e r t a i nc o n d i t i o n st h r o u g ht h e i n t r o d u c t i o no ft h ec o n c e p to fs e c o n d d i r e c t i o n a ld e r i v a t i v e f o rt h ec h a r a c t e r i s t i c so fm a xf u n c t i o n , t h ea c c o u n to fs s u b g r a d i e n t o fm a xf u n c t i o ni sg i v e n , a n dt h e nac l a s so fa l g o r i t h mi sg a i n e dt or e s o l v eam i n i m a x p r o b l e ma n dt h ec o n v e r g e n c eo ft h ea l g o r i t h mi sp r o o f b yn u m e r i c a le x p e r i m e n tf o rt h et w o t y p e so ff u n c f i o n ，t h en u m e r i c a lr e s u l t ss h o w t h a tt h eg i v e na l g o r i t h mi sf e a s i b l ea n de f f e c t i v e ， a n dh a st h ec h a r a c t e r i s t i c so fl a r g e s c a l e c o n v e r g e n c e c o m p a r e 、7 i r i t h t h ee x i s t i n g n o n d i f f e n r e n t i a b l eo p t i m i z a t i o na l g o r i t h m ，o u ra l g o r i t h mh a st h ea d v a n t a g e so ff a s t c o n v e r g e n c e a n di t e r a t i v e f e w e r e s p e c i a l l y f o r t h ef u n c t i o np r o v i d e d 、i t l lr i g o r o u s n o n d i f f e n r e n t i a b l ep o i n ta n dt h em i n i m a xp r o b l e m , o u ra l g o r i t h mh a st h ee v e no b v i o u s a d v a n t a g e s f i n a l l y ，l i n e a rc l a s s i f i c a t i o np r o b l e m sa r ec o n v e r t e dt oac l a s so fu n c o n s t r a i n e d o p t i m i z a t i o np r o b l e m a n dt h et h e s i sp r e s e n tan u m e r i c a lm e t h o df o rc a l c u l a t es u b g r a d i e n t ， t h e nt os o l v el i n e a rc l a s s i f i c a t i o np r o b l e m sb yu s eo ft h es u b g r a d i e n ta l g o r i t h m e x a m p l e s s h o wt h a tt h en o n d i f f e n r e n t i a b l eo p t i m i z a t i o na l g o r i t h mf o rl i n e a rr e g r e s s i o ne q u a t i o ni s s i m p l ea n dp r a c t i c a l k e y w o r d s ：n o n d i f f e n r e n t i a b l eo p t i m i z a t i o nm i n i m a x s u b g r a d i e n t l i n e a rc l a s s i f i c a t i o n t y p e s o ft h e s i s ：t h e o r yr e s e a r c h 姿错技大学 学位论文独创性说明 本人郑重声明：所呈交的学位论文是我个人在导师指导下进行的研究工作 及其取得研究成果。尽我所知，除了文中加以标注和致谢的地方外，论文中不 包含其他人或集体已经公开发表或撰写过的研究成果，也不包含为获得西安科 技大学或其他教育机构的学位或证书所使用过的材料。与我一同工作的同志对 本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意。 学位论文作者签名：籽翱茏日期：伽宕俄i ， 学位论文知识产权声明书 本人完全了解学校有关保护知识产权的规定，即：研究生在校攻读学位期 间论文工作的知识产权单位属于西安科技大学。学校有权保留并向国家有关部 门或机构送交论文的复印件和电子版。本人允许论文被查阅和借阅。学校可以 将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩 印或扫描等复制手段保存和汇编本学位论文。同时本人保证，毕业后结合学位 论文研究课题再撰写的文章一律注明作者单位为西安科技大学。 保密论文待解密后适用本声明。 学位论文作者签名：籽； 3 法 指导教师签名：主匆均 沙臼多年伽侈日 i 绪论 l 绪论 本章介绍了不可微优化理论与算法的发展历史、研究意义及应用领域；给出了不可 微优化的一般形式及解的概念；分析了现有不可微优化算法的研究现状；最后是本文的 内容安排。 1 1 不可微优化理论与算法的发展历史、研究意义及应用领域 最优化是一门应用性强、内容丰富的年轻学科，它讨论决策问题的最佳选择的特性， 构造寻求最佳解的计算方法，研究这些计算方法的理论性质及实际表现。最优化广泛应 用于工农业、国防、金融、化工、能源、通信等重要领域，而且与分析、几何、代数、 概率论，以及计算机科学、系统科学、自动化等学科密切联系，互相促进。如果说“模 拟 深刻地改变着人们改造世界的能力，那么“优化”则深刻地改变着人们改造世界的 方法与途径。 最优化是运筹学的一个主要组成部分，也是应用数学的基本研究对象之一，它研究 不同决策问题的最优选择的数学理论和方法。根据决策问题的数学结构的不同，最优 化问题的类型从数学规划、最优控制、随机运筹到最优估计等，涉及范围广、跨度大， 几乎理、工、医、农、管理、军事乃至人文经法领域，都存在着大量形式多样的最优化 问题。它的主体由规划论，组合数学，控制论，运筹和计算数学等组成。最优化已是工 程师们寻求最优系统和结构，挖掘系统潜力的有力武器。最优化技术是一种以数学为基 础，结合各学科专业知识，优化求解各类实际问题的应用技术。从它的产生到应用，一 直受到人们的广泛关注，并在实际应用中迅速推广，例如，在生产计划与调度、交通运 输、商业运作、金融管理等领域都有数不清的成功实例。 最优化是一门应用性很强的学科。简单地讲，它研究某些用数学模型表述的问题， 并求出其最优解，即对于给出的实际问题，从众多方案中选出最优方案。具体来说，它 讨论决策问题的最佳选择之特性，构造寻求最佳解的计算方法，研究这些计算方法的理 论性质及其实现。虽然最优化可以追溯到古老的极值问题，然而它成为- 1 7 独立的学科 是在上世纪4 0 年代末，在1 9 4 7 年d a n t z i g 提出求解一般线性规划问题的单纯形法之后。 现在，对线性规划、非线性规划以及随机规划、非光滑规划、多目标规划、几何规划、 整数规划等各种最优化问题的理论研究发展迅速，新方法不断涌现，实际应用日益广泛。 最优化理论和方法在自然科学、经济计划、工程设计、生产管理、交通运输、网络交通、 农业预测、国防等重要领域，已受到政府部门、科研机构和产业部门的高度重视，成为 - - f - j 十分活跃的学科。伴随着计算机的高速发展和优化计算方法的进步，规模越来越大 的优化问题可以得到解决。 西安科技大学硕士学位论文 最优化方法在各种工程系统、经济系统，乃至社会系统中得到了广泛的应用。最优 化理论的研究也一直是一个十分活跃的领域。但是，传统的最优化方法有较大的局限性。 它往往要求目标函数是凸的、高阶连续可微的，可行域是凸集等等。而且其处理非确定 性信息的能力很差。这些弱点使常规的优化方法在复杂系统中的应用受到了限制。出于 现代工程、经济管理和国防建设等方面的需要，不可微最优化问题作为最优化的一个分 支在二十世纪六十年代开始形成。其所研究的内容包括模型创建、算法设计及收敛性分 析、数值试验等。由于不可微最优化问题特别注重算法的可计算性和实用性，因而传统 的最优化问题实质上是运筹学与计算数学的交叉。不可微规划被用来解决目标函数或约 束函数中有不可微函数最优化问题的最优解。 在自然科学和社会科学的研究中，有大量理论问题和实际问题都与数学规划有关。 其中，不可微优化问题又是数学规划理论中的一个重要的而又困难的研究领域。科学研 究、经济领域以及工程技术中的诸多问题都依赖于用数值方法寻求相应问题的全局解。 长期以来，全局优化问题一直受到研究人员和工程技术人员的关注。近三十年来，尤其 是最近几年，对全局优化问题的研究在世界范围更受重视，也有了很多新的研究成果。 在g b d a n t z i g 提出线性规划单纯型法的第二年，也就是1 9 4 8 年，a t u c k e r h k u h n g a l e 就开始了对非线性规划的研究。这一理论的初步形成约在1 9 5 1 年，其标志 是与f r i t z - j o h n 条件( 1 9 4 8 ) 相关的k u h n t u c h e r 条件的提出。非线性规划是最优化问 题中的重要一类。由于受到数学分析工具的限制，6 0 年代前的非线性规划不自觉地假定 所涉及的函数是平滑的，但实际的问题却总是不平滑的。凸规划( c o n v e xp r o g r a m m i n g ) 理论首先打破了这一限制，对数学分析的微分理论做了推广，从而开始了非光滑规划的 研究。但是只对凸的情况下的非光滑规划研究还不能满足实际的需要，因而进一步展开 了对非凸规划的研究，近三十年来，非光滑规划为众多学者所关注，其中r o c k f e l l a r , c l a r k e 属于这一领域的领军人物。而非光滑优化的应用主要在控制、经济、金融及非线性规划 等的几乎所有领域。 不可微非线性函数优化问题具有广泛的工程和应用背景，如结构设计中使得结构内 最大应力最小而归结为极大极小优化( m i n m a x ) 问题、数据鲁棒性拟合中采取最小绝对 值准则建立失拟函数等。其求解方法的研究越来越受到人们的重视，常用的算法有模式 搜索法、单纯形法、p o w e l l 方法等，但是这些方法都是局部优化方法，优化结果与初值 有关。由于科学和工程等领域所需要解决的问题大都可以归结为求不可微规划全局解的 问题，从而促使过去三、四十年里，关于不可微规划全局最优化的理论和算法层出不穷。 而大多数算法都要计算函数的次梯度，由于次梯度的计算比较困难，所以很多算法难以 实现，因此或避开计算次梯度，或用其它方法逼近次梯度，建立一个可实现的算法非常 必要。 2 l 绪论 1 2 不可微优化问题概述 不可微优化问题，可用如下形式予以表述： n l i i l 八x ) ( 1 2 1 ) s 1 x c 设c r 。是一个非空闭集，或称为约束集，( x ) ：r ”专足1 在c 上李普希兹连续。要求 x c ，使得厂( x ) ( x ) ，对所有的x c 成立，则称x 是厂( x ) 在c 上的一个( 严格) 全 局最优解。若c = r “，则称上述问题为无约束不可微规划。解决上述问题就是至少找到 一个最优解x $ ， 5 - 乏f ( x ) s ( 工) ，对所有的x c 成立，或证明最优解不存在，这样的问题 称为不可微优化问题。 不可微优化( 或非光滑优化) 讨论具有不连续一阶偏导数的函数的极小化( 或极大 化) 问题，在经济数学与其它一些实际问题中往往会遇到，近三十余年来，不可微优化 的理论与方法有了很大的发展。 实际当中经常遇到以下两类不可微优化问题： ( 1 ) 极小极大问题：设z ( x ) ，i = 1 ，2 ，脚为连续可微函数。则厂( x ) = m 。a ；x 。f ( 工) ，在使 乃( x ) = z ( 工) ，f 的某些x r ”处是不可微的，因此极小极大问题 m 删i n 厂( x ) 2 噼m a x z ( x ) ( 1 2 2 ) 是不可微优化问题。 ( 2 ) 问题：同样，当z ( x ) ，f = 1 ，2 ，m ，光滑时， rm、 卿 饰) = 善) ” ( 1 2 3 ) 是不可微优化问题。 容易看出，极小极大问题可以化为标准的非线性规划问题 m i n d 舢z ( 石) ，f ：l ，2 ，嬲 ( 1 2 4 ) 求解，而正问题与 3 西安科技大学硕士学位论文 r a i n z o , 戤 掌i = l 端嚣三 m 2 5 ) 等价，但人们往往宁愿直接求解不可微问题。事实上，将光滑的非线性规划问题 曲巾) ， ( 1 2 6 ) s t q ( x ) o ，i = 1 ，2 ，m 、7 化为不可微无约束优化问题，乃是约束优化中一类重要的方法，例如 精确罚函数法： r辨、 卿 p ( x ) = 坤) + m 善一( 一q ( x ) ，o ) 及分解算法：线性规划问题 a l i a ( c t x + d r y ) s i 。触+ b y s b 司化为不司微优化i 司题： 曲 厂( x ) 全c7 x + i i l i n d r y ，b y o 是给定的正数，( ) o 是加权因子，得以( ( f 厶) ，取破= 一名岛为第女 f e 厶 次迭代方向。 1 3 2 基于光滑函数优化问题的解法 通过适当的转换，化为光滑函数的优化问题，直接使用现有的优化算法软件解这类 问题。具体有以下三种： ( 1 ) 最小p 阶算法 一 一i 由范数的定义，对任何向量y e r 一，称，= i 窆川91 9 为向量y 的p 范数( p 1 ) ，当 广1 三 p - - - ，o o 时，则有，= 懋 只 成立。因此，如果每个z ( x ) o ( f = l 2 ，肌) ，那么可用l - 喜i 乃i j 一一i 近似代替目标函数，只要p 足够大，上述近似总是合理的。称c ，( 毛p ) ：m i i l i 窆i 乃i ，l ，为最 小p 阶目标函数。这样，为求解m i n i m a x 问题的最优解，可通过逐步加大p 而求解一系 列的无约束优化问题u ( x ，p ) 如果z ( x ) o ，利用摄动的方法将z ( x ) 加上一个常数f ，使得 z ( x ) + 善o 。这一方法由c h a r a l a m b o u s 首先提出，目的是克服m i n i m a x 问题的不可微性， 使m i n i m a x 函数光滑。c h a m l a m b o u s 和b a n d l e r 于1 9 7 8 年提出了对每个队( 工) ，的加权 算法，令射( x ，善) = m 。a ；。x f , ( x ) 一孝) = ( x ) 一善，q = 尸x s 缪( m ( 薯善) ) ，p 1 ，相应的最小p 阶目标函数 吣只沪卜悄锚门i 裁篙3 【0 6 1 绪论 而 s ( x ，善) = 引z ( x ) 一； 。， 苎m ! x 孝) o“3 4 ) 若m ( x ，孝) 刀时具有二阶收敛速度，但若 研刀仅具有线性收敛速度。 对非光滑优化的研究主要集中在三个方面：1 ) 基础理论的研究。包括凸分析、非线 性分析等；2 ) 优化理论的研究。主要包括各种最优性条件的研究、算法收敛性的研究 等；3 ) 对方法的研究。主要分为两个大类：次梯度法和捆集( b u n d l e ) 法，见文 3 】，值 得注意的是，现在已有利用非光滑函数的结构特点寻求新算法的成果。见文【4 6 】。 随着其应用理论基础及算法的快速发展，这一领域日益呈现出其活力，呈现三个特 点： 第一、非光滑优化问题范围很广，不仅包括目标和约束函数不可微的优化问题，而 且包括那些目标和约束函数是一阶可微但不是二阶可微的问题。此外非光滑变分不等式 问题、半定规划、非光滑方程、集值问题、双层规划等均在非光滑优化范围之列。而这 样宽广的范围也使得解析工具和算法有了广阔的应用。 第二、非光滑分析的迅速发展。非光滑分析起源于凸分析，现在也包括广义二阶微 分，集值分析，广义凸性和其它许多论题。一方面，非光滑分析现在自身就是一门学科， 另一方面，它源源不断的为非光滑优化提供了有力的工具。见文 7 】 第三、非光滑优化新算法的发展。这一领域，从收敛性分析到数值实验都重新焕发 出壮观的场面。 1 4 本文内容及安排 本文共分五部分，首先在绪论部分介绍了不可微优化理论与算法的发展历史、研究 8 1 绪论 意义及应用领域，分析了现有不可微优化算法的研究现状。第二章给出了本文要用到的 基本概念，提出了紧凸集的外接长方体的概念，构造了一个次微分集的外接长方体。第 三章给出了一类不可微优化算法及求解极小极大问题的算法，并证明了算法的收敛性及 线性收敛性。第四章通过数值例子进行数值试验。第五章主要介绍不可微优化算法在求 解线性分类问题的应用。第二章至第五章是本文的主要工作。 9 西安科技大学硕士学位论文 2 基本概念与基本理论 本章首先介绍文章中要用到的一些基本概念，提出了次微分集的外接长方体的概 念，然后证明了q ( x ) 确实是次微分集的外接长方体。并指明了当( x ) = 恻l ：时，a f ( o ) 为 一球体，这时所说的外接就是通常意义下的外接。 2 1 基本概念 定义2 1 1 【7 】( 局部李普希兹) 设( x ) 是定义在尺”上的实值函数，弱i g f ( x ) 在点石是 局部t i p s c h f t z 的，如果存在点x 的一个邻域( x ) 和一个非负常数k ，使得 l 厂( 五) 一厂( 而) i 训五- x 2 1 i 弘，x 2 ( x ) ( 2 1 1 ) 其中1 1 i i 是r ”上的欧氏模，后为函数厂( x ) 在点x 的局部，枷c 办沱常数。如果对任意x 掣， o ) 在x 都是局部l i p s c h i t z 的，则称o ) 是局部l i p s c h i t z 的。 定义2 1 2 8 】设厂( x ) 是定义在s r ”上的函数，如果存在所 0 ，使得 f ( a x l + ( 1 一口) 而) 口厂( 而) + ( 1 一口) 八吃) 一所口( 1 一口) 0 五- x 2 1 1 2 ，而es ，v a 0 ，1 】 ( 2 1 2 ) 成立，则称函数厂( x ) 为s 上的具有强凸常数所的强凸函数。 定义2 1 3 1 7 ( c l a r k e 意义下的方向导数) 设厂是掣上的局部李普希兹函数，称 代v ) ：l 州i m s u p 业竽型v r f - o 为f 在x 的沿方向v 的广义方向导数。 通常意义下的方向导数定义如下： m v ) ：蛳丛竿盟 定义2 1 4 【7 】( 次梯度) 满足条件 ( 孝，v ) o ( 训) v v r “ 的f 称为f 在点x 的次( 广义) 梯度元。 ( 2 1 3 ) ( 2 1 4 ) ( 2 1 5 ) 2 基本概念与基本理论 所有这样的善组成的集合鲈( x ) = f ( 孝，v ) 厂。( x ，v )v v e r ” ，称为厂在点x 的次微分 集。 定义2 i 5 7 】设厂：r ”一r 1 是凸函数，占 0 是常数，称满足条件 厂( y ) 厂( x ) + ( 善，y z ) 一g v y r ”， ( 2 1 6 ) 的孝为。在点x 的e - - 次梯反。 而其组成的集合 a 。( x ) = 孝i 厂( y ) 厂( x ) + ( 孝，y x ) 一f ) 为厂在点x 的占一次微分。 2 2 算法的收敛性及收敛速度 下面给出几个关于算法收敛性的概念。 所谓算法的局部收敛性指的是：存在点x 的一个邻域u ( x ) ，使得当初始点 x u ( x ) 时，算法产生的点列 x ) 收敛于z 算法的全局收敛性指的是：当初始点x ( o 是某个较大的集合中的任意点时，算法产生 的点列 x 收敛于x + 定义2 2 1 【2 6 】设序列 x ) ) c r ”收敛于工 1 、若存在常数p ( 0 , i ) ，使得当k 充分大时， x 忙“一x + 8s 夕8 z 似一x 。l ( 2 2 1 ) 则称 x 。) ) 线性收敛于x ，或称 x 。) ) 的收敛速度是线性的。 2 、若 l i m 七 = 0( 2 2 2 ) 高 西安科技大学硕士学位论文 则称 x 。 超线性收敛于x ，或称 x ) 的收敛速度是超线性的。一般地，若对某个常数 p l ，存在常数m 0 ，使得当k 充分大时， ”“一x i l 0 ( 2 3 4 ) 1 2 2 基本概念与基本理论 证明：f 。( x o ，一v ) 2 倒m i l ( k 而) ( 孝，一y ) = ( 磊，一y ) = 吨 0 这个引理说明如果厂在某一方向递减，则沿其相反方向必递增，反之不一定成立。 定理2 3 1n ( x ) 是非空紧凸集钞 ) 的外接长方体。 证明：显然n ( x ) 2o f ( x ) 以下只需验证定义2 3 1 中( 2 ) 。 由于妒( x ) 是一个非空紧凸集，故存在善o f ( x ) ，使得 当然对一也存在互o f ( 功，使得 ( 孝，v ) = 厂。( 石，1 ，) v v r ” 亿，畴) = 厂o ( 而k ) i = 1 ，2 ，刀 这就是说，在平面z 1 7 = 厂o ( x ，m ) 上存在z l a f ( x ) ，z f 。是z j 的第f 个分量。 同样对每一个1 ，在q ( x ) 的每一个面上也都存在钞( x ) 中的点。 所以，n ( x ) 是非空紧凸集钞( x ) 的外接长方体。 f = i i x l l ：时，o f ( o ) 为一球体，这时所说的外接就是通常意义下的外接。 1 3 西安科技大学硕士学位论文 3 算法及其收敛性 3 1 算法及其收敛性 i & 0 定理3 1 1 乙= 矾咴0其中c k = - f o ( x i ，一v k ) ，d k - - f o ( x i ，v k ) ， 1 0其它 设z = ( z l ，z 2 z 。) 0 ，则- z 体是问题( 2 3 1 ) 的一个下降方向。 证明：由于f l ( x ) 2 a f ( x ) ，故v 氕0 f ( x ) 都有氕q ( x ) ， 即有 c k 氕d k 所以 ( 氕，z ) o 即一z ( i 【) 是问题( 2 3 1 ) 的一个下降方向。 算法3 1 1 ( z y c a 算法) s t e p l ，给定初始点x i ，终止误差g 0 ，置k = l ， s t e p 2 ，计算c i = - f o ( x k ，一v i ) ，d i = f o ( x k ，v i ) i = 1 ，2 ，n s t e p 3 ，令p k = 一z 若| | p k i i 0 ，v o j = h 扛1 ，2 ，胛，旋转变换矩阵b ，旋转 次数m ，置k = l ， s t e p 2 ，计算c “= 一f o ( x k ，一v j j ) ，d i 【i = f o ( x k ，v j j ) i = 1 ，2 ，1 1 1 4 3 算法及其收敛性 i i i i e i ji i 。 q 宣暑宣i 宣每 s t e p 3 ，令p k = 一z 若f i p k 忙g ，则转s 剐，否则一维搜索求五，使 f ( x k + 五p k ) = m 脚i n f ( x k + 2 p k ) 令x k + l = x k 十九p k ，k = k + l ，转s t e p 2 s t e p 4 ，令( k l ，l ，_ + 1 ，2 ，_ + l ，。) = b ( 叶l ，_ 2 ，_ ，) ，若 _ k o ，当七2 n 时，有 即 显然存在气( o ，1 ) ，使得： ( g ，( ) ，p o ) - 一p ( x o ) br b 。：+ 仅l ：p t ) ，p o ) - - p ( x o ) ( g ，( 气+ 九吒既) ，1 , o ) - - p ( x o ) 1 5 西安科技大学硕士学位论文 所以由算法3 1 1 产生的点列满足口一锐角条件。 定理3 1 3 设f ：r ”专r 1 是局部李普希兹的，在可微点处严格可微，由算法3 1 1 产生的点列，对充分大的k ，x k 为可微点，极限点可以不可微，若x 为 稚 的任一聚点， 贝0 0 o f ( x ) 张连生教授已给出了迭代点列在满足口一锐角条件时，算法不仅收敛而且全局收敛 的证明【2 0 】，这里证明就从略了。 3 2 算法的线性收敛性 设x o ) 是 o ，丁】上的胛维连续且可微的向量函数，令缈( r ) = 厂【x ( ，) 】，f ：尺”专r 1 是李 普希兹的，不难证明砷) 在【o ，列是绝对连续函数，故存在可积函数c o ( t ) ，使得 缈o ) = 缈( o ) + j ：c o ( t ) d t ( 3 2 1 ) 引理3 。2 1 设函数f ：r ”寸r 1 在点而是局部李普希兹的，则在而具有以下性质 卜o t 由( 3 2 1 ) 及引理3 2 1 可知， = ( x o ，) v v r ” 厂( x ( f ) ) = 厂( x ( o ) ) + f ( x ( f ) ，x ( ，) ) 西 故 厂o + 耐) = 八x ) + f 厂o + 掰，d ) 峦 ( 3 2 2 ) 这就是一阶的积分中值定理。 定义3 2 1 ( 二阶方向导数) 设厂：r ”j r l 是局部李普希兹函数，f 。似口) 对x 也是 局部李普希兹的，若极限厂( 毛由= l ，i m 。垒塑掣存在，则称其为厂在点x 沿 方向d 的二阶方向导数。 引理3 2 2 设f ：r ”一r 1 是局部李普希兹的f ( x ，d ) 对x 也是李普希兹的，则下列 积分中值定理成立： 厂o + 耐，d ) = f 。( x ，d ) + f 厂 + t d ，d ) d t ( 3 2 3 ) + 嬲) = 厂( x ) + 名厂( z ，d ) + r ( 名一t ) f 。 + t e l ，d ) d t ( 胁o ) ( 3 2 4 ) 引理3 2 3 若存在朋，m ，k 使得：聊m 2 厂。( x ，d ) 0 ，使当肛一x u - 占时，恒有 詈j l x - x 1 1 2 ( 功一( x ) m 2 。i x - 1 1 2 ，i i 孝 x ) l l ，竹l i x x 。i j ( 3 2 5 ) 其中m = 毛+ k ，善( x ) 满足 = 厂( x ，x z ) 引理3 2 4 ，设矽( 旯) 在 0 ，b 】上是局部李普希兹的，_ r c a ( 0 ，1 ) o ，( 缈( 0 ，一1 ) o ) 糊啦【0 ，6 】上的极小肼( o 沏，则材瘟竽( 如万= 半) 其中o 是c a 。( 0 ，1 ) ，( 伊。( 0 ，一1 ) ) 的正上界。 证明：构造辅助函数( 五) = 缈t ( 0 ，1 ) + 姒，它有唯一的零点万= 一生詈旦 由( 3 2 3 ) 知 矽( 名，1 ) = 伊( o ，1 ) + r 伊。( t 2 ，o d t - c a ( o ，1 ) + m = y ) ( 3 2 6 ) 因为对伊( 五) 的任一极小点均有 驴( 五，i ) 0 ( 3 2 7 ) 即 y ( ) 0 ( 3 2 8 ) 故 驴( 0 ，1 ) + 姒0 ( 3 2 9 ) 由此推出 万= 丁- c a ( 0 , 1 ) ( 3 2 1 0 ) 如果p ( o ，一i ) 0 ，证明类似。 下面用上述引理来证明算法的线性收敛性 定理3 2 。1 设f ：足”一r 1 是局部李普希兹的，且正则，f ( 工，d ) 对x 也是局部李普 希兹的，x 是问题( 2 3 1 ) 的一个最优解，并且假定存在加，m ，k 使当忙一x i i 占时， m i i ，1 1 2 厂( x ，d ) - m , ld l l 2 ，厂( x ，d ) - 等d l l 2 ， 坼 是算法3 1 1 产生的点列，且 稚寸x ( 后寸) ，则 稚) 线性收敛子x 证明 l i m x | i = x ，故不妨假设8 一z 0 占，( 七= l ，2 ) j 由于 西安科技大学硕士学位论文 k 。o i i - 0 ，使： 0 黾+ ( 五+ 万) 反一x l - - i i x 。+ 一x + 万畋0 s ( 3 2 1 1 ) ( 3 2 1 2 ) 考虑对伊( z ) = 瓴+ 碱) 在区间 0 ，五+ 葶】上应用引理3 2 3 ，并注意咴的取法， 伊( o ，1 ) = 厂( 黾，畋) ，驴( 旯，1 ) = ( x k + 弛，或) ，伊。( 名，1 ) = 厂( 黾+ 戤，畋) 由于厂( + 畋，以) 有界，所以矿。( 五，1 ) 有界。驴( 力) 在 o ，4 + 拶】上的整体极小点五满足： 枷器铡铲叁万 2 m ) 其中m = m 1 + k ， = 厂( 诈，畋) ，口( ) ( 0 ，1 ) i 发一x k = x k + 飘，则其位于耳到吒+ 。的闭线段上，即有f x k - - x 0 占， 由引理3 2 4 知 胞+ 五畋) 一低) ，( 吒+ 无反) 一讹) 万( 吨( 训孝( 酬+ 三m 以2 i i 以1 1 2 = 一鲁) 降警脚2 卜x 屿掣宇) 2 ( 讹h f ) ) ( 3 2 1 4 ) 于是 f ( x k + 。) - f ( x 。) 研( ) 一f ( x ) 】 其中 ( 3 2 1 5 ) p = 1 - 擘) 2 】； 则有：