《非线性规划的基本概念精选PPT.ppt》由会员分享，可在线阅读，更多相关《非线性规划的基本概念精选PPT.ppt（78页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、关于非线性规划的基本概念现在学习的是第1页，共78页 在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。线性函数，则这样的规划问题就属于非线性规划。非线性规划是运筹学的重要分支之一。最近非线性规划是运筹学的重要分支之一。最近3030多年来发展很快，不断多
2、年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也一般来说，求解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有大都有自己特定的使用范围，
3、都有一定的局限性。到目前为止还没有适适合于各种问题的一般算法合于各种问题的一般算法，这是需要深入研究的一个领域。我们只是对一些模，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。型及应用作简单介绍。现在学习的是第2页，共78页1 1非线性规划问题举例非线性规划问题举例例一：选例一：选址问题址问题设有设有 个市场，第个市场，第 个市场位置为个市场位置为 ，它对某种货物的需要，它对某种货物的需要量为量为 。现计划建立。现计划建立 个仓库，第个仓库，第 个仓库的存储个仓库的存储容量为容量为 试确定仓库的位置，使各仓库对各市场的试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为
4、最小。运输量与路程乘积之和为最小。设第设第 个仓库的位置为个仓库的位置为 第第 个仓库到第个仓库到第 个市场的货物供应量为个市场的货物供应量为 则第则第 个个仓库到第仓库到第 个市场的距离为个市场的距离为现在学习的是第3页，共78页目标函数为目标函数为约束条件为约束条件为 （1 1）每个仓库向各市场提供的货物量之和不能超过它的存储）每个仓库向各市场提供的货物量之和不能超过它的存储容量。容量。（2）每个市场从各仓库得到的货物量之和应等于它的需要）每个市场从各仓库得到的货物量之和应等于它的需要量。量。（3）运输量不能为负数）运输量不能为负数现在学习的是第4页，共78页例例2.木木梁设计问题梁设计问
5、题 把圆形木材加工成矩形横截面的木梁，要求木梁高度把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过不超过 ，横截面的惯性矩（高度的平方，横截面的惯性矩（高度的平方 宽度）不小宽度）不小于于 ，而且高度介于宽度与，而且高度介于宽度与4倍宽度之间。问如何确定木倍宽度之间。问如何确定木梁尺寸可使木梁成本最小梁尺寸可使木梁成本最小.设矩形横截面的高度为设矩形横截面的高度为 ，宽度为宽度为 ，则圆形木材的半径，则圆形木材的半径而木梁长度无法改变，因此成本只与圆形而木梁长度无法改变，因此成本只与圆形而木梁长度无法改变，因此成本只与圆形而木梁长度无法改变，因此成本只与圆形木材的横截面积有关。木材的横截面
6、积有关。木材的横截面积有关。木材的横截面积有关。现在学习的是第5页，共78页目标函数为目标函数为约束条件为约束条件为 现在学习的是第6页，共78页（1）数学规划模型的一般形式：）数学规划模型的一般形式：其中其中,简记为简记为MP(Mathematical Programming)2 2 非线性规划问题的数学模型非线性规划问题的数学模型现在学习的是第7页，共78页（2）简记形式：）简记形式：引入引入向量函数向量函数符号：符号：现在学习的是第8页，共78页（3）数学规划问题的分类：）数学规划问题的分类：若若 为线性函数，即为为线性函数，即为线性规划线性规划(LP)；若若 至少一个为非线性至少一个为
7、非线性,即为即为非线性规划非线性规划(NLP)；对于非线性规划，对于非线性规划，若没有若没有 ,即即X=Rn,称为称为 无约束非线性规划无约束非线性规划或或无约束最优化问题无约束最优化问题；否则称为否则称为约束非线性规划或约束最优化问题约束非线性规划或约束最优化问题。现在学习的是第9页，共78页（4）可行域和可行解：）可行域和可行解：称称为为MP问题的问题的约束集约束集或或可行域可行域。若若x在在X内，称内，称x为为MP的的可行解可行解或者或者可行点可行点。现在学习的是第10页，共78页（5）最优解和极小点）最优解和极小点对于非线性规划（对于非线性规划（MP），若），若 ，并且有，并且有如果有
8、如果有定义定义:现在学习的是第11页，共78页如果有如果有定义定义则称则称 x*是是(MP)的的局部最优解或或局部极小解,现在学习的是第12页，共78页 例1：用图解法求解 min f(x)=(x12)2+(x22)2 s.t.h(x)=x1+x2-6=0 x1x20662233最优解 x*=(3，3)T可行解 x=(1.5，4.5)T最优级解即为最小圆的半径：最优级解即为最小圆的半径：f(x)=(x12)2+(x22)2=23 非线性规划问题的图解法 对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上
9、作图，此法失效。上作图，此法失效。现在学习的是第13页，共78页x1x206622D可行域最优解最优解 x x*=(2(2，2)2)T T 例2：用图解法求解 min f(x)=(x1-2)2+(x2-2)2 s.t.h(x)=x1+x2-6 03 3 非线性规划问题的图解法非线性规划问题的图解法最优级解即为最小圆的半径：最优级解即为最小圆的半径：f f(x x)=()=(x x1 1-2)-2)2 2+(+(x x2 2-2)-2)2 2=0=0现在学习的是第14页，共78页解：先画出等式约束曲线 的图形抛物线，例3：用图解法求解 再画出不等式约束区域，最后画出目标函数等值线，所以 最优解最
10、优解 x*=(4,1),最优值最优值 min f(x)=4.现在学习的是第15页，共78页4 梯度、Hesse矩阵、Jacobi阵(1)(1)二次函数二次函数一般形式:矩阵形式:二次型:矩阵A的正定性:正定、半正定、负定、不定。其中AAT。二次型的正定性:正定、半正定、负定、不定。现在学习的是第16页，共78页（2 2）梯度梯度 定义：f(x)是定义在是定义在En上的可微函数。上的可微函数。f(x)的的n个偏导数为分量个偏导数为分量的向量称为的向量称为f(x)的的梯度梯度.性质：设f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：性质一 函数在某点的梯度不为零，则该梯度方
11、向必与过该点的等值面垂直;性质二 梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。现在学习的是第17页，共78页解：由于例：试求目标函数 在点 x=0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。则函数在 x=0,1T 处的最速下降方向是这个方向上的单位向量是：现在学习的是第18页，共78页解：由于例：试求目标函数 在点x=0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。新点是：函数值：现在学习的是第19页，共78页几个常用的梯度公式几个常用的梯度公式：现在学习的是第20页，共78页（3 3）HesseHesse矩阵
12、矩阵多元函数 f(x)关于x的二阶导数，称为 f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即Hesse矩阵是对称的.时，时，现在学习的是第21页，共78页几个常用Hessian公式：现在学习的是第22页，共78页（4 4）JacobiJacobi矩阵矩阵向量变量值函数：向量值函数g(x)在点 x0处的Jacobi矩阵向量变量值函数的导数：现在学习的是第23页，共78页(1)凸函数：凸函数：定义定义5 凸函数和凸规划凸函数和凸规划现在学习的是第24页，共78页例：正定二次函数例：正定二次函数其中其中A是正定矩阵，是正定矩阵，f(x)是凸函数。是凸函数。参见参见参见参见P104P1
13、04例。例。例。例。现在学习的是第25页，共78页性质性质1:（2）凸函数的性质）凸函数的性质性质性质2:是凸集。是凸集。证明证明:略略.现在学习的是第26页，共78页定理定理1：（一阶条件）：（一阶条件）n=1时几何意义：可微函数是凸的等价于切线不在函数图像上时几何意义：可微函数是凸的等价于切线不在函数图像上方。方。（3）凸函数的判定凸函数的判定现在学习的是第27页，共78页定理定理2：（二阶条件）：（二阶条件）现在学习的是第28页，共78页（4）凸规划的定义及其性质：）凸规划的定义及其性质：凸规划定义：凸规划定义：现在学习的是第29页，共78页凸规划性质：凸规划性质：凸规划的任一局部最优解
14、都是它的整体最优解。凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸规划是以后重点讨论的一类非线性规划凸函数凸函数线性函数线性函数现在学习的是第30页，共78页（1）微分学方法的局限性：）微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。6 6 非线性规划方法概述非线性规划方法概述现在学习的是第31页，共78页（2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列xkxk的最后一点为最优解xk有限xk无限xk收敛于最优解现在学习的是
15、第32页，共78页迭代格式迭代格式xkxk+1pk称称pk为第为第k轮轮搜索方向搜索方向，tk为第为第k轮沿轮沿pk方向的方向的步长步长。产生产生tk和和pk的不同方法，形成了不同的算法。的不同方法，形成了不同的算法。现在学习的是第33页，共78页定义定义：特殊搜索方向：特殊搜索方向下降方向下降方向现在学习的是第34页，共78页定义：定义：特殊搜索方向特殊搜索方向可行可行可行可行下降方向下降方向解非线性规划问题，关键在于找解非线性规划问题，关键在于找到某个方向，使得在此方向上，到某个方向，使得在此方向上，目标函数得到下降，同时还是可目标函数得到下降，同时还是可行方向。行方向。这样的方向称为这样
16、的方向称为可行下降方向。可行下降方向。现在学习的是第35页，共78页定义：算法收敛、下降迭代算法定义：算法收敛、下降迭代算法集合集合S上的迭代算法：上的迭代算法：（1）初始点）初始点；（2）按照某种搜索方向）按照某种搜索方向pk产生下一个迭代点产生下一个迭代点（i）如果点列）如果点列收敛于最优解收敛于最优解，则称此，则称此算法收敛算法收敛。（ii）如果）如果，则称此算法为，则称此算法为下降迭代算法下降迭代算法。.现在学习的是第36页，共78页（3）下降迭代算法步骤）下降迭代算法步骤（1）给出初始点）给出初始点，令，令；（2）按照某种规则确定下降搜索方向）按照某种规则确定下降搜索方向；（3）按照
17、某种规则确定搜索步长）按照某种规则确定搜索步长，使得，使得；（4）令）令 ，；（5）判断）判断是否满足是否满足停止条件停止条件。是则停止，否则转第。是则停止，否则转第2步。步。搜索步长确定方法：搜索步长确定方法：称称为为最优步长最优步长，且有对，且有对 k的梯度的梯度现在学习的是第37页，共78页（4）终止条件终止条件现在学习的是第38页，共78页（5）常用的收敛性判别准则）常用的收敛性判别准则:（）点收（）点收敛敛准准则则:(可取可取Rn中任一种模中任一种模)。e e-)1()(kkxx（）目（）目标标函数函数值值准准则则：（绝对绝对差）。差）。e e-)()()1()(kkffxx（）目（
18、）目标标函数函数值值准准则则：（相（相对对差）。差）。e e-)()()()()1()(kkkfffxxx取其中之一取其中之一,也可同时取也可同时取(1)与与(2);(1)与与(3);或或(1),(2)和和(3)等。等。现在学习的是第39页，共78页（6）算法的收敛速度）算法的收敛速度则称则称 的收敛阶为的收敛阶为 。设算法所得的点列为设算法所得的点列为，如果，如果1.线性收敛（当线性收敛（当k充分大时）：充分大时）：2.超线性收敛：超线性收敛：3.二阶收敛：二阶收敛：（*）式中）式中 =2时成立。时成立。（*）现在学习的是第40页，共78页 单变量单变量(一维一维)最优化最优化一维最优化问题
19、一维最优化问题进退法进退法黄金分割法黄金分割法抛物线搜索法抛物线搜索法三次插值法三次插值法现在学习的是第41页，共78页下降迭代算法下降迭代算法中最优步长的确定中最优步长的确定.一维最优化问题：一维最优化问题：解析的方法解析的方法（极值点的必要条件）极值点的必要条件）一、一维最优化问题一、一维最优化问题现在学习的是第42页，共78页1.单峰函数单峰函数定义定义：设：设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点，且对任意的上的极小点，且对任意的有有（a）当）当时，时，（b）当）当.则称则称 是单峰函数。是单峰函数。.现在学习的是第43页，共78页性质性质：通过计算区间：通过计算区
20、间 a,b 内两个不同点的函数值，就可以确内两个不同点的函数值，就可以确定一个包含极小点的子区间。定一个包含极小点的子区间。定理定理 设设是区间是区间上的一元函数，上的一元函数，是是在在上的极小点。任取点上的极小点。任取点则有则有（1）如果）如果，则，则（2）如果）如果则则.现在学习的是第44页，共78页2 搜索法求解：搜索法求解：或或基本过程：基本过程：给出给出a,b,使得使得x*在在a,b中。中。a,b称为称为搜索区间搜索区间。迭代缩短迭代缩短a,b的长度。的长度。当当a,b的长度小于某个预设的值，或者导数的绝对值小于某的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止
21、。个预设的正数，则迭代终止。现在学习的是第45页，共78页二进退法二进退法思想思想从一点出发从一点出发,按一定的步长按一定的步长,试图确定出函数值呈现试图确定出函数值呈现“高高-低低-高高”的三的三点。一个方向不成功，就退回来，再沿相反方向寻找。点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤进退法的计算步骤如何确定包含极小点的一个区间？如何确定包含极小点的一个区间？现在学习的是第46页，共78页例：例：现在学习的是第47页，共78页假定：已经确定了单峰区间假定：已经确定了单峰区间a,bx1x2ababx12新搜索区间为新搜索区间为a,x2新搜索区间为新搜索区间为x1,b三三.
22、黄金分割法（黄金分割法（0.618法）法）现在学习的是第48页，共78页区间缩小比例的确定：区间缩小比例的确定：区间缩短比例为区间缩短比例为(x2-a)/(b-a)缩短比例为缩短比例为(b-x1)/(b-a)缩短比例缩短比例 满足：满足：每次插入搜索点使得两个区间每次插入搜索点使得两个区间a,x2和和x1,b相等；相等；每次迭代都以相等的比例缩小区间。每次迭代都以相等的比例缩小区间。0.618法法x1x2ababx1x2现在学习的是第49页，共78页黄金分割法的计算公式的推导：黄金分割法的计算公式的推导：现在学习的是第50页，共78页现在学习的是第51页，共78页通过确定通过确定 的取值，使上
23、一次迭代剩余的迭代点恰与下一次迭代的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。的一个迭代点重合，从而减少算法的计算量。同理可得。同理可得。现在学习的是第52页，共78页3.0.618法的算法步骤：法的算法步骤：现在学习的是第53页，共78页确定确定a,b,计算探索点计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a)是是否否是是停止，输出停止，输出x1否否以以a,x2为新的搜索区间为新的搜索区间是是停止，输出停止，输出x2否否以以x1,b为新的搜索区间为新的搜索区间3.0.618法的算法框图：法的算法框图：现在学习的是第54页，共78
24、页黄金分割法的迭代效果：黄金分割法的迭代效果：第第 k 次后迭代后所得区间长度为初始区间长度的次后迭代后所得区间长度为初始区间长度的其它的试探点算法：其它的试探点算法：Fibonacci算法。算法。现在学习的是第55页，共78页例例：解：解：t1t230t1、第一轮：、第一轮：t1=1.146,t2=1.854t200.5现在学习的是第56页，共78页2、第二轮：、第二轮：t2=1.146,t1=0.708t20=1.1460.53、第三轮：、第三轮：t1=0.438,t2=0.708b-t1=1.146-0.4380.51.8540tt2t11.1460tt2t1现在学习的是第57页，共78
25、页4、第四轮：、第四轮：t2=0.876=(1.146-0.438),t1=0.708b-t1=1.146-0.7080，求目标函数值的计算次数，求目标函数值的计算次数 n，使，使置辨别常数置辨别常数0。计算试探点。计算试探点 计算函数值和计算函数值和 。置。置k=1。（2）若若 ，则转（，则转（3）；）；若若 ，则转（，则转（4）。）。现在学习的是第62页，共78页（3）（5）置置k=k+1，转（，转（2）。）。（4）（6）现在学习的是第63页，共78页思想思想在极小点附近，用二次三项式在极小点附近，用二次三项式四四.抛物线（二次）插值抛物线（二次）插值即即“两头大中间小两头大中间小”现在学
26、习的是第64页，共78页如何计算函数如何计算函数令令x=33221123322221111111121fxfxfxxfxfxf-现在学习的是第65页，共78页抛物线插值算法步骤：抛物线插值算法步骤：解出解出现在学习的是第66页，共78页思路：思路：五五.三次插值法三次插值法现在学习的是第67页，共78页设设令令则有则有现在学习的是第68页，共78页求解满足求解满足的极小点的极小点 令令而而解方程（解方程（3），有两种情况：），有两种情况：由（由（2）可知）可知现在学习的是第69页，共78页现在学习的是第70页，共78页极小点的计算公式：极小点的计算公式：令令现在学习的是第71页，共78页算法步
27、骤：算法步骤：现在学习的是第72页，共78页现在学习的是第73页，共78页其它插值算法：其它插值算法：有理插值。有理插值。收敛速度：三次插值算法的收敛阶为收敛速度：三次插值算法的收敛阶为2。现在学习的是第74页，共78页六、六、MATLAB单变量函数求最小值的标准形式为单变量函数求最小值的标准形式为 s.t 函数函数 fminbnd格式格式 x=fminbnd(fun,x1,x2)%返回自返回自变变量量x在区在区间间上函数上函数fun取最小值时取最小值时x值，值，fun为目标函数的表达式字符串或为目标函数的表达式字符串或MATLAB自定义函数的函数柄。自定义函数的函数柄。函数函数fminbnd
28、的算法基于黄金分割法和二次插值法，它要求目标函数的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。必须是连续函数，并可能只给出局部最优解。现在学习的是第75页，共78页x=fminbnd(fun,x1,x2,options)%options为指定优化参数选为指定优化参数选项项x,fval=fminbnd()%fval为目标函数的最小值为目标函数的最小值x,fval,exitflag=fminbnd()%xitflag为终止迭代的条件为终止迭代的条件x,fval,exitflag,output=fminbnd()%output为优化信息为优化信息说明说明 若
29、参数若参数exitflag0，表示函数收敛于，表示函数收敛于x，若，若exitflag=0，表示超过函数估计值或迭代的最大数字，表示超过函数估计值或迭代的最大数字，exitflag0表示函数表示函数不收敛于不收敛于x；若参数；若参数output=iterations表示迭代次数，表示迭代次数，output=funccount表示函数赋值次数，表示函数赋值次数，output=algorithm表表示所使用的算法。示所使用的算法。现在学习的是第76页，共78页例例1 计算下面函数在区间计算下面函数在区间(0，1)内的最小值。内的最小值。解：解：x,fval,exitflag,output =fminbnd(x3+cos(x)+x*log(x)/exp(x),0,1)x=0.5223fval=0.3974exitflag=1output=iterations:9 funcCount:9 algorithm:golden section search,parabolic interpolation现在学习的是第77页，共78页感谢大家观看现在学习的是第78页，共78页