运筹学课件-ch7非线性规划.ppt

1,南京农业大学工学院 陈青春 制作,运 筹 学,课件,第七章 非线性规划,2,目录,定义,第七章 非线性规划,第一节 引言,第二节 基本概念,第三节 凸规划,第四节 一维搜索,3,第七章 非线性规划,第七章 非线性规划,第一节 引言,定义：,具有以下特征的问题称为非线性规划问题：,难点：,4,第一节 引言,第七章 非线性规划 第一节 引言,例7-2,一、引例,5,第七章 非线性规划 第一节 引言,二、非线性规划的数学模型,6,第七章 非线性规划 第一节 引言,二、非线性规划的图示,二、非线性规划的数学模型,7,第七章 非线性规划 第一节 引言,立体图解,二、非线性规划的图示,分析:,(1) 立体图解（图7-1 ）,8,第七章 非线性规划 第一节 引言,平面投影图解,图7-1 例7-3立体图解,9,第七章 非线性规划 第一节 引言,讨论,(2) 平面投影图解（图7-2 ）,D,图7-2 例7-3平面投影图解,（1）求可行域：,（2）求目标函数等值线：,（3）利用目标函数等值线求最优点,该问题可行域的平面投影为第一象限内满足约束条件的一段直线。 （注意：直线，而不是封闭区域）,该问题目标函数等值线平面投影为圆,（4）最优点 、最优解、最优值,10,第七章 非线性规划 第一节 引言,第二节 基本概念,讨论：,D,图7-2 例7-3平面投影图解,考虑约束条件改为：,最优点可位于可行域内部，即非线性规划的可能在可行域的任意一点得到，这与线性规划不同。,非线性规划最优点的特点：,最优解有何变化?,11,第七章 非线性规划 第二节 基本概念,一局部极值与全局极值,第二节 基本概念,极值问题（回顾） 极值存在的条件 凸函数 凸函数性质及定理,主要内容：,12,第七章 非线性规划 第二节 基本概念,1. 局部极小点及局部极小值，严格局部极小点及严格局部极小值,一局部极值与全局极值,线性规划的最优解是整个可行域的全局最优解，这是由于：线性规划的目标函数为线性函数，且可行域为凸集。,线性规划的最优解与 全局最优解的关系：,非线性规划的极值点与 全局最优点的关系：,非线性规划的极值点（局部极值点）：不一定是 整个可行域的最优极值点（图7-3）。,13,第七章 非线性规划 第二节 基本概念,（图7-4）,1. 局部极小点及局部极小值，严格局部极小点及严格局部极小值,定义:,解释:,14,第七章 非线性规划 第二节 基本概念,2. 全局极小点及全局全局极小值，严格全局极小点及严格全局全局极小值,图7-4 局部极小点与严格局部极小点,15,第七章 非线性规划 第二节 基本概念,二极值存在的条件,2. 全局极小点及全局极小值，严格全局极小点及严格全局极小值,定义:,16,第七章 非线性规划 第二节 基本概念,极值存在的条件,第二节 基本概念,极值问题（回顾） 极值存在的条件 凸函数 凸函数性质及定理,主要内容：,17,第七章 非线性规划 第二节 基本概念,2. 驻点,二极值存在的条件,1. 极值存在的必要条件,定理1:,18,第七章 非线性规划 第二节 基本概念,3. 极值存在的充分条件,2. 驻点,满足式（7-1）的点称为驻点，极值点必为驻点，但驻点不一定是极值点。,19,第七章 非线性规划 第二节 基本概念,注：充分条件非必要条件,3. 极值存在的充分条件,定理2:,20,第七章 非线性规划 第二节 基本概念,补充知识：二次型及正定二次型,注1:,注2:,21,第七章 非线性规划 第二节 基本概念,（2）二次型展开式及其矩阵表示,补充知识：二次型及正定二次型,（1）二次型的定义：,22,第七章 非线性规划 第二节 基本概念,（3）正定二次型及正定矩阵,（2）二次型展开式及其矩阵表示,23,第七章 非线性规划 第二节 基本概念,（5）负定二次型及负定矩阵,（3）正定二次型及正定矩阵,（4）半正定二次型及半正定矩阵,24,第七章 非线性规划 第二节 基本概念,（7）不定二次型及不定矩阵,（5）负定二次型及负定矩阵,（6）半负定二次型及半负定矩阵,25,第七章 非线性规划 第二节 基本概念,（8）二次型为正定的充要条件（或正定矩阵的充要条件）,（7）不定二次型及不定矩阵,26,第七章 非线性规划 第二节 基本概念,（11）矩阵的阶顺序主子式,（8）二次型为正定的充要条件（或正定矩阵的充要条件）,（9）二次型为负定的充要条件（或负定矩阵的充要条件）,（10）矩阵的k阶主子式,27,第七章 非线性规划 第二节 基本概念,例7-3（必要条件非充分条件举例）,（11）矩阵的k阶顺序主子式,28,第七章 非线性规划 第二节 基本概念,鞍点（图7-5）,29,第七章 非线性规划 第二节 基本概念,例7-4求极小点及极小值,鞍点：,图7-5 驻点、极值点、鞍点,30,第七章 非线性规划 第二节 基本概念,三凸函数,1阶顺序主子式：,2阶顺序主子式：,因此， 为正定矩阵,根据定理2（极值存在的充分条件），所给函数的极小点为,极小值为,31,第七章 非线性规划 第二节 基本概念,凸函数,第二节 基本概念,极值问题（回顾） 极值存在的条件 凸函数 凸函数性质及定理,主要内容：,32,第七章 非线性规划 第二节 基本概念 三、凸函数,1. 凸函数的定义,三凸函数,主要内容： 凸集（见线性规划） 凸函数 凸函数的性质 函数凸性的判定 凸函数的极值 上述内容为研究非线性规划不可缺少的内容。,33,第七章 非线性规划 第二节 基本概念 三、凸函数,推导g(x3),1. 凸函数的定义,（1）一元凸函数,（i）一元凸函数的几何特性（参考图7-6）,34,第七章 非线性规划 第二节 基本概念 三、凸函数,凸函数定义,35,第七章 非线性规划 第二节 基本概念 三、凸函数,（ii）一元凸函数的定义,因此，对于凸函数，应有：,而：,因此，凸函数应满足的条件为：,如果,则函数f(x)称为凹函数。,36,第七章 非线性规划 第二节 基本概念 三、凸函数,（2）多元凸函数,（ii）一元凸函数的定义,37,第七章 非线性规划 第二节 基本概念 三、凸函数,2. 凸函数的性质,（2）多元凸函数,38,第七章 非线性规划 第二节 基本概念 三、凸函数,2. 凸函数的性质,三凸函数,主要内容： 凸集（见线性规划） 凸函数 凸函数的性质 函数凸性的判定 凸函数的极值 上述内容为研究非线性规划不可缺少的内容。,39,第七章 非线性规划 第二节 基本概念 三、凸函数,3. 函数凸性的判断,2. 凸函数的性质,性质1:,性质2:,40,第七章 非线性规划 第二节 基本概念 三、凸函数,3. 函数凸性的判断,三凸函数,主要内容： 凸集（见线性规划） 凸函数 凸函数的性质 函数凸性的判定 凸函数的极值 上述内容为研究非线性规划不可缺少的内容。,41,第七章 非线性规划 第二节 基本概念 三、凸函数,定理4,3. 函数凸性的判断,直接方法:,定理3:,利用凸函数定义判断，难度较大。,42,第七章 非线性规划 第二节 基本概念 三、凸函数,例7-5 函数凸性的判断,定理4:,证略。,43,第七章 非线性规划 第二节 基本概念 三、凸函数,例7-5 函数凸性的判断,44,第七章 非线性规划 第二节 基本概念 三、凸函数,4. 凸函数的极值,三凸函数,主要内容： 凸集（见线性规划） 凸函数 凸函数的性质 函数凸性的判定 凸函数的极值 上述内容为研究非线性规划不可缺少的内容。,45,第七章 非线性规划 第二节 基本概念 三、凸函数,定理4,4. 凸函数的极值,局部极小点虽然易于求得 但函数的局部极小点不一定等于其全局极小点（最小点） 实际优化问题的目标为求函数的全局极小点（或全局极大点） 常用方法为将全部极小值进行比较（有时需考虑边界值） 但对于凸函数，局部极小点就是全局极小点。,46,第七章 非线性规划 第二节 基本概念 三、凸函数,第三节 凸规划,定理5:,证略。,定理6:,47,目录,第三节 凸规划,第七章 非线性规划,第一节 引言,第二节 基本概念,第三节 凸规划,第四节 一维搜索,48,第七章 非线性规划 第三节 凸规划,二凸规划的解,一凸规划的定义,第三节 凸规划,定义:,49,第七章 非线性规划 第三节 凸规划,例7-6 讨论凸规划问题,二凸规划的解,凸规划的局部最优解为全局最优解。 当凸规划的目标函数为严格凸函数时，最优解唯一（如最优解存在）。 线性规划与凸规划：由于线性函数既为凸函数，又为凹函数，所以线性规划也属于凸规划。 凸规划是非线性规划中既简单又具有重要理论意义的一类规划。但是，用解析方法求解依然不实际。,50,第七章 非线性规划 第三节 凸规划,约束函数凸性判断,1阶顺序主子式:,2阶顺序主子式:,51,第七章 非线性规划 第三节 凸规划,图7-7,1阶顺序主子式:,2阶顺序主子式:,综上，该规划为凸规划，其目标函数等值线投影及可行域如图7-7所示。,52,第七章 非线性规划 第三节 凸规划,第四节 一维搜索方法,53,目录,第四节 一维搜索方法,第七章 非线性规划,第一节 引言,第二节 基本概念,第三节 凸规划,第四节 一维搜索方法,54,第七章 非线性规划 第四节 一维搜索方法,一维搜索概要,一、概述,第四节 一维搜索方法,1.非线性规划解析方法的局限性,55,第七章 非线性规划 第四节 一维搜索方法,多维搜索与一维搜索的关系,2.求解无约束非线性规划的一维搜索方法概要,56,第七章 非线性规划 第四节 一维搜索方法,多维搜索与一维搜索的关系（续）,3.多维搜索与一维搜索之间的关系,57,第七章 非线性规划 第四节 一维搜索方法,3.一维搜索的两大步骤,3.多维搜索与一维搜索之间的关系,58,第七章 非线性规划 第四节 一维搜索方法,二、斐波那契（Fionacci）法,3.一维搜索的两大步骤,（1）确定初始搜索区间，该区间必须为单峰区间。 （2）确定最优步长。,单峰区间:,下单峰函数:,4. 搜索方法优劣的衡量标准,59,第七章 非线性规划 第四节 一维搜索方法,斐波那契法概述（续）,二、斐波那契（Fionacci）法,1.斐波那契法概述,图7-9 下单峰函数极小点所在区间,60,第七章 非线性规划 第四节 一维搜索方法,斐波那契法须解决的问题,图7-9 下单峰函数极小点所在区间,启发:,61,第七章 非线性规划 第四节 一维搜索方法,f2=?,斐波那契法须解决的问题:,问题:,现考虑计算两次函数值的情形。即：,62,第七章 非线性规划 第四节 一维搜索方法,如果区间长度等于2？,63,第七章 非线性规划 第四节 一维搜索方法,递推公式,64,第七章 非线性规划 第四节 一维搜索方法,给定区间长度及缩短精度，函数值计算次数？,(7-2),斐波那契数:,表7-1 斐波那契数表,65,第七章 非线性规划 第四节 一维搜索方法,斐波那契法的步骤,2. 给定区间长度及缩短精度，函数值计算次数？或 计算函数值多少次，才能将给定长度的区间缩短为满足精度的区间？,66,第七章 非线性规划 第四节 一维搜索方法,确定试算点个数,3. 斐波那契法的步骤,（1）确定试算点个数,（4）重复步骤（3）,67,第七章 非线性规划 第四节 一维搜索方法,（1）确定试算点个数,将区间缩短至那个区间？或保留那个试算点更好？,最好的方案是使两种可能性相等。如何实现？,确定试算点,68,第七章 非线性规划 第四节 一维搜索方法,计算另一试算点,(i)考虑原区间长度为fn的情况（图7-12）：,第1次缩短：,(ii)考虑原区间长度为b0-a0的情况，显然：,69,第七章 非线性规划 第四节 一维搜索方法,（3）计算并比较函数值，确定保留区间及保留区间内新的试算点,由于两个试算点互为对称，因此：,第2次缩短时，只要将新区间端点的下标改为1，即可直接利用以上公式。,第3次缩短时，只要将新区间端点的下标改为2。,类似地：,第4次缩短时，只要将新区间端点的下标改为3。,第(n-1)次缩短时，只要将新区间端点的下标改为(n-2) 。,70,第七章 非线性规划 第四节 一维搜索方法,（3）计算并比较函数值，确定保留区间,3. 斐波那契法的步骤,（1）确定试算点个数,（4）重复步骤（3）,71,第七章 非线性规划 第四节 一维搜索方法,重复步骤（3）,72,第七章 非线性规划 第四节 一维搜索方法,重复步骤（3）,3. 斐波那契法的步骤,（1）确定试算点个数,（4）重复步骤（3）,73,第七章 非线性规划 第四节 一维搜索方法,特殊情况：k=n-1,74,第七章 非线性规划 第四节 一维搜索方法,0.618法（黄金分割法）,根据试算点一般公式：,k=n-1时：,即：两个试算点位置相同，因此无法通过比较函数值确定最终区间。为此，xn-1取计算值，而 人为取值为：,斐波那契法采用对称搜索的方法，逐步缩短搜索区间，该方法能以尽量少的函数值计算次数，达到预定的某一缩短率。,75,第七章 非线性规划 第四节 一维搜索方法,黄金分割法的缩短率,三、黄金分割法（ 0.618法）：,所谓黄金分割，指