资源描述：
《浅谈最优化方法的发展及其优化软件new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1浅谈最优化方法的发展及其优化软件王建迟学斌谷同祥（中国科学院计算机网络信息中心超级计算中心100080jwang@jupiter.cnc.ac.cn）摘要本文描述了最优化问题的基本概念、分类和通常的求解方法，全局最优化在特定领域里的最近发展，同时简单介绍了几个优化软件。关键词全局最优化，确定性方法，单调最优化方法，二次多项式规划引言从上个世纪后半期开始，最优化这门学科蓬勃发展。许多新的理论和算法已经用来解决科学计算和工程应用中的许多问题。在现实生活中，最优化问题也存在于方方面面，其应用遍布于工农业生产、工程技
2、术、交通运输、生产管理、经济计划、国防、金融、分配和定位问题、运筹学、统计、结构优化、工程设计、网络传输问题、数据库问题、化学工程设计和控制、分子生物学等方面。最优化问题已受到科研究构、政府部门和产业部门的高度重视。很多实际问题都可以抽象转化成最优化问题，然后从数学的角度求解其最优解，即对于给出的实际问题，从众多的选择中选出符合条件的最优方案。最优化可以追溯到十分古老的极值问题。为了求解最优化问题，人们构造了很多十分经典的计算方法。并且它们很多都有了串行实现，但是在求解如天气预报、石油勘探等大规模问题时，用串行
3、算法要用时几天，几年甚至更长时间，于是最优化问题的并行计算是十分有效的途径，好的算法可以节约大量的时间。我们即将把一些成熟的并行优化软件在网络信息中心的超级计算机－曙光2000上实现，为用户提供更加完备的并行优化环境。1、最优化问题的基本概念与分类最优化问题的一般形式是：minf(x)(1.1）s.t.(P)c(x)=0,i=1,?,m′,(1.2)ic(x)≥0,i=m′+1,?,m,(1.3)in其中x=(x,x,?,x)T∈R，即x为n维向量，而f(x)和c(x)，i=1,2,?,m,s.t.12ni是s
4、ubjectto的缩写，表示x受约束条件（1.2）、（1.3）的限制；f(x)称为目标函数，（1.2）称为等式约束，（1.3）称为不等式约束。1受到国家重点基础研究专项（G1999032805）和国家高技术研究发展计划（2001AA111043）的支持1x的取值范围叫作问题(P)的可行域D，其中的x叫作可行解(feasiblesolution)。**如果f(x)=minf(x)并且x∈D称作全局最优解(globaloptimalsolution)，如果***在包含x的适当邻域内，f(x)=minf(x)成立，称
5、x为局部最优解(localoptimalsolution)。求解最优化问题就是要求目标函数f(x)在约束条件（1.2）、（1.3）下的极小点，即求出全局最优解。根据变量可分为变量取连续实数的连续最优化问题(continuousoptimizationproblem)以及取整数或者类似0，1离散值的离散最优化问题(discreteoptimizationproblem)。后者多用组合性质来表达，亦称为组合优化问题(combinatorialoptimizationproblem)。连续最优化问题分为f(x)和c(
6、x)，i=1,2,?,m,都是线性函数，则称为线性规划问i题(linearprogrammingproblem)；若f(x)与各c(x)，i=1,2,?,m,中至少有一个非i线性函数，就称为非线性规划问题(nonlinearprogrammingproblem)，并且如果f(x)还具有特殊形式：l2f(x)＝∑fi(x)i=1则称此类问题为非线性最小二乘问题。根据约束条件，若m′=m=0，也就是不存在约束，则问题(P)就化为古典的求函数极值的问题，我们称之为无约束优化问题；若m>0，即有等式和/或不等式约束存在
7、，则称为约束最优化问题。通常所说的约束最优化问题均指非线性规划问题。2、求解最优化问题的常用方法对不同类型的问题有不同的求解方法，解线性规划问题的单纯形法(simplexmethod)、整数规划的分枝定界法(branchandboundmethod)和枚举法(enumerativealgorithm)，解非线性问题的牛顿法(Newtonmethod)、共轭梯度法(conjugategradientmethod)、拟牛顿法(quasi-Newtonmethod)、非二次模型最优化方法(nonquadraticmo
8、deloptimization)、罚函数法(penaltyfunctionmethod)、可行方向法(feasibledirectionmethod)、信赖域法(trustregionmethod)等。经验表明，求解对于数学结构信息知道很少的连续最优化问题，分枝定界法(branchandbound)通常是最好的方法。3、全局最优化(globaloptimization)方面的新发展科学
