全局优化问题的区间算法的探讨

摘要

自从20世纪70年代中后期以来，全局优化以惊人的速度在许多方面取得了飞速的进展，许多新的全局优化理论及算法也相继出现，并得到了广泛应用。目前全局优化已作为最优化领域中一个独立的学科分支，引起了国内外学者的广泛重视并掀起了该领域的研究热潮，成为一个强有力的工具，被人们应用十对实际问题进行的建模和分析中。由十在一个全局优化问题里很可能存在多个局部最优解，它们不同十问题的全局最优解，因此人们无法借助十经典的局部优化方法求解这些问题，特别是至今还没有很好的全局性判定准则，使得全局优化的研究极具挑战性。在全局优化的问题上，目前存在的诸多优化算法都是以一定的概率来确保获得全局最优解，通常由十初始点选取因素的影响，都容易陷入到“局部最优解”问题，}fU本文提出的基十区间数学的全局优化算法能完全避免上述问题，确保获得真正的全局优化问题的全局最优解，并为全局最优化问题提供一个判别准则。本文分别针对无约束全局优化问题和有约束全局优化问题进行区间全局优化算法的理论介绍，从起始域的选择，无解区间的删除一直到算法的终止准则。其中，详细的阐述了FritzJohn条件在算法中的作用，并对John条件的求解进行分析论证，以及拉格朗口乘子的选取、标准化以及拉格朗口乘子的界定等。此外，本文还分别从数学实例和机械优化设计实例两个角度对区间全局优化算法进行了可行性论证。其中，从区间数学实例中得出的结论是:基十区间数学的全局优化算法对十区间数学优化实例具有精确、高效等特点。本文还将区间全局优化算法引用到机械优化设计中，以汽车悬架系统的优化设计为依托，建立全局优化的数学模型，在基十Matlab软件和INTLAB软件库的软件平台上，对其进行优化分析，得出了理想的结果。

关键字

区间数学、全局优化、区间迭代、JOHN条件、拉格朗口乘子

1

globalandofinitialtheofthesetwodemonstratedforbymathematicsintervalglobalandofinitialtheofthesetwodemonstratedforbymathematicsintervalmathematicswithprecise,mathematics,overalldeletionanglesfeasibility.is,theglobal,forintervalefficientetc.Thisoptimization,Intervalof,theintervalglobaltheconclusionoptimummathematicalpaperiteration,JOHNnoalgorithm,whichoptimization,haswillalsoquotesolutionboxtothealgorithmtermination

Sincethemiddleof1970s,Globaloptimizationwithamazingspeedinmanywaysmadearapidprogress,Manyofthenewglobaloptimizationtheoryandthealgorithmalsoarise,andgottheextensiveapplication.Currentlyalreadyasanindependentdisciplinebranchinthefieldofoptimization,Globaloptimizationgetstheattentionofscholarsbothathomeandabroadandtheresearchinthefieldofaboom,beapowerfultool,isappliedtopracticalproblemsofmodelingandanalysisbypeople.Becauseinthisglobaloptimizationproblems，likelytherearemorethanonelocaloptimalsolutions,buttheyaredifferentfromtheglobaloptimalsolution,sojustaccordingtotheclassiclocaloptimizationmethod,peoplecan'tsolvetheseproblems.Inglobaloptimizationproblem,atpresent,somanyoptimizationalgorithmensurethatyougettheglobaloptimalsolutionatacertainprobability,usuallybecauseoftheinfluenceofinitialpointselections,itiseasytofallintothe"localoptimalsolution"，Andinthispaper,theglobaloptimizationalgorithmbasedonintervalmathematicalcancompletelyavoidtheproblems,ensurethatyougettherealoptimalsolutionoftheglobaloptimizationproblem,andprovidesacriterionforglobaloptimization.Thispaperforunconstrainedglobaloptimizationproblemsconstrainedglobaloptimizationproblemsinthetheoryofintervalglobaloptimizationalgorithmisintroduced.Itstatesanddemonstratesfromthechoicedomain,rules.Amongthem,itexpoundsFritzJohnconditionsintheroleofthealgorithmindetails,andanalysisthesolutionofJohnconditions,andLagrangemultiplierselection，standardization，boundingtheLagrangemultiplier,etcInaddition,inthispaper,fromthemathematicalexamplesandmechanicaloptimaldesignexampleoptimizationalgorithmisfromexamplebasedoncharacteristicsintervalglobaloptimizationalgorithmtotheoptimizeddesignofmachinery,basedontheoptimizationdesignoftheautomobilesuspensionsystem,EstablishglobaloptimizationmathematicaKeywords:intervalconditions,Lagrangeexportmultiplier

2

目录

