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