资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,要求：,空集和单元素集也是凸集。,三角形，矩形，圆，球，凸多边形，第一象限，第一卦限等都是凸。,等价定义（凸集）：,设,凸集与性质,定义（凸集）：,若集合 中任意两点连线都属于 ，则称 为凸集。,因为两点,连线上任一点能够表示为,凸集几何特征,凸集代数特征,称集合 为凸集。,恒有,凸集、凸函数与凸规划,第1页,例1:,证实集合,S=,x,Ax=b,是凸集，其中,A,为,m,n,矩阵，,b,为,m,维向量。,凸集与性质,证实:,即,所以,即,S,是凸集。,例2:,集合,是凸集,称为超平面，,c,为,n,维向量。,例3：,邻域,是凸集。,第2页,定义：,设 那么称,是,凸组合。,性质2：,S,是凸集,S,中任意有限个点凸组合属于,S。,凸集与性质,性质1：,设 是凸集，则 也是凸集。,注：,不一定是凸集。,第3页,定义（凸函数）:,设集合,D,R,n,为凸集，函数,f,:,D,R,若,x,y,D,(0,1)，都有,f,(,x,+(1-,),y,),f,(,x,)+(1-,),f,(,y,),，,则称,f,(,x,)为凸集,D,上凸函数。,若深入有上面不等式以严格不等式成立，则称,f,(,x,)为凸集,D,上,严格凸函数,。,当-,f,(,x,)为凸函数(严格凸函数)时，则称,f,(,x,)为,凹函数,(,严格凹函数,)。,严格凸函数,凸函数,严格凹函数,凸函数,-,推广到多元函数,第4页,定理(一阶条件):,设,D,R,n,为非空凸集，函数,f,:,D,R,在,D,上可微，则,(1),f,在D上为凸函数,任意,x，y,D,，恒有,f,(,y,),f,(,x,),+,f,T,(,x,)(,y-x,),(1),(2),f,在D上为严格凸函数,任意,x,y,D,，恒有,f,(,y,),f,(,x,),+,f,T,(,x,)(,y-x,),.,(2),凸函数判定定理,第5页,定理（二阶条件）:,设,D,R,n,为含有内点非空凸集，函数,f,:,D,R,在,D,上二次可微，则,a),f,在,D,上为凸函数,x,D,，,2,f,(,x,),半正定；,b)若,x,D,，,2,f,(,x,),正定，则,f,在,D,上为严格凸函数。,回想：,一个矩阵半正定充要条件是全部主子式非负；,一个矩阵正定充要条件是全部次序主子式非负。,凸函数判定定理,第6页,例：,设二次函数,(1)：若 为半定矩阵，在 中为凸函数；,(2)：,若 为正定矩阵，在 中为严格凸函数。,例：,判断,f,(,x,),=5x,1,2,-6x,1,x,2,+5x,2,2,在凸集,D,上是否是凸函数？,次序主子式都是正，所以正定，所以,f,(,x,)在凸集,D,上是严格凸函数。,凸函数判定定理,第7页,定义（凸规划）:,考虑以下非线性规划,当 都是凸函数时,称规划 为凸规划,凸规划,第8页,性质1:,设(1)为凸规划，则,i,)(1)可行集,R,是凸集；,ii,)(1)最优解集是凸集；,iii,)(1)任何局部极小点都是全局极小点。,性质2:,设(1)为凸规划，若,f,(,x,)在非空可行集,R,上是严格凸函 数，则(1)全局极小点是唯一。,证实：,见书中(P24)定理 3.11.,注:,非线性规划局部最优解不一定是,全局最优解,其可行解和最优解集也,不一定是凸集,甚至不是连通集.如,果是凸规划,就有很多好性质。,凸规划性质,证实：,见书中(P23)定理 3.9、3.10.,第9页,普通情况下,为正整数,分别表示约束条件个数和决议变量个数,为价值向量,为决议向量,通常,为已知常数。,称,m,为线性规划阶数,称,n,为线性规划维数。,线性规划标准形,第10页,怎样化成标准形,若要求目标函数是:max,z,=,c,T,x,只需将目标函数最大值变换为求目标函数最小值,即 max,z,=min,(-,z,)。令,z=-z,于是得到：,min,z,=-,c,T,x,。,目标函数转换,第11页,若约束方程组为不等式,约束条件为“,”形式不等式,则在,“,”号左边加入非负松弛变量;把原,“,”形不等式变为等式;,约束方程转换：由不等式转换为等式,称为松弛变量,对应松弛变量在目标函数中价值系数取值为0。,怎样化成标准形,第12页,约束条件为“”形式不等式,则可在“”号左端减去一个非负剩下变量。,约束方程转换：由不等式转换为等式,称为剩下变量,对应剩下变量在目标函数中价值系数取值为0。,怎样化成标准形,第13页,若存在取值无约束变量 ，可令,其中：,变量转换,若 ，,可令 ，显然,怎样化成标准形,第14页,例1:,试将以下线性规划问题化成标准形,任何形式线性规划问题都能够化成标准形。现举例以下：,怎样化成标准形,第15页,解：令,x,3,=,x,4,-,x,5,x,4,x,5,0,(1),式左端加上非负松弛变量,x,6,(2),式左端减去非负剩下变量,x,7,则可将上述线性规划问题化成以下标准形:,怎样化成标准形,第16页,可行解（或允许解）:,满足约束条件解,x,=,(,x,1,x,2,x,n,),T,称为线性规划问题可行解;,可行域：,全部可行解集合称为可行解集或可行域。,3.最优解:,使得目标函数取到最小值可行解称为线性规划问题最优可行解，简称为最优解或者解。,线性规划问题标准形为：,线性规划基本概念,第17页,基:,假设,A,是约束方程组系数矩阵,其秩数为,m,B,是矩阵,A,中由,m,列组成非奇异子矩阵(,B,行列式值不为0），则称,B,是 线性规划问题一个基。,矩阵,B,是由,m,个线性无关列向量组成,不失普通性,可假设:,称,P,j,(,j,=1,2,m,),为基向量,与基向量,P,j,相对应变量,x,j,(,j,=1,2,m,),为基变量,不然称为非基变量。,线性规划基本概念,第18页,5.基本解：,若令(2.1)式中非基变量,x,m,+1,=,=,x,n,=0,求出一个解,x=,(,x,1,x,2,x,m,0,0),T,这个解非0分量数目小于方程个数,m,称,x,为基本解。,线性规划基本概念,当基本解中有一个或者一个以上基变量是0时，称这个基本解是,退化基本解,。,第19页,基本可行解:,满足非负约束条件基本解称为基本可行解.,基本可行解非0分量数目小于,m,都是非负。,7.可行基:,对应于基本可行解基称为可行基.,约束方程组,Ax=b,基本解数目至多是,C,n,m,个.普通地讲,基本可行解数目要小于基本解数目,至多相等.,以上提到几个解概念,可用以下列图来表示:,基解,可行解,基,本,可行解,线性规划基本概念,第20页,1947年,美国学者George Dantzig(丹茨格)提出了求解线性规划单纯形法,为线性规划推广奠定了基础。,从可行域,一个顶点,(基本可行解)开始,转移到另一个顶点,(另一个基本可行解)迭代过程，,转移条件,是,使目标函数值得到改进,(逐步变优),当目标函数到达最优值时,问题也就得到了最优解。,基本思想,单纯形法,第21页,重复以上过程，能够深入改进基本可行解，直到全部 时为止。,单纯形法基本原理,基变量,基变量,非基变量,非基变量,初始基本可行解,改进基本可行解,目标函数值减小,了,进基变量确实定,离基变量确实定,f,0,是最优值,当前基本可行解是最优解,第22页,以极小化问题为例,每次迭代必出现以下三种情形之一,(1).这时当前基本可行解就是最优解。,(2).这种情形下，我们知道 取任何正数，总能得到可行解。所以当 无限增大时，目标函数趋于负无穷，所以解无界。,(3)，大于零。这时求出新基本可行解，经迭代使目标函数下降。,单纯形法收敛性,第23页,z,k,-c,k,y,mk,y,rk,y,1,k,z,j,-c,j,z,m+1,c,m+1,0,0,0,y,mj,y,mm+,1,1,0,0,y,rj,y,rm+,1,0,1,0,y,1,j,y,1,m,+1,0,0,1,初始单纯形表,使用表格形式单纯形方法,1.结构单纯形表,x,k,是进基变量，是离基变量；,主元,把,x,k,所对应列向量,p,k,变成 所对应列向量，即是单位向量。,把,x,k,和,位置对换，,第24页,对应新目标函数值即为：,使用表格形式单纯形方法,2.高斯主元消去法,以,y,rk,为主元素进行Gauss消元:,将第,r,行每个元素除以,y,rk,:,将第,r,行每个元素乘以,y,ik,/y,rk,加到第,i,行(,i=,1,m,i,r,),将第,r,行每个元素乘以,(,z,k,c,k,),/y,rk,加到检验数行,第25页,经过Gauss消元后，针对于新基,B,1,基本可行解为：,使用表格形式单纯形方法,2.高斯主元消去法,第26页,min x,6+,x,7,s.t.x,1,+x,2,-,x,3,+,x,6,=,2,x,1,-x,2,-,x,4,+,x,7,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,7,例3,.利用单纯形算法求解以下线性规划问题。,解：,x,6,，,x,7,，,x,5,对应是单位矩阵，可选择作为基变量,，,建立单纯形表，利用主元消去法，进行迭代。,第27页,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,1 1 -1 0 0 1 0,1 -1 0 -1 0 0 1,1 0 0 0 1 0 0,x,6,x,7,x,5,2,1,3,2 0 -1 -1 0 0 0,0 2,-1 1 0 1 -1,1 -1 0 -1 0 0 1,0 1 0 1 1 0 -1,x,6,x,1,x,5,1,1,2,0 2 -1 1 0 0 -2,c,B,1,1,0,2,1,3,1/2,-,2,1,0,0,x,2,x,1,x,5,0 1 -1/2 1/2 0 1/2 -1/2,1 0 -1/2 -1/2 0 1/2 1/2,0 0 1/2 1/2 1 -1/2 -1/2,1/2,3/2,3/2,0 0 0 0 0 -1 -1,0,0,0,min x,6+,x,7,s.t.x,1,+x,2,-,x,3,+,x,6,=,2,x,1,-x,2,-,x,4,+,x,7,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,7,c,0 0 0 0 0 1,1,第28页,x,2,x,1,x,5,0 1 -1/2 1/2 0 1/2 -1/2,1 0 -1/2 -1/2 0 1/2 1/2,0 0 1/2 1/2 1 -1/2 -1/2,1/2,3/2,3/2,0 0 0 0 0 -1 -1,0,0,0,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,c,B,c,0 0 0 0 0 1,1,全部判别数,z,j,-,c,j,0,，,所以到达最优解,第29页,两阶段法和大,M,法,对于标准线性规划问题(简写为,LP,):,这里,A,=(,a,ij,),m,n,b,0,秩(,A,)=,m,.,使用单纯形方法，需要给定一个初始基本可行解，方便从这,个基本可行解出发，求改进基本可行解。,若,A,中包含,m,阶单位矩阵，则初始基本可行解轻易找到。,若,A,中不包含,m,阶单位矩阵，初始基本可行解怎么找？,初始基本可行解怎么找？,第30页,设,A,中不包含,m,阶单位矩阵,引入人工变量,得到(5)一个基,本,可行解：,显然(5)系数矩阵中包含一个,m,阶单位矩阵，取做基矩阵，,人工变量,人为引入,变量个数变多了，线性规划维数变大了,把每个等式增加一个,非负变量,，得到,怎样排除人工变量，求出原线性规划最优解呢？,惯用方法：,两阶段法,大M法,第31页,两阶段法,第一阶段,是用单纯形法消去人工变量(可能话)，即把人工变量都变换成非基变量，求出原来问题一个基本可行解。,消去人工变量其中一个方法是解以下一个问题：,其中,e,是分量全为1,m,维列向量，,两阶段法基本思想,第32页,两阶段法基本思想,设(6)最优基本可行解是,实际上，假如(,LP,)存在可行解 ，则 是(6)可行解，对应(6)目标函数值是,矛盾！,是(6)最优解,这时，,m,个基变量都是原来变量，是(6)基本可行,解，,(,i,)若 ，则标准线性规划(,LP,)没有可行解；,(,ii,)若 ，且,x,a,分量都是非基变量。,是(,LP,)一个基本可行解。,第33页,两阶段法基本思想,设(6)最优基本可行解是,此时最优值是0.,这时，可用主元消去法，把原来变量中非基变量引进基，替换,出基变量中人工变量，此时最优值一直都保持是0，从而就,得到,(,LP,),一个基本可行解。,第一阶段结束，得到原来线性规划一个基本可行解。,(,iii,)若 ，且,x,a,一些分量是基变量。,可化为第(,ii,)种情况，,第34页,两阶段法,第二阶段,，就是从得到基本可行解,出发，用单纯形法求问题(*)最优解。,第35页,例1.,利用两阶段法求解以下线性规划问题。,min -2x,1,-x,2,s.t.x,1,+x,2,2,x,1,-x,2,1,x,1,3,x,1,x,2,0,min -2x,1,-x,2,s.t.x,1,+x,2,-,x,3,=,2,x,1,-x,2,-,x,4,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,5,解,：,1.首先把问题化成标准形式,：,系数矩阵中不包含单位矩阵,第36页,min x,6+,x,7,s.t.x,1,+x,2,-,x,3,+,x,6,=,2,x,1,-x,2,-,x,4,+,x,7,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,7,2.,引进人工变量,x,6,x,7,结构单位矩阵,，,求解下面问题,3.,x,6,，,x,7,，,x,5,对应是单位矩阵，可选择作为基变量,，,建立单纯形表，利用主元消去法，进行迭代。,第37页,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,1 1 -1 0 0 1 0,1 -1 0 -1 0 0 1,1 0 0 0 1 0 0,x,6,x,7,x,5,2,1,3,2 0 -1 -1 0 0 0,0 2,-1 1 0 1 -1,1 -1 0 -1 0 0 1,0 1 0 1 1 0 -1,x,6,x,1,x,5,1,1,2,0 2 -1 1 0 0 -2,c,B,1,1,0,2,1,3,1/2,-,2,1,0,0,x,2,x,1,x,5,0 1 -1/2 1/2 0 1/2 -1/2,1 0 -1/2 -1/2 0 1/2 1/2,0 0 1/2 1/2 1 -1/2 -1/2,1/2,3/2,3/2,0 0 0 0 0 -1 -1,0,0,0,min x,6+,x,7,s.t.x,1,+x,2,-,x,3,+,x,6,=,2,x,1,-x,2,-,x,4,+,x,7,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,7,c,0 0 0 0 0 1,1,第38页,x,2,x,1,x,5,0 1 -1/2 1/2 0 1/2 -1/2,1 0 -1/2 -1/2 0 1/2 1/2,0 0 1/2 1/2 1 -1/2 -1/2,1/2,3/2,3/2,0 0 0 0 0 -1 -1,0,0,0,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,c,B,c,0 0 0 0 0 1,1,4.,全部判别数,z,j,-,c,j,0,，,所以到达最优解。,从表中可看到：在一阶段问题最优解中，人工变量,x,6,，,x,7,都是非基变量。所以我们得到了,原线性规划基本可行解,第39页,x,B,x,1,x,2,x,3,x,4,x,5,c,B,-1,-2,0,0 1 -1/2 1/2 0,1 0 -1/2 -1/2 0,0 0 1/2 -1/2 1,x,2,x,1,x,5,1/2,3/2,3/2,min -2x,1,-x,2,s.t.x,1,+x,2,-,x,3,=,2,x,1,-x,2,-,x,4,=1,x,1,+,x,5,=,3,x,j,0,j=1,2,5,0 0 3/2 1/2 0,c,-2 -1 0 0 0,5.第二阶段，修改最终单纯形表。,x,2,x,1,x,5,0 1 -1/2 1/2 0 1/2 -1/2,1 0 -1/2 -1/2 0 1/2 1/2,0 0 1/2 1/2 1 -1/2 -1/2,1/2,3/2,3/2,0 0 0 0 0 -1 -1,0,0,0,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,c,B,c,0 0 0 0 0 1,1,修改检验数和目标函数，去掉人工变量对应列，其它不变。,第40页,x,B,x,1,x,2,x,3,x,4,x,5,x,2,x,1,x,3,2,3,3,0 0 0 -1 -3,c,B,-1,-2,0,-,-,3,-1,-2,0,0 1 -1/2 1/2 0,1 0 -1/2 -1/2 0,0 0 1/2 -1/2 1,x,2,x,1,x,5,1/2,3/2,3/2,0 0 3/2 1/2 0,0 1 0 0 1,1 0 0 -1 1,0 0 1 -1 2,c,-2 -1 0 0 0,6.,这时，检验数全部小于等于0，,得到最优解：,x,=(3,2,3,0,0),T,目标函数最小值为：,f,=-2*3-1*2=-8,第41页,大,M,法基本思想,在约束中添加人工变量 ，,M,0,e,为全1,m,维列向量。,(7）是可行,基本可行解,因为大,M,是充分大正数，在极小化目标函数过程中，就会迫使人工变量离基。,同时修改目标函数，加上处罚项,经过求解（7）而取得(*)最优解,第42页,用单纯形法求解,(7)，,假如(7)存在有限最优解,，设为,(ii)当 时，(7)无可行解。,(i)当 时,x*,是问题(*)最优解。,实际上，假如(*)存在可行解 ，则 是(7)可行解，对应(7)目标函数值是,M是充分大正数,是(7)最优解,矛盾！,第43页,在单纯形表中,假如(7)不存在有限最优解,(i)当 时，,问题,(,LP,),无界;,(ii)当 时，,即 ，问题,(,LP,)无可行解.,第44页,例3.,利用大M法求解以下线性规划问题。,min x,1,+x,2,-3x,3,s.t.x,1,-2x,2,+x,3,11,2x,1,+x,2,-4x,3,3,x,1,-2x,3,=,1,x,1,x,2,x,3,0,解,：,1.将问题化成标准形式,，引进松弛变量,x,4,x,5,min x,1,+x,2,-3x,3,s.t.x,1,-2x,2,+x,3,+,x,4,=11,2x,1,+x,2,-4x,3,-x,5,=,3,x,1,-2x,3,=,1,x,j,0,j=1,2,5,系数矩阵中不包含单位矩阵,第45页,2.引进人工变量,x,6,x,7,结构单位矩阵,，,用单纯形法求解以下问题,min x,1,+x,2,-3x,3,+M(x,6,+x,7,),s.t.x,1,-2x,2,+x,3,+,x,4,=11,2x,1,+x,2,-4x,3,-x,5,+,x,6,=,3,x,1,-2x,3,+,x,7,=,1,x,j,0,j=1,2,7,3.,x,4,，,x,6,，,x,7,对应是单位矩阵，可选择作为基变量，建立单纯形表，利用主元消去法，进行迭代。,第46页,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,x,4,x,6,x,7,11,3,1,3M-1 M-1 -6M+3 0 -M 0 0,x,4,x,6,x,1,10,1,1,0 M-1 1 0 -M 0 1-3M,c,B,0,M,M,11,3/2,1,-,1,-,0,M,1,x,4,x,2,x,1,12,1,1,0,1,1,c,1 1 -3 0 0 M,M,1 -2 1 1 0 0 0,2 1 -4 0 -1 1 0,1 0 -2 0 0 0 1,min x,1,+x,2,-3x,3,+M(x,6,+x,7,),s.t.x,1,-2x,2,+x,3,+,x,4,=11,2x,1,+x,2,-4x,3,-x,5,+,x,6,=,3,x,1,-2x,3,+,x,7,=,1,x,j,0,j=1,2,7,0 -2 3 1 0 0 -1,0 1 0 0 -1 1 -2,1 0 -2 0 0 0 1,0 0 3 1 -2 2 -5,0 1 0 0 -1 1 -2,1 0 -2 0 0 0 1,0 0 1 0 -1 1-M -1-M,4,-,-,第47页,0 0 0 -1/3 -1/3 1/3-M 2/3-M,4,1,9,x,B,x,1,x,2,x,3,x,4,x,5,x,6,x,7,c,B,x,4,x,2,x,1,12,1,1,0,1,1,c,1 1 -3 0 0 M,M,0 0 3 1 -2 2 -5,0 1 0 0 -1 1 -2,1 0 -2 0 0 0 1,0 0 1 0 -1 1-M -1-M,4,-,-,x,3,x,2,x,1,-3,1,1,0 0 1 1/3 -2/3 2/3 -5/3,0 1 0 0 -1 1 -2,1 0 0 2/3 -4/3 4/3 -7/3,4.检验数全部小于等于0，而且人工变量全取0，,于是得到最优解：,最优值为：,f,=9+1-3*4=-2,x,=(9,1,4),T,第48页,(1)对称形式,特点：目标函数求极小值，约束条件“”，变量非负;,目标函数求极大值，约束条件“”，变量非负;,对偶定义,互为对偶,第49页,普通称不含有对称形式一对线性规划为非对称形式对偶规划。,方法一：,对于非对称形式线性规划，能够先化成对称形式线性规划，写出其对偶规划。,(2)非对称形式对偶问题,对偶定义,第50页,例1：,写出以下线性规划问题对偶问题,第51页,第52页,原问题,对偶问题,第53页,例2：,标准形式对偶问题,对偶定义,对偶问题,第54页,变量数：,n,个,第,j,个变量 0,第,j,个变量 0,第,j,个变量是自由变量,约束条件：,m,个,第,i,个约束类型为“”,第,i,个约束类型为“”,第,i,个约束类型为“”,目标函数max,对偶问题（原问题）,约束条件：,n,个,第,j,个约束类型为“”,第,j,个约束类型为“”,第,j,个约束类型为“”,变量数：,m,个,第,i,个变量 0,第,i,个变量 0,第,i,个变量是自由变量,目标函数 min,原问题（对偶问题）,方法二：,按照下面对应关系直接给出其对偶规划:,(2)非对称形式对偶问题,第55页,变量数：,n,个,第,j,个变量 0,第,j,个变量 0,第,j,个变量是自由变量,约束条件：,m,个,第,i,个约束类型为“”,第,i,个约束类型为“”,第,i,个约束类型为“”,目标函数max,对偶问题（原问题）,约束条件：,n,个,第,j,个约束类型为“”,第,j,个约束类型为“”,第,j,个约束类型为“”,变量数：,m,个,第,i,个变量 0,第,i,个变量 0,第,i,个变量是自由变量,目标函数 min,原问题（对偶问题）,第56页,定理1(对称性),对偶问题对偶是原问题,对偶问题基本定理,第57页,定理2(弱对偶定理),设,分别是原问题,和对偶问题,可行解,则,原问题任一可行解对应目标函数值大于其对偶问题任一可行解对应目标函数值。,对偶问题基本定理,第58页,定理3(最优性定理),设,分别是原问题,和对偶问题,可行解,若,则 分别是它们最优解。,对偶问题基本定理,定理4(强对偶定理),若原问题,有最优解，则其对偶问题,一定有最优解,且它们目标函数值相等。,第59页,n=1时，是一维无约束优化问题-第三章第1部分内容,n1时，是多维无约束优化问题-第三章第2部分内容,n,元函数,求解无约束优化问题,第60页,找初始点,判断当前点是否满足终止条件,下一个迭代点,最优解,(a)找初始点,(b)终止条件,(c)迭代格式,找步长 和下降方向 ，,确定下一个迭代点,不一样,对应不一样算法,是,否,循环,线搜索迭代法框架分析,不一样,对应不一样算法,第61页,求目标函数,f,(,x,)极小：,因为这项工作是求以,为变量一元函数,极小点,，故常称这一过程为,（准确）一维搜索或,线搜索迭代法框架分析-,一维搜索,（准确）线搜索或一维最优化,，确定步长为最正确步长。,第62页,在搜索方向上所得最优点处梯度和该搜索方向正交。,定理,设目标函数,含有一阶连续偏导数，,规则产生,则有,（准确）一维搜索一个主要性质,按下述,证实：,结构,函数 ，则得,即 是函数 极小点，所以,第63页,“成功失败”法（进退法）,基本思想：一个试探法：从一点出发，按一定步长搜索新点，若搜索成功，加大步长继续搜索；若搜索失败，缩小步长小步后退。,第64页,“成功失败”法（进退法）,步骤1：,选取初始点,x,R,初始步长,h,0 及精度,0，,步骤2：计算,步骤3：若 搜索成功,转步骤4；不然，搜索失败，,转步骤5。,步骤4：令,x:=x+h,转步骤 2。,步骤5：判断 若 停顿迭代，；不然令,转步骤 2。,缺点：效率低。优点：能够求,搜索区间,。,注意：初始步长不能选得太小,第65页,例1,：设给定初始点,为,a,及初始步长为,h,求搜索区间,c,d,1)前进运算,首先计算,f,(,a,),f,(,a+h,),假如,f,(,a,),f,(,a+h,),则步长加倍,计,算,f,(,a+3h,).若,f,(,a+h,)=,f,(,a+3h,),则,c=a,d=a+3h;,不然将步,长再加倍，并重复上面运算.,2)后退运算,假如,f,(,a,),f,(,a+h,),则将步长缩为原来1/4并改变符号，即,将步长改为,-h/4,假如,f,(,a,),f,(,a-h/4,),则,c=a-h/4,d=a+h,;不然,将步长加倍，并继续后退。,注意,:,1.,h,选择要适当.(太大含多个单峰区间,太小迭代次数多)；,2.,f(x),单调时无结果,(加迭代次数限制)；,“成功失败”法（进退法）,第66页,0.618法（黄金分割法）,0.618法是求单峰函数极值一个试探法，有书上也称为区,间收缩法。,在搜索区间a,b上插入两个点，将分为三个子区间，经过比较,2个插入点函数值大小，可删去左边或者右边区间，使搜索区,间缩短。重复上述过程，使搜索区间不停缩短，当区间缩短到一,定程度时，区间上各点都能够作为极小点近似。,仅适合用于求解单峰函数,第67页,例,：,利用“成功-失败”法求函数 搜索区间，,取初始点 ，步长,解：,取初始点 ，步长,“成功失败”法,-算例,得到搜索区间为,第68页,0.618法（黄金分割法）,定义(单峰函数),：,设,f(x),是定义在,a,b,上函数，若,1）,x,*,a,b,是,在,a,b,上最小点，,2）若对任意,x,1,x,2,a,x,1,f,(,x,2,);,2 若,x,1,x,*,，则,f,(,x,1,),f,(,x,2,).,则称,f(x),为,a,b,上单峰函数。,第69页,定理：,设,f,：,R,R,在,a,b,上是单峰函数，,a,x,1,x,2,b,。,那么,1若,f,(,x,1,),f,(,x,2,)，则,x,*,x,1,b,如左下列图,2,若,f,(,x,1,),f,(,x,2,)，则,x,*,a,x,2,如右下列图,x,1,x,2,b,x,1,x,2,b,0.618法（黄金分割法）,缩短区间第一个标准-去坏留好标准,选二点,x,1,x,2,比较,f,(,x,1,),与,f,(,x,2,),可去掉,a,x,1,或者,x,2,b,.,第70页,考虑条件：,2对称标准：,x,1,a,=,b-,x,2,（使“坏”情况去掉，区间长度大于“好”情况）,3保持缩减比标准,t,=(保留区间长度原区间长度)不变。,（使每次保留下来节点，,x,1,或,x,2,，在下一次比较中成,为一个对应百分比位置节点）。,推导缩减比,t,:,如图设第一次保留,a,x,2,(去掉,x,2,b),第二次保留长度为,x,1,则,x,1,x,2,b,0.618法（黄金分割法）,第71页,整理：,x,2,=a+t,(,b-,),x,1,=a+t,(,x,2,-,),结合式：,t,2,+t 1=0,故,t0.618,注意:上式有,t,2,=1-t,故有,x,1,=a+,(,1-t,)(,b-a,)=,a+,0.328(,b-a,),x,2,=a+t,(,b-a,)=,a+,0.618(,b-a,),0.618法（黄金分割法）,第72页,优点：不要求函数可微，且每次迭代只需计算一,个函数值，计算量小，程序简单,缺点：收敛速度慢。,黄金分割法（0.618 法）优缺点,0.618法（黄金分割法）,第73页,例,：,试用0.618法求目标函数 最优解。,给定初始区间0,2，收敛精度,解：,第一次区间缩短计算过程：,计算两点及对应函数值：,作数值比较，可见 ,再做置换：,0.618,法,-算例,第74页,第二次区间缩短计算过程：,作数值比较，,再做置换：,第三次区间缩短计算过程：,作数值比较，,再做置换：,第75页,各次迭代结果以下：,迭代次数,x,1,x,2,f,(,x,1,),f,(,x,2,),a,b,|,b-a,|,第1次,0.764,1.236,-0.0821,0.4126,0,1.236,1.236,第2次,0.472,0.764,0.1612,-0.0821,0.472,1.236,0.788,第3次,0.764,0.944,-0.0821,-0.0468,0.472,0.944,0.472,第4次,0.652,0.764,-0.0268,-0.0821,0.652,0.944,0.292,第5次,0.764,0.832,-0.0821,-0.0881,0.764,0.944,0.230,第6次,0.832,0.906,-0.0881,-0.0683,0.764,0.906,0.124,缺点：收敛速度慢,优点：不要求函数可微，且每次迭代只需计算一个函数,值，计算量小,第76页,设,f(,x,),在,a,b,上可微，求函数,f,在,a,b,极小点，就是求,函数导数为零点。假如 ，则在(,a,b,),内一定存在一点,x,，使得 。为求极小点，可取,，若,x,为最小点,x=x,*;,x,0,在上升段,x,*,x,0,，去掉,a,x,0,.,二分法-,基本思想,第77页,用 或者 作新区间a,b，继续这个过程，,逐步将区间a,b缩小，,当区间a,b,长度充分小时，可将a,b中点取做极小,点近似点。,二分法-,基本思想,第78页,优点：计算量较少，而且总能收敛到一个局部极小点。,缺点：收敛速度较慢,二分法-,计算步骤,步骤1：计算,步骤2：若 ，令 ，转步骤3；,若 ，令 ，转步骤3；,若 ，停顿，。,步骤3：若 ，则 ，停顿，不然，转步骤1.,第79页,例,：,试用二分法求目标函数 最优解。,给定初始区间0,2，收敛精度,解：,在0,2内有极小点。,二分,法,-算例,第一次区间缩短计算过程：,因为,所以函数,第80页,第二次区间缩短计算过程：,第三次区间缩短计算过程：,第81页,各次迭代结果以下：,迭代9次后，|b-a|=0.003910.004,故,迭代次数,x,0,=(,a+b,)/2,f,(,x,0,),a,b,|b-a|,第1次,x,0,=1,1,0,1,1,第2次,x,0,=1/2,-5/4,1/2,1,1/2,第3次,x,0,=3/4,-5/16,3/4,1,1/4,第4次,x,0,=7/8,19/64,3/4,7/8,1/8,第5次,x,0,=13/16,-0.0195,13/16,7/8,1/16,第6次,x,0,=27/32,0.0136,13/16,27/32,1/32,第7次,x,0,=53/64,0.0574,13/16,53/64,1/64,第8次,x,0,=105/128,0.0184,13/16,105/128,1/128,第9次,x,0,=209/256,-0.0004,209/256,105/128,1/256,第82页,牛顿法（Newton）,-基本思想,对,f(x),在,x,k,点二阶泰勒展开：,略去高阶项得,两边对,x,求导，,令 ，得到,牛顿法是一个函数迫近法，,基本思想是：,在极小点附近用函数二阶泰勒多项式近似代替目标函数，从而求得目标函数极小点近似值。,第83页,牛顿法（Newton）,-基本思想,取,作为新迭代点，继续迭代，直到抵达精度，这么就得到了,函数,f,一个驻点 。,第84页,牛顿法（Newton）,-计算步骤,步骤1：给定初始点 令 。,步骤2：计算 。,步骤3：若 ，停顿，不然转步骤4。,步骤4：计算,令 ，转步骤2。,特点：收敛速度快，局部二阶收敛。,缺点：须计算二次导数，工作量大；对初始点要求高，要求初始点离极小点不太远，不然有可能使极小化发散或收敛到非极小点；局部收敛,。,第85页,例,：,试用Newton法求函数,最优解。,解：,Newton,法,-算例,第86页,Newton,法,-算例,Newton,法收敛速度快,得到近似解,第87页,用,在2 个或3 个点函数值或导数值，结构2 次或3次多项式作为,近似值，以这多项式极小点作为新迭代点。包含,3点2次，2点2次，4点3次，3点3次，2点3次等插值法.,下面以3点2次插值法（二次插值法）为例：,利用 在区间 函数值,作出以下二次插值多项式,它应满足条件,（1）,插值法,（2）,（3）,第88页,从极值必要条件 求得,求出系数 和 ，就可得到极小点表示式。,插值法-,求二次插值多项式极小点,第89页,1.寻找满足以下条件点（成功失败法寻找），成为两头大中间小点：,x,1,x,2,f,(,x,2,),f,(,x,2,)0,则 为,g,(,x,)极小值点，且,3.若 ，则迭代结束，取 ，不然在点,中,，选取使,f,(,x,)最小点作为新,x,2，,并使新,x,1,，,x,3,各是新,x,2,近旁左右两点，继续进行迭代，直到满足终止准则。,插值法-,算法思绪：,第90页,2）用二次插值法迫近极小点,(1)相邻三点及其函数值,:,x,1,=0,x,2,=1,x,3,=2;,f,1,=2,f,2,=1,f,3,=18.,例用二次插值法求函数,f,(,x,)=3,x,3,-4,x,+2极小点，给定,x,0,=0,h,=1,=0.2。,解：,1）确定初始搜索区间,初始区间,a,b,=0,2,另有一中间点,x,2,=1。,依据公式计算差值多项式极小点,第91页,(2)在新区间，相邻三点及其函数值:,x,1,=0,x,2,=0.555,x,3,=1;,f,1,=2,f,2,=0.292,f,3,=1.,故新区间,a,b,=,a,x,2,=0,1，,应继续迭代。,x,1,=0,x,2,=1,x,3,=2;,f,1,=2,f,2,=1,f,3,=18,因为,依据公式计算差值多项式极小点,第92页,故新区间,a,b,=,x,2,b,=0.555,1，,迭代终止。,x,1,=0,x,2,=0.555,x,3,=1;,f,1,=2,f,2,=0.292,f,3,=1,因为,故,第93页,目标是找 中一点 ，使对 ，都有,，称为此无约束最优化问题全局极小点。,无约束最优化问题：,求解无约束最优化问题计算方法称为,无约束最优化方法,。,多维无约束最优化方法,第94页,无约束最优化方法应用广泛，理论也比较成熟；,可将约束优化问题转化为无约束优化问题来处理；,最优化方法中基本方法,-,无约束优化方法,：利用函数一阶或二阶导数方法,收敛速度快，需要计算梯度或者,Hesse,矩阵,：仅利用函数值信息，寻找最优解,不包括导数，适用性强，但收敛速度慢,可求得目标函数梯度时使用解析法,在不可能求得目标函数梯度或偏导数时使用直接法,我们介绍解析法,第95页,最优性条件(Optimality Conditions),所谓,最优性条件,，是指最优化问题最优解所要满足,必要条件或充分条件,。,解析法要用到目标函数梯度或者,Hesse,矩阵，轻易想到,利用一阶必要条件将无约束优化问题转化成一个梯度为0确定,方程组。,这里用到一阶必要条件就是最优性条件
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