第一章引言.........................................................1第二章全局优化问题................................................32.1全局优化问题的研究方向.....................................32.2全局优化问题的研究现状.....................................4第三章区间算法的简介.............................错误！未定义书签。3.1区间算法..................................错误！未定义书签。3.2区间方法的由来............................错误！未定义书签。3.3实数的区间表达和区间算法..................错误！未定义书签。第四章常用的区间算法.............................错误！未定义书签。4.1中点测试在全局优化区间算法的一种实现......错误！未定义书签。4.1.1介绍区间算法及相关结果..............错误！未定义书签。4.1.2具体算法............................错误！未定义书签。4.1.3算法分析............................错误！未定义书签。4.2一种求lipschitz连续函数的全局优化区间算法错误！未定义书签。4.2.1.区间算法相关结果介绍...............错误！未定义书签。4.2.2.算法主要思想.......................错误！未定义书签。4.3一类求解线性等式约束全局优化问题的区间算法错误！未定义书签。4.3.1引言..............错误！未定义书签。4.3.2算法主要思想和具体步骤..............错误！未定义书签。4.3.3算法分析............................错误！未定义书签。第五章总结.......................................错误！未定义书签。致谢............................................错误！未定义书签。参考文献...........................................错误！未定义书签。

3

第一章引言

在现实生活中，许多领域都存在大量的最优化问题，如分子生物学经济金融，数据挖掘与知识发现，环境工程，网络运输，图像处理与模式识别，化学工程设计与工业制造等.最优化与分析，几何:代数，概率论.计算机科学，系统科学，自动化等学科密切联系，互相促进.如果说“模拟”深刻地改变着人们改造世界的能力，那么“优化”则深刻地改变着人们改造世界的方法和途径.人们通过问题的相关信息，提出最佳的选择，再构造寻求最佳解的计算方法，再进一步研究这些计算方法的理论性质及实际表现.在分析问题的过程中所抽象出的优化模型，大都可以归结为求全局解的问题早在20世纪60年代，就有人开始研究现在称为全局优化的问题，但是，那时候大多数人的关注点主要集中在线性规划和非线性规划局部化数值算法方面.到20世纪70年代中后期开始出现了有关全局优化的论文集，再经过近30年的发展，全局优化已经成长为最优化领域中独立的学科分支，成为人们研究实际问题时进行建模和分析的重要手段之一全局优化研究的间题是多变量非线性函数在某个约束区域上的全局最优解的特性和构造寻求全局最优解的计算方法，由于很可能在一个全局优化问题里存在多个局部最优解，且它们不同于问题的全局最优解，因此人们无法借助于经典的局部优化方法求解这些问题，特别是今天还没有很好的全局性判定准则，从而使得全局优化的研究极具挑战性.然而，在最近二三十年里，全局最优化以惊人的速度在许多领域取得了快速发展，许多新的全局优化理论及算法已被广泛地应用于科学和工程中遇到的困难问题上，特别是最近出现的全局优化方法作为强有力的工具以被成功地应用于人们的生产和设计问题中.一般来说.现有的求解全局优化问题的方法依据它们的收敛性质分为两大类，即确定性方法和随机性方法.确定性方法能够利用问题的解析性质产生一定的有限或无限点序列使其收敛于全局最优解，如区间方法，分支定界方法，填充函数方法，罚函数法，积分水平集法，外逼近方法、原始对偶方法等.凸性，单调性，等度连续性，稠密性，lipschitz常数，水平集等通常称为这些问题全局性的解析性质这类方法依据某一确定性策略搜索局部极小，并试图跳跃已经获得的局部极小，而达到某个全局最优点.随机方法类是利用概率机制来描述迭代过程，如随机投点方法，遗传算法，模拟退火算法，演化策略方法等，这些都是常用的随机算法，这类方法具有对目标函数性质要求低，应用广泛，容易实现，稳定性好等突出特点.近年来，随着科学技术，别是信息技术的飞速发展，全局优化在经济模型，固定费用，金融，网络，运输，图像处理核能和机械设计，化学工程设计，分子生物学以及环

1

境工程等众多领域中的应用越来越广泛使得在科学，经济和工程中的许多进展都依赖于计算相应全局最优解的数值技术，因此，全局最优化理论和方法值得我们去深入研究.这是一篇介绍几种求解全局优化问题算法的综述，针对不同的问题，而采取不同的优化算法，更能得到事半功倍的效果.第一章对全局优化间题做一个简要的概述，介绍全局优化间题的背景，发展状况.及全局优化研究的重要性.第二章介绍全局优化的基本概念，定理和相关性质，为后文做了铺垫.在第三章，我们主要介绍全局优化问题的两种确定性方法，即区间算法和分支定界算法.不仅论述两种方法的主要研究方向，适合研究的某些具体问题和两者最近研究的发展状况，同时也对区间算法和分支定界算法的基本概念，主要思想，算法步骤，各自的优缺点做了一定的描述，此外，还通过一些例子来说明两种算法的有效性.四章简要地介绍了几种其它方法，包括应用不同的方法来解决相应类型的问题，算法思想和算法基本实现步骤.

2

全局优化问题全局优化问题的研究方向

第二章全局优化问题全局优化问题的研究方向

2.1

