运筹学发展概况 (三)

整数规划

整数规划是带整数变量的最优化问题,即求解一个全部或部分变量为整数的多元函数受约束于一组等式和不等式条件的最优化问题。整数规划的历史可以追溯到上世纪50 年代,丹齐格首先发现可以用0-1 变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函数等。他和富尔克森、约翰逊对旅行商问题的研究成为后来分支定界法和现代混合整数规划算法的开端。1958 年戈莫里发现了第一个一般线性整数规划的收敛算法-割平面方法。随着整数规划理论和算法的发展,整数规划已成为应用最广泛的最优化方法之一,特别是近年来整数规划算法技术和软件系统的发展和推广,整数规划得到了广泛的应用和发展。
整数规划问题的困难和挑战来源于3 个方面:一是大部分整数规划问题都是NP-难的,故本质上不太可能存在和线性规划与凸规划一样有效的算法;二是对整数点集合(如多面体格点理论和全单模理论)和整数

变量的函数在数学上缺乏有力的理论和工具;三是实际问题的规模往往超过现有算法的求解能力,尽管现有的一些整数规划软件可以求解任意线性、二次和非线性整数规划问题,但往往不能处理来源于实际问题的整数规划模型,例如运输和交通中的大规模0-1 混合线性整数规划问题、金融优化中的离散约束问题等。整数规划未来发展方向和关键问题包括:
(1)整数多面体凸包的刻画;
(2)随机整数规划;
(3)多层整数规划;
(4)混合0-1 二次整数规划;
(5)协正规划;
(6)半定整数规划。

动态规划

当系统模型具备马尔科夫性,同时目标函数可分且嵌套单调时,基于贝尔曼提出的最优性原理,运用动态规划可将求解多阶段全局最优决策问题分解为一系列在各时间段上的局部优化问题。相比其他解法,特别是在有扰动或在随机情况下,动态规划总能有效地提供一个在当前信息集下的最优反馈控制策略。在过去的若干年里,动态规划取得了不少可喜的进展,特别是它被扩展到多目标动态规划;动态规划应用在本世纪前后的一个重大突破是其在海量数据分析中的应用,特别是人类基因组计划完成以后,它成为生物信息学的一个基本模型和工具。

然而,在克服被贝尔曼称之为“维数灾”的这一动态规划致命弱点方面,至今尚未取得突破性的进展。所以寻求克服维数灾的有效算法对动态规划在高维问题中的应用具有紧迫性。另外,求解不可分优化问题得到的最优策略并不满足最优性原理,或不具备时间一致性,这牵涉到不可分优化问题模型本身的合理性,因此怎样找出一组可分优化问题来逼近一个给定的不可分优化问题也对动态规划发展具有它显然的重要性。

全局优化

全局优化是非线性规划的一个分支,主要研究求解非凸优化问题的全局最优或近似全局最优解。由于非凸优化问题可能存在多个不同的局部最优点,基于导数信息的卡罗胥-库恩-塔克最优性条件不再适用于刻画非凸问题的全局最优性,从而,经典的局部优化方法不能保证收敛到全局最优解。全局优化较系统的研究始于上世纪70 年代。图伊和霍斯特是早期全局优化研究的先驱者,他们在凹规划的系统研究成果使全局优化开始形成一个真正的学科。90 年代初全局优化作为非线性规划的一个分支开始受到广泛的关注,越来越多的研究者开始从事该领域的研究,特别是对一些具有特殊结构的非凸优化问题的研究取得了许多突破性的成果,如非凸二次规划,非凸多项式规划,机会约束问题的凸逼近,以及在实际应用中遇到的许多特殊形式的非凸优化问题的研究都有很多深刻的研究成果。一些基于分支-定界的全局优化通用软件的发展及其在优化建模系统中的嵌入应用使学术界和工业界可以方便地求解一定规模的非凸问题的全局解。

全局优化问题的困难在于非凸性使卡罗胥-库恩-塔克条件一般不足以保证全局最优性,从而我们无法利用局部优化算法寻找全局最优点。本质上,由于导数是局部性质,因而不能期望基于导数性质的传统优化算法有希望求到全局解,全局算法需要函数和问题的全局性质。目前的数学理论很难或无法刻画一般多元函数的全局性质,这是全局优化问题的本质困难所在。全局优化的未来发展方向和关键问题包括:
(1)凸逼近和凸松弛方法;
(2)非凸二次规划;
(3)基于模拟仿真技术的全局优化算法;
(4)特殊结构的全局优化问题。

除了上面所介绍的分支外,数学规划在近些年来兴起了若干新的分支。例如,近10 年来国际上对鲁棒优化,微分方程所控制的优化,多项式优化,稀疏优化的研究相当重视,这些新方向的研究十分活跃。在即将举行的第21 届国际数学规划大会上这些新兴的分支都安排了专题报告。我国数学规划工作者,特别是青年科技工作者要充分重视这些新的方向,力争在国际上刚刚起步阶段参与研究,这样就有可能很快占领国际制高点。

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: