单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章,非线性最优化问题,3.3.1,无约束条件下多变量的优化方法,3.3,多变量的优化方法,3.3.2,等式约束条件下多变量的优化方法,3.3.3,不等式约束条件下多变量的优化方法,一、数学模型,3.3.1,无约束条件下多变量的优化方法,二、优化方法,变量轮换法、单纯形加速法、一阶梯度法、共轭梯度法等。,3.3.1.1,变量轮换法,一、基本思想,把多变量的优化问题转化为一系列单变量的优化问题方法。,二、基本原理,沿着,坐标轴的方向,轮流进行,搜索，,直至,最优点,。又称,坐标轮换法,。,三、计算方法（两种计算方法）,（一）第一种计算方法,1,以,二元函数情况为例,设二元函数,f,(,X,)=,f,(,x,1,，,x,2,),，,区间,a,1,x,1,b,1,，,a,2,x,2,b,2,，,初始点,X,(0),=(,x,1,(0),，,x,2,(0),),，,f,(,X,(0),),。,(1),令,x,1,=,x,1,(0),不动，变动,x,2,，,求以,x,2,为单变量的函数最优值,X,(1),=(,x,1,(0),，,x,2,(1),),，得,f,(,X,(1),),；,(2),再令,x,2,=,x,2,(1),不动，变动,x,1,，,求以,x,1,为单变量的函数最优值,X,(2),=(,x,1,(1),，,x,2,(1),),，得,f,(,X,(2),),；,(3),重复搜索。再令,x,1,=,x,1,(1),不动，求以,x,2,为单变量的函数最优值,X,(3),=(,x,1,(1),，,x,2,(2),),，得,f,(,X,(3),),，,如此反复搜索,，,直到满足精度为止。,x,1,x,2,b,1,a,1,b,2,a,2,x,1,(0),x,1,(1),x,2,(0),x,2,(1),X,(0),X,(1),X,(2),X,(3),x,2,(2),例：,用变量轮换法求函数,f,(,x,)=60,10,x,1,4,x,2,x,1,2,+,x,2,2,x,1,x,2,的极小点，初始点,X,(0),=(0,，,0),T,，,要求,f,(,X,(,k,),),f,(,X,(,k,1),),0.05,。,0.0352,8.0117,X,(7),=(,7.875,，,5.9375,),f,(,x,2,)=43.26611.875,x,2,+,x,2,2,X,(6),=(,7.875,，,5.75,),7,0.1406,8.0469,X,(6),=(,7.875,，,5.75,),f,(,x,1,)=70.062515.75,x,1,x,1,2,X,(5),=(,7.5,，,5.75,),6,0.5625,8.1875,X,(5),=(,7.5,，,5.75,),f,(,x,2,)=41.2511.5,x,2,+,x,2,2,X,(4),=(,7.5,，,5,),5,2.25,8.75,X,(4),=(,7.5,，,5,),f,(,x,1,)=6515,x,1,x,1,2,X,(3),=(,6,，,5,),4,9,11,X,(3),=(,6,，,5,),f,(,x,2,)=3610,x,2,+,x,2,2,X,(2),=(,6,，,2,),3,36,20,X,(2),=(,6,，,2,),f,(,x,1,)=5612,x,1,x,1,2,X,(1),=(,0,，,2,),2,4,56,X,(1),=(,0,，,2,),f,(,x,2,)=604,x,2,+,x,2,2,X,(0),=(,0,，,0,),1,60,X,(0),=(0，0),0,函数值,x,j,单变量函数,f,(,x,j,),固定,x,i,n,解:,2,多元函数情况,设函数,f,(,X,)=,f,(,x,1,，,x,2,，,，,x,n,),，,区间,a,i,x,i,b,i,，,初始点,X,0,(0),=(,x,1,(0),，,x,2,(0),，,，,x,n,(0),),，,f,(,X,0,(0),),。,(1),令,x,i,=,x,i,(0),(,i,2,),不动，变动,x,1,，,f,(,X,)=,f,(,x,1,),，,求以,x,1,为单变量的函数最优值,X,0,(1),=(,x,1,(1),，,x,2,(0),，,，,x,n,(0),),，得,f,(,X,0,(1),),；,(2),再令,x,1,=,x,1,(1),，,x,i,=,x,i,(0),(,i,3,),不动,，,f,(,X,)=,f,(,x,2,),，,求以,x,2,为单变量的函数最优值,X,0,(2),=(,x,1,(1),，,x,2,(1),，,x,3,(0),，,，,x,n,(0),),，得,f,(,X,0,(2),),，,每次固定,n,1,个变量，只对一个变量寻优，对,n,个变量寻优后，才完成第一轮；,(3),若,f,(,X,(k),),f,(X,(,k,1),),成立，,则停止搜索，否则进入下一轮寻优，直至满足精度为止。,3,程序框图,f,(,X,)，,X,0,，,k,=1，,f,(,X,)=min,f,(,X,k,i,),f,(,X,k,i,),f,(X,k,i,1,),i,n,X,0,=X,k,n,k=k+,1,END,Y,N,N,Y,（二）,第二种计算方法,设,e,i,为第,i,个坐标轴的单位矢量，,e,i,=(0,，,0,，,1,，,，,0),T,。,第,i,行,(1),给定初始点,X,(1),=(,x,1,(1),，,x,2,(1),，,，,x,n,(1),),；,(2),从,X,(1),出发，先沿着第一坐标轴由,e,1,进行搜索，求出新点,X,(2),及最优步长,1,，即,X,(2),=,X,(1),1,e,1,，,f,(,X,(2),)=,f,(,X,(1),1,e,1,)=min,f,(,X,(1),e,1,),，,将其代入,f,(,X,)=,f,(,x,1,，,x,2,，,x,3,，,，,x,n,),中只有一个变量,，,只有当,取最小，,f,(,X,),才能取到最小，,也就是说,1,为沿第一坐标轴方向上的最优步长，,X,(2),为沿第一坐标轴方向上的最优点。,(3),类似地，从,X,(2),出发，先沿着第二坐标轴由,e,2,进行搜索，求出新点,X,(3),及最优步长,2,，即,X,(3),=,X,(2),2,e,2,，,f,(,X,(3),)=,f,(,X,(2),2,e,2,)=min,f,(,X,(2),e,2,),，,，,X,(,n,1),=,X,(,n,),n,e,n,，,f,(,X,(,n,1),)=,f,(,X,(,n,),n,e,n,)=min,f,(,X,(,n,),e,n,),。,这样，从初始点,X,(1),经,n,次搜索得到新点,X,(,n,1),，,完成一轮迭代。,(4),若,f,(,X,(k),),f,(X,(,k,1),),成立，,则停止搜索，否则进入下一轮寻优（令,X,(1),=,X,(,n,1),），,直至满足精度为止。,程序框图,f,(,X,)，,X,1,，,k,=1，,e,，,f,(,X,)=min,f,(,X,k,i,i,e,i,),f,(,X,k,i,),f,(X,k,i,1,),i,n,X,1,=X,k,n,k=k+,1,END,Y,N,N,Y,例：,用变量轮换法求函数,f,(,x,)=,x,1,2,+,x,2,2,x,3,2,的极小点，初始点,X,(1),=(1,，,2,，,3),T,。,解：令,e,1,=(1,，,0,，,0),T,，,e,2,=(0,，,1,，,0),T,，,e,3,=(0,，,0,，,1),T,（,1,）从,x,(1),=(1,，,2,，,3),T,出发，沿着,e,1,方向搜索。,（,2,）从,x,(2),=(0,，,2,，,3),T,出发，沿着,e,2,方向搜索。,（,3,）从,x,(3),=(0,，,0,，,3),T,出发，沿着,e,3,方向搜索。,四、变量轮换法讨论,1,、变量轮换法搜索速度的快慢，取决于目标函数的性质。,（,1,）若目标函数的等高线为圆形（二维）、球形（三维）或长短轴都平行于坐标轴的椭圆形（椭球形），这种方法搜索最快。这种情况下，变量之间无交互作用。,（,2,）若目标函数的等高线类似于椭圆形（椭球形），且长短轴不平行于坐标轴，这种方法必须经过多次迭代才能到达极值点。这种情况下，变量之间存在弱交互作用。,x,1,x,2,b,1,a,1,b,2,a,2,x,1,(0),x,1,(1),x,2,(0),x,2,(1),X,(0),X,(1),X,(2),X,(3),x,2,(2),（,3,）若目标函数的等高线出现山脊时，这种方法完全无效。这种情况下，变量之间存在强交互作用。因为这种方法的搜索方向总是平行于一坐标轴，不能斜向搜索，因此遇到山脊时，不能继续搜索。,x,1,x,2,2,、变量轮换法的基本思想认为坐标轴方向为有利的搜索方向，因此，在搜索时总是沿着互相垂直的坐标轴方向，并变换多次，才能达到极值点。搜索效率低，且越接近极值点，搜索速度越慢。,