在现实生活中，许多领域都存在大量的最优化问题，如分子生物学经济金融，数据挖掘与知识发现，环境工程，网络运输，图像处理与模式识别，化学工程设计与工业制造等。最优化与分析，几何:代数，概率论。计算机科学，系统科学，自动化等学科密切联系，互相促进。如果说/模拟0深刻地改变着人们改造世界的能力，那么/优化0则深刻地改变着人们改造世界的方法和途径。人们通过问题的相关信息，提出最佳的选择，再构造寻求最佳解的计算方法，再进一步研究这些计算方法的理论性质及实际表现。在分析问题的过程中所抽象出的优化模型，大都可以归结为求全局解的问题。早在20世纪60年代，就有人开始研究现在称为全局优化的问题，但是，那时候多数人的关注点主要集中在线性规划和非线性规划局部化数值算法方面。到20世纪70年代中后期开始出现了有关全局优化的论文集，再经过近30年的发展，全局优化已经成长为最优化领域中独立的学科分支，成为人们研究实际问题时进行建模和分析的重要手段之一。全局优化研究的间题是多变量非线性函数在某个约束区域上的全局最优解的特性和构造寻求全局优解的计算方法，由于很可能在一个全局优化问题里存在多个局部最优解，且它们不同于问题的全局最优解，因此人们无法借助于经典的局部优化方法求解这些问题，特别是今天还没有很的全局性判定准则，从而使得全局优化的研究极具挑战性。然而，在最近二三十年里，全局最优化以惊人的速度在许多领域取得了快速发展，许多新的全局优化理论及算法已被广泛地应用于科学和工程中遇到的困难问题上，特别是最近出现的全局优化方法作为强有力的工具以被成功地应用于人们的生产和设计问题中。一般来说。现有的求解全局优化问题的方法依据它们的收敛性质分为两大类，即确定性方法和随机性方法。确定性方法能够利用问题的解析性质产生一定的有限或无限点序列使其收敛于全局最优解，如区间方法，分支定界方法，填充函数方法，罚函数法，积分水平集法，外逼近方法，原始对偶方法等。凸性，单调性，等度连续性，稠密性，liPs面tz常数，水平集等通常称为这些问题全局性的解析性质。这类方法依据某一确定性策略搜索局部极小，并试图跳跃已经获得的局部极小，而达到某个全局最优点。随机方法类是利用概率机制来描述迭代过程，如随机投点方法，遗传算法，模拟退火算法，演化策略方法等，这些都是常用的随机算法，这类方法具有对目标函数性质要求低，应用广泛，容易实现，稳定性好等突出特点。近年来，随着科学技术，特别是信息技术的飞速发展，全局优化在经济模型，固定费用，金融，

3

全局优化问题的研究现状（+EMBEDEquation.KSEE3为一随机变全局优化问题的研究现状（+EMBEDEquation.KSEE3为一随机变量)，并以一定概率接受或以EMBEDEquation.KSEE3\*初始值而由某个局部休化过程产生的局部极小为新的近似，，这一过程直至满足某一人为给=EMBEDEquation.KSEE3\*，其中EMBED工程等众多领域中的应用越来越广泛使得在科学，经济和工程中的许多进展都依赖于计算相应全局最优解的数值技术，因此，全局最优化理论和方法值得我们去深入研究。

2.2

