生产运筹--非线性规划的基本概念（PPT 78页）(2)

1、第五讲 非线性规划的基本概念 非线性规划问题 非线性规划数学模型 非线性规划的图解法 梯度、Hesse矩阵、Jacobi阵 凸函数和凸规划 解非线性规划方法概述 一维最优化1 在科学管理和其他领域中，大量应用问题可以归结为线性规划问题，但是，也有另外许多问题，其目标函数和（或）约束条件很难用线性函数表达。如果目标函数和（或）约束条件中包含有自变量的非线性函数，则这样的规划问题就属于非线性规划。 非线性规划是运筹学的重要分支之一。最近30多年来发展很快，不断提出各种算法，而其应用范围也越来越广泛。比如在各种预报、管理科学、最优设计、质量控制、系统控制等领域得到广泛且不短深入的应用。 一般来说，求

2、解非线性规划问题比线性规划问题困难得多。而且，也不象线性规划那样有单纯形法这一通用的方法。非线性规划的各种算法大都有自己特定的使用范围，都有一定的局限性。到目前为止还没有适合于各种问题的一般算法，这是需要深入研究的一个领域。我们只是对一些模型及应用作简单介绍。2非线性规划问题举例例一：选址问题设有 个市场，第 个市场位置为 ，它对某种货物的需要量为 。现计划建立 个仓库，第 个仓库的存储容量为 试确定仓库的位置，使各仓库对各市场的运输量与路程乘积之和为最小。设第 个仓库的位置为 第 个仓库到第 个市场的货物供应量为 则第 个仓库到第 个市场的距离为3目标函数为约束条件为 （1）每个仓库向各市场

3、提供的货物量之和不能超过它的存储容量。 （2）每个市场从各仓库得到的货物量之和应等于它的需要量。（3）运输量不能为负数4例2. 木梁设计问题 把圆形木材加工成矩形横截面的木梁，要求木梁高度不超过 ，横截面的惯性矩（高度的平方 宽度）不小于 ，而且高度介于宽度与4倍宽度之间。问如何确定木梁尺寸可使木梁成本最小.设矩形横截面的高度为 ， 宽度为 ，则圆形木材的半径而木梁长度无法改变，因此成本只与圆形木材的横截面积有关。5目标函数为约束条件为 6（1）数学规划模型的一般形式：其中, 简记为MP(Mathematical Programming) 2 非线性规划问题的数学模型7（2）简记形式：引入向量

4、函数符号：8（3）数学规划问题的分类：若 为线性函数，即为线性规划(LP)；若 至少一个为非线性, 即为非线性规划(NLP)；对于非线性规划，若没有 ,即X=Rn,称为 无约束非线性规划或无约束最优化问题；否则称为约束非线性规划或约束最优化问题。9（4）可行域和可行解：称为MP问题的约束集或可行域。若x在X内，称x为MP的可行解或者可行点。10（5）最优解和极小点对于非线性规划（MP），若 ，并且有如果有定义:11如果有定义则称 x* 是(MP)的局部最优解或局部极小解,12 例1： 用图解法求解 min f(x)=(x12)2 +(x22)2 s.t. h(x)= x1 + x2 - 6 =

5、 0 x1x20662233最优解 x* = ( 3，3 )T可行解 x = ( 1.5，4.5 )T最优级解即为最小圆的半径：f(x)=(x12)2 +(x22)2 = 23 非线性规划问题的图解法 对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。13x1x206622D可行域最优解 x* = ( 2，2 )T 例2： 用图解法求解 min f(x)=(x1 - 2)2 +(x2 - 2)2 s.t. h(x)= x1 + x2 - 6 03 非线性规划问题的图解法最优级解即为最小圆的半径：f(x)=(x1 - 2)2 +(x2 - 2)2 = 014

6、解：先画出等式约束曲线 的图形抛物线， 例3：用图解法求解 再画出不等式约束区域， 最后画出目标函数等值线， 所以 最优解 x*=(4,1), 最优值 min f(x)=4.154 梯度、Hesse矩阵、Jacobi阵(1) 二次函数一般形式:矩阵形式:二次型:矩阵A的正定性: 正定、半正定、负定、不定。其中AAT。二次型的正定性: 正定、半正定、负定、不定。16（2） 梯度 定义：f(x) 是定义在En上的可微函数。f(x) 的n个偏导数为分量的向量称为f(x) 的梯度. 性质：设f(x) 在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质： 性质一 函数在某点的梯度不为零，则该

7、梯度方向必与过该点的等值面垂直; 性质二 梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。17解： 由于例：试求目标函数 在点 x =0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。 则函数在 x =0,1T 处的最速下降方向是这个方向上的单位向量是：18解： 由于例：试求目标函数 在点x =0,1T 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。新点是：函数值：19几个常用的梯度公式：20（3）Hesse矩阵多元函数 f(x) 关于x的二阶导数，称为 f(x)的Hesse矩阵.当f(x)的所有二阶偏导数连续时,即Hesse

8、矩阵是对称的.时，21几个常用Hessian公式：22（4）Jacobi矩阵向量变量值函数：向量值函数g(x)在点 x0处的Jacobi矩阵向量变量值函数的导数：23(1)凸函数：定义5 凸函数和凸规划24例：正定二次函数其中A是正定矩阵，f(x)是凸函数。参见P104例。25性质1:（2）凸函数的性质性质2:是凸集。证明:略.26定理1：（一阶条件）n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。 （3） 凸函数的判定27定理2：（二阶条件）28（4）凸规划的定义及其性质：凸规划定义：29凸规划性质：凸规划的任一局部最优解都是它的整体最优解。凸规划是以后重点讨论的一类非线性规划凸

