（计算数学专业论文）约束非线性规划问题的一种降维算法.pdf

重庆大学硕士学位论文中文摘要 摘要 本文讨论了约束非线性规划问题的降维算法及最优化算法在实际问题巾的 应用，为非线性规划算法的研究提供了一种新的途径。首先本文利用李泽民教 授提出的k u h n t u c k e r 条件的降维形式，通过求解非线性方程组获得非线性等 式约束优化问题的k t 点，完善了等式约束舰划问题的降维算法。其次，在等 式约束降维算法的基础上，结合起作用集策略，本文分别给出了一般不等式约 束非线性规划和线性约束非线性规划的降维算法，并对算法的收敛性进行了研 究，给出了一定条件下算法的收敛性证明。鉴于目前对一般的非线性舰划闷题 还没有一个通用的算法，降维算法的提出为非线性规划问题的求解提供了一种 新的途径。再次，文中对提出的不同类型规划的降维算法都进行了数值实验， 与既有的算法相比较，结果具有较高的精确度，显示了算法的可行性与有效性。 最后，我们对工程设计和资产配置中的实际问题通过建立数学优化模型并进行 求缁，其中用降维算法对资产配置模型进行求解，对最优化方法在实际领域中 的应用进行了较为深入的研究。 关键词：等式约束，不等式约束，线性约束，非线性j ；! i l 划，降维算法，应用研究 重庆人学硕【学位沦文 a b s t r a c t i n t h i st h e s i s ad e s c e n d i n ga l g o r i t h mf o rt h ec o n s t r a i n e dn o n l i n e a rp r o g r a m m i n g p r o b l e ma n da p p l i c a t i o n so ft h eo p t i m i z a t i o nm e t h o di nf a c t u a lp r o b l e m sa r ed i s c u s s e d ， a n dw eo f f e ran e ww a yt or e s e a r c hm e t h o d so fn o n l i n e a rp r o g r a m m i n gb yt h a t ，f i r s t l y , w eg e tt h ek tp o i n to ft h en o n l i n e a rp r o g r a m m i n gp r o b l e mw i t he q u a lc o n s t r a i n sb y s o l v i n ga ne q u a t i o n sb yt h ed e s c e n d i n gf o r mo ft h ek u l m - t u c k e rc o n d i t i o n ，a n dt h e d e s c e n d i n ga l g o r i t h m f o rt h e o p t i m i z a t i o np r o b l e m w i t he q u a lc o n s t r a i n si s c o n s u m m a t e d ；s e c o n d l y , o nt h eb a s i so ft h ed e s c e n d i n ga l g o r i t h m ，i ts e p a r a t e l yo f f e rt h e d e s c e n d i n ga l g o r i t h mf o rt h eg e n e r a ln o n l i n e a rp r o g r a m m i n gw i t hu n e q u a lc o n s t r a i n s a n dt h en o n l i n e a rp r o g r a m m i n gw i t hl i n e a rc o n s t r a i n sc o m b i n e dw i t ha c t i v e s e ts t r a t e g y e l s e ，t h ec o n v e r g e n c eo ft h e s ea l g o r i t h m si sa l s od i s c u s s e d ，a n dt h ec o n v e r g e n c er e s u l t s u n d e rc e r t a i nc o n d i t i o n sa r eg i v e n c o n s i d e r i n gt h a tt h e r ea r en og e n e r a lm g o r i t h m sf o r t h en o n l i n e a rp r o g r a m m i n gp r o b l e m ，t h ed i s c u s s i o ni nt h i sp a r to f f e ran e ww a yt o r e s e a r c hi t t h i r d l y , n u m e r i c a lt e s t sa r eg i v e nf o re v e r yk i n do f t h ed e s c e n d i n ga l g o r i t h m ， c o m p a r i n gw i t ht h ek n o w na l g o r i t h m s ，t h er e s u l t ss h o ws a r i s 聊n gp r e c i s i o n , s ot h e a l g o r i t h mi s f e a s i b l ea n de f f e c t i v e f i n a l l y , w es e tu pt h eo p t i m i z a t i o nm o d e l sf o r e n g i n e e r i n gd e s i g na n dp o r t f o l i oa l l o c a t i o na n ds o l v et h e m ，t h e r e i n t ow es o l v et h el a g e r b yb o t ht h ed e s c e n d i n ga l g o r i t h ma n ds q p , s ot h ea p p l i c a t i o no fo p t i m i z a t i o nm e t h o d s i nf a c t u a lp r o b l e m sa r er e s e a r c h e di nc e r t a i nd e e p n e s s k e y w o r d s ：e q u a lc o n s t r a i n t ，u n e q u a lc o n s t r a i n t , l i n e a rc o n s t r a i n t ，n o n l i n e a r p r o g r a m m i n g ，d e s c e n d i n ga l g o r i t h m ，a p p l i c a t i o nr e s e a r c h ， i t 重庆人硕士学伉论文 1 绪论 i 1 非线性规划理论与算法研究现状概述 非线性规划是计算数学和运筹学交叉的学科，对非线性规划模型的研究源于实 际生活中对问题进行更为精确的描述并解决的迫切需要。非线性规划理论是基于 线性规划理论发展起来的，自上世纪4 0 年代人们获得求解线性规划问题的单纯形 法之后，线性规划在理论上日趋成熟，并在实践中获得广泛的应用，然而随着社 会各个方面的发展，许多实际问题用线性规划理论建立模型并解决的效果并不好， 这种情形促使科学研究转移到非线性领域。近几十年来许多专家和学者为有效地 求解非线性规划问题付出了艰辛的探索，促使非线性规划理论不断成熟和完善。 对非线性规划算法的研究主要集中在如何提高算法的效率以及扩大算法的适用范 围。按数学空间划分，理淦上可将非线性理论的研究分为有穷维优化和无穷维优 化，由于现实条件的限制，目前已经实现的大多数非线性规划算法只限于有限维 空间，而且相应的理论也比较成熟。在无穷维空问上，随着许多优化学者和专家 的深入研究，这方面的研究成果不断涌现，将很多有限维空间的理论推到无穷 维空间。 1 1 i 非线性规划理论研究现状 向量优化、集值优化及其对偶理论是目前优化领域理论研究的三个重要课题。 向量优化又称为多目标规划，其涉及的范围卜分广泛，目前对向量优化问题的 理论研究大致有以下几个方向：一是关于向量优化问题解的概念及性质，相对于 单目标规划，解的定义对求解多目标觌划问题有更重要的意义，目前为止，关于 多目标规划解的概念有影响的已不下2 0 种，而对每一种解都可以讨论它的一些性 质，如存在性、最优性条件、连通性、稳定性及解之间的关系等，关于这些问题 的研究，具体可参考y h w a n 、j b o r w e n 、j g l i n 及陈光亚等在这方面的文章；二 是多目标规划的对偶问题，关于这方面的成果出比较丰富，t a n i n o 、e e r o s i n g e r 及林锉云等国内外学者对l a g , r a n g e 对偶、共轭对偶和多目标规划问题的对称对偶 和自身对偶进行了大量研究，引起了这一领域学者的重视：另外不可微多目标规 划的研究也比较活跃，自二十世纪7 0 年代非光滑函数广义梯度的研究开始，非光 滑分析已经成为优化领域的一仑重耍研究方向，只是由于j 义梯度是一个集合， 无法具体计算，使这方面的研究还只停留在理论阶段。 集值优化问题主要研究集值分析学及其在最优化中的应用。随着优化领域对广 义凸性及择定理、最优性条件等问题的研究，许多有限维空间的结论在集值优 化问题中得到了广泛的推广。一方面，用研究向量优化闽题的方法研究集值映射 重庆人学硕! f ：学位论文 绪绝 的最优化问题；另一方呵将集值分析学与优化问题相结合，使集值优化问题成为 联系不同领域优化问题的桥梁，将最优化理论在一定程度上达到统一，使之标准 化。集值优化正在成为优化领域较为活跃的研究课题之一，关于这一课题的研究 有大量成果，具体可参见c o r l e y 、a u b i n 及陈光亚、李泽民等国内外学者的有关文 童。 对偶理论是最优化理论研究的重要组成部分，其主要研究一对规划问题之间的 重要关系，它对原问题的求解以及最优性条件的揭示都有重要作用。自二l 世纪 7 0 年代开始进行这一领域的研究，研究对象从线性规划发展到非线性规划，从单 目标问题扩展到多目标问题乃歪集值映射优化问题，对偶理论一直是优化领域的 一个主要研究课题，同时由于对偶性有其客观存在的实际背景，在实际问题中有 重要应用价值。由于对偶理论不局限于数学空间，所以对这一领域的研究通常足 与具体优化问题相联系的，而且对偶理论进一步又可划分为l a g r a n g e 对偶、共轭 对偶等，因而对偶理论的研究成果也相当丰富，具体可参见t a m m i n e n 、b r a n d a o 及林锉云、董加礼等学者的有关著作。 1 1 2 非线性规划算法研究现状 对最优化算法的研究历来是优化领域研究的重要课题，是最优化理论应用价 值的直接体现。 是关于最优化算法的专业性刊物，主 要介绍各种最优化模型算法的最新进展， 、( a p p l i e dm a t h e m a t i c sa n do p t i m i z a t i o n 、 等刊物也经常有关于最优化算法研究的大量文章，体现 了这一领域研究的活跃，也促进了最优化算法的发展，而非线性规划算法作为最 优化算法的主要构成部分，也吸引了很多学者的关注。其中价值函数的选择、迭 代方向的确定以及算法的收敛性是非线性规划算法研究的三个重要课题。 价值函数的研究是非线性规划算法研究的一个重要分支，由于大多数非线性 规划算法属于迭代算法，在算法的迭代过程中需要评价每一迭代点的优劣，所以 在算法中需要引入评价函数( 也可称为罚函数) ，不同的罚函数有不同的性质， 从而对算法的效果也有不同的影响。文献 1 1 研究了精确罚函数与极小极人问题的 关系，表明极小极大问题的鞍点是精确罚函数的解。由于价值幽数中罚因了的影 响，一些学者也尝试选择其它策略替代罚函数，f l e t c h e r , l e y f f e r 在 4 1 中研究了一 种不需要罚函数的非线性规划算法，通过引入一种筛选n ( f i l t e r ) 概念来决定迭代 点的取舍，并结合信赖域法给出了算法的框架及算法的全局收敛性证明结果。 迭代方向的确定是非线性规划算法的主要步骤，很多算法的区别就在于这一 环节，如无约束优化算法比较常见的梯度法、共轭梯度法及牛顿法等。p o w e l l 在 文献8 5 1 中比较了目标函数是二：次函数时的b f g s 迭代格式和d f p 迭代格式，说 重庆人学硕士学位论文 绪 仑 明了对于般无约束优化迭代计算b f g s 格式比d f p 格式更有效；对于约束非线 性规划，常常在迭代过程中构造二次规划子问题，并把其解作为迭代方向，由于 序列二次规划在解决大规模问题的优势，因而二次规划子问题的研究成为许多文 章研究的对象。文献 4 0 讨论了基于_ 二次规划子问题的非线性规划算法在子问题构 成及求解等环节的异同以及起作用集策略、l a g r a n g e 乘子估计等问题。 算法的收敛性有局部收敛性和整体收敛性之分，对收敛性问题的研究主要是 研究算法的收敛性结果和减弱算法收敛的条件。s 。r h a n 在文献 3 3 1 中讨论了一种 非线性规划的全局收敛性方法，在原来牛顿法及拟牛顿法局部收敛性结果的基础 上，通过提出一种步长策略以保持精确罚函数的单调下降性，获得了算法的全局 l 改敛性结论；m s a h b a 在文献【8 3 中讨论了一般非线性约束优化闻题的全局收敛性 算法，该方法通过求解线性规划和二次规划问题获得算法的迭代方向，结合一种 新的确定罚因子的方法获得了算法的全局收敛性结论。 对非线性姚划算法的研究还育许多其它的方向，如将非线性规划模型推广，研 究半无穷维规划、非线性多目标规划的算法，步长策略与非线性方程组的关系等， 具体可参见文献 7 9 3 8 6 3 等。 1 2 非线性规划算法综述 非线性规划模型按照目标函数的多少，可分为单目标规划和多目标规划。这两 类规划模型在算法上既有联系又有区别，下面分别作简要介绍： 1 2 1 单目标规划算法 求解单目标非线性规划模型的算法大都属于迭代算法，其中只有一个变量的优 化问题的计算方法是优化方法中最基本的，是多变量问题求解中迭代过程的重要 步骤。而对于多维优化模型，目前在算法上可以分为两类：一类是线搜索( l i n e s e a r c h ) 方法；另一类是信赖域( t r u s tr e g i o n ) 方法。 目前非线性规划算法的研究主要集中在线搜索方法。线搜索方法有两个重要的 环节，一是搜索方向的选取，二是迭代步长的确定，这两个环节的差异衍七出许 多不同的算法。搜索方向的产生依赖于子问题的构造，由此衍生出的方法有梯度 法、共轭梯度法、拟牛顿法、变尺度法等，许多文章对这类问题进行了大量深入 灼研究，立1 1 1 6 、 4 6 、 4 9 、 5 3 等，其中戴在 4 6 q h 对拟牛顿法及共轭梯度法的 研究，提出并完善了b r o y d e n 族、h u a n g 族，在提高拟牛顿法性能的基础上完善了 此类方向的研究。变尺度法具有一些很好的性质，如收敛性等，是无约束优化算 法中比较有效的算法，近来有许多文章将变尺度法与其他方法相结合，形成性能 更好的算法，文献 3 0 l 用效益函数作为约束优化问题的精确罚函数，在精确线性搜 索的前提下，证明了方法的整体收敛性质， 4 6 1 1 4 7 1 对前面的工作又作了改进，建 重庆大学硕j 二学位论文1 绪论 立了新的价值幽数，简化了b f g s 迭代公式；步氏的确定取决于线性搜索的技巧 或评价幽数，这一环节对算法收敛的性质及速度有很大影响，由此衍生出来的方 法有精确一维搜索方法、非精确一维搜索方法和罚函数法等，文献 4 5 、 5 2 等在 这一领域作了大量的研究，提出了一些改进罚函数性质的策略。 信赖域法是一类较新的方法，白上世纪8 0 年代以来有很多文章对这一领域进 行了研究，目前虽然没有线搜索法成熟，但由于其本身具有较强的收敛性和可靠 性，这一问题仍吸引了很多优化专家和学者。上个世纪8 0 年代，文献 6 0 1 将信赖 域法应用到等式约束问题上，借用不可微精确 h 函数证明了信赖域法的整体收敛 性。国内袁在文献 6 i 中对信赖域法进行了较为深入的研究，得出了许多有价值的 结论。另外还有一些文章对信赖域法和其它方法相结合进行研究，得出了一些新 的算法，具体可参看文献 4 1 】等。 1 2 2 多目标规划算法 在实际生产与分配的活动中有许多问题，它们具有多个彼此联系而又矛盾的 决策目标，这些问题的出现促使了多目标最优化问题的产生。多目标规划问题成 为正式学科始于2 0 世纪5 0 年代，由最初研究数量经济问题到关于向量极值问题 的研究，为多目标最优化问题的研究奠定了良好的基础。目前多目标最优化问题 不仪在理论上逐渐成熟，而且在工程技术、经济、管理及系统工程等许多领域获 得了广泛的应用，引起了许多学者和专业人员的重视。 多同标最优化问题是在单目标规划问题的基础上建立起来的，因而在算法上 主要是研究如何建立多目标与单目标问题的联系和如何衡量解的优劣，以及解的 存在性、稳定性等。常见的多目标规划算法有主要目标法、线性加权和法、理想 点法和评价函数法等，下面介绍多目标优化中一个常用的算法一线性加权和法： 线性加权和法是根据p 个单目标函数f ( x ) ( j = 1 2 ，p ) 的重要程度，分别赋 以不同的权重五i ( j = l 2 ，pk 然后简单相加构成单目标优化问题的目标函数，在 多目标优化问题的约束集合r 上求最优解。所构造的单目标问题形式如下： 曾u ( x ) 。荟五，乃( x ) 称此单目标问题的解叫做原多目标问题在线性加权和意义下的最优解。这里 f ( x ) = ( f l ( x ) ，f p ( x ) ) t ，l = ( 旯j ， p ) t + 或a + + ，其中 p ，、+ = z = ( 五，五p ) 1 l 各2 j _ o 且= i 。君 + + = 丑= ( 五l ，五p ) 7 1 各2 i 0 且五= 1 j = 】 a 称为权向量。 4 丑! 废人学硕 ，学位论文 绪论 1 3 非线性规划的应用 非线性规划从二十世纪7 0 年代起就是数学规划中最受重视的分支之一，特别 是通过对变尺度法的研究，涌现出了如p o w e l l 、f l e c t h e r 、d e n n i s 等一批著名的非 线性规划专家。近年束，求解。般非线性规划问题的序列= 次规划f s e q u e n t i a l q u a r d r a t i cp r o g r a m m i n g ，s q p ) 方法的大量成功应用，使非线性规划计算方法成为大 栅模科学研究和工程计算的个疆耍方向，本文第六章介绍了这方面的一个应用。 八卜1 年代初辫i 开始必起的信赖域法进步拓展了非线性规划算法胡研究范围成 为非线性舰曼i 的一+ 个很热门的研究方f _ ，进1 步健进了非线性规划的研究利应用。 金融管理是非线性规划理论应用的个重要领域，随着二 纪5 0 年代以来 现代金融理论的迅速发展，数量化分析方法与金融烈论紧密结合，产生r 明显的 社会效益。证券组合理沦是现代金融理沦的重要成果，其中的编合证券最优化模 型是现代证券理沧的基石，特别是随着国内近年柬基金、l k 的迅速发展，组合证券 模型已经逐步受到吾金融机构的重视，本文第六章介绍了这方面的一个应用。另 外，非线性规划理沧与其它学科柏结合产生的随机最优控制理论、脉冲晟优控制 理论等正成为现代金融理论的发腱趋势，文献 1 9 、 2 3 等介绍了这些方面的些 成果， 经济均衡问题是经济学家和优化工作者共同关注的问题，许多文章都对这一 问题进行研究，以更好地描述市场的行为，有些学者利用l a g r a n g e 乘子法和随机 过程论，研究了非连续价格的市场中投资者的消费，投资模型，推广了b l a c k ，s e h o l e s 公式；另外最优化方法在博弈问题、工程设计、参数优化等领域也有较高的应用 价值。 1 4 本文研究的主要内容及研究途径 对非线性划划算法及应用的研究具自非常重要的实际意义，是最优化理论价 值的集中体现。本文的研究内容主要包括三种不同的非线性规划模型的降维算沤 以及最优化算法存工程设计及资产配置中的应用，其中对原有的二次观划降维算 法进行_ 广推广，为最优化算法的研究提供了一种新的思路。由李泽民教授上个世 纪9 0 年代提出的最优化降维算法，经过他的四届研究生数值计算研究，方法的可 行性和有效性得到了证明。不过他们对此种降维算法的研究主要是基于二次舰划 降维算1 法，对一般的非线一胜规划模型则是利用序列二次规划的思路，将日标函数 发约束函数分别二次化和线性化，选代求解。但是这种降维算法的原理并不局强 干二次规划，对于一般的等式约束非线性舰划，其思想也是成立的本文第二章 中实现j ，一般等式约束非线性规划问题的降维算法，对已有的研究是。个很重要 中实现了一般等式约束非线性规划问题的降维算法，对已有的研究是个很重要 重庆人学硕上学位论文 绪论 l 。3 非线性规划的应用 非线性规划从二十世纪7 0 年代起就是数学规划中最受重视的分支之，特别 是通过对变尺度法的研究，涌现出了如p o w e l l 、f l e c t h e r 、d e n n i s 等一批著名的非 线性规划专家。近年来，求解般非线性规划问题的序列二次规j i l ( s e q u e n t i a l q u a r d r a t i cp r o g r a m m i n g ，s q p ) 方法的大量成功应用，使非线性规划计算方法成为大 规模科学研究和工程计算的个重要方向，本文第六章介绍了这方面的一个应用。 八卜年代初期开始兴起的信赖域法进一步拓展了非线性规划算法的研究范围，成 为非线性规划的一4 个很热门的研究方向，进一步促进了非线性规划的研究和应用。 金融管理是非线性规划理论应用的一个重要领域，随着二十世纪5 0 年代以来 现代金融理论的迅速发展，数量化分析方法与金融理论紧密结合，产生了明显的 社会效益。证券组合理论是现代金融理论的重要成果，其中的组合证券最优化模 型是现代证券理沦的基石，特别是随着国内近年来基金业的迅速发展，组合证券 模型已经逐步受到各金融机构的重视，本文第六章介绍了这方面的一个应用。另 外，非线性规划理沦与其它学科相结合产生的随机最优控制理论、脉冲最优控制 理论等正成为现代金融理论的发展趋势，文献 1 9 、 2 3 】等介绍了这些方丽的一些 成果。 经济均衡问题是经济学家和优化工作者共同关注的问题，许多文章都对这一 问题进行研究，以更好地描述市场的行为，有些学者利用l a g r a n g e 乘予法和随机 过程论，研究了非连续价格的市场中投资者的消费一投资模型，推14 了b l a c k s c h o l e s 公式：另外最优化方法在博弈问题、工程设计、参数优化等领域也有较高的应用 价值。 1 4 本文研究的主要内容及研究途径 对非线性规划算法及应用的研究具有非常重要的实际意义，是最优化理论价 值的集中体现。本文的研究内容主要包括三种不同的非线性规划模型的降维算法 以及最优化算法在工程设计及资产配置中的应用，其中对原有的二次规划降维算 法进行了推广，为最优化筛法的研究提供了一种新的思路。由李泽民教授上个吐 纪9 0 年代提出的最优化降维算法，经过他的四届研究生数值计算研究，方法的可 行性和有效性得到了证明。不过他们对此种降维算法的研究主要是基于二次规划 降维算法，对一般的非线性规划模型则是利用序列二次规划的思路，将目标函数 及约束函数分别二次化和线性化，迭代求解。但是这种降维算法的原理并不局限 于二次规划，对于一般的等式约束非线性规划，其思想也是成立的。本文第三章 中实现了一般等式约束非线性规划问题的降维算法，对已有的研究是“个很重要 重庆火学硕b 学位论文l 绪论 的补充。通过利用数学软件进行符号矩阵求逆，我们将约束最优化问题转化为非 线性方程组求解，如果是线性约束，则省却了符号矩阵求逆，直接将数值矩阵求 逆后形成方程组，从而在算法结构上统一了原有的二次规划降维算法。 不等式约束非线性规划的研究历来是非线性规划研究的重要内容，对于非线 性规划一般算法、算法收敛性及稳定性等内容的研究有重要意义。目前对于这一 类型规划的研究中，很多文章都把重心放在搜索方向的选择及：二次规划予问题的 研究上，力图寻找收敛速度更快，具有全局收敛性质的算法，另外也有文章对特 殊凸规划的求解问题进行了研究，其中文章【7 8 利用度舰( g a u g e ) 概念讨论了伪凸 函数的一种可行下降算法，本文第四章借鉴其中的思想，将文章 7 8 】中的抽象算法 具体化，结合k u h n t u c k e r 条件的降维形式，构成了一般不等式约束的降维算法， 并讨论了算法的部分性质及收敛性。 线性约束非线性规划是一种较为特殊的最优化模型，特别对于一般非线性规 划模型的求解有重要意义。对这类模型前人已经作了一些研究，本文第五章借鉴 起作用集算法的策略，对原有的算法进行了一些改进，使算法产生的迭代序列在 迭代次数趋于无穷的情况下能更好的收敛于原问题的解，另外对迭代过程中的等 式约束子问题，算法采用了降维算法，在一定程度上降低了计算的复杂度，提高 了算法的效率。 最后本文介绍了最优化算法在工程设计及金融资产配置等实际问题中的应 用，并用降维算法求解金融资产配置模型，一方面说明了最优化算法的经济价值， 另一方面通过对实际问题的求解检验了降维算法的有效性，进一步完善了对降维 算法的研究。另外，在对三种优化模型降维算法j | 】讨论中，文中都给出了具有代 表性的算例，在一定程度上验证了算法的可行性与有效性，对算法的实际应用进 行了积极的探索。 重庆大学硕士学位论文 2 预备知识 2 预备知识 2 1 非线性规划 非线性规划问题的一般形式是 ( r a i n f ( x ) ( n l p )js t c ，( x ) = 0 ，j _ l 2 ，m 。：( 2 1 ) ic 。( x ) o ，i = m 。+ 1 ，2 ，r n ；( 2 2 ) 其中，x = ( x 1 ，x 2 ，x n ) r ”，f ：r ”呻r 1 为目标函数，c 。：r ”寸尺，i _ 1 m 为约 束函数，其中( 2 1 ) 为问题( n l p ) 的等式约束，( 2 2 ) 为问题( n l p ) t 拘不等式约束。若 记x = ( x r nc 。( x ) = 0 ，i = l 2 ，m c 。( x ) 茎0 ，i = m 。+ l ，2 ，r n ) ，贝0 称集合x 为问 题洲l p ) 的可行域，可行域x 中的点称为问题( n l p ) 的可行解或可行点。给定上述 符号后，非线性规划模型( n l p ) 又可简记作m 砷f ( x ) 。在模型( n l p ) 中，目标函数 和约束函数中至少有一个变量x 的非线性函数，约束函数也可只9 a ( 2 1 ) 或( 2 1 2 ) 组 成。记e = ( 1 ，2 ，m 。 ，i = i n 。+ 1 ，m ，i ( x ) = i ic i ( x ) = 0 ，1 2 1 1 蔓i m ) 。对任何 x e r ”，称集合a ( x ) = e ut ( x ) 是在x 点的起作用集合。 设点x 4 x ，使对一切x e x ，均有f ( x ) f ( 妒) 成立，则称x + 是问题( n l p ) 的整体最优解，相应地称f ( x + ) 为问题( n c p ) 的整体最优值。 设x + e x ，若存在x 4 的一个邻域以( 工4 ) ：= x 善一上吲 o ，使对 v x x n 也( 矿) ，总有f ( x ) f ( x + ) ，则称x 4 是( n l p ) 的一个局部最优解，相应地 称f ( x + ) 为问题( n l p ) 的局部最优值。 求解一个非线性规划，通常是寻求它的局部和整体极小点。整体最优解可能 在某个局部最优解处取得，也可能在可行域x 的边晁上达到。在很多实际应用中 通常局部最优解便已满足问题的需要。 2 1 1 梯度、h e s s e 矩阵与j a c o b i 矩阵 假定f ( x ) ：d cr ”斗r 1 为连续可微函数( 厂c ( d ) ) ，则定义f ( x ) 在x 处的梯度 为n 维向量v 胁i 型一o f ( x ) 型i t m l口， 。l 假定盯x ) ：d cr ”一剧为二阶连续可微函数( ，c2 ( d ) ) ，则定义f ( x ) 在x 处 的h e s s e 矩阵为n n 对称矩阵 匝庆人学硕士学位论文 2 预矫知j = i 扩r ( 掰 d 2 ，( ) a k 屯 扩，( z ) 弼a k a ! ( z ) 出： 即其第( i ，j ) 元素为_ 0 2 f _ ( x ) ，为简单记， g 记g = v f ，g ；v ：，等。 ( ，x i o x j 称f ：r “一r 是连续可微的，如果它的每一个分量函数f ，( x ) ：i = l 2 ，m 在每点x 处是连续可微的。f 在x 处的导数f ( x ) 是个m r l 矩阵，它的第i 行是 在x 处的梯度v ( x ) 的转置。f 的导数常常称为f 的雅可比矩阵，记作j ( x ) = f ( x ) ， h e s s e 矩阵则是它的梯度的雅可比矩阵。 2 1 2 凸集、凸函数 非空集合s cr ”称为凸集，若对于任意x l ，x 2 s 和任意实数兄( 0 , 1 ) ，有 瓜，+ ( 1 一z ) 岛s 成立。另外通常约定空集是凸集，下面是凸集的一些简单性质： ( i ) s l n 岛= 扛：x s l ，x s 2 是凸集； ( 2 ) s l + s 2 = 工l + 工2 ：x l s i , x 2 s 2 是凸集； ( 3 ) a s 】= 鼢：x s 1 ) 是凸集； ( 4 ) s i s ：= s 。+ ( - s 2 ) 是凸集 集合s c r ”是凸集的充要条件是，对任意正整数m l ，若x i ：x 2 ，x 。s ，则 它们的凸组合属于s ，即： 口，_ s ，其中o ( i = 1 2 ，m ) ， = 【 并且口，= 1 设s c r 。是非空凸集，f 、s r 。，如果对于任意的x l ，。2 s ，口( 0 ，1 ) ，有 f ( a x 。+ ( 1 一口) 石2 ) a f ( x 。) + ( 1 一a ) f ( x 2 ) ，则称f 是s 上的凸函数。下面是凸函数 的。些基本运算性质： 设s ( 2 2 r ”是非空凸集，若f r o r 1 是s 上的凸函数，口 0 ，则口f 是s 上的 凸函数；若f 1 ，f 2 ：r n r 都是s 上的凸函数，则f 1 + f 2 是s 上的凸函数。 发s c r ”是非空开凸集，f = s r 1 在s 上连续可微，则f 是s 上的凸函数的充 要条件是对任意的。b x 2 e s ，有w ( 气) 7 ( x ：一) f ( x ：) 一f ( x ，) 成立。 设s c r 4 是非空开凸集，s r 在s 上二阶可导，如果f 的h e s s e 矩阵v2 f ( x ) 在s 上是半正定的，则f 是s 上的凸函数。 对于非线性规划问题( n l p ) ，若川。行域x 是凸集，函数厂是可行域x 上的凸 重庆人学顶十学位论文 2 预备知识 函数，则称问题( n l p ) 为凸规划凸规划的任一局部最优解都是它的整体最优解。 2 1 _ 3 中值定理与t a y l o r 公式 设f ( x ) 在开凸集d o c r n 上可微，n x , jd o 中任意x ，y ，存在五( 0 ，1 ) ，使 f ( y ) = f ( x ) + vf ( x + ，【( y x ) ) 1 ( y x ) 成立。设f ( x ) 在开凸集d o c r n 上二次可微，则对d o 中任意x ，y ，存在五( 0 ，1 ) ， 使 f ( ) = f ( x ) + vf ( x ) v ( y x ) + 当( y x ) 1v2 f ( x + 五( y x ) ) 1 ( y x ) z 成立。 设d o c r n 是开的，f ：d o 斗r ，x e d 0 ，则当充分小时，f 分别在可微、二次 可微条件下有下面形式的t a y l o r 公式： f ( x + h ) = f ( x ) + vf ( x ) 1 h + o ( 1 陋0 ) f ( x + h ) = f ( x ) + v f ( x ) r h + 妻h t v2 f ( x ) + d ( 1 l h l lz ) z 2 1 4 最优化算法的结构 最优化算法通常采用迭代方法求得最优解，因而对最优化算法的研究，主要 包括对特定非线性规划模型如何构造寻求问题最优解的迭代点列，迭代算法的收 敛性及算法收敛速度的估计等。迭代算法的基本思想是：从一个选定的初始点 x o i t 出发，按照某一特定的迭代规则产生一个点列 x k ) ，使得当 x k 是有穷点列 时，其最后一个点是问题( n l p ) 的最优解，当 x 。 是无穷点列时，它有极限点，并 且其极限点是问题( n l p ) 的最优解。一个好的算法应具备的典型特征为：迭代点 x 。能稳定地接近局部极小点x + 的邻域，然后迅速收敛于x + 下面是最优化算法中的几个基本概念： 设f ：r n r 1 ，x + r n ，p ( r n ) 0 ，若存在占 0 ，使对v t ( o ，占) ，有f ( x 幸+ t 力 o ，使对v t ( o ，j ) ，有x + + p x ，则称向量p 足点x + 处关于x 的可行方向。 一个向量p ，若既是函数f 在点x * 处的下降方向，又是该点处关于区域x 的可行 方向，则称这个方向为函数f 在点x + 处的可行下降方向。 下面是最优化算法的基本结构： s t e p l ：确定搜索方向p 。，即按照一定规则，构造f 在点x 。处的可行下降方向 作为搜索方向p 。 s t e p 2 ：确定步长因子口。，使目标函数值有某种意义上的下降； s t e p 3 ：令x = x 。- t - o ! 。p 。，若x 已满足某种终止条件，停止迭代，得到近似 最优解x ；否则，重复上述步骡。 里塑i 兰登堡圭兰焦笙塞 ! 塑鱼塑塑 2 2k u h n t u c k e r 条件的等价降维形式 定理2 3 ( k u h n t u c k e r 定理) 设tr ”寸尺和c 。：r “叶r 1 ( i ( 一) ) 在点 x 4 r ”处可微，c 。( f ，1 ( x + ) ) 在点x 8 处连续，并且各v t ( 妒) ( j ，0 * ) ) 线性无关， 若妒是( n l p ) 的局部最优解，则存在石( f j ( 矿) ) 和p ：( ，占) ，使得 w ( x + ) + z v t ( 妒) + j w ，( 扩) = o ，且z o ，i m s )( 2 3 ) i e ( + 】j e e 条件( 2 3 ) 叫做( n l p ) 的k u h n t u c k e r 条件，简称k t 条件，j 、l 满足k t 条件f 2 3 ) 的 可行点都叫做( n l p ) 的k t 点。 设c ( x ) = 0 ，x e r “，c ：r o r “，m n ，则有下面定理： 定理2 4 ( 隐函数定理) 设x o = ( x ? ，x ；，x ：) sr ”满足： ( 1 ) x o 的某个邻域中c c 9 ，p 1 ； ( 2 ) c ( x 。) = o ； ( 3 ) m i n 阶j a c o b i a n 矩阵 3 c 。( x o ) 咖 a c 。( x o ) 础 8 c 。( x o ) 麻” 是非奇异的。 现存在石。= ( x ：。，x ：) r 的一个邻域 x = o ，x 。) u 的函数，记为x ，= 中，( x ) ，i = 1 , 2 ， ( 1 ) 巾，c ”； ( 2 ) x ? = o 。( x o ) ，i = 1 , 2 ， ； ( 3 ) c 。( 1 ( z ) ，0 。( z ) ，工) = 0 ，i = 1 , 2 ，删x u 考虑等式约束问题 fm i n f ( x ) 【s f c ( x ) = 0 u ，使得x i , x 2 ，x 。是 ，m ，具有下列性质： ( 2 4 ) 其中x r “，厂：r “斗r 1 ，c ：r ”一r ，珊 0 ，k ：= 1 ，初始点x ，按照在总体中选取m 个样本的选 取方法，选出基础向量x 。； s t e p 2 ：求得嘭( x ) ，或( j ) ，埘：( x ) ，：( x ) ，m ；( x ) ，构得方程组( 3 2 ) ： f 蹭( x ) = ( ；( x ) 。1 ；( z ) ) 7 雕( x )f 3 2 1 1c i ( 。) ：0 ，i 。e s t e p 3 ：用最小二乘法求解非线性方程组( 3 2 ) ，若方程组无解，转s t e p 5 ：否则得 解x ： s t e p 4 ：计算矩阵埘：( x ) 的秩r ： 若r = m ，则令x = x ，退出： 否则继续； s t e p 5 ：若k o ，初始点xo ，常数n ，m ，约束函数下标集合e 1 ，2 ，札) ，令k ：= 1 ，p ：= 1 ，t = p + l ，q ：2 p + m 一1 ： s t e p 2 ：令基础变量f 标集合b = p ，t ，t + m 一3 ，q ，n b = e b = s ，s 矿s ) 其中集合b 有m 个元素，集合n b 有n m 个元素，b nn b = g ，b u n b 2 e ： s t e p 3 ：根据集合8 和n b 的元素，分别计算矩阵： j v ：( x ) 瑶( x ) ( j ) 妇p a c ，( 王) 黜h l 型型 瓠。融 fa c l ( x ) l 啦 昆。( 功 融j 妒( x ) 黜 a f ( x ) 出一 a c 。( x ) 黜。 a c 。( 工) 出口 a c l ( x ) d x 。 a c 。( x ) 融 瑶( x ) 可( x ) 出口 a f ( 工) 出口 得到方程组( 3 2 ) ： s t e p 4 ：用最小二乘法将解非线性方程组( 3 2 ) 转化为求解无约束极值问题，用插 值法对无约束极值问题进行求解，若方程组无解，转s t e p 6 ；否则得解x ： s t e p 5 ：计算数值矩阵m ：( ) 的秩r ： 若r = m ，则令x = x ，得到问题( e p ) 的解，算法终止； 否则继续s t e p 6 ； s t e p 6 ：令k ：= k + l ； 着q n ，则令q = q + l ，b = p ，t ，t + m 一3 ，q ，n b 2 e b ，转s t e p 3 ： 否则若q = n ，t n m + 2 ，则令t = t + l ，q = t + m ：2 ，转s t e p 7 ： 否则若q = n ，t = n m + 2 ，则令p = p + l ，t = p + l ，q = t + m 一2 ，转s t e p t ； 里塑型苎兰生兰兰坚坠 ! 查生二墼篓垫竺壅塑兰塑堕丝多法 s t e p 7 ：若k 玉c ：1 ，则转s t e p 2 ：否则算法无效，退出 3 2 数值实验 例3 1m i nf = x t2 + x 2 2 + x 3 2 s t x l2 + 1 z - x 3 = o x 【x 2 十x 3 1 = o 给出初始点x u = e 。，。，。，b ，= ，硝，则m c x ，= 2 2 ：2 ，允许误差t = e s ，构 得的方程组如下： r2 x 3 + l = 0 x i z + x 2 2 - - x f 0 【x t + x 2 十x 31 = 0 浚方程组是无解的，于是重新寻找基础向量，令e ：2c “x 执则m c x ，= 2 i 1i 1 ， 得方程组如下： f ( 1 + 2 x 3 ) ( 一x + x 2 ) ( 2 x 。+ 1 ) = 0 x 2 + x 2 。一x 3 = o ix 。+ x ：+ x 。一l = o 用最小= 乘法求解该方程组，得解x = ( 0 3 6 6 0 2 5 4 0 4 5 4 0 8 9 ，0 3 6 6 0 2 5 4 0 4 4 8 7 5 4 ， 0 2 6 7 9 4 9 1 9 2 2 3 5 5 8 ) ，且m ( x )