在过去几十年里，关于局部优化方法及其在工程和科学中的应用等方面的研究已获得丰富的理论和优秀的数值方法。但大量的最优化问题，特别是从工程优化中设计出来的优化模型都要求全局解而不是局部解，它们来源于分子生物学11从经济金融121，网络运输[31，数据挖掘与知识发现141，图像处理与模式识别151，环境工程，化学工程设计与工业制造等。另外，科学与工程的许多最新成果都依赖于计算优化问题全局解的数值技术。全局优化主要研究非线性函数在某个区域上的全局最优点的特征及其计算方法，用传统的非线性规划求解方法己无法有效地求解。全局优化问题的研究始于六十年代中期，但这项研究进展缓慢，与求解局部极值问题相比，其主要困难在于问题中局部极值点的个数及极值点的大体位置均为未知;判断一个局部极值点是否为总体极值点的判别准则不易确定。:近年来，全局优化己成为优化领域最受关注的方向之一，已引起许多优化工作者的广泛关注。随着全局优化问题的广泛应用，许多全局优化算法得到不断地发展。现有的全局优化算法依据它们的收敛性质分为随机型方法和确定型方法两大类。前者包含遗传算法，模拟退火算法，演化策略，进化程序等，这类算法从当前近似值气

出发，以随机扰动方式生成新的初始点

MERGEFORMAT

Equation.KSEE3

EMBEDEquation.KSEE3

MERGEFORMAT

EMBEDEquation.KSEE3

定的终止准则。当算法的执行时间趋于无穷时，它们按照概率逼近收敛到最优解。这类方法具有算法易于设计，对目标函数要求不高从而应用广泛，容易实现，稳

4

定性好等优点。但效率低，可靠性差，不能保证产生优化问题的最优解，并且它的理论基础也不完善，结论常常带有随机性。相比之下，确定性方法可以充分利用优化问题的特殊结构，通常能在预先给定的精度内有限步收敛于问题的最优解。这类方法包括:牛顿法，共扼梯度法，变尺度法，分支定界法，网格算法，罚函数法，积分水平集法，区间算法，填充函数法，神经网络方法等。这类方法依据某一确定性策略搜索局部极小，并试图跳越已获得的局部极小而达到某个全局最优点。这类方法虽然有较高的计算效率，但算法复杂。一般的确定性方法大体可分为两类:解析方法，直接方法。前者主要利用函数的分析性质去构造迭代公式，使之收敛到极值和极值点，主要有:最速下降法，牛顿法，共辘梯度法，变尺度法等。对于多变量的一般非线性函数的极小化问题，虽然利用导数能够为寻找极值点提供有效信息，但是为求其导数却可能不得不耗费大量时间来做计算导数的工作，而且目标函数的导数有时是不存在的，甚至目标函数本身是不明确的解析表达式，这就迫使人们寻找不需要计算函数导数或梯度的方法。直接方法对函数的分析性质没有要求，而且根据一定的数学原理，用尽量少的计算量，通过直接比较函数值的大小来确定极值点的位置。直接方法有;区间方法，填充函数法，分支定界法，网格算法等。

5

,EMBEDEquation.3及EMBEDEquation.3EMBEDEquation.3.在区间算法里，这被称为表达的包含原理.这样无,EMBED]都包含了r的全部信息.由于所有的实数都用区间来表达，那,EMBEDEquation.3及EMBEDEquation.3EMBEDEquation.3.在区间算法里，这被称为表达的包含原理.这样无,EMBED]都包含了r的全部信息.由于所有的实数都用区间来表达，那，EMBED]和y=[EMBEDEquation.KSEE3\*，EMBEDEquation.KSEE3≠x在计算机上实现区间]来表达.均可被计算机精确表rEMBEDEquation.3]是两个区间。3.1区间算法摩尔(R.E.Moore)于20世纪50年代末提出了区间算法念([l]和[2])..摩尔扬弃了实数在计算机上的浮点近似表达方法.他提出一个实数r在计算机上应当用一个区间r=[EMBEDEquation.3

这里EMBEDEquation.3

达，且EMBEDEquation.3

EMBEDEquation.3

论r本身能否被计算机用浮点精确表达，区间[EMBEDEquation.3

Equation.3

末对于它们之间的运算，也必须给以定义.摩尔给出的定义为:若op为下列运算+，-，×之一，x=[EMBEDEquation.KSEE3

Equation.KSEE3

MERGEFORMAT

那末xopy={xop|EMBEDEquation.KSEE3

x∈x，y∈y}(1)

根据这个定义，我们有下面的例子:[1，2]+[-1，0]=[0，2]，[0，2]-[-1，0]=[0，3]和[1，2]*[-1，0]=[-2，0]。从这些简单例子中，我们注意到，x+y=z，但是z-EMBEDEquation.KSEE3

运算时，应当注意到机器可精确表达的两个数字的运算结果可能是机器无法精确存储的。因此在计算机上进行区间运算时，一切计算结果(包括中间步骤)的存储都必须满足包含原理。从而保证计算的可靠性。但是人们很快发现区间算法可以有更广泛的应用.从上面的简单例子中，我们已经看到，区间算术具有与传统算术不同的性质.另外，由于区间本身的集合属性，区间之间的集合运算可以被很容易地施行.对于区间数学的研究衍生了区间分析这一近代数学的分支.这一分支莫定了基于区间算法而形成的许多新的计算方法的理论基础.这些新的计算方法能够可靠地解决一些传统方法难以解决的问题.例如求解非线性方程组在给定

6

的形式.这里a0,a1,a2,a3,的形式.这里a0,a1,a2,a3,⋯为0,1,2,⋯,9中.这里b0,b1,b2,b3⋯为0,或1,p是一个二进表述的.人们可以很方便地运用区间算法把它们包括在计算中.这些使得区间算法在诸如金融风险控制火箭喷口受力，核磁共振机设计和机器人等应用方面取得了一些成功.区间算法很快就成了计算数学的一个活跃分支.许多研究论文不断被发表在国际期刊上.一个名为可靠计算的国际期刊被专门用来发表区间算法方面的研究成果.近年来，区间算法运用于计算科学和工程取得了一些显著成果，区间算法提出初衷是为了提高计算结果的可靠性，但是人们很快发现区间算法可以有更广泛的应用，如工程，金融等多方面.区间算法对传统浮点算法进行了一个根本改革，它把计算的数存储为区间，并对这些区间进行运算，使避免浮点算法所产生的计算误差成为可能.另外，区间算法使得区间参数能被直接包含在计算之中、这在实际应用里具有重要的意义.区间算法是对浮点算法的一个有益补充，值得从事科技计算研究的工作者了解和应用.区间算法是一种很有效的数学工具，它适合解决很多跟优化有关的问题.3.2区间方法的由来要说明为什么需要区间算法,我们需要对通用的浮点算法作一点深入的了解.任何一个实数r都可以被表达成±a0.a1a2a3⋯*EMBEDEquation.KSEE3

的任何一个,n是一个整数.计算机内部使用二进制数.为了表达一个实数,计算机首先将它转换成二进制形式±b0.b1b2b⋯*EMBEDEquation.KSEE3

制整数.如果r≠0,则b0=1.计算机通过用一个二进制单元(bit)序列来记录b0,b1,b2,b3,⋯和指数p,来实现对于实数的记录和运算.IEEE发布了这种表达和运算的标准.如果用32个二进制单元(bit)序列来记录一个实数,这个标准规定用第一个单元来记录正负号(0为+,1为-);用第二到第九个单元来记录加权后的指数e(e=p+127);而第十到第三十二个单元则用来存储b1,b2,b3,⋯,b23,假定b0=1.第二到第三十二个单元都为零被用来专门存储实数零.标准里对于用64个,128个或更多的二进单元存储实数都作了相应的规定.在以32单元存储实数的机器里,二进制小数的第24位之后的数位将无法被存入.计算机可以直接舍去第24位及之后的全部小数或根据第24位的数值0舍1入.显然,绝大部分实数都无法被计算机精确存储.这些不精确的存储将会影响计算结果.另外,在对这些浮点表达实数的计算中,新的误差也是会不断产生和难以避免的.人们通常认为,小数点多位之后的误差应当不会对计算结果有太大的影响,因此可以忽略不计.然而,事情远非那

7

EMBEDEquation.3xi-1.假如在计算机上用浮点算法来算出这个等价.所以无穷序列{xn}应,EMBEDEquation.3及EMBEDEquation.3xi-1.假如在计算机上用浮点算法来算出这个等价.所以无穷序列{xn}应,EMBEDEquation.3及EMBEDEquation.3EMBEDEquation.3EMBEDEquation.3,EMBEDEquation.31,xi+1=EMBEDEquation.3]均可被计算rEMBED.在区间算法里,这被称为表达的包]都含了r的全部信息.由于所有的x1=13;如果i

i-EMBEDEquation.3

序列,并根据数据结果来推断序列的敛散性,人们会很容易地得到一个错误的结论.那就是该序列发散于无穷大(在一些计算机和计算语言下发散到正无穷,而在另一些发散到负无穷).但是用数学归纳法,我们可以方便地证明该序列与EMBEDEquation.KSEE3

当收敛于零.所以,人们不能简单地接受计算机提供的计算结果.在大规模的计算中,如何确认结果的可靠性,成为了一个极具挑战性的问题.摩尔认识到这类计算结果的不可靠性完全是由于实数的浮点表达和浮点运算本身产生的.因此,他提出了对计算机实数存储与运算方面一个根本上的改革.3.3实数的区间表达和区间算法摩尔扬弃了实数在计算机上的浮点近似表达方法.他提出一个实数r在计算机上应当用一个区间¹r=[EMBEDEquation.3

来表达.这里EMBEDEquation.3

机精确表达，且EMBEDEquation.3

Equation.3

含原理.这样无论r本身能否被计算机用浮点精确表达,区间[EMBEDEquation.3

实数都用区间来表达,,但是人们很快发现区间算法可以有更广泛的应用.从上面的简单例子中,我们已经看到,区间算术具有与传统算术不同的性质.另外,由于区间本身的集合属性,区间之间的集合运算可以被很容易地施行.对于区间数学的研究衍生了区间分析这一近代数学的分支.这一分支奠定了基于区间算法而形成的许多新的计算方法的理论基础.这些新的计算方法能够可靠地解决一些传统方法难以解决的问题.例如求解非线性方程组在给定区域内的所有数值解[4],整体优化等问题.另外,实践中许多计算参数是用区间来表述的.人们可以很方便地运用区间算法把它们包括在计算中.这些使得区间算法在诸如金融风险控制,火箭喷口受力,核磁共振机设计和机器人等应用方面取得了一些成功.

8

[R是区间映射,称F(X)是函EMBEDEquation.3F(X)成立。[表示X的下界和上界;EMBEDEquation.3EMBEDEquation.3[4]];EMBEDEquation.3EMBEDEquation.3X且X2]数f(x)在区间[R是区间映射,称F(X)是函EMBEDEquation.3F(X)成立。[表示X的下界和上界;EMBEDEquation.3EMBEDEquation.3[4]];EMBEDEquation.3EMBEDEquation.3X且X2]数f(x)在区间X上的X有f(x)3](X+EMBEDEquation.3-X为区间X的宽度.两区间X=[X,<Y;YEMBEDEquation.3设f:R对X=[X,EMBEDEquation.3)为X中EMBEDEquation.3EMBEDEquation.3EMBEDEquation.3n]EMBEDEquation.3],Y=[Y,Y.EMBEDEquation.3EMBEDEMBEDR;F:RnEMBED4.1中点测试在全局优化区间算法的一种实现4.1.1介绍区间算法及相关结果

定义1

Equation.3

区间扩张,如果EMBEDEquation.3

EMBEDEquation.3

定义2

I(R)分别定义:

(1)X、EMBEDEquation.3

(2)m(X)=

点;

(3)w(X)=

定义3

Equation.3

(1)X<YEMBEDEquation.3

(2)X

Equation.3

假设f(x)是定义在X上以C(>0)为常数的Lipschitz连续函数,F(X)=f(m(X))+c(X-(m(X)),

9

(1)(2)(n),iiiiiikfk由(3)式存在某个k0,使fkF(XF(X有f(x)xk0),cw(0)=cw(x)/k由(4(1)(2)(n),iiiiiikfk由(3)式存在某个k0,使fkF(XF(X有f(x)xk0),cw(0)=cw(x)/k由(4)和(5)得fk-minf(X)cw(X)/k故k[cw(X)/E时,命题成立指出,对Lipschitz连续函数f(x),我们可以按(2)及(3)计算构造子kEMBEDEquation.3kx^={xEMBEDEquation.3ik0)k0),因此,F(0)-f(x)EMBEDEquation.3KEMBEDEquation.3maxf(X).进一步,我们0,EMBEDEMBEDEquation.3X,f(x)并且对每个xEMBEDEquation.3k时可EMBEDEquation.3w(F(0)).这K对问题(1)Shen在[1]中假设目标函数f(x)为X上常数为c的Lipschitz连续函数,将区间X分成具有相同宽度n个部分:X,X,,,XX=F(X)=f(m())+c(-m(X))=[F()F(),i=1,2,,,k,(2)定义=maxF(X).(3)显然有

maxf(x)EMBEDEquation.3

(4)且当k充分大时,有定理1对任意的E>0,存在K,使得当k>K时fk-maxf(x)<E.证

EMBEDEquation.3

F(X

EMBEDEquation.3

EMBEDEquation.3

定理1区间X上的上界区间列{fk}且当分割次数k

以得到收敛性,即fk

总有对充分大的k,|m(X)-^x|EMBEDEquation.3

Equation.3

里EMBEDEquation.3

=maxf(X)}.

4.1.2具体算法假f(x)X上常数为c的Lipschitz连续函数,给定松驰变E>0,|maxf(x)-f^|<E,则认为f^为maxf(x)的满意值.L是以区间(Xi,bi,

10

ii为X上的标志矢量,取值0或1,Ri=0表明X中明显不含最

i00)=f(m(X0))+c(X00)),设ii为X上的标志矢量,取值0或1,Ri=0表明X中明显不含最

i00)=f(m(X0))+c(X00)),设0)

0)),R0=1。

0,b0,d0,R0)}01iiii

