管理运筹学 06 非线性规划.ppt

1、2020/8/11,1,第六章 非线性规划,非线性规划问题及其数学模型 极值问题 凸规划 一维搜索 无约束极值问题 约束极值问题,2020/8/11,2,1. 非线性规划问题及其数学模型,非线性规划问题举例： Example1：第82页例6-1 Example2：第82页例6-2 非线性规划问题的数学模型 非线性规划问题的图示,2020/8/11,3,1.1 非线性规划问题举例,Example1: 某商店经销A、B两种产品，售价分别为20和380元。据统计，售出一件A 产品的平均时间为0.5小时，而售出一件B 产品的平均时间与其销售的数量成正比，表达式为1 + 0.2n。若该商店总的营业时间为

2、1000小时，试确定使其营业额最大的营业计划。,2020/8/11,4,1.1 非线性规划问题举例,解 设x1和x2分别为商店经销A、B两种产品的件数，于是有如下数学模型：,2020/8/11,5,1.1 非线性规划问题举例,Example 2: 在层次分析（Analytic Hierarchy Process, 简记为 AHP）中，为进行多属性的综合评价，需要确定每个属性的相对重要性，即它们的权重。为此，将各属性进行两两比较，从而得出如下判断矩阵：,2020/8/11,6,1.1 非线性规划问题举例,a11 a1n J= , an1 ann 其中： aij是第i个属性与第j个属性的重要性之比

3、。,2020/8/11,7,1.1 非线性规划问题举例,现需要从判断矩阵求出各属性的权重，为使求出的权重向量W在最小二乘意义上能最好地反映判断矩阵的估计，由aij=wi/wj可得：,2020/8/11,8,1.2 非线性规划问题的数学模型,s.t. 其中 是n维欧氏空间En中的向量点。,2020/8/11,9,1.2 非线性规划问题的数学模型,由于， ,“”不等式仅乘“-1”即可转换为“”不等式；因此上述数学模型具有一般意义。又因为等价于两个不等式： ; ,因此非线性规划的数学模型也可以表示为：,2020/8/11,10,1.3 非线性规划问题的图示,若令其目标函数f (X)=c,目标函数成为

4、一条曲线或一张曲面；通常称为等值线或等值面。此例，若设f (X)=2和f (X)=4可得两个圆形等值线，见下图：,2020/8/11,11,1.3 非线性规划问题的图示,由左图可见,等值线f (X)=2和约束条件直线6-6相切，切点D即为此问题的最优解，X*=(3, 3)，其目标函数值 f (X*)=2。,2020/8/11,12,1.3 非线性规划问题的图示,在此例中，约束 对最优解发生了影响，若以 代替原约束，则非线性规划的最优解是 ，即图中的C点，此时 。由于最优点位于可行域的内部，故事实上约束 并未发挥作用，问题相当一个无约束极值问题。,2020/8/11,13,1.3 非线性规划问题

5、的图示,注 线性规划存在最优解，最优解只能在其可行域的边缘上（特别能在可行域的顶点上）得到；而非线性规划的最优解（如果存在）则可能在可行域的任意一点上得到。,2020/8/11,14,2. 极值问题,局部极值与全局极值 极值点存在的条件 凸函数和凹函数 凸函数的性质 函数凸性的判定,2020/8/11,15,2.1 局部极值与全局极值,线性规划 最优解 全局最优解 非线性规划 局部最优解 未必全局最优,2020/8/11,16,局部极值,对于X-X* f (X*) ，则称 X*为 f (X)在 R上的严格局部极小点， f (X*)为严格局部极小值；,2020/8/11,17,全局极值,对于X,

6、X* R均有不等式 f (X) f (X*) ，则称 X*为 f (X)在 R上的全局极小点，f (X*)为全局极小值； 对于X,X* R均有不等式f (X) f (X*) ，则称X*为f (X)在R上的严格全局极小点， f (X*)为严格全局极小值。,2020/8/11,18,2.2 极值点存在的条件,必要条件 设R是En上的一个开集，f (X)在R上有一阶连续偏导数，且在点 取得局部极值，则必有 或,2020/8/11,19,必要条件,为函数 f (X)在 X*点处的梯度。 由数学分析可知， 的方向为X*点处等值面（等值线）的法线方向，沿这一方向函数值增加最快，如图所示。,2020/8/1

