生产运筹--非线性规划的基本概念 78页(1).ppt

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

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

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

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

5、，4.5)T,最优级解即为最小圆的半径：f(x)=(x12)2+(x22)2=2,3非线性规划问题的图解法,对二维最优化问题，总可以用图解法求解，而对三维或高维问题，已不便在平面上作图，此法失效。,x1,x2,0,6,6,2,2,D可行域,最优解x*=(2，2)T,例2：用图解法求解minf(x)=(x1-2)2+(x2-2)2s.t.h(x)=x1+x2-60,3非线性规划问题的图解法,最优级解即为最小圆的半径：f(x)=(x1-2)2+(x2-2)2=0,解：先画出等式约束曲线的图形抛物线，,例3：用图解法求解,再画出不等式约束区域，,最后画出目标函数等值线，,所以最优解x*=(4,1),

6、最优值minf(x)=4.,4梯度、Hesse矩阵、Jacobi阵,(1)二次函数,一般形式:,矩阵形式:,二次型:,矩阵A的正定性:正定、半正定、负定、不定。,其中AAT。,二次型的正定性:正定、半正定、负定、不定。,（2）梯度,定义：f(x)是定义在En上的可微函数。f(x)的n个偏导数为分量的向量称为f(x)的梯度.,性质：设f(x)在定义域内有连续偏导数，即有连续梯度，则梯度有以下两个重要性质：性质一函数在某点的梯度不为零，则该梯度方向必与过该点的等值面垂直;性质二梯度方向是函数具有最大变化率的方向（负梯度方向也叫最速下降方向）。,解：由于,例：试求目标函数在点x=0,1T处的最速下降

7、方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,则函数在x=0,1T处的最速下降方向是,这个方向上的单位向量是：,解：由于,例：试求目标函数在点x=0,1T处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。,新点是：,函数值：,几个常用的梯度公式：,（3）Hesse矩阵,多元函数f(x)关于x的二阶导数，称为f(x)的Hesse矩阵.,当f(x)的所有二阶偏导数连续时,即,Hesse矩阵是对称的.,时，,几个常用Hessian公式：,（4）Jacobi矩阵,向量变量值函数：,向量值函数g(x)在点x0处的Jacobi矩阵,向量变量值函数的导数：,(1)凸函数：,定义

8、,5凸函数和凸规划,例：正定二次函数,其中A是正定矩阵，,f(x)是凸函数。,参见P104例。,性质1:,（2）凸函数的性质,性质2:,是凸集。,证明:略.,定理1：（一阶条件）,n=1时几何意义：可微函数是凸的等价于切线不在函数图像上方。,（3）凸函数的判定,定理2：（二阶条件）,（4）凸规划的定义及其性质：,凸规划定义：,凸规划性质：,凸规划的任一局部最优解都是它的整体最优解。,凸规划是以后重点讨论的一类非线性规划,线性函数,（1）微分学方法的局限性：,实际的问题中，函数可能是不连续或者不可微的。需要解复杂的方程组，而方程组到目前仍没有有效的算法。实际的问题可能含有不等式约束，微分学方法不

9、易处理。,6非线性规划方法概述,（2）数值方法的基本思路：迭代,给定初始点x0,根据x0,依次迭代产生点列xk,xk的最后一点为最优解,xk有限,xk无限,xk收敛于最优解,迭代格式,xk,xk+1,称pk为第k轮搜索方向，tk为第k轮沿pk方向的步长。,产生tk和pk的不同方法，形成了不同的算法。,定义：特殊搜索方向下降方向,定义：特殊搜索方向可行下降方向,解非线性规划问题，关键在于找到某个方向，使得在此方向上，目标函数得到下降，同时还是可行方向。这样的方向称为可行下降方向。,定义：算法收敛、下降迭代算法,集合S上的迭代算法：,（1）初始点,；,（2）按照某种搜索方向pk产生下一个迭代点,（

10、i）如果点列,收敛于最优解,，则称此算法收敛。,（ii）如果,，则称此算法为,下降迭代算法。,.,.,.,（3）下降迭代算法步骤,（1）给出初始点,，令,；,（2）按照某种规则确定下降搜索方向,；,（3）按照某种规则确定搜索步长,，使得,；,（4）令,，,；,（5）判断,是否满足停止条件。是则停止，否则转第2步。,搜索步长确定方法：,称,为最优步长，且有对k的梯度,（4）终止条件,（5）常用的收敛性判别准则:,取其中之一,也可同时取(1)与(2);(1)与(3);或(1),(2)和(3)等。,（6）算法的收敛速度,则称的收敛阶为。,设算法所得的点列为,，如果,1.线性收敛（当k充分大时）：,2