ii

i

0,b0,d0,R0),并计

i

0))<E,

0)

[6]

i

i假设x‘EMBEDEquation.3f(‘),f(m(XEMBEDEquation.3),即(X,bi,ci,Ri)不可能被删除.XL中移走(XEMBEDEquation.3F(X),f(m(X0))2,从0,X为maxf(x)的最优解,则i0))F(XiEMBED然区间扩张函数上界F(X),di为X中点函数值,计为di=f(m(X

1)),Riii优解,Ri=1表明到目前为止不能确定X中是否含最优解.具体算法步骤为:step1设X=Xstep2计F(X-m(Xb0F(X,d0=f(m(Xstep3初始化区间列L={(X

step4二分区X=XEMBEDEquation.3

b0,d0,R0)。step5i=1,2计F()=f(m())+c(m(X)),biF(X),di=f(m()),Ri=1.step6假b1<d2R1=0否则R1=1如b2<d1,取R2=0,否则取R2=1step7Ri=区间(X,bi,di,Ri列入L中,后L中区间按第二元素bi不增的顺序排列,令第一个区间为(XL中区间个数为k。step8比d0L中其它k-1个区间中的第二个元bi,bi<d0则将区间(X,bi,di,RiL中移去。step9当w(F(X则转入step10,否则转入step4step10输出b0为maxf(x)的满意值,m(X为maxf(x)的满意解,计算终止4.1.3算法分析

以上算法是Shen在[1]的算法基础上引入标志矢量R,在计算过程中剔出Ri=0的区间(X,bi,di,Ri),即删除X明显不含最优解的区间以减少L中区间的数量来释放空间,对节约计算时间和加快运算速度非常有效.算法的收敛性见文献[1],且有较好的可靠性.定理2以上算法终止时,maxf(x)的所有最优解都在区间L中元素X.

证

f(x’)

Equation.3

ii

11

i

If(x)

fx)b]上通过对区间[a,b]分割来构造对每个区间X=[X,EMBEDEquation.3FXfi

If(x)

fx)b]上通过对区间[a,b]分割来构造对每个区间X=[X,EMBEDEquation.3FXfXcXXFXfx)mXXxXXfFX(n)(k)(i)XfXcXmXFXfx)M,

(k)

XFX

fb]上常数为cEMBEDEquation.3XXX

(0)(0)ffc]和cbc=1/2(a+b]X(0)，(x)≤(i)(i)(i)(i)]⊆X=a,b],有()=(0),(0)fb(0)=[a,],=(EMBEDEquation.3F)。把分割X最优解时,在取E足够小下把算法终止条件改为w(F(X))<E时,用以上算法可以求出max的所有最优解.

4.2一种求lipschitz连续函数的全局优化区间算法4.2.1.区间算法相关结果介绍

在文[1]中沈祖和利用moore“二分原则”（[2],[3]），对定义在区间[a,b]上的单变量函数(定义在区间[,函数值上界数列收敛于全局最优值。设f(x)定义在区间[a,b]上常数为c的Lipschitz连续函

数，

有()=(m())−(−(m()).其中()为(的自然扩张,()为的中点.即对∈,有(x)∈

()0成N个独立部分,即(1)(2),X,∪X,FX,,=(m())+(−())，M=max()及max(≤则当N→∞,有M→max(x)且inf|m(X)-x→0,x∈{x|x∈[a,b],f(x)=maxf(x)}.在算法中通过构造区间列(,())，利用中点测试来获得全局最优值，从理论与实践证明是稳定和可靠的。本文利用Moore的“二分法原则”，对Lipschitz连续函数全局最优值的存在区间压缩来寻找全局最优值。从实例可以看出，这算法收敛性好且速度快.4.2.2.算法主要思想也设(x)定义在区间[a,的Lipschitz连续函数.对每

个区间=,

f(m(X))−c(X−(m(X)),其中F(X)为f(x)的自然扩张,m(X)为的中点.即对x∈⊆有f(x)∈F(X)令a==(X)b=(X)0得到包涵(x)全局最优值的区.即max(x)[a,b],二分区间[a,b]为[,[,],).至少有一个区间含有最0000000

12

fx)ba,b]}bababkk(x)∈[ab],k=0,1,2....kfb)b)kkkfx)设=[,()=())+计算fx)ba,b]}bababkk(x)∈[ab],k=0,1,2....kfb)b)kkkfx)设=[,()=())+计算()=())+−)),设a=(0)(0)(00),00二分区间x：x[a,b=a,c∪[c,b]，c(a+b设H=H=EMBEDEquation.DSMT4对给定的ε>0，如|EMBEDEquation.DSMT4|<ε则输出EMBEDEquation.DSMT4EMBED)为全局最大值，否则转入step3；运算终止。)n