7、1,20,必要条件,满足 的点称为平稳点或驻点。极值点一定是驻点；但驻点不一定是极值点。,2020/8/11,21,充分条件,充分条件 设R是En上的一个开集，f (X)在R上具有二阶连续偏导数，对于 ，若 且对任何非零向量有： 则X*为 f (X)的严格局部极小点。 称为 f (X)在点X*处的海赛（Hesse）矩阵。,2020/8/11,22,充分条件,2020/8/11,23,充分条件,（充分条件）等价于： 如果函数f (X)在X*点的梯度为零且海赛矩阵正定，则X*为函数f (X)的严格局部极小点。,2020/8/11,24,2.3 凸函数和凹函数,设 f (X)为定义在En中某一凸集R

8、上的函数，若对于任何实数（01）以及R中的任意两点X(1)和X(2) ，恒有： 则称 f (X)为定义在R上的凸函数；若上式为严格不等式，则称 f (X)为定义在R上的严格凸函数。改变不等号的方向，即可得到凹函数和严格凹函数的定义。,2020/8/11,25,凸函数和凹函数示意图,2020/8/11,26,非凹非凸函数示意图,2020/8/11,27,2.4 凸函数的性质,设f (X)为定义在凸集R上的凸函数，则对于任意实数0 ,函数 f (X)也是定义在R上的凸函数。 设f1 (X)和f 2(X)为定义在凸集R上的两个凸函数，则其和f (X) = f1 (X) + f 2(X)仍然是定义在R

9、上的凸函数。 设f (X)为定义在凸集R上的凸函数，则对于任意实数,集合S =X|XR, f (X) 是凸集。,2020/8/11,28,2.4 凸函数的性质,设f (X)为定义在凸集R上的凸函数，则它的任一极小点就是它在R上的最小点（全局极小点）；而且它的极小点形成一个凸集。 设f (X)为定义在凸集R上的可微凸函数，若它存在点X*R，使得对于所有的XR有 f (X *)T (X- X*) 0，则X*是f (X)在R上的最小点（全局极小点）。,2020/8/11,29,2.5 函数凸性的判定,根据凸函数的定义进行判定； 根据一阶条件进行判定； 根据二阶条件进行判定；,2020/8/11,30

10、,一阶条件,设R为En上的开凸集， f (X)在R上具有一阶连续偏导数，则f (X)为R上的凸函数的充分必要条件是，对于属于R的任意两个不同点X(1)和X(2)恒有：,2020/8/11,31,二阶条件,设R为En上的开凸集， f (X)在R上具有二阶连续偏导数，则 f (X)为R上的凸函数的充分必要条件是： f (X)的海赛矩阵H(X)在R上处处半正定（ ZTH(X)Z0 ）。,2020/8/11,32,3. 凸规划,凸规划的定义 下降迭代算法,2020/8/11,33,3.1 凸规划的定义,考虑非线性规划： 假定其中 f (X)为凸函数， g j (X)为凹函数（- g j (X)为凸函数

11、），这样的非线性规划称为凸规划。,2020/8/11,34,3.1 凸规划的定义,凸规划： 可行域是凸集、局部最优即为全局最优；若为严格凸函数，最优解若存在必唯一。,2020/8/11,35,3.2 下降迭代算法,基本思想： 给定一个初始估计解X(0)，然后按某种规则（即算法）找出一个比X(0)更好的解X(1) ，如此递推即可得到一个解的序列X(k) ，若这一解的序列有极限X* ，即 则称X*为最优解。,2020/8/11,36,3.2 下降迭代算法,基本问题： 递推步骤的有限性，一般说很难得到精确解，当满足所要求的精度时即可停止迭代而得到一个近似解。,2020/8/11,37,3.2 下降迭

