《3.3变量轮换法无约束条件多变量函数的选优方法》由会员分享,可在线阅读,更多相关《3.3变量轮换法无约束条件多变量函数的选优方法(18页珍藏版)》请在金锄头文库上搜索。
1、第第三三章章非非线线性性最最优优化化问问题题3.3.1 无约束条件下多变量的优化方法无约束条件下多变量的优化方法 3.3 多变量的优化方法多变量的优化方法 3.3.2 等式约束条件下多变量的优化方法等式约束条件下多变量的优化方法 3.3.3 不等式约束条件下多变量的优化方法不等式约束条件下多变量的优化方法 第第三三章章非非线线性性最最优优化化问问题题一、数学模型一、数学模型3.3.1 无约束条件下多变量的优化方法无约束条件下多变量的优化方法 二、优化方法二、优化方法 变量轮换法、单纯形加速法、一阶梯度法、共轭变量轮换法、单纯形加速法、一阶梯度法、共轭梯度法等。梯度法等。第第三三章章非非线线性性
2、最最优优化化问问题题3.3.1.1 变量轮换法变量轮换法 一、基本思想一、基本思想 把多变量的优化问题转化为一系列单变量的优化问把多变量的优化问题转化为一系列单变量的优化问题方法。题方法。 二、基本原理二、基本原理 沿着沿着坐坐标轴的方向的方向轮流进行轮流进行搜索,搜索,直至直至最最优点点。又。又称称坐标轮换法坐标轮换法。 第第三三章章非非线线性性最最优优化化问问题题三、计算方法(两种计算方法)三、计算方法(两种计算方法)(一)第一种计算方法(一)第一种计算方法1 以以 二元函数情况为例二元函数情况为例 设二元函数设二元函数f(X)=f(x1,x2) ,区间区间a1 x1b1, a2 x2b2
3、,初始点初始点X(0)=(x1(0) ,x2(0) , f(X(0) 。 (1) 令令x1=x1(0) 不动,变动不动,变动x2,求以求以x2为单变量的函数最优为单变量的函数最优值值X(1)=(x1(0) ,x2(1),得,得f(X (1);(2)再令再令x2=x2(1)不动,变动不动,变动x1,求以求以x1为单变量的函数最为单变量的函数最优值优值X(2)=(x1(1),x2(1),得,得f(X (2) ;第第三三章章非非线线性性最最优优化化问问题题(3) 重复搜索。再令重复搜索。再令x1=x1(1)不动,求以不动,求以x2为单变量的函数为单变量的函数最优值最优值X(3)=(x1(1),x2(
4、2),得,得f(X(3),如此反复搜索如此反复搜索,直直到满足精度为止。到满足精度为止。 x1x2b1a1b2a2x1(0)x1(1)x2(0)x2(1)X(0)X(1)X(2)X(3)x2(2)第第三三章章非非线线性性最最优优化化问问题题例例:用用变变量量轮轮换换法法求求函函数数f(x)=6010x14x2x12+ x22x1x2的的极极小小点点,初始点初始点X(0)=(0,0)T,要求要求 f(X(k)f(X(k1) 0.05。0.0352 8.0117X(7)=(7.875,5.9375)f(x2)=43.26611.875x2+ x22X(6)=(7.875,5.75)70.1406
5、8.0469X(6)=(7.875,5.75)f(x1)=70.062515.75x1x12X(5)=(7.5,5.75)60.5625 8.1875X(5)=(7.5,5.75)f(x2)=41.2511.5x2+ x22X(4)=(7.5,5)52.258.75X(4)=(7.5,5)f(x1)=6515x1x12X(3)=(6,5)4911X(3)=(6,5)f(x2)=3610x2+ x22X(2)=(6,2)33620X(2)=(6,2)f(x1)=5612x1x12X(1)=(0,2)2456X(1)=(0,2)f(x2)=604x2+ x22X(0)=(0,0)160X(0)=(
6、0,0)0 函数值函数值xj单变量函数单变量函数f(xj)固定固定xin解解:第第三三章章非非线线性性最最优优化化问问题题2 多元函数情况多元函数情况 设函数设函数f(X)=f(x1,x2 , xn) ,区间区间ai xibi, 初初始点始点X0(0)=(x1(0) ,x2(0) , , xn (0) ) , f(X0(0) 。 (1) 令令xi=xi(0)(i 2) 不动,变动不动,变动x1, f(X)= f(x1) ,求以求以x1为单变量的函数最优值为单变量的函数最优值X0(1)=(x1(1) ,x2(0) , , xn(0),得得f(X0(1);(2)再令再令x1=x1(1),xi=xi
7、(0)(i 3)不动不动 , f(X)= f(x2) ,求以求以x2为单变量的函数最优值为单变量的函数最优值X0(2)=(x1(1),x2(1) ,x3(0) , , xn (0),得,得f(X0(2) ,每次固定每次固定n1个变量,只对一个变个变量,只对一个变量寻优,对量寻优,对n个变量寻优后,才完成第一轮;个变量寻优后,才完成第一轮;第第三三章章非非线线性性最最优优化化问问题题(3)若若 f(X(k)f(X(k1) 成立,成立, 则停止搜索,否则则停止搜索,否则进入下一轮寻优,直至满足精度为止。进入下一轮寻优,直至满足精度为止。3 程序框图程序框图f(X) ,X0 ,k=1, f(X)=m
8、inf(Xki) f(Xki)f(Xki1) i nX0 =Xknk=k+1ENDYNNY第第三三章章非非线线性性最最优优化化问问题题(二)(二)第二种计算方法第二种计算方法设设ei为第为第i个坐标轴的单位矢量,个坐标轴的单位矢量, ei=(0,0,1,0)T 。 第第i 行行(1) 给定初始点给定初始点X(1)=(x1(1),x2(1) ,xn(1) ;(2) 从从X(1)出出发发,先先沿沿着着第第一一坐坐标标轴轴由由e1进进行行搜搜索索,求求出出新新点点X(2)及及最最优优步步长长 1,即即X(2)=X(1) 1e1,f(X(2)=f(X(1) 1e1)=minf(X(1) e1),将将其
9、其代代入入f(X)= f(x1,x2,x3,xn) 中中只只有有一一个个变变量量 ,只只有有当当 取取最最小小,f(X)才才能能取取到到最最小小,也也就就是是说说 1为为沿沿第第一一坐坐标标轴轴方方向向上上的的最最优优步步长长,X(2)为为沿沿第第一一坐坐标标轴轴方方向向上的最优点。上的最优点。第第三三章章非非线线性性最最优优化化问问题题(3) 类类似似地地,从从X(2)出出发发,先先沿沿着着第第二二坐坐标标轴轴由由e2进进行行搜搜索索,求求出出新新点点X(3)及及最最优优步步长长 2,即即X(3)=X(2) 2e2,f(X(3)=f(X(2) 2e2)=minf(X(2) e2), X(n1
10、)=X(n) nen, f(X(n 1)=f(X(n) nen)=minf(X(n) en)。这这样样,从从初初始始点点X(1)经经n次次搜搜索索得得到到新新点点X(n1),完成一轮迭代。完成一轮迭代。(4)若若 f(X(k)f(X(k1) 成立,成立, 则停止搜索,否则则停止搜索,否则进入下一轮寻优(令进入下一轮寻优(令X(1) = X(n1) ),),直至满足精度为止。直至满足精度为止。第第三三章章非非线线性性最最优优化化问问题题程序框图程序框图f(X) ,X1 ,k=1,e, f(X)=minf(Xki iei) f(Xki)f(Xki1) i nX1 =Xknk=k+1ENDYNNY第
11、第三三章章非非线线性性最最优优化化问问题题例例:用用变变量量轮轮换换法法求求函函数数f(x)=x12+ x22 x32的的极极小小点点,初初始始点点X(1)=(1,2,3)T。解:令解:令e1=(1,0,0)T,e2=(0,1,0)T,e3=(0,0,1)T(1)从)从x(1)=(1,2,3)T出发,沿着出发,沿着e1方向搜索。方向搜索。第第三三章章非非线线性性最最优优化化问问题题(2)从)从x(2)=(0,2,3)T出发,沿着出发,沿着e2方向搜索。方向搜索。第第三三章章非非线线性性最最优优化化问问题题(3)从)从x(3)=(0,0,3)T出发,沿着出发,沿着e3方向搜索。方向搜索。第第三三
12、章章非非线线性性最最优优化化问问题题四、变量轮换法讨论四、变量轮换法讨论1、变量轮换法搜索速度的快慢,取决于目标函数的性质。、变量轮换法搜索速度的快慢,取决于目标函数的性质。(1)若目标函数的等高线为圆形(二维)、球形(三维)若目标函数的等高线为圆形(二维)、球形(三维)或长短轴都平行于坐标轴的椭圆形(椭球形),这种方法搜或长短轴都平行于坐标轴的椭圆形(椭球形),这种方法搜索最快。这种情况下,变量之间无交互作用。索最快。这种情况下,变量之间无交互作用。第第三三章章非非线线性性最最优优化化问问题题(2)若目标函数的等高线类似于椭圆形(椭球形),且长)若目标函数的等高线类似于椭圆形(椭球形),且长
13、短轴不平行于坐标轴,这种方法必须经过多次迭代才能到达短轴不平行于坐标轴,这种方法必须经过多次迭代才能到达极值点。这种情况下,变量之间存在弱交互作用。极值点。这种情况下,变量之间存在弱交互作用。x1x2b1a1b2a2x1(0)x1(1)x2(0)x2(1)X(0)X(1)X(2)X(3)x2(2)第第三三章章非非线线性性最最优优化化问问题题(3)若目标函数的等高线出现山脊时,这种方法完全无效。)若目标函数的等高线出现山脊时,这种方法完全无效。这种情况下,变量之间存在强交互作用。因为这种方法的搜这种情况下,变量之间存在强交互作用。因为这种方法的搜索方向总是平行于一坐标轴,不能斜向搜索,因此遇到山脊索方向总是平行于一坐标轴,不能斜向搜索,因此遇到山脊时,不能继续搜索。时,不能继续搜索。x1x2第第三三章章非非线线性性最最优优化化问问题题2、变量轮换法的基本思想认为坐标轴方向为有利的搜索方、变量轮换法的基本思想认为坐标轴方向为有利的搜索方向,因此,在搜索时总是沿着互相垂直的坐标轴方向,并变向,因此,在搜索时总是沿着互相垂直的坐标轴方向,并变换多次,才能达到极值点。搜索效率低,且越接近极值点,换多次,才能达到极值点。搜索效率低,且越接近极值点,搜索速度越慢。搜索速度越慢。