线性和非线性最优化理论、方法、软件及应用

zhonggang_nuaa

1 @% y$ j: m, B I1 D. I M

最优化在航空航天、生命科学、水利科学、地球科学、工程技术等自然科学领域和经济金融等社会科学领域有着广泛和重要的应用, 它的研究和发展一直得到广泛的关注. 最优化的研究包含理论、方法和应用.最优化理论主要研究问题解的最优性条件、灵敏度分析、解的存在性和一般复杂性等.而最优化方法研究包括构造新算法、证明解的收敛性、算法的比较和复杂性等.最优化的应用研究则包括算法的实现、算法的程序、软件包及商业化、在实际问题的应用. 这里简介一下线性和非线性最优化理论、方法及应用研究的发展状况.

1. 线性最优化

$ H- B2 S, f4 k N2 k9 O) N

线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支.这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题. 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注. 线性规划研究的第一高潮是著名的单纯形法的研究. 这一方法是Dantzig在1947年提出的,它以成熟的算法理论和完善的算法及软件统治线性规划达三十多年. 随着60年代发展起来的计算复杂性理论的研究, 单纯形法在七十年代末受到了挑战. 1979年前苏联数学家Khachiyan提出了第一个理论上优于单纯形法的所谓多项式时间算法--椭球法, 曾成为轰动一时的新闻, 并掀起了研究线性规划的第二个高潮. 但遗憾的是广泛的数值试验表明, 椭球算法的计算比单纯形方法差.

1984年Karmarkar提出了求解线性规划的另一个多项式时间算法. 这个算法从理论和数值上都优于椭球法, 因而引起学术界的极大关注, 并由此掀起了研究线性规划的第三个高潮. 从那以后, 许多学者致力于改进和完善这一算法,得到了许多改进算法.这些算法运用不同的思想方法均获得通过可行区域内部的迭代点列, 因此统称为解线性规划问题的内点算法. 目前内点算法正以不可抗拒的趋势将超越和替代单纯形法.

线性规划的软件, 特别是由单纯形法所形成的软件比较成熟和完善.这些软件不仅可以解一般线性规划问题, 而且可以解整数线性规划问题、进行灵敏度分析, 同时可以解具有稀疏结构的大规模问题.CPLEX是Bixby基于单纯形法研制的解线性和整数规划的软件, CPLEX的网址是http://www.cplex.com/. 此外,这个软件也可以用来解凸二次规划问题, 且特别适合解大规模问题. PROC LP是SAS软件公司研制的SAS商业软件中OR模块的一个程序.

这个程序是根据两阶段单纯形法研制的,可以用来解线性和整数规划问题并可进行灵敏度分析, 是一个比较完善的程序.用户可以根据需要选择不同的参数来满足不同的要求。关于内点法的软件也在研制之中.BPMPD是Cs.Mzos基于原始对偶内点法研制的解线性和整数规划的软件，其FTP地址是ftp://ftp.sztaki.hu/pub/oplab/SOFTWARE/BPMPD/,可以自由下载.此外,在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS（线性，整数和非线性规划）,FMP（线性和混合整数规划），HS/LPLO（线性规划），KORBX（线性规划），LAMPS（线性和整数规划），LPBLP（线性规划），MILP（混合整数规划），MINTO（混合整数规划）， MPSIII（线性和混合整数规划），OML（线性和混合整数规划）， OSL（线性，二次和混合整数规划），PROCLP（线性和整数规划），WB（线性和混合整数规划），WHIZARD（线性和混合整数规划），XPRESSMP（线性和混合整数规划）等.

& h4 W% w. ~" R. a8 N% n5 Y1 v

2.非线性最优化

在实际研究工作和生产实践中存在大量非线性最优化问题, 把它们完全简化成线性问题来处理是不妥当的.随着科学技术和计算机的发展, 这些实际问题具有这样一些特点.一是问题的变量比较多, 因为问题涉及的因素越来越多; 二是问题的规模越来越大;三是问题越来越复杂, 问题的非线性程度越来越高. 这类问题通常描述成在一组非线性约束条件下寻求某一非线性目标函数的最小或最大值。

非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立.此后的50年代主要是对梯度法和牛顿法的研究.以Davidon(1959), Fletcher和Powell(1963)提出的DFP方法为起点, 60年代是研究拟牛顿方法活跃时期, 同时对共轭梯度法也有较好的研究. 在1970年由Broyden,Fletcher,Goldfarb 和Shanno从不同的角度共同提出的BFGS方法是目前为止最有效的拟牛顿方法. 由于Broyden, Dennis 和More的工作使得拟牛顿方法的理论变得很完善. 70年代是非线性规划飞速发展时期, 约束变尺度(SQP)方法(Han和Powell为代表)和Lagrange乘子法(代表人物是Powell 和Hestenes)是这一时期主要研究成果.计算机的飞速发展使非线性规划的研究如虎添翼.80年代开始研究信赖域法、稀疏 拟牛顿法、大规模问题的方法和并行计算, 90年代研究解非线性规划问题的内点法和有限储存法. 可以毫不夸张的说, 这半个世纪是最优化发展的黄金时期.

