全局优化问题的分支定界算法

第1章 绪论 1.1 *优化问题的基本概念 本节介绍*优化问题的基本概念和*优性条件. *优化是一门内容丰富、应用性很强的应用数学分支，简而言之，它主要讨论如何在众多方案中寻求*佳方案，构造寻求*优解的计算方法，以分析这些计算方法的理论性质及实际表现为主要内容.因*优化概念反映了人类实践活动中十分普遍的现象，所以*优化问题已成为现代数学的一个重要课题，其应用涉及人工智能、生产调度管理、计算机工程和模式识别等各个领域.*优化方法和理论方面的研究对改进算法、拓宽算法的应用领域以及完善算法体系具有重要作用.目前，*优化技术已作为一个重要的科学分支受到众多学者的关注，他们提出了许多解决实际问题的优化方法. 以*小化问题为例，*优化问题的一般描述如下 (1.1.1) 其中称为可行域，称为目标函数，和称为约束函数.若，则称该问题为无约束优化问题;若，则称该问题为约束优化问题. 因为，所以通过简单转换，*大化问题可以转化为上述*小化问题.鉴于此，本章以下内容均考虑*小化问题模型的求解. 在问题(1.1.1)中，若满足以下条件，则称其为线性规划问题: (1)所有变量是连续的; (2)只有一个目标函数; (3)目标函数和约束函数都是线性函数. 线性规划问题是一类很重要的优化问题，原因是许多实际问题都可以描述为线性规划问题，如炼油管理、生产计划、人力资源分布计划、经济金融计划等.解决此类问题的通用方法是单纯形方法. 当线性规划问题的部分或全部变量要求取整数时，称上述问题为整数规划或整数线性规划问题.特别地，当 x 仅能取0或1时，上述问题称为0-1整数规划问题. 当 f(x)， gi(x)和 hj(x)中至少有一个为非线性函数时，问题(1.1.1)称为非线性规划问题.函数的非线性，使得问题的求解变得非常困难.本书所解决的问题均为非线性规划问题. 在问题(1.1.1)中，假定 f(x)是连续函数，且是非空闭集.给出如下定义. 定义1.1.1 若存在 x.∈S使得对所有 x ∈S有，则称为f(x)在S上的一个全局极小点，对应值称为 f(x)在S上的一个全局极小值.能够确定出这样一个解的优化方法称为全局*优化方法. 定义1.1.2 若存在使得对任意有，则称 x.为 f(x)在S上的一个局部极小点，对应值 f(x.)称为 f(x)在S上的一个局部极小值，其中.是一个小的实数，是一个以 x.为中心，以.为半径的球，即.能够确定出这样一个解的优化方法称为局部*优化方法. 由定义1.1.1和定义1.1.2知，局部极小点未必是全局极小点. 定义1.1.3 对于*优化问题(1.1.1)，当目标函数和约束函数均为凸函数时，该问题称为凸规划问题. 对于凸规划问题，具有很好的性质，即其任一局部极小点必是全局极小点，故对于凸规划问题不存在极小点全局*优性的判断问题.对于一般的非凸规划问题，下面给出一些主要的*优性判定准则结果，详细内容参考文献[1—4]. 定理1.1.1 (Weierstrass定理)若是一非空紧集， f(x)是S上的连续函数，则 f(x)在S上至少有一个全局极小点(极大点). 可以看出，在定理1.1.1中，若将 f 的连续性替换成下半连续性，则定理仍成立.类似地，在非空紧集上，若函数 f 是上半连续性的，则 f 在S上存在全局极大值. 下面给出一些关于局部和全局极小点特征的结果，这里不妨假定问题(1.1.1)中目标函数 f(x)，约束函数和均为连续可微函数. (1)稳定点: x.∈S称为问题(1.1.1)的稳定点，若对任意的 x ∈S成立. 显然，若S= Rn，则稳定点条件变为.f(x.)=0.对于凸规划问题，稳定点总是全局极小点. (2) Fritz John 条件: 定理1.1.2 设 x.为问题(1.1.1)的可行点， f 和在点 x.处可微，在点 x.处具有一阶连续偏导数.若 x.为问题(1.1.1)的局部极小点，则存在不全为零的数，且，使. (1.1.2) 上述方程组(1.1.2)称为 Fritz John 条件，满足 Fritz John 条件的点称为 FritzJohn 点.对 Fritz John条件，若 u0=0，则这个条件变得无意义;若，则Fritz John条件就是下面的 KKT 条件. (3) KKT 条件: 定理1.1.3 设为问题(1.1.1)的可行点， f和在点处可微，在点处具有一阶连续偏导数，且向量组线性无关.若 x.为问题(1.1.1)的局部极小点，则存在数和，使. (1.1.3) 方程组(1.1.3)称为约束优化问题(1.1.1)的 KKT 条件，有时也称 KT 条件，满足KKT 条件的点 x.称为 KKT 点. 对于凸规划问题，上述 KKT 条件也是全局*优性的充分条件，但是对于非凸情形，充分性无法得到保证，且 KKT 点还可能不是局部极小点.因此，对于非凸优化问题，求解和验证全局*优解是一件非常棘手的事情，人们往往借助凸包络概念来研究非凸全局优化问题的求解方法. 本书主要研究确定约束优化问题(1.1.1)全局*优解的方法，即全局优化方法.全局优化的应用领域相当广泛，包括分子生物学、网络运输、经济金融、化学工程设计和控制、图像处理及环境工程等.解决这些实际问题的需求促使越来越多的学者从事全局优化方面的研究，全局优化也正在以惊人的速度在许多领域取得快速发展.但与局部优化方法相比，其理论和算法还远没有那么成熟和完善.一般在求解全局优化问题时会遇到以下两个困难:.1如何从当前局部极小点得到另一个更好的局部极小点;.2如何判断当前极小点是否是全局*优解.目前有很多方法可以解决**个问题，而第二个问题(即全局收敛条件)的研究仍然没有突破性的进展. 前面已经指出，当问题(1.1.1)是凸规划问题时，其局部*优解也是全局*优解，但当问题(1.1.1)是非凸优化问题时，可能存在多个非全局的局部*优解，此时经典的非线性规划技术仅能够成功地计算出此类问题的稳定点和局部*优解，因此不能使用通常意义下求解目标函数局部极小的方法确定问题的全局解.这种特性就迫使我们需要依据所研究问题的具体特点构造出可以确定全局解的全局优化方法.从构造特点上来看，这些方法可以分为确定性方法[1.8]和随机性方法[9，10]. 确定性方法是通过利用凸性、稠密性、单调性和利普希茨性等解析性质确定一有限或无限点列使其收敛于全局*优解，或在较弱情形下产生一点列，使其存在子列收敛到全局*优解的一类方法.这类方法包括:分支定界算法[11.13]、单调优化方法[14，15]、填充函数方法[5，8]、D. C.规划方法[16]等. 在实际问题中寻找全局*优解是非常困难的，随着问题规模的增大，局部*优点数目的增加，传统的确定性优化算法容易陷入局部*优解，难以寻找到全局*优解.当然，对确定性算法也可以采用多初始点的方法，使其收敛到不同的局部*优解，然后在局部*优解中寻找较好的解作为全局*优解.但是这样的方法也有明显的缺陷，它对问题本身的依赖性非常强.初始点的选取、问题的光滑性都是寻找*优解的关键.为了寻找全局*优解，一类不依赖于问题本身性质的随机性算法应运而生.这类算法对优化问题通常没有太多的假定，比较适用于求解那些不知道问题结构的优化问题，即黑匣子优化问题.随机性方法是通过利用概率机制寻求出一非确定的点列来描述迭代过程的一类方法.这类方法包括:遗传方法[17.20]、模拟退火方法[21.24]和蚁群优化方法[25.28]等.但随机性方法也有自身的一些缺点，比如计算效率低、可靠性差、不能保证全局收敛性.因此，与随机优化方法相比，确定性优化方法不仅能充分利用所研究的全局优化问题的数学模型特点及函数性质，而且通常能在给定的误差精度范围内保证算法经过有限步迭代收敛于优化问题的全局*优解. 1.2 确定性全局优化方法的基本思想及研究现状 下面给出确定性方法中一些典型而重要的全局优化方法的基本思想及一些重要问题的研究现状. 1.分支定界算法 分支定界算法是求解全局优化问题的*主要的方法之一，该算法的基本思想是对问题初始可行域逐次剖分，同时构造并计算相应的松弛问题确定*优值的下界，通过求解一系列的松弛问题产生一个单调递增的下界序列，并通过探测松弛问题*优解及所考察区域端点或中点的可行性，构造问题的一个单调递减的上界序列，当问题全局*优值的上界与下界的差满足终止性误差条件时，算法终止，从而得到所求问题的全局*优解;否则算法继续迭代下去.根据区域剖分的方法不同及上、下界计算方法的选取不同，分支定界算法大体上可分为:矩形分支松弛定界算法、锥分分支定界算法、单纯形分支对偶松弛定界算法等[11，12]. 本书将针对不同的非凸规划全局优化问题，根据问题的特殊结构，选取合适的分支方法，构造恰当的定界技巧及剪枝技巧，详细地介绍其分支定界算法. 2. D. C.规划方法 对于问题(1.1.1)，当目标函数和约束函数中至少有一个是非凸函数时，问题的求解变得比较复杂，目前还没有一个十分有效的解决办法，比如下面这种形式的优化问题， (1.2.1) 其中 X 是一紧凸集，均为 X 上的凸函数.此时由于目标函数和约束函数均为两个凸函数之差，所以这些函数就是所谓的 D. C.函数，相应的问题(1.2.1)称为 D. C.规划问题. 因为存在以下性质: (1)任何一个定义在紧凸集上的二次连续可微函数(尤其是多项式函数)都可表示成 D. C.函数; (2) Rn 中的任何闭子集都可以表示成一个 D. C.不等式的解集，其中 gs(x)是 Rn 上的连续凸函数; (3)如果f1(x)， f2(x)， ， fm(x)是 D. C.函数，则函数，也都是 D. C.函数. 所以现实中的很多问题都可归结为 D. C.规划问题(1.2.1)，这引起了人们对D. C.规划问题求解的极大兴趣. 上述D. C.规划问题有一个比较有趣的特征是该问题可归约为典范形式的问题，即可以转化为一个带线性目标函数及不多于一个凸约束和一个反凸约束的 D.C 规划问题.具体参看文献[3，4，29]. 对于D. C.规划问题的求解，人们首先通过引入新的变量，将其转化为一个目标函数为凹函数的*小化问题;然后利用凹函数在凸可行集上的*优解必在可行域的顶点处达到这一性质，提出了一些求解凹*小化问题的有效算法[3，4，29，30]. 3.单调优化方法 目标函数和约束函数均为单调函数的全局优化问题称为单调规划问题.单调规划问题经常出现在经济、工程和其他一些领域的应用中，比如*优资源配置、可靠性网络*优等问题[31.33].因为单调函数的一些运算是封闭的，所以许多*优化问题*终可归约为单调优化问题，如:多乘积规划、多项式规划、非凸二次规划和利普希茨优化等问题[30].这些问题的一般形式如下，其中均为 Rn+上的增函数. 对于上述优化问题，不失一般性，假定g(x)=0，则有.显然F(x)， G(x)都是增函数，这样初始问题就被归约为一个正则区域上的单调优化问题[33]. 在过去的十几年间，对于较低维的上述问题，人们提出了对偶基的补偿方法和参数化方法.诸如，文献[31，32]给出了一种单调函数的凸化方法.该方法首先通过使用含参数的变量替换和函数变换将上面的问题转化为一个等价的凸极大化问题，然后利用现有的求解凸极大化问题算法确定出问题的*优解.文献[33]利