11、.超线性收敛：,3.二阶收敛：（*）式中=2时成立。,（*）,单变量(一维)最优化,一维最优化问题进退法黄金分割法抛物线搜索法三次插值法,下降迭代算法中最优步长的确定,.,.,一维最优化问题：,解析的方法（极值点的必要条件）,一、一维最优化问题,1.单峰函数,定义：设,是区间,上的一元函数，,是,在,上的极小点，且对任意的,有,（a）当,时，,（b）当,.,.,.,.,.,则称是单峰函数。,.,.,性质：通过计算区间a,b内两个不同点的函数值，就可以确定一个包含极小点的子区间。,.,.,.,.,.,2搜索法求解：,或,基本过程：给出a,b,使得x*在a,b中。a,b称为搜索区间。迭代缩短a,b

12、的长度。当a,b的长度小于某个预设的值，或者导数的绝对值小于某个预设的正数，则迭代终止。,二进退法,思想,从一点出发,按一定的步长,试图确定出函数值呈现“高-低-高”的三点。一个方向不成功，就退回来，再沿相反方向寻找。,进退法的计算步骤,如何确定包含极小点的一个区间？,例：,假定：已经确定了单峰区间a,b,新搜索区间为a,x2,新搜索区间为x1,b,三.黄金分割法（0.618法）,区间缩小比例的确定：,区间缩短比例为(x2-a)/(b-a),缩短比例为(b-x1)/(b-a),缩短比例满足：每次插入搜索点使得两个区间a,x2和x1,b相等；每次迭代都以相等的比例缩小区间。,黄金分割法的计算公式

13、的推导：,通过确定的取值，使上一次迭代剩余的迭代点恰与下一次迭代的一个迭代点重合，从而减少算法的计算量。,同理可得。,3.0.618法的算法步骤：,确定a,b,计算探索点x1=a+0.382(b-a)x2=a+0.618(b-a),停止，输出x1,以a,x2为新的搜索区间,停止，输出x2,以x1,b为新的搜索区间,3.0.618法的算法框图：,黄金分割法的迭代效果：第k次后迭代后所得区间长度为初始区间长度的,其它的试探点算法：Fibonacci算法。,例：,解：,1、第一轮：t1=1.146,t2=1.854,t200.5,2、第二轮：t2=1.146,t1=0.708,t20=1.1460.

14、5,3、第三轮：t1=0.438,t2=0.708,b-t1=1.146-0.4380.5,4、第四轮：t2=0.876=(1.146-0.438),t1=0.708,b-t1=1.146-0.7080.5,输出：t*=t2=0.876为最优解，最优值为-0.0798,四Fibonacci法,此法类似于0.618法，也是用于单峰函数。其计算过程也与0.618类似，第1次迭代计算两个试探点，以后每次迭代只需新加一点，另一试探点取自上次的迭代点。此法与0.618法的主要差别为：区间长度的缩短比率不是常数，而是由Fibonacci数确定；给出精度后，迭代次数可预先确定；适合于参数只能取整数值的情况。

15、,定义称满足条件（i）F0=F1=1；（ii）的数列Fn为Fibonacci数列。,由定义推知Fibonacci数列的前10项为1,1,2,3,5,8,13,21,34,55,89。通过求解递推关系可求得该数列的通项为,在Fibonacci法中，第n次迭代的搜索区间的长度（记为）是上一次区间长度的倍,所以要使在第n次迭代时搜索区间的长度不超过，只需,即可。因是已知值，所以给出精度后利用（2.4）式可求得迭代次数。,Fibonacc法在迭代中计算试探点的公式为,即有,Fibonacci法,(1)对初始区间和精度0，求目标函数值的计算次数n，使置辨别常数0。计算试探点计算函数值和。置k=1。,（2

16、）若，则转（3）；若，则转（4）。,（3）,（5）置k=k+1，转（2）。,（4）,（6）,思想,在极小点附近，用二次三项式,四.抛物线（二次）插值,即“两头大中间小”,如何计算函数,令,抛物线插值算法步骤：,解出,思路：,五.三次插值法,设,令,则有,求解满足,的极小点,令,而,解方程（3），有两种情况：,由（2）可知,极小点的计算公式：,令,算法步骤：,其它插值算法：,有理插值。,收敛速度：三次插值算法的收敛阶为2。,六、MATLAB,单变量函数求最小值的标准形式为s.t,函数fminbnd格式x=fminbnd(fun,x1,x2)%返回自变量x在区间上函数fun取最小值时x值，fun为

17、目标函数的表达式字符串或MATLAB自定义函数的函数柄。函数fminbnd的算法基于黄金分割法和二次插值法，它要求目标函数必须是连续函数，并可能只给出局部最优解。,x=fminbnd(fun,x1,x2,options)%options为指定优化参数选项x,fval=fminbnd()%fval为目标函数的最小值x,fval,exitflag=fminbnd()%xitflag为终止迭代的条件x,fval,exitflag,output=fminbnd()%output为优化信息说明若参数exitflag0，表示函数收敛于x，若exitflag=0，表示超过函数估计值或迭代的最大数字，exitflag0表示函数不收敛于x；若参数output=iterations表示迭代次数，output=funccount表示函数赋值次数，output=algorithm表示所使用的算法。,例1计算下面函数在区间(0，1)内的最小值。,解：x,fval,exitflag,ou