运筹学非线性规划_第1页
运筹学非线性规划_第2页
运筹学非线性规划_第3页
运筹学非线性规划_第4页
运筹学非线性规划_第5页
已阅读5页,还剩72页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、第三章 非线性规划,请回顾线性规划: ,其目标与约束函数 均为线性的。线性规划具有相对完美的理论与方法,应用也很广泛,但它终究不能穷尽各种优化问题,因为世界是非线性的。 非线性规划(Nonlinear Programming)研究具有非线性构成函数的优化问题,是运筹学中相对活跃的重要研究分支。,第一节 基本概念,一、非线性规划问题与模型,投资决策问题,2.模型,二 、模型的解及相关概念,1.可行解与最优解,可行解:约束集D中的X。,最优解:如果有 ,对于任意的 , 都有 ,则称 为(NLP)的最优 解,也称为全局最小值点。,局部最优解:如果对于 ,使得在 的邻 域 中的任意 都有 ,则称 为(

2、NLP)的局部最 优 解,也称为局部最小值点。,例1:考虑非线性问题,如果约束改为 呢?,2.梯度、海塞阵与泰勒公式,梯度,海塞阵,泰勒公式,例2:写出 在 点的二阶泰勒展开式,解:,3.极值的条件,对于无约束极值问题,可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数 与一元函数 的极值条件加以对比并归纳如下:,例3:求 的极小值点,解,4.凸规划,注:判断一个可导函数f(X)是否是凸函数的方法 一元函数f(x) :二阶导大于等于零; 多元函数f(X) :海塞阵半正定。,凸规划,性质:约束集是凸集; 最优解集是凸集; 任何局部最优解也是全局最优解; 若目标函数是严格凸函数,且最优解

3、存在,则 其最优解是唯一的。,在非线性规划模型(NLP)中,若目标函数f(X)是凸函数,不等式约束函数 为凹函数,等式约束函数 为仿射函数,则称(NLP)是一个凸规划。,例4:判断下面的非线性规划是否为凸规划,标准化,计算,第二节 无约束极值问题,一般模型:,求解(f(X)可微):应用极值条件求解,往往得到一个非线 性的方程组,求解十分困难。因此,求 解无约束问题一般 采用迭代法,称为下降类算法。,一、下降类算法的基本步骤与算法收敛性,1.基本思想,2.基本步骤,(1),(2),(3),(4),注:不同的搜索方向,就形成了不同的算法,不 同的算法所产生的点列收敛于最优解的速度 也不一样。,3.

4、收敛性,衡量标准:,二阶收敛超线性收敛线性收敛,二、一维搜索,1.分数法(斐波那契法),基本思想,怎样在区间中取点最好?,基本概念,步骤,例5:,2. 0.618法,区别:每次取点得比例是定值0.168,即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。,特点:简单,更易于应用; 效果也比较好。,3.近似最佳步长公式,例6:,三、梯度法和共轭梯度法,1.梯度法,一般步骤,(1),(2),(3),(4),例7:,上例中,目标函数是同心圆族。无论初始点选在何处,在该点的负梯度方向总是指向圆心,而圆心就是极小点,故沿负梯度方向搜索一步便可得极小点。,但对于一般的函数,若每次迭代均采

5、用负梯度方向,则由于这些方向是彼此正交的,很可能形成开头几步下降较快,但后来便产生直角锯齿状的“拉锯”现象,收敛速度很慢。可以证明,梯度法是线性收敛的。,注:,2.共轭梯度法,基本概念,这一性质说明采用共轭方向作为搜索方向,对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的性质往往与二次函数很相似,因此共轭方向算法一般也可用于其他非线性函数,并且至少是线性收敛的。,一般步骤,例8:,四、牛顿法与拟牛顿法,1.牛顿法,牛顿方向,一般步骤,当一维搜索是精确的,牛顿法为二阶收敛。,缺点:,2.拟牛顿法,DFP方法的一般步骤,例9:,第三节 约束极值问题,一般模型,1.基本概念和性质,起作用约束,可行下降方向,可行下降方向的条件,2.最优性条件(K-T条件),定理 (K-T条件),例10:利用KT条件求解下面的非线性规划,为解此方程组,可分几种情况考虑:,例11:考虑非线性规划并验证它为凸规划,用KT条件求解,计算目标和约束函数的海赛阵,3.二次规划,一般模型,思考:能否在此基础上构想基于线性规划求解的方法?,例12: 求解二次规划,解,求得的结果是:,4.罚函数,外点法的关键是基于(NLP)构造一个新的目标函数P(X,M),称为罚函数。,当X是可行点时,罚项为0,当X不是可行点时

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论