与线性规划相比，非线性规划软件还不够完善. 但是已有大量解非线性规划问题的软件, 其中有相当一部分可从互联网上免费下载.BTN是利用线搜索技术的块截断牛顿方法解无约束问题的软件，近似牛顿方向是通过块共轭梯度法解牛顿方程得到. 块状结构比较方便对线性代数方程和函数计算进行并行化处理. BTN有两个版本: 简本和用户版本. 简本不需并行化技术, 而用户版本允许多种复杂运算, 包含并行化处理. 此软件可以通过

3 k4 b( a; J+ F) e. ]/ C5 O

ftp://netlib2.cs.utk.edu/opt获得。BQPD是Fletcher研制的解二次规划的软件, 所使用的基本方法是零空间积极集法. DONLP2是Spellucci研制的用SQP方法解一般非线性约束问题的软件，适合解小规模优化问题, 可以从网址ftp://netlib2.cs.utk.edu/opt/donlp2/上免费下载。HOOKE是解无约束最优化问题的一个直接方法的软件，可以通过 ftp: //netlib2.cs.utk.edu /opt /hooke.c获得。LANCELOT是由Conn,Gould和Toint研制的解大规模最优化问题的软件包,适合解无约束最优化、非线性最小二乘、边界约束最优化和一般约束最优化问题.这个软件的基本思想是利用增广Lagrange函数来处理约束条件, 在每步迭代中解一个边界约束优化子问题, 其所用的方法结合信赖域和投影梯度等技术.MINPACK是美国Argonne国家实验室研制的软件包，适合求解非线性方程组和非线性最小二乘问题, 所用的基本方法是阻尼最小二乘法, 此软件可以从网上图书馆获得. PROC NLP是SAS软件公司研制的SAS商业软件中OR模块的一个程序，这个程序适合解无约束最优化、非线性最小二乘、线性约束最优化、二次规划和一般约束最优化问题.TENMIN是Schnabel等研制的解中小规模问题（$n<100$）的张量方法软件。在互联网上能访问到的解非线性最优化问题的软件还有:CONOPT（非线性规划），DOT（优化设计工具箱），Excel and Quattro Pro Solvers（线性，整数和非线性规划），FSQP（非线性规划和极小极大问题），GRG2（非线性规划)， LBFGS（有限储存法），LINDO（线性、二次和混合整数规划），LSSOL（最小二乘和二次规划），MINOS（线性和非线性规划），NLPJOB（非线性多目标规划）， OPTPACK（约束和无约束最优化）,PETS（解非线性方程组和无约束问题的并行算法），QPOPT（线性和二次规划）,SQOPT（大规模线性和凸二次规划），SNOPT（大规模线性、二次和非线性规划），SPRNLP（稀疏最小二乘,稀疏和稠密非线性规划），SYSFIT（非线性方程组的参数估计），TENSOLVE（非线性方程组和最小二乘）， VE10(非线性最小二乘)等.

# O7 p) @5 o1 w6 h, q7 ~3 \

0 h$ n8 M+ t) _8 a- C; @& x ( N0 @' H5 b3 z3 Y# H! I2 `

3.最优化的应用

最优化的应用是非常广泛的, 下面仅就最优化在金融和航空方面的应用作一点介绍.

3.1金融和最优化

随着世界经济的发展和知识经济的到来, 金融数学已变成一个热门研究课题,普遍得到各国政府的重视和支持. 而金融数学的一个重要方面是与优化理论及算法相联系的. 诺贝尔经济学奖得主马尔柯维茨提出证券组合选择的均值--方差模型(MV模型)便是一个二次规划问题. 这个模型使得证券组合选择方法实现了从定性描述到定量描述质的飞跃,使得人们可以科学而准确地分析与选择投资策略.

3.2 航空和最优化

' e" o+ N$ [. [6 X/ o; R4 B

最优化在航空方面的应用也很多.从90年代引起国际学术界重视的"气动数值优化设计"是计算流体力学和优化设计技术相结合来研究飞行器气动性能及其它流动问题的方法. 这一方法的研究包含了大量的最优化算法和应用研究.

6 N- ~/ f5 o1 D* ^9 _8 `

在航空航天广泛应用的结构优化设计是最近三十多年来发展起来的一门新兴的现代化科学技术. 它的发展是与最优化理论和方法的发展是密不可分的. 从60年代起, 结构设计问题开始用一般非线性规划问题来处理. 此后, 一种新的优化理论和方法一出现并被用到结构设计问题上来, 从而推动了结构优化设计的快速发展.目前处于优化研究热点的信赖域法被用于解飞机设计中颤振问题模型, 收到了良好效果.

6 l3 I# U0 D+ W

[此贴子已经被作者于2005-1-8 16:38:50编辑过]

andrew001

长知识了

roman_900

谢了

xqq309

很不错!大家努力哈!

malei1984mm

好事了

[em05]

yorhun

very good!

cyberagui

好，现在有的学了。　

lilycang

介绍得不错

lilycang

有关规划论的内容首要的还是线性规划，它是其他一些理论的基础，诸如对策论、图论等都可以转化为线性规划问题

cyberagui

真不错，楼主的说明真是让我大开眼界。　看来要学的东西又多了！　呵呵。[em06]