kk−kxab],FXfm(Xc(X-m(x));FXfm(Xc(Xm(Xkkkkkkkk=1/2kkH(k)ck;(k)ck,-EMBED,Equation.DSMT4EMBED(0)

(0)(0)(0)(0)(k=,EMBEDEquation.DSMT4=+Equation.DSMT4)aφ则令bk;EMBED0,i=1,2,...,k,={=(x),,x|cfxkEMBED[a,]}，b11一个区间列{[[a,]⊇[,]⊇...[,]⊇...0011max对ε>0当足够大时得到max(x)−1/2(a+<ε,取1/2(a+全局最大值。本算法是max(的包含区间按几何级数2收敛，速度是较快的。4.2.3算法step1.step2.0=(X),b=(X)1/2abx[ab];0step3.step4.如φ，则令EMBEDEquation.DSMT4

Equation.DSMT4

如

Equation.DSMT4

step5.

Equation.DSMT4

=1/2(

Equation.DSMT4

step6.

4.3一类求解线性等式约束全局优化问题的区间算法4.3.1引言

约束条件下非线性优化问题一般表示为minf(x),

gi(x

13

[设f:EMBEDEquation.3x∈X,有f(x)∈F(X)成立.对X=[EMBEDEquation.3,EMBEDEquation.3+EMBEDEquation.3-EMBEDEquation.3两区间X=[EMBEDEquation.3,EMBEDEquation.3EMBED[设f:EMBEDEquation.3x∈X,有f(x)∈F(X)成立.对X=[EMBEDEquation.3,EMBEDEquation.3+EMBEDEquation.3-EMBEDEquation.3两区间X=[EMBEDEquation.3,EMBEDEquation.3EMBEDEquation.3EMBEDEquation.3EMBEDEquation.3EMBEDEquation.3EMBEDEquation.31]R;FEMBEDEquation.3,EMBEDEquation.3表示X的上界和)为X为区间X,EMBEDEquation.3],EMBEDEquation.3YEMBEDEquation.3EMBEDEquation.3的区间算法来求解.该算法不仅能求出问R:是区间]∈(R)分别],Y=[EMBEDEMBEDEquation.3且EMBED.EMBEDhi(x)=0,i=k+1,k+2,,,r.对这类问题,通常采用随机搜索的方法来解决,但是,随机搜索法不能证明所得到的解就是全局最优解.本文将非线性约束优化问题转化为可行域子域上的无约束优化问题,再利用沈祖和题(1)的可行域,而且能求出一个最优解,给出解的包含区间,并很容易获得解的逼近误差,这是随机搜索等其他方法做不到的.定义1

映射,称F(X)是函数f(x)在区间X上的区间扩张,如果对EMBED

Equation.3

定义2

定义(i)EMBEDEquation.3

下界;(ii)m(X)=12(EMBEDEquation.3

中点;(iii)w(X)=EMBEDEquation.3

的宽度.定义3

EMBEDEquation.3

(i)X<Y

Equation.3

(ii)X

Equation.3

Equation.3

假设f(x)是定义在X上以C(>0)为常数的Lipschitz连续函数,F(X)=f(m(X))-c(X-m(X)),则显然,F(X)是函数f(x)在区间X上的具有包含单调的区间扩张.

14

nnn是利用

n0,(i=1,2,,,k)或hi(x)=nnn是利用

n0,(i=1,2,,,k)或hi(x)=0(i=k+1,k+2,,,nn0hi(x)=0;Ri=-1,表X内没有可行点.EMBEDEquation.DSMT40.如果EMBEDEquation.DSMT4>0,则表示通过把原问题的等,](i=k+1,k+2,,,r),x∈X所代替,解决原EMBEDEquation.DSMT40,如果|f-minf(x)EMBEDEquation.31,f为最优值.L1中的元X,w()EMBEDEMBEDEquation.DSMT4nn,EMBEDEquation.DSMT4)=(0,0,...,0).计F(X)=f(m())+c1(-m())且F(X)=

00建两个区间L1L2初始化区间L1=(X0,F(),),L二等X,X=YX计F(X))+c1(X-m(X)),从L1nEMBED=0,则原约束优化1EMBEDnn/c1R(0,0,...,0),令R=(1,1,,,00000

000012j)=f(m(XjjjEMBED设初始域X,F,G,H分别是f,g,h在X上的区间扩张,L1L2是以(X,F(X),R)为元素的区间列,其XMoore二分原则分割得到的子域,R=(R1,R2,,,Rr)是子域的标志矢量,R的分量取值-1,01.若Ri=0,表明到目前为止,对任意x∈X,还不能判断是否满足gi(x)

EMBEDEquation.3

r),称X是未定的;Ri=1则表示对任x∈X,都满gi(x)EMBED

Equation.3

假设函f(x),gi(x),hi(xX[a,b]上常数分别c1,c2,c3的Lipschitz连续函数.给定松弛数

Equation.DSMT4

问题被解决;如果EMBEDEquation.DSMT4

式约束h(x)=0用不等式约hi(x∈[-EMBEDEquation.DSMT4

EMBEDEquation.DSMT4

问题的松弛问题;给定松弛参数

Equation.DSMT4

Equation.DSMT4

Equation.3

1)且将(X,F(X),R列入L2中第一部分计算步骤为:step10=X,(EMBEDEquation.DSMT4

,.....EMBEDEquation.DSMT4

step2[F(X),F()].step3初始为空step4step5

15

00计算Gi(X)=gi(m(X))+c2(Xjjiiji如L2为空,则转入step11,00计算Gi(X)=gi(m(X))+c2(Xjjiiji如L2为空,则转入step11,终止计算,表明初始域内没有将L2中区间按第二个元素递增排列,将第一个区间,000非空,区间个数为t,将iiiEMBEDEquation.DSMT4EMBEDEquation.DSMT40,i=1,2,,,k和hi(x)=0,i=k+1,k+2,,,EMBEDEquation.3jjj0,Ri=1;如果GiX,x0∈X’,有gi(x)0,i=1,2,,,kiEMBEDstep6j=1,2设R=(R1,R2,,,Rr);对于i=1,2,,,k,-m(X))且令Gi()=[Gi(X),Gi(X)]

如Gi(X)EMBEDEquation.DSMT4

(X>0,取Ri=-1;否则Ri=0;Step7可行点.

Step8计为(X,F(X),R),输出.step11终止计算.4.3.3算法分析带非线性约束优化问题的可行域是很难确定的,本文在Moore二分法的基础上,通过构造的区间列L中标志矢量R的分量取值来删除部分不满足约束条件的区域,在不漏解前提下,将非线性约束优化问题(1)转化为初始域子域上的无约束优化问题(2).如以上算法终止时L2L2中区间按第二个元素非减排列,重新编号为

L2={(X,F(X),R)}(i=0,1,,,t).在算法中删除的只是部分不满足约束条件的区域,所以有

X’EMBEDEquation.DSMT4

其中X’为(1)的可行域.即以上算法不漏解.

证

Equation.3

r成立.gi(x),hi(x)为X=[a,b]上的Lipschitz连续函数,所以vD>0,使得PxI[x0-D,x0+D],总有

gi(x)

16

EMBEDEquation.DSMT4],i=k+1,k+2,,,riEMBEDEquation.DSMT4X([x0,x0+XX)成立,所以EMBEDEquation.DSMT4],i=k+1,k+2,,,riEMBEDEquation.DSMT4X([x0,x0+XX)成立,所以x∈X,从而X’EMBEDEquation.DSMT4X.00[-EMBEDEquation.DSMT4,x0+iiiiX.i,EMBEDEMBEDEquation.DSMT4EMBEDEquation.DSMT4或[x0-EMBEDEquation.DSMT4i]]),hi(x)

Equation.DSMT4

同时成立.当X=[