非线性优化-凸非线性优化-全局最优化

有人问我这个问题;

 

(1)什么是非线性优化问题。

(2)什么是非线性凸优化问题。

(3)什么是全局最优化问题。

最优化问题

在现实生活中许多重要的问题,都涉及到选区一个最好的目标,或者为达到这个目标而选择某些参数、确定某些值,这些问题都可以归结为最优化问题。

对于一个最小值问题,其形式的描述为

(1)

这里的S为解的可行域,也称为解空间或搜索空间,条件 概括了对向量 的约束。这些约束可以包括线性或非线性函数,以及离散变量,都可以根据实际要求设置。

最优化问题的目标是找到(1)的最优解(全局最优解或局部最优解)。显然,只要改变目标函数的符号,最大值问题就可以转变成最小值问题,因此,本文在说明都是以最小值问题问标准。解决最优化问题的算法称为最优化算法,可以分为经典优化算法和启发式优化算法。

Ø         什么是线性优化问题:

如果:f(x), g(x), h(x) 都是线性的…. 该问题就是线性优化问题

Ø         什么是非线性优化问题:

如果:f(x), g(x), h(x) 都是有一个是非线性的,。。。 该问题就是

非线性问题。

Ø         什么是非线性凸优化问题。

如果S.T是凸集合,且F(x)是凸函数,。。。。则该问题时非线性的优化问题。

Ø         什么是全局最优化问题。

必须面白一个概念:局部最优和全局最优
 http://ariszheng.googlepages.com/3.jpg (图的地址)

如图有三个高点…. 每个高点都是一个局部最优的,但是全局最优只由一个红的那个,(全局最优点可以有多个,但是最优值只有一个)

 

但是; 非线性凸优化问题就只有一个局部最优解,那个解也就是全局最优,线性优化问题本身就是凸优化问题。

 

参考内容:

http://blog.csdn.net/aris_zzy/archive/2006/04/13/662478.aspx(论全局最优化)

(附录1)经典优化算法

而经典优化算法又分为线形与非线性最优化算法,下面分别对两类算法的发展及常用的软件包做了介绍。

1. 线性最优化[1][10]:

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

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

在互联网上能访问到的解线性和整数规划问题的软件还有:EQPS(线性,整数和非线性规划),FMP(线性和混合整数规划),HS/LPLO(线性规划),KORBX(线性规划),LAMPS(线性和整数规划),LPBLP(线性规划),MILP(混合整数规划),MINTO(混合整数规划), MPSIII(线性和混合整数规划),OML(线性和混合整数规划), OSL(线性,二次和混合整数规划),PROCLP(线性和整数规划),WB(线性和混合整数规划),WHIZARD(线性和混合整数规划),XPRESSMP(线性和混合整数规划)等[41]。

2.非线性最优化[1][2][3][10]:

非线性规划的一个重要理论是1951年Kuhn-Tucker最优条件(简称KT条件)的建立[2].此后的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年代研究解非线性规划问题的内点法和有限储存法. 可以毫不夸张的说, 这半个世纪是最优化发展的黄金时期.

    与线性规划相比,非线性规划软件还不够完善. 但是已有大量解非线性规划问题的软件, 其中有相当一部分可从互联网上免费下载.LANCELOT是由Conn,Gould和Toint研制的解大规模最优化问题的软件包,适合解无约束最优化、非线性最小二乘、边界约束最优化和一般约束最优化问题.这个软件的基本思想是利用增广Lagrange函数来处理约束条件, 在每步迭代中解一个边界约束优化子问题, 其所用的方法结合信赖域和投影梯度等技术.MINPACK是美国Argonne国家实验室研制的软件包,适合求解非线性方程组和非线性最小二乘问题, 所用的基本方法是阻尼最小二乘法, 此软件可以从网上图书馆获得. PROC NLP是SAS软件公司研制的SAS商业软件中OR模块的一个程序,这个程序适合解无约束最优化、非线性最小二乘、线性约束最优化、二次规划和一般约束最优化问题.TENMIN是Schnabel等研制的解中小规模问题的张量方法软件。在互联网上能访问到的解非线性最优化问题的软件还有:CONOPT(非线性规划),DOT(优化设计工具箱),Excel and Quattro Pro Solvers(线性,整数和非线性规划),FSQP(非线性规划和极小极大问题),GRG2(非线性规划), LBFGS(有限储存法),LINDO(线性、二次和混合整数规划),LSSOL(最小二乘和二次规划),MINOS(线性和非线性规划),NLPJOB(非线性多目标规划), OPTPACK(约束和无约束最优化),PETS(解非线性方程组和无约束问题的并行算法),QPOPT(线性和二次规划),SQOPT(大规模线性和凸二次规划),SNOPT(大规模线性、二次和非线性规划),SPRNLP(稀疏最小二乘,稀疏和稠密非线性规划),SYSFIT(非线性方程组的参数估计),TENSOLVE(非线性方程组和最小二乘), VE10(非线性最小二乘)等[38][39][40][41].

 

本文来自CSDN博客,转载请标明出处:http://blog.csdn.net/aris_zzy/archive/2007/04/06/1554202.aspx

发表评论

电子邮件地址不会被公开。 必填项已用*标注

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>