12、代算法,下降算法： 若产生的解序列X(k) 能使目标函数f (X(k)逐步减少，就称此算法为下降算法。“下降”的要求很容易满足，因此它包括了很多具体的算法。,2020/8/11,38,3.2 下降迭代算法,若从 X (k)出发沿任何方向移动都不能使目标函数值下降，则 X (k)是一个局部极小点；若从 X (k)出发至少存在一个方向能使目标函数下降，则可选定某一下降方向 P (k) ，沿这一方向前进一步，得到下一个点 X (k+1) 。 沿P (k)方向前进一步相当于在射线 上选定新的点 ,其中P (k)为搜索方向， 为步长。,2020/8/11,39,3.2 下降迭代算法,确定搜索方向P (k

13、)是关键的一步，各种算法的区别主要在于确定搜索方向P (k)的方法不同。 步长 的选定一般都是以使目标函数在搜索方向上下降最多为依据的，称为最佳步长，即沿射线 求目标函数的极小值 由于确定步长是通过求以 为变量的一元函数 的极小点来实现的，故称这一过程为一维搜索。,2020/8/11,40,4. 一维搜索,一维搜索即沿某一已知方向求目标函数的极小点，一维搜索的方法很多，在此只介绍斐波那契法和黄金分割法。,2020/8/11,41,4.1 斐波那契法,一维搜索过程是建立在一个被称为斐波那契数序列基础上的。斐波那契数序列是具有如下递推关系的无穷序列： F0=F1=1 Fn=Fn-1+Fn-2，n

14、=2,3, ,2020/8/11,42,4.1 斐波那契法,斐波那契法成功地实现了单峰函数极值范围的缩减。 设某一单峰函数在a, b上有一极小点 x*，在此区间内任意取两点a1和b1 ，使a1b1 ，计算其函数值可能出现以下两种情况： (1) f (a1) f (b1)，如图(1)所示；此时极小点x*必在期间a, b1内。 (2) f (a1) f (b1)，如图(2)所示；此时极小点x*必在期间a1, b内。,2020/8/11,43,4.1 斐波那契法,f (x),o a a1 x* b1 b x,图(1),2020/8/11,44,4.1 斐波那契法,f (x),o a a1 x* b1

15、 b x,图(2),2020/8/11,45,4.1 斐波那契法,只要在区间a, b内任意取两点a1和b1 ，使a1b1并计算其函数值加以比较，就可以把搜索区间a, b缩减成a, b1或a1, b。若要继续缩小搜索期间a, b1或a1, b ，只需在期间内再取一点算出其函数值并与f (a1)或 f (b1)加以比较即可。 由此可见，计算函数的次数越多，搜索期间就缩得越小，即区间的缩短率（缩短后的区间长度与原区间长度之比）与函数的计算次数有关。,2020/8/11,46,斐波那契法的具体步骤,1. 根据相对精度或绝对精度，确定试点个数； 2. 确定两个试点的位置a1、b1（对称搜索）；,2020

16、/8/11,47,斐波那契法的具体步骤,3. 计算函数值和并比较其大小，从而缩减搜索区间； 4. 重复2、3两步，直到得到近似最小点。,2020/8/11,48,斐波那契法例(第90页例6-6),例6-6： 用斐波那契法求函数 f (x)=3x2-12x+10的近似极小点和极小值，要求缩短后的区间不大于初始区间1,4的0.05倍。,2020/8/11,49,4.2 黄金分割法,用斐波那契法以n个点缩减某一区间时，区间长度的缩减率依次为：Fn-1/Fn, Fn-2/Fn-1 , F1/F2 。现将以上数列分为奇数项F2k-2/F2k和偶数项F2k/F2k+1 ，可以证明这两个数列收敛于同一个极限

17、。,2020/8/11,50,4.2 黄金分割法,以不变的区间缩减率，代替斐波那契法每次不同的缩减率，就得到了黄金分割法。 黄金分割法是一种等速对称的搜索方法，每次试点均取在区间长度的倍和倍处。,2020/8/11,51,黄金分割法例(第92页例6-7),例6-7： 求二次函数 f (x)=3x2-21x-1在区间0,20上的极小点，要求缩短后的区间长度不大于原区间长度的5%。,2020/8/11,52,5. 无约束极值问题,2020/8/11,53,三种方法,梯度法（最速下降法） 牛顿法 变尺度法,2020/8/11,54,5.1 梯度法（最速下降法）,基本原理,2020/8/11,55,5.1 梯度法（最速下降法）,基本步骤,2020/8/11,56,5.1 梯度法（最速下降法）,第94页例6-8 试用梯