9、函数线性函数30（1）微分学方法的局限性：实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不易处理。6 非线性规划方法概述31（2）数值方法的基本思路：迭代给定初始点x0根据x0,依次迭代产生点列xkxk的最后一点为最优解xk有限xk无限xk收敛于最优解32迭代格式xkxk+1pk称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。产生tk和pk的不同方法，形成了不同的算法。33定义：特殊搜索方向下降方向34定义：特殊搜索方向可行下降方向解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到

10、下降，同时还是可行方向。这样的方向称为可行下降方向。35定义：算法收敛、下降迭代算法集合S上的迭代算法：（1）初始点；（2）按照某种搜索方向pk产生下一个迭代点（i）如果点列收敛于最优解，则称此算法收敛。（ii）如果，则称此算法为下降迭代算法。.36（3）下降迭代算法步骤（1）给出初始点，令；（2）按照某种规则确定下降搜索方向；（3）按照某种规则确定搜索步长，使得；（4）令 ，；（5）判断是否满足停止条件。是则停止，否则转第2步。搜索步长确定方法：称为最优步长，且有对k的梯度37（4） 终止条件38（5）常用的收敛性判别准则:（）点收敛准则:(可取Rn中任一种模)。e-)1()(kkxx（）目

11、标函数值准则：（绝对差）。e-)()()1()(kkffxx（）目标函数值准则：（相对差）。e-)()()()()1()(kkkfffxxx取其中之一,也可同时取(1)与(2);(1)与(3);或(1),(2)和(3)等。39（6）算法的收敛速度则称 的收敛阶为 。设算法所得的点列为，如果1.线性收敛（当k充分大时）： 2.超线性收敛：3.二阶收敛： （*）式中 =2时成立。（*）40 单变量(一维)最优化一维最优化问题进退法黄金分割法抛物线搜索法三次插值法41下降迭代算法中最优步长的确定.一维最优化问题：解析的方法（极值点的必要条件）一、一维最优化问题421. 单峰函数定义：设是区间上的一元

12、函数，是在上的极小点，且对任意的有（a）当时，（b）当.则称 是单峰函数。.43性质：通过计算区间 a, b 内两个不同点的函数值，就可以确定一个包含极小点的子区间。定理 设是区间上的一元函数，是在上的极小点。任取点则有（1）如果，则（2）如果则.442 搜索法求解：或基本过程：给出a,b,使得x*在a,b中。a,b称为搜索区间。迭代缩短a,b的长度。当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。45二进退法思想从一点出发,按一定的步长, 试图确定出函数值呈现“高 - 低 - 高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。进退法的计算步骤如何确定包含

13、极小点的一个区间？46例：47假定：已经确定了单峰区间a,bx1x2ababx12新搜索区间为a,x2新搜索区间为x1,b三. 黄金分割法（0.618法）48区间缩小比例的确定：区间缩短比例为(x2-a)/(b-a)缩短比例为(b-x1)/(b-a)缩短比例 满足：每次插入搜索点使得两个区间a,x2和x1,b相等；每次迭代都以相等的比例缩小区间。0.618法x1x2ababx1x249黄金分割法的计算公式的推导：50通过确定 的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。同理可得。513. 0.618法的算法步骤：52确定a,b,计算探索点x1=a+0.

14、382(b-a)x2=a+0.618(b-a)是否是停止，输出x1否以a,x2为新的搜索区间是停止，输出x2否以x1,b为新的搜索区间3. 0.618法的算法框图：53黄金分割法的迭代效果：第 k 次后迭代后所得区间长度为初始区间长度的其它的试探点算法：Fibonacci算法。54例：解：t1t230t1、第一轮：t1=1.146, t2=1.854t200.5552、第二轮：t2=1.146, t1=0.708t20=1.1460.53、第三轮：t1=0.438, t2=0.708b -t1=1.146-0.4380.51.8540tt2t11.1460tt2t1564、第四轮：t2=0.8

15、76=(1.146-0.438), t1=0.708b-t1=1.146-0.7080，求目标函数值的计算次数 n，使置辨别常数0。计算试探点 计算函数值和 。置k =1。（2） 若 ，则转（3）； 若 ，则转（4）。61（3） （5） 置k= k+1，转（2）。（4） （6） 62思想在极小点附近，用二次三项式四. 抛物线（二次）插值即“两头大中间小”63如何计算函数令x=33221123322221111111121fxfxfxxfxfxf-64抛物线插值算法步骤：解出65思路：五. 三次插值法66设令则有67求解满足的极小点 令而解方程（3），有两种情况：由（2）可知68极小点的计算公式

16、：令69算法步骤：70其它插值算法：有理插值。收敛速度：三次插值算法的收敛阶为2。71六、MATLAB单变量函数求最小值的标准形式为 s.t 函数 fminbnd格式 x = fminbnd(fun,x1,x2) %返回自变量x在区间上函数fun取最小值时x值，fun为目标函数的表达式字符串或MATLAB自定义函数的函数柄。 函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。72x = fminbnd(fun,x1,x2,options) % options为指定优化参数选项x,fval = fminbnd() % fval为目标函数的最

17、小值x,fval,exitflag = fminbnd() %xitflag为终止迭代的条件x,fval,exitflag,output = fminbnd() % output为优化信息说明 若参数exitflag0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag0表示函数不收敛于x；若参数output=iterations表示迭代次数，output=funccount表示函数赋值次数，output=algorithm表示所使用的算法。 73例1 计算下面函数在区间(0，1)内的最小值。解：x,fval,exitflag,output =fminbnd(x3+cos(x)+x*log(x)/exp(