《非线性规划 (2)2精选PPT.ppt》由会员分享,可在线阅读,更多相关《非线性规划 (2)2精选PPT.ppt(77页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、非线性规划第1页,此课件共77页哦第一节第一节 基本概念基本概念一、非线性规划问题与模型1.问题问题生产计划问题x:产量;P(x):价格;C(x)成本第2页,此课件共77页哦 投资决策问题第3页,此课件共77页哦 2.模型模型第4页,此课件共77页哦 二、模型的解及相关概念1.可行解与最优解可行解与最优解可行解:约束集D中的X。最优解:如果有 ,对于任意的 ,都有 ,则称 为(NLP)的最优 解,也称为全局最小值点。局部最优解:如果对于 ,使得在 的邻 域 中的任意 都有 ,则称 为(NLP)的局部最 优 解,也称为局部最小值点。第5页,此课件共77页哦例1:考虑非线性问题如果约束改为 呢?第
2、6页,此课件共77页哦2.梯度、海塞阵与泰勒公式梯度、海塞阵与泰勒公式 梯度第7页,此课件共77页哦海塞阵第8页,此课件共77页哦泰勒公式第9页,此课件共77页哦例2:写出 在 点的二阶泰勒展开式解:第10页,此课件共77页哦3.极值的条件极值的条件对于无约束极值问题,可以利用微积分的知识给出局部极值点的条件。将n(n1)元函数 与一元函数 的极值条件加以对比并归纳如下:充分条件 必要条件第11页,此课件共77页哦例3:求 的极小值点解第12页,此课件共77页哦4.凸规划凸规划凸函数:f(X)是定义在凸集D上且满足对任意 有下式成立的函数:若不等式中严格不等号成立,则称f(X)为严格凸函数注:
3、判断一个可导函数f(X)是否是凸函数的方法一元函数f(x):二阶导大于等于零;多元函数f(X):海塞阵半正定。第13页,此课件共77页哦凸规划性质:约束集是凸集;最优解集是凸集;任何局部最优解也是全局最优解;若目标函数是严格凸函数,且最优解存在,则 其最优解是唯一的。在非线性规划模型(NLP)中,若目标函数f(X)是凸函数,不等式约束函数 为凹函数,等式约束函数 为仿射函数,则称(NLP)是一个凸规划。第14页,此课件共77页哦例4:判断下面的非线性规划是否为凸规划标准化计算第15页,此课件共77页哦第二节第二节 无约束极值问题无约束极值问题一般模型:求解(f(X)可微):应用极值条件求解,往
4、往得到一个非线 性的方程组,求解十分困难。因此,求 解无约束问题一般 采用迭代法,称为下降类算法。第16页,此课件共77页哦一、下降类算法的基本步骤与算法收敛性1.基本思想基本思想第17页,此课件共77页哦2.基本步骤基本步骤(1)(2)(3)(4)注:不同的搜索方向,就形成了不同的算法,不 同的算法所产生的点列收敛于最优解的速度 也不一样。第18页,此课件共77页哦3.收敛性收敛性衡量标准:二阶收敛超线性收敛线性收敛第19页,此课件共77页哦二、一维搜索第20页,此课件共77页哦1.分数法分数法(斐波那契法)基本思想怎样在区间中取点最好?第21页,此课件共77页哦基本概念满足绝对精度:满足相
5、对精度:斐波那契数:553421138532119876543210第22页,此课件共77页哦第23页,此课件共77页哦步骤第24页,此课件共77页哦例5:第25页,此课件共77页哦2.0.618法法区别:每次取点得比例是定值0.168,即每次区间内两 点得位置均在区间相对长度得0.328和0.168处。特点:简单,更易于应用;效果也比较好。第26页,此课件共77页哦3.近似最佳步长公式近似最佳步长公式第27页,此课件共77页哦例6:第28页,此课件共77页哦三、梯度法和共轭梯度法1.梯度法梯度法第29页,此课件共77页哦 一般步骤(1)(2)(3)(4)第30页,此课件共77页哦例7:第31
6、页,此课件共77页哦上例中,目标函数是同心圆族。无论初始点选在何处,在该点的负梯度方向总是指向圆心,而圆心就是极小点,故沿负梯度方向搜索一步便可得极小点。但对于一般的函数,若每次迭代均采用负梯度方向,则由于这些方向是彼此正交的,很可能形成开头几步下降较快,但后来便产生直角锯齿状的“拉锯”现象,收敛速度很慢。可以证明,梯度法是线性收敛的。注:第32页,此课件共77页哦2.共轭梯度法共轭梯度法基本概念第33页,此课件共77页哦 这一性质说明采用共轭方向作为搜索方向,对二次函数求极小可以有限步终止。由此可构造二次函数的共轭方向算法。共轭方向算法用于二次函数时均具有二次终止性。由于一般函数在一点附近的
7、性质往往与二次函数很相似,因此共轭方向算法一般也可用于其他非线性函数,并且至少是线性收敛的。第34页,此课件共77页哦一般步骤 第35页,此课件共77页哦第36页,此课件共77页哦例8:第37页,此课件共77页哦第38页,此课件共77页哦四、牛顿法与拟牛顿法1.牛顿法牛顿法牛顿方向第39页,此课件共77页哦第40页,此课件共77页哦一般步骤 当一维搜索是精确的,牛顿法为二阶收敛。第41页,此课件共77页哦缺点:计算海赛阵的逆的工作量很大。要求f(X)的二阶导存在且海赛阵是正定的(以保证H的逆阵存在和算法是下降的);改进:构造一个矩阵 代替牛顿方向中的 ,使 满足:正定 只用到f(X)的一阶导信
8、息随着k的增加,充分接近于称 为尺度阵。由于它每次都在变,故称以 代替牛顿法中的 的算法为变尺度法。第42页,此课件共77页哦2.拟牛顿法拟牛顿法拟牛顿法是尺度阵 满足 的一类变尺度法;拟牛顿法一般是超线性收敛的;DFP是一种著名的拟牛顿法;当f(X)为二次函数时,DFP法是共扼方向法,且具有二 次终止性。第43页,此课件共77页哦DFP方法的一般步骤 第44页,此课件共77页哦例9:第45页,此课件共77页哦第46页,此课件共77页哦第47页,此课件共77页哦第三节第三节 约束极值问题约束极值问题一般模型第48页,此课件共77页哦1.基本概念和性质基本概念和性质起作用约束第49页,此课件共7
9、7页哦可行下降方向第50页,此课件共77页哦可行下降方向的条件第51页,此课件共77页哦第52页,此课件共77页哦2.最优性条件最优性条件(K-T条件)第53页,此课件共77页哦第54页,此课件共77页哦第55页,此课件共77页哦定理定理(K-T条件)第56页,此课件共77页哦例10:利用KT条件求解下面的非线性规划第57页,此课件共77页哦为解此方程组,可分几种情况考虑:第58页,此课件共77页哦例11:考虑非线性规划并验证它为凸规划,用KT条件求解第59页,此课件共77页哦计算目标和约束函数的海赛阵第60页,此课件共77页哦第61页,此课件共77页哦3.二次规划二次规划一般模型第62页,此
10、课件共77页哦第63页,此课件共77页哦思考:能否在此基础上构想基于线性规划求解的方法?第64页,此课件共77页哦第65页,此课件共77页哦第66页,此课件共77页哦例12:求解二次规划解第67页,此课件共77页哦第68页,此课件共77页哦 1 1 3/13-2/13-4/39 1 4/13 0 9/26-3/13-9/26 3/13 2/13 133/13 0 132/13 0 2/3 1-2/3-4/9-26/9 3 1/3 2/3 1 2 033/13 1-2/3 -1 2/3 4/9 26/9 22/3 1 1/3-1/3 1-2/9-4/9 4/3 0 1 1 -5 1/3-2/3
11、1/3 2/3 1 2 0 5 1 -1 2 2 10 1 4/3 1 -1 3-2/3-4/3 4 1 1 1 -5 -2 -2 2 1 2 3 6 0 1 -1 2 2 10 1 4 1 -1 3 2 8 1 1 1 0 0 0 0 0 0第69页,此课件共77页哦求得的结果是:第70页,此课件共77页哦4.罚函数罚函数基本思想:将约束与目标组合在一起,化为无约束 极值问题求解。内点法:从可行域的内部逐步逼近最优解。外点法:从可行域的外部逐步逼近最优解。第71页,此课件共77页哦外点法的关键是基于(NLP)构造一个新的目标函数P(X,M),称为罚函数。当X是可行点时,罚项为0当X不是可行点时,罚项是很大的整数。对P(X,M)求极小,可采用无约束优化方法,罚项能保证X逐步趋近可行域。第72页,此课件共77页哦一般步骤:第73页,此课件共77页哦例13:求解非线性规划解 构造罚函数第74页,此课件共77页哦第75页,此课件共77页哦例14:求解非线性规划解 构造罚函数第76页,此课件共77页哦第77页,此课件共77页哦