My dreams and endeavors for SMDG

最优化理论、方法、软件及应用（待续）

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

1． 线性最优化

线性最优化, 又称线性规划, 是运筹学中应用最广泛的一个分支。这是因为自然科学和社会科学中许多问题都可以近似地化成线性规划问题。 线性规划理论和算法的研究及发展共经历了三个高潮, 每个高潮都引起了社会的极大关注。 线性规划研究的第一高潮是著名的单纯形法的研究。 这一方法是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（线性和混合整数规划）等。

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有两个版本: 简本和用户版本。 简本不需并行化技术, 而用户版本允许多种复杂运算, 包含并行化处理。 此软件可以通过

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(非线性最小二乘)等。

Studies serve for delight, for ornament, and for ability. Their chief use for delight, is in privateness and retiring; for ornament, is in discourse; and for ability, is in the judgment and disposition of business. For expert men can execute, and perhaps judge of particulars, one by one; but the general counsels, and the plots and marshalling of affairs, come best from those that are learned. To spend too much time in studies is sloth; to use them too much for ornament, is affectation; to make judgment wholly by their rules, is the humour of a scholar. They perfect nature, and are perfected by experience: for natural abilities are like natural plants, that need pruning by study; and studies themselves do give forth directions too much at large, except they be bounded in by experience. Crafty men contemn studies, simple men admire them, and wise men use them; for they teach not their own use; but that is a wisdom without them, and above them, won by observation. Read not to contradict and confute; nor to believe and take for granted; nor to find talk and discourse; but to weigh and consider. Some books are to be tasted, others to be swallowed, and some few to be chewed and digested; that is, some books are to be read only in parts; others to be read, but not curiously; and some few to be read wholly, and with diligence and attention. Some books also may be read by deputy, and extracts made of them by others; but that would be only in the less important arguments, and the meaner sort of books; else distilled books are, like common distilled waters, flashy things.

Reading makes a full man; conference a ready man; and writing and exact man. And therefore, if a man write little, he had need have a great memory; if he confer little, he had need have a present wit; and if he read little, he head need have much cunning, to seem to know that he does not. Histories make men wise; poets witty; the mathematics subtle; natural philosophy deep; moral grave; logic and rhetoric able to contend. Abeunt studia in mores. Nay there is no stond or impediment in the wit, but may be wrought out by fit studies: like as diseases of the body may have appropriate exercises. Bowling is good for the stone and reins; shooting for the lungs and breast; gentle walking for the stomach; riding for the head; and the like. So if a man's wit be wandering, let him study the mathematics; for in demonstrations, if his wit be called away never so little, he must begin again. If his wit be not apt to distinguish or find differences, let him study the schoolmen; for they are cymini sectores. If he be not apt to beat over matters, and to call up one thing to prove and illustrate another, let him study the lawyers' cases. So every defect of the mind may have a special receipt.

On the greenery of protect of choreographic,Is the mood of the fresh and cool dew dropsOn the greenery of protect of choreographic,Is the mood of the fresh and cool dew drops .

读书足以冶情，足以博彩，足以长才。其冶情也，最见于独处幽居之时；其博彩也，最见于高谈阔论之中；其长才也，最见于处世判事之际。练达之士虽能分别处理细事或一一判别枝节，然纵观统筹、全局策划，则非好学深思者莫属。读书费时过多易惰，文采藻饰太盛则矫，全凭条文断事乃学究故态。读书补天然之不足，经验又补读书之不足；因为天生才干犹如自然花草，读书之后方知如何修剪移接，而书中所示，如不以经验范之，则又大而无当。有手艺者鄙读书，无知者羡读书，唯明智之士用读书，然书并不以用处告人，用书之智不在书中，而在书外，全凭观察得之。读书时不可存心诘难作者，不可尽信书上所言，亦不可只为寻章摘句，而应推敲细思。书有可浅尝者，有可吞食者，少数则须咀嚼消化。换言之，有只须读其部分者，有只须大体涉猎者，少数则须全读，读时须全神贯注、孜孜不倦。书亦可请人代读，摘要也可请人代作，但只限题材较次或价值不高者，否则书经提炼犹如水经蒸馏，淡而无味矣。

读书使人充实，讨论使人机智，笔记使人准确。因此不常动笔者须记忆特强，不常讨论者须天生聪颖，不常读书者须欺世有术，始能无知而显有知。读史使人明智，读诗使人灵秀，数学使人周密，科学使人深刻，伦理学使人庄重，逻辑修辞使人善辩。凡有所学，皆成性格。人之才智如有滞碍，无不可读适当之书使之顺畅，一如身体百病，皆可借相宜之运动除之。保龄利睾肾，射箭利胸肺，慢步利肠胃，骑马利头脑，诸如此类。如智力不集中，可令读数学，因为演题须全神贯注，稍有分散即须重演；如不能辩异，可令读经院哲学，因为研究经院哲学者吹毛求疵者也；如不善分析论证，不善以一物阐证另一物，可令读律师之案卷。头脑中凡有缺陷，皆有特药可医。