（计算数学专业论文）一种具有全局性的牛顿内点优化算法.pdf

摘要 该篇论文针对约束最优化的一般性问题，提出一种具有全局收敛性的内点 算法本文应用的牛顿迭代法与罚函数法优缺点互补的特性在【3 】，【4 】，【5 】，1 1 3 ， 1 4 1 等文章中均有应用，在此基础上我们提出一种具体形式的增广函数区别于 其他牛顿内点法算法，该算法中减少了对罚因子的讨论，从而减少了由于罚因子 过大而带来的一些不便，使算法更加简便、易行 论文第一部分，我们介绍了一些与最优化相关的基础知识，阐述了优化的结 构及算法的必要组成部分，提出了约束优化问题中的一些充分必要条件，为下文 算法的提出作铺垫 第二部分，首先介绍了内点优化算法在线性规划中产生和发展，以及在非 线性规划中发展前景其次介绍和分析了内点优化中的罚函数法和牛顿迭代法， 指明了罚函数法和牛顿迭代法在解决约束优化问题时出现的问题，从而引出对 近几年较为热门的牛顿内点优化方法的讨论 第三部分，针对于第二部分中提到的牛顿内点优化方法的构成特点，提出 一种新的牛顿内点优化算法这一算法中通过提出种新组合形式的增广函数， 得到不同的步长因子选择准则，并保证其迭代点为扰动k k t 方程的内点最后 给出算法全局收敛性的证明，以及与 3 中的算法进行理论上的分析比较，并给出 实际计算的数值例子 关键字：内点法、罚函数法、牛顿内点法、增广函数 a b s t r a c t y i n g y i n gz h a n g ( c o m p u t a t i o n a lm a t h e m a t i c s ) d i r e c t e db yp r o f d a n f uh a u ，p r o f z h e n g d ah u a n g i nt h i sp a p e rw ed e s c r i b ea ni n t e r i o ra l g o r i t h mw i t hg l o b a lc o n v e r g e n c eo ft h e g e n e r a lo p t i m i z a t i o np r o b l e m c o n s i d e r i n gt h ec o m p l e m e n t a r ya c t i o nb e t w e e n n e w t o nm e t h o da n dp e n a l t ym e t h o d 、d e f i n eam e r i tf u n c t i o nt os i m p l i f yt h e s e l e c t i o no fi n i t i a lp o i n t ，s ot h a ta l g o r i t h mh a v ee x c e l l e n tg l o b a lb e h a v i o r t h e n e wm e r i tf u n c t i o ni sg o o df o rg l o b a lc o n v e r g e n c ea n ds i m p l i f i c a t i o na l g o r i t h m w i t h o u tt h ep e n a l t yp a r a m e t e r f i r s t ，w ed e s c r i b es o m ef u n d a m e n t a lk n o w l e d g eo ft h eo p t i m i z a t i o n s u c h a s ，t h ef r a m e w o r ko ft h eo p t i m i z a t i o n ，t h ee s s e n t i a lp r o c e s so ft h ea l g o r i t h m t h es e c o n dc h a p t e r w ed e s c r i b es o m ec l a s s i c a li n t e r i o r m e t h o d s i ar e - c e n ty e a r s ，m a n yp e o p l es t u d i e dt h ec o n v e r g e n c eo ft h en e w t o nm e t h o da n dt h e p e n a l t ym e t h o d ，a n dg a v em a n yd i f f e r e n ta l g o r i t h m f i n a l l y , w ep r o v i d eai n t e r i o r - p o i n tn e w t o nm e t h o dw i t han e wm e r i tf u n c - t i o nb a s i n go ut h ec l a s s i c a li n t e r i o r - p o i n tn e w t o nm e t h o d s ，s ot h a tt h es t e p p a r a m e t e r 口h a v ed i f f e r e n ts e l e c t i o np r i n c i p l ef r o mo t h e ri n t e r i o r p o i n tm e t h - o d s i nt h i sc h a p t e r ，w eg i v et h ep r o o fo ft h eg l o b a lc o n v e r g e n c ew i t hs t a n d a r d c o n d i t i o n s k e y w o r d s ：i n t e r i o r - p o i n tm e t h o d ，p e n a l t yf u n c t i o nm e t h o d ，i n t e r i o r - p o i n t n e w t o nm e t h o d ，m e r i tf u n c t i o n 第一章引论 1 1引言 最优化就是在众多的决策里挑选”最优的”，如寻求最大利润、最短路径、最 佳弹道、最少下料、最少实验次数等等它在化学反应、工程设计、交通运输、城 市规划、油田开发、自动控制、经济市场、空间技术、生命科学、大气海洋等方面 都有着广泛的应用而这些实际问题中，最优的不是仅仅解决一个函数就能完 成的，它的最值常常伴随着一些条件问题的约束，就像讨论最大利润时，我们要 考虑总资本有限这一事实因此约束最优化问题可看作最优化问题中的一个重 要分支，也是解决实际生活问题不可回避的一个问题在文献【1 、f 7 】、 8 】、【1 1 】等 优化类书刊中均把约束优化当作是以后的优化计算问题的重点研究方向 最优化问题的一般形式为 m i n f ( x ) s t o x 其中茁r “是决策变量，( z ) 为目标函数，xc 酽为约束集其中，约束最优化 问题通常写为 m i n f ( x ) s t c ( o ) 0 ，i i ， h i ( x ) = 0 ，j e 这= 里e $ i 1 1 分别是等式约束的指标集和不等式约束的指标集，c f ( 。) 和( 石) 是约束 函数，当目标函数和约束函数均为线性函数时，问题称为线性规划当目标函数 和约束函数均为非线性函数时，问题称为非线性规划本论文针对于非线性约 束最优化问题，研究该类问题的计算方法，主要是寻求构造求解最优化问题的数 值计算方法 1 2 数学基础 在讨论最优化之前，介绍些必备的基础知识 第一章 弓f 论 2 1 2 1 范数 定义1 2 1 映射：r “一研际为j p 上的半范数，当且仅当它具有以下的 性质： ( 1 ) i i x l i 0 ，v x r “ ( 2 ) 彻| | = ，她r ，妇舻 ( 3 ) 1 i x + 可| i 1 | z 0 + | | | | ，v x ，y r ，1 此外，除了以上三个性质外，如果映射还满足 ( 4 ) ll x l i = 0 甘。= 0 ， 则称为r ”上的范数 设x = ( x 1 ，一，z 。) t r “，常用的向量范数为： 设z k 是向量序列，如果 l i x l l 。= y l l a xl x l 俐1 = 阱 。= ( z 秒2 t ；1 j i mi i 。k z + | i = ，_ 0 r u u 则称序列 辄) 依范数收敛到，简称收敛到矿 在口；中，如果序列满足 l i mi i x 。一吼8 = 0 ， 1 ，b 一( 则称序列x c a u c h y 序列，这就是说，对于任给的e 0 ，存在整数札，使得每 当m ，z 札时，就有 0 z m 黝0 0 ，使得对于所有0 n 茎丘，有z + a d 为可行域内的点，则称d 为。处的一 可行方向 定义1 3 3 设矿是可行域内点，如果任取可行域的一点z 有 ，( 。) ( x ) 成立，则称是问题( 1 3 1 ) 的全局极小点，如果任取可行域的一点。，且z 有 ，( 。) f ( x ) 第一章引论 5 成立，则称矿是问题( 1 3 1 ) 的全局严格极小点 定义1 3 4 问题( 1 3 1 ) 中，任给一点x + s 后，有些不等式约束在矿以等 式成立，它们的下标集不妨用，表示，即i ，均成立c c ( ) = 0 通常将约束条 件c f ( z ) ，h j ( z ) 0 i ，j = 1 ，z ) ，称为在x + 处起作用约束 起作用约束在矿的邻域限制了可行点的范围，也就是说，当点沿着某些方 向稍微离开矿时，仍能满足这些约束条件；而沿着另一些方向离开x 时，不论步 长多么小，都将违背这些约束条件 其余约束条件情形则不同，当点稍微离开x + 时，不论沿着什么方向，都不会 违背，这些约束称为在矿处不起作用约束在该篇论文提到的算法中也是通过 引入一个扰动变量避免起作用约束，从而保证在迭代点处不起作用约束的 定义1 3 1 1 3 ，4 参见文献f 1 1 约束最优化问题在数学上是满足一些约束条件( 如不等式、等式等) 求函 数的极大值或极小值由于判断一个点是不是极值点要知道该点附近所有点的 函数值，而这样的点往往是无穷多个，故要直接验证个点的最优性几乎是不可 能的所以要研究最优点应满足的条件( 必要条件) 以及能保证该点为最优点的 条件( 充分条件) 是非常重要的 1 3 2 一阶最优性条件 通过上面的一些定义，下面给出相关的一些定理，从而得到最优解存在的一 阶必要条件 定理1 3 5 ( f r i t i z j o h n 条件) 设在问题( 1 3 1 ) 中，x + 为可行点，i = i l c a ( x 4 ) = o ) ，和c f 0 i ) 在z 可微，q ( j ) 在点连续，吗o = 1 ，f ) 在。+ 连续可微 如果矿是局部最优解，则存在不全为零的数咖，w i a ) ，和0 = 1 ，j ) ，使 得 w 0 v s ( z + ) 一v c a ( x + ) 毗一v h & + ) = 0 ， 讵，j = l 叫o ，w t 0 ，i 1 证明见文献 7 j 通常将满足f r i t zj o h n 条件的点称为f r i t zj o h n 点 第一章引论 6 定义1 3 6l a g r a z _ l g e 函数 l ( x ，w ，v ) = f ( x ) 一q ( 咖扎 ( 。) j = l 若满足 v 。l ( x + ，w ， ) = 0 ， 其中= ( w l ，u k ) 7 ，口= ( u h 一，) 7 称为l a g r a n g e 乘子，矿称为k k - t 点 定理1 3 7 ( k u h m n d ( e r 定理) 设在问题( 1 3 1 ) 中为可行点，i = ( i l c , ( x ) = o ，和q 0 ，) 在x 可微，q ( 岳，) 在点矿连续，乃d = l ，z ) 在矿连续可微 如果矿是局部最优解，则存在0 = 1 ，z ) 和非负数的数w ( ) ，使得 1 w 一v q + ) w i 一v h , ( x ) 吩= 0 i c l j = l 证明见文献【7 】 有上述定理知，在最优解处，目标函数的梯度可用起作用约束梯度的非负线 性组合及等式约束梯度的线性组合来表示 上述条件可等价的写为以下形式： ml v y ( x + ) 一v q ( z + ) 毗一v h j ( x + ) v j = 0 ， ( 1 舢) i = l j = l 训i 臼 ) = 0 ，i = 1 ，m ( 1 3 3 ) 称为互补松弛条件 一阶必要条件的等价形式二： v 。l ( x + ，w ，v ) = 0 ，( 1 3 4 ) c ；i 0 ) 20 ，i = 1 ，m ， h i ( x ) = 0 ，i = 1 ，1 ， w ic i ( x ) = 0 ，i = l ，- ，仇 毗0 ，i = 1 ，一，m 第一章引论7 1 3 3 二阶最优化条件 局部最优解的二阶必要条件和充分条件： 定义1 3 8 设矿是k k t 点，w i + ，喀0 = 1 ，m ，j = 1 ，f ) ，是相应的l a g r a n g e 乘子，如果存在序列呶( 自= 1 ，2 ，) 和如 0 ( k = 1 ，2 ，) ，使得 茁+ + 6 k d s s 一 2 l q ( z ) 0 ，( 2 ) = 0 ，i 一1 ，m ，j = 1 ，一，1 ) 且有以一0 和民一0 ，则称d 是在。+ 处的序列零约束方向在z + 处的序列零约束 方向的集合记为s ( 矿，w + ，矿) 定理1 3 9 设矿是问题( 1 3 1 ) 的局部最优解，岛0 = 1 ，m ) 币 f l h j ( j = 1 ，z ) 二阶连续可微，并存在满足一阶必要条件的l a g r a n g e 乘子w = ( w 一， 眦。) r ，u = ( v l ，研) 7 ，则必有 d r v ：。l ( z 4 ，t 矿，口+ ) d 0 ，v d s ( z 4 ，w + ， + ) 其中l ( z ，w ，口) 是l a g r a n g e 匪i 数 证明参见文献 1 】、【7 等 通过这个定理给出了约束最优化的二阶必要条件在给出充分条件之前先 给出一个线性化零约束方向的定义 定义1 3 1 0 设矿是k k t 点，嵋， i 0 = 1 ，m ，j = 1 ，f ) ，是相应 的l a g r a n g e 乘子，如果存在d 满足 d r v c i ( x + ) 三0 ，i = 1 ，m a c v h a z + ) = 0 ，j = 1 ，2 ， w i d r v c t ( x ) = 0 ，v i ，( 矿) 则称d 是在。+ 处的线性化零约束方向在x + 处的线性化零约束方向的集合记 为g ( ，叫+ ，矿) o f f k d k p d+o q l 砒 m 渊 第一章引论 8 定理1 3 1 1 设矿是k k t 点，w i ，嵋0 = 1 ，m ，j = 1 ，f ) ，是相应 的l a g r a n g e 乘子如果 d t v ：。三( z + ，w + ， + ) d 0 ，v d g ( z + ，埘+ ，v + ) 其中三( z ，w ，v ) 是l a g r a a g e 函数，w = ( w i ，。) 7 ，v = ( v i ，v 1 ) t ，则。+ 是局 部严格极小点( 证明可参见文献 1 】、1 7 1 、【8 】、1 9 】等) 以上k u h n t u c k e r 定理告诉我们：一个规划问题的最优点乃是它的l a g r a n g e 函数的稳定点定理1 3 1 1 告诉我们：如果( 牙，口，2 ) 是l a g r a n g e 函数的驻点，则骨 是规划问题的最优解，而由驻点定义知，牙是l a g r a n g e 函数对某组给定的w ，口的 关于。的极小点这样我们希望通过求l a g r a n g e i 函数的极小点来求解原来的问 题 1 4 最优化结构 最优化方法是通常采用迭代方法求它的最优解，其基本思想是：给定一个 初始点z o r ”，按照某一迭代规则产生一个点列口女，使得当。是有穷点列时， 其最后一个点是最优化模型问题的最优解当x k 是无穷点列时，它有极限点，且 其极限点是最优化模型问题的最优解 最优化方法的基本结构是： 给定初始点 ( a ) 确定搜索方向以，即依照一定的规则，构造，在x k 点处的下降方向作为 搜索方向 ( b ) 确定步长因子a ，使得目标函数值有某种意义上的下降 ( c ) 令 x k + 1 = o k + o ：k d k ， 若x k + l 满足某种终止条件，则停止迭代，得到近似最优解z k + 1 否则，重复上述步 骤 从基本结构上可以看出，存众多优化算法中，不同之处在于，搜索方向毗和 步长因子a k 的选取方式不同一个好的算法应具备的典型特征为：迭代点g j k + 1 能稳定的接近局部极小点矿的邻域，然后迅速的收敛于x 4 当给定的某种收敛 准则满足时，迭代即终止在本文提出的新算法中即证明迭代点列z k 的聚点( 即 子序列的极限点) 为一局部极小点 第一章引论9 在算法终止的众多判断标准中，较为实用的是要求i ，( 。k ) 一f ( x k + 1 ) i e 或0o 女一z k + 1 | l e ，但这种终止准则仅局限对于一些预计会有较快收敛性 的算法是比较理想的；或利用阶导数信息，采用如下的准则：i l 鲰0 e 其 中g k = g ( ) = v ，( z k ) 但由于临界点可能是鞍点，因此，有些情况单独使用该 准则是不适当的其中参数e 由使用者提供而在本文的算法中，我们将两个准 则相结合，扬长避短 第二章最优化中的内点法 内点算法，顾名思义指的是每个迭代点都是某个区域内的点的算法 2 1 线性规划中的内点法 优化界乃至整个科学计算领域在8 0 年代最轰动的是k a r m a r k a r 算法的提出 k a r m a r k a r 算法是求解线性规划的一个利用投影的内点算法，它在1 9 8 4 年被提出 后立即受到了广泛的注意，纽约时报、华盛顿邮报等美国重要报纸都在醒 目的位置报道了这一成果 线性规划问题是在线性等式或线性不等式的约束下求一个线性函数的极小 值，它相当于求一个凸多边形的最高的顶点传统的求解方法是单纯形法，沿着 棱边从一个顶点爬到另一个更高的相邻顶点，直到达到最高点单纯形法在大 量的实际应用中是非常有效的，但可以构造出例子说明其不足之处是，单纯形法 计算所有的顶点后才能找到最优点由于顶点的个数是随着问题的规模增长而 指数增长的，因此单纯形法的复杂性是指数的也就是说，利用单纯形方法求解 线性问题，在最坏的情况下所需的时间将随着问题规模增长而以指数增长是 否存在和能否找到计算时间仅以多项式速度增长的方法，自然就引起了不少专 家的注意 1 9 8 4 年，贝尔实验室的nkk a r m a r k a r ，提出了一个求解线性规划问题的内 点算法，这是一个多项式时间的算法该算法不仅具有很好的理论性质，而且在 实际计算中也表现良好由于代数线性方程组也可以看成是一个特殊形式的线 性规划问题，几乎所有的科学计算问题最内层的迭代都是求解线性规划问题这 种算法不同于单纯形算法，每次迭代不是从个极点出发求一个改进的极点，而 是使迭代点保持在可行域内部因此是一种内点算法其基本思想是，给定一个 可行内点，对解空间进行变换，使得现行解位于变换空间众多细胞形的中心附 近，然后是他沿着最速下降方向移动，求一个改进的可行内点，再作逆变换，将 交换空间中求得的点映射回原来的解空间，得到新的内点重复上述过程，直到 求得满足精度要求的最优解 k a r m a r k a r 算法的提出，掀起了研究线性规划内点法的热潮，目前内点算法 第二章最优化中的内点法 1 1 已成为线性规划研究的主流如何探讨将单纯形方法与内点有机的结合，可能 是线性规划方法突破的途径由此在非线性规划问题中内点法的推广显得不可 回避，从理论上可证明k a x m a r k a r 算法在定意义下是一个特殊的基于对数罚函 数的内点罚函数方法从事非线性优化研究的人员都知道，利用罚函数方法求 解约束优化问题并不是很好k a r m a r k a r 方法成功地告诉我们，一些在一般情况 下不好的方法可能对某类特殊问题非常有效，因此不可以忽略那些“不好”的算 法内点算法也促使人们重新认识传统的罚函数，进一步深入研究罚函数 通过对线性规划中的内点法的介绍，最后指明把内点法推广到求解非线性 约束问题中也可以有较好的应用，下面针对于非线性约束问题讨论内点法的具 体应用 2 2 罚函数 作为解决约束优化问题方法之一的罚函数法，主要作用表现在将约束问题 转化成无约束问题来讨论最初是出f i a c c o 和m c c o r m i c k 在文献3 1 】提出，而当 时只是针对于线性规划问题因而与当时风头正劲的对偶单纯形相比，显得没有 太大价值随着软件的更新和算法的改进，人们开始着手解决非线性优化问题， 从而人们又开始重拾对罚函数的兴趣，在将它推广到非线性优化问题的过程当 中，出现了一系列的难题，而这些问题之间又是层层相扣的研究过程人们发现， 罚函数法在解决大规模优化问题方面，有着其它算法不可比拟的优点，正是由于 这一点，吸引了更多的研究人员加入到罚函数在非线性约束问题上应用的研究 目前这些研究还是不够完善的，但研究表明该方法值得更进一步的探讨和研究， 使他能够在实际问题中发挥作用 2 2 1 罚函数的一般形式 考虑问题( 1 3 1 ) r a i n ，( z ) q ( z ) 0 ，i = 1 ，一，m ， 岛x ) = 0 ，j = 1 ，- 一，z 其中， 乃，c ：r “一r ( i = 1 ，们，j = 1 ，z ) ，都是舻上的连续函数 第二章最优化中的内点法 1 2 罚函数的基本思想是，利用目标函数和约束函数组成具有“罚性质”的函数 f ( z ，口) = f ( x ) + a p ( x ) ( 2 2 1 ) 所谓的“罚性质”，即点。位于i j 丁行域外时，函数f ( x ，口) 取值很大，而且离可 行域越远其值越大；当点z 位于_ 口j 行域内时，函数f ( x ，口) = ，( z ) 这样，可将原 问题转化成为关于辅助函数f o ：，o - ) 的无约束极小值问题： 在极小化的过程中，若x 不是可行点，则辅助函数中的f f p ( x ) 取很大的正值 其作用在于迫使迭代点靠近可行域，因此，求解问题( 2 2 2 ) 能够得到约束问 题( 1 3 1 ) 的近似最优解，而且，口越大，近似程度越好，通常将a p ( x ) 称为罚项， 盯称为罚因子，f ( x ，口) 称为罚函数 实际计算中，罚因子的选择很重要如果太小，则罚函数的极小点与实际问 题最优解有较大差距由于简单罚函数法比较简单，使用灵活，在许多实际问题 的应用中能够奏效，因此它在约束最优化方法中是一个较为常用的方法简单 罚函数法也有它的不足之处，文献f 9 】给出分析结论，大致可以把简单罚函数法 的缺点总结如下： 一、反复进行的无约束极小化过程罚因子盯要求是一个非常大的量，而 在反复迭代的过程中，简单罚函数要求o - k 是一个趋向于无穷大的序列，对于 每一个盯k 越大，罚函数f ( x ，吼) 的函数值就越大除了上面提到的引起罚函 数f ( ，o k ) 值上溢之外，还是问题失真的主要原因之一对于内点罚函数来说， 由于约束最优化的最优解往往是约束集合的边界上达到的，迭代中又不能让迭 代点超出边界，所以罚因子盯k 越大，说明迭代点越靠近边界，无约束极小化的步 长也就要越小，这样就造成了在无约束最优化过程中过大的工作量 二、无约束极小化的困难一般无约束极小化算法用于简单罚函数方法上 都有一些困难，而且以越大，表现的越为严重不可避免的发生的困难有，在使 用内点法且a 很大时，迭代点容易跳出约束集合的边界，而f ( o ，盯k ) 在边界外足 没有定义的即使采用一些边界处理手法，有时很难保证求出新点的目标函数 值比前面的点的目标函数值小因此无约束极值的一维搜索方法往往要引起麻 烦的另外，不管内点法还是外点法迭代点在临近约束集合边界时，f ( o ，吼) 的 值变化很快，这时用各类约束极值方法都要发生困难，特别是理论分析上所遇到 的困难更大 第二章最优化中的内点法 1 3 三、另一个本质性的困难是目前无约束极值算法的理论基础基本上是函数 的泰勒展开式取二次式但当盯取值很大时，极小化函数的的h e s s e j 眶阵往往是 病态的，这就造成了在无约束极值算法上的困难 2 2 2 乘子罚函数 为了克服这些困难，人们在p o w e l l 罚函数方法的基础上作了一系列工作为 了有别于一般简单的罚函数法，我们称之为l a g r a n g e 乘子罚函数法 首先介绍等式约束下的增广l a g r a n g e 乘子法 等式约束问题为 m i nf ( x ) ( 2 2 3 ) s t h j 0 ) = 0 ，j = 1 ，f 其相应的l a g r a n g e 函数形式 l ( x ，y ) = ，( z ) + 九( 。) 7 y ， 其中 ( 。) = ( h i ( z ) ，h i ( 茁) ) t ，y r 。，相应的增广l a g r a n g e 乘式定义为 于是我们用求解约束最优化问题 来代替求解约束最优化问题( 2 2 3 ) 定理2 2 1 无约束最优化问题 m i n 垂( z ，o k ，y k ) o k 0 ， 的最优解o + 是约束优化问题 m i n f ( x ) s t b ( z + ) = 0 ，j = 1 ，f 刃 ：芦 2 盯 + 鲈 z厶 j j 掣 盯。垂 。 幻 。硝 2 盯+ 可 zl = 鲈 盯z圣nm 第二章最优化中的内点法1 4 的最优解( 证明见文献【1 】，【7 ，f 8 】) 下面介绍不等式约束条件下的增广l a g r a l l g e 乘子罚函数法 不等式约束问题为 m i nf ( x ) ( 2 2 ，4 ) s t 只要引进m 个非负变量s l ， g 如) 0 ，i = 1 ，一，m ，s 。，问题( 2 2 4 ) 就可以写成是 m i n ，( z ) s t c i ( z ) 一s i = 0 ，i = 1 ，m ， 而此时问题就转化成等式约束问题，我们便可以得到以下l a g r a n g e 乘子式 m m i n f f ( x ，刚) = f ( 叩，可) + 口2 ( q ( 。) 一岛) 2 t = 1 其中l a g r a n g e 函数2 ( 。，s ，y ) = f ( x ) + 銎1 ( g ( 。) 一s ) 了1 y i ，z 印，s ，y 兄m 2 。3全局性的内点法的一般形式 2 3 1 优化中的牛顿迭代法 考虑问题 m i n ，( z ) 若目标函数在开凸集上是连续的，一般可以将问题转换为求解其一阶导数的零 点 g ( x ) = v ，( z ) = 0 从而最优化问题转化成了方程求解问题，面在方程数值求解方法中牛顿迭代法 具有局部收敛快的特性，因此在优化算法中也是多有涉及 进一步将牛顿法推广到约束优化问题中 考虑问题( 1 3 1 ) r a i n ，( z ) q ( 。) 0 ，1 = 1 ，m ， 第二章最优化中的内点法 1 5 ( ) = 0 ，j = 1 ，f 其中，臼，h j ：舻一r ，i = 1 ，m ，j = 1 ，f ，都是舻上的连续函数其相 应的l a g r a n g e 函数为上( z ，y ，。) = ，( z ) 一墨1 岛( 。) 兹+ ：；1y j 吩( 。) 在满足第一章姐3 节中最优化一阶、二阶等充分必要条件下，问题( 1 3 1 ) 最 优解的求解转化为求解其k k t 点，也即求解方程 v 。t ( x ，y ，。) l 尸( z ，y ，。) = i ( z )i = 0 ， le ( 咖j ( c ( z ) ，2 ) 0 ， 其中，v 。f ( 茁，z ) = v ，( z ) + v ( ) 掣一v c ( ) ：， ( z ) = ( h i ( 茁) ，h ( z ) ) 7 ， c ( x ) = ( c l ( z ) ，c 。( z ) ) 7 ，c ( x ) = d i a g ( c l ( x ) ，c 2 ( 。) ，c 。( z ) ) 而方程 f ( x ，y ，z ) = 0 ， 可以通过牛顿迭代法求出在迭代点的下降方向如 但由于考虑到在对该k k t 方程f ( x ，y ，z ) = o 用牛顿法求解的过程中，当迭 代点为边界点时，可能会出现病态矩阵，致使近似解失真为了避免这一问题的 出现，我们在此引入一个扰动量p 0 ，使迭代点离开边界，保持为内点迭代，则 得到以下的扰动k - k t 方程 v 。z 如，y ，z ) h ( x ) g ( z ) z 一肛e 0 ( c ( o ) ，z ) 0 其中v 。f ( 。，y ，z ) = v f ( x ) + v h ( x ) y w ( z ) z ，c ( x ) = d i a g ( c l ( x ) ，( z ) ) ，e = ( 1 ，1 ) t 当弘趋向于0 时，该扰动k k t 方程得到的解。：近似于原k k t 方程的解 但牛顿法的局部性限制了它在实际问题中的应用，该算法不具有全局性， 也即意味着对于初始点的选取有严格要求它要求初始点非常靠近极值点时， 迭代过程才能得到较为精确的近似解，算法才有意义而在实际应用中，我们时 常是无法预测精确解的位置的，这一点是牛顿法难以独立存在的原因 第二章最优化中的内点法 1 6 2 3 2 约束优化中的牛顿内点法 为了寻求一种既具有全局性又快速收敛的算法，在近些年里将牛顿法、 罚函数等相结合的内点算法相继出现，并显示出其不可忽视的作用这也 是k a r m a r k a r 算法热点问题的后续将具有快速收敛性的牛顿法用来求解下降方 向，将具有全局性的内点罚函数法用来判断步长因子，从而完成了的优化算法表 现出较强的理论性的同时，也被采用在解决实际问题中 这类优化算法的基本思路如下： 首先将k k t 司题的求解，通过引入扰动变量卢，转化成扰动k k t 方程的求 解 对于方程 兄( 。，y ，o ) = 0 ， 用迭代式 v b ( z ，y ，z ) = 一昂( z ，y ，z ) ， 其中 = ( z ，a y ，a z ) ，求得的 即为所求的下降方向 接下来足确定步长因子口通过引进一个具有罚函数性质的增广函 数钆( 。，y ，。) ，每一迭代过程中确定。使其满足 壬p 扣+ n ) 垂p 扣) + 0 v ( i ) p ) 丁a v ， 其中 = ( x ，y ，z ) ，p ( 0 ，1 ) ，由口和a ，从而确定了下一个迭代点z 女+ l = z 女+ o 女仉 第三章新的全局性内点算法 3 1引言 由2 2 3 中介绍的内点牛顿法，已成为当今非线性约束优化领域的个热 点在文献【4 】及【2 4 】_ 【3 1 】的基础 ：，如何将内点法在非线性优化问题中的应用形 式具体化成为了一个讨论点其中一个论文方向表现在对于增广函数的选取上 以下提出的新的算法也是在原先已有的众多思想和增广形式中，寻找一种较好 的组合方式，使算法在满足较为精确的同时，也能较为简便、实用在该篇论文 中，将牛顿法、内点法及互补条件下求极值的知识相关结合，给出另一种具体形 式的增广函数，提出了不同于文献 3 l 、 4 i 中提出的算法及【2 j 中总结的已有的牛 顿内点法的全局性新算法由于该算法减少了不必要罚因子参数的讨论，在理 论上表现的更加简便 3 2 新牛顿内点法 考虑约束问题 r a i nf ( x ) ( 3 2 1 ) s t c ( x ) 0 ， h ( x ) = 0 ， 其中，：r n r ，c ( x ) = ( c l ( z ) ，c 。( 。) ) t ，h ( x ) = ( h i ( x ) ，t l ( ) ) 7 ，c ，h j ： 邸一r ，f ，q ，h j0 = 1 ，m ，j = 1 ，z ) ，都有连续_ 阶偏导数 问题( 3 2 1 ) i 掏l a g r a n g i a n 函数 l ( x ，y ，z ) = f ( x ) j - ( 。) t y c ( 。) t 。 其中y r 2 ，z 其k k t 条件为： f ( x ，y ，z ) = v 。f ( z ，y ，z ) h ( x ) g ( z ) z = 0 第三章新的全局性内点算法 1 8 ( c ( 。) ，z ) 0 ， 其中v 。z ( 。，y ，z ) = v f ( x ) 一v c ( 。) + v h ( x ) z ，c ( x ) = d i a g ( c l ( z ) ，- - ，c h ( z ) ) 根据1 3 中提出的约束最优化一阶、二阶必要条件和二阶充分条件，推出以 下的的充分条件： 3 2 1 一阶、二阶假设前提条件 ( a ) 问题( 3 2 1 ) 存在一个最优解矿 ( b ) v 2 f ，v 2 砖，v 2 q 0 = 1 ，m ，j = 1 ，f ) ，在矿的某个邻域内满足l i p _ 一s c h i t z 连续 ( c ) ( v h l ( x + ) ，一，v h l ( x + ) ) u v q ( z ) ：i ，) ，i = i ：q ( 。+ ) = o ) 是线性 无关的 ( d ) 任取目( r ”) 0 ，”满足 v h j ( x + ) 7 叩= 0 ，j = 1 ，2 ， 、t c d x + ) r 口= 0 ，i i ，i = i ：q ( 。+ ) = 0 ) ， 有 矿v 挈( z 4 ，y + ，矿) 叩 0 ( e ) c f ( 矿) + 芎 0 ，i = 1 ，一，m 在满足以上的一阶、二阶的充分条件下，则有k k t 点一定是问题( 3 2 1 ) 的 最优解充分性证明见4 1 在2 3 中我们提到了为了避免边界点处牛顿迭代法无法正常进行，可通过 引入一个扰动变量肛( o ) ，将求解k k t 点转化为求解扰动k k t 点，在该算法中 我们也将引用该扰动变量，进行转化处理 在对k k t 条件中的互补条件c ( z ) 7 z = 0 ，( c ( z ) ，z ) 0 讨论中，引入扰动一 k k t 条件 兄( z ，y ，2 ) = v 。f ( z ，y ，z ) h ( x ) c ( x ) z 一“e = 0 ，( 3 2 2 ) 第三章新的全局性内点算法 1 9 其中，c ( x ) = a i a g ( c l ( x ) ，c 。( z ) ) ，e = ( 1 ，一，1 ) r 胛 其另一种等价形式为 兄x ，y ，z ) = f ( x ，y ，z ) 一p e ( 3 2 3 ) 由( 3 2 3 ) 可知，当p 一0 时，以( z ，y ，z ) = 0 的求解近似于对f ( z ，y ，z ) = 0 的求 解 3 2 2 非线性问题中新的增广函数 首先考虑方程( 3 2 2 ) 中的互补性问题 g ) z p e = 0 ， ( c ( z ) ，2 ) 0 其中p 0 ，g ( z ) = d i a g ( c l ( z ) ，( z ) ) 7 ，e = ( 1 ，- ，1 ) 7 在文献 2 1 e e , e , 结了最优化问题中互补性问题的诸多方法的讨论，在此我们 引入其中一种近似逼近方法，即将上述互补性问题转化为如下问题： 性质3 2 1 给定参数p 0 ，若( c ( 。) ，。) 0 ，函数吼( z ，。) 有下界，其全 局最小值为 妒( 1 1 n 肛) 且当o 0 ， + g ( 枷) = 一t l n ( w ) 的全局极4 、点为= t ，则岛( 。) 荔= 肛时，q ( z ) 盈一 l n ( c i ( 。) 盏) 达到最小，从而q ( z ) 盈= p 0 = 1 ，m ) 时，兰l ( 白( z ) 磊一l n ( c i ( x ) z i ) ) 达到最小 _ 在g ( z ) z = “e 时吼( 。，z ) 达到最小值 口 ( z ，z ) 将作为我们的增广函数的一个组成部分，其作用是使迭代点在某一 区域内 42 z q n 力m 试 q 肛 “ 一 妒 = n t m c = 力 o p妒 第三章新的全局性内点算法 2 0 下面给出新增广函数的具体形式 定义3 2 2 给定参数“ 0 ，定义新的增广函数如下 叽：口“”制_ r ， 西。0 ，y ，。) = 1 2 1 1 a ( , c ，y ，z ) t l i + 妒p ( 。，= ) ， ( 3 2 5 ) 铷( 叩) = c ( z ) 7 z 一弘l n ( 臼( 。) 麓) ， g 舭卜 乳嚣 慨。脚 已知( z ，y ，2 ) 在( 。，y ，z ) t 内有意义，这里 t = ，y = ( z ，y ，。) r “尉r “：( c ( 。) ，z ) o ) 为了方便引用我们在此称t 为内点域可见在内点域t 内点v = ( 。，y ，。) 处 有a ( z ) _ 1 存在，其中e ( 。) = d i a g ( c l ( x ) ，c m ( 石) ) 在内点域t 内分析( 。，z ) 的偏导和关于z 的h e s s i a n 矩阵： v 。妒“( 。，z ) = c ( x ) 一p z 一1 e ， v 。礼( z ，z ) = v c ( 茁) ( z p g 一1 ( 口) e ) ， v 扣i 篙；涔1 1 v 。2 吼( z ，。) = v 2 q ( 茁) 慨一p q ( z ) _ 1 ) + p v c ( 。) g ( 。) 。v c ( z ) r 其中，z = d i a g ( z 1 ) 一，z m ) ，g ( 。) 以= d i a g ( o ( x ) ，( 。) 。) 在内点域t 内的点”= ( x ，y ，z ) 处有 v 。虬( ) = v a ( x ，y ，z ) a ( x ，y ，z ) + v 。钆( z ，z ) = v ：f ( 口) v 。l ( v ) + v h ( x ) h ( x ) + v c 扣) 0 一肛a 一1 ( 。) e ) 下面讨论该增广函数的极值点与满足扰动方程( 3 2 2 ) 的扰动k k t 点吃= ( z ：，啦，。：) 之间的关系 定理3 2 3 给定参数p 0 若呓= ( ，啦，) 满足扰动k k t 条件( 3 2 2 ) ， 则有岱：是西。( z ，啦，) 的驻点 第三章新的全局性内点算法 证明垂，在( 。，啦，2 ；) 点关于。的偏导 v z ( $ ，：，z ：) = v ：2 0 ，虻，z ：) v 。l ( x ，虻，) + v ( z ) ( z ) + v c ( z ) ( 一肛e 。如) e ) 因为z ：满足扰动k k t 条件( 3 2 2 ) ，也即 h ( x 4 ) = 0 ，c ( x + z + = p e ，v m z 0 + ，虻，) = 0 ， 则有 v 西。( 吒) = 0 口 定理3 2 4 给定参数芦 0 ，屹= ( ，鲸，) 满足扰动k k t 条件( 3 2 2 ) ， 若f ( z ，y ，z ) 在的某个邻域内存在三阶偏导，则圣。( 。，y ，z ) 在吒= ( z ：，啦，) 点 关于z 的h e s s i a n 阵是正定的 证明中p ( g ，y ，2 ) 在吒= ( z ：，啦，) 点关于。的h e s s i a n 阵是 v ：西。( 呓) = v ( 吒) v 。z ( ”：) + v ：j ( 屹) v ：l ( 呓) 7 + v h ( z ：) v ( 茁：) t + v ： ( ) ( 。：) + v 2 t 、x p * ，苟) = v ：f ( 吒) v 挈( 吒) t + v ( z