资源描述
单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,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),
展开阅读全文