3.3(变量轮换法)无约束条件多变量函数的选优方法课件.ppt

1、3.3.1 无约束条件下多变量的优化方法无约束条件下多变量的优化方法 3.3 多变量的优化方法多变量的优化方法 3.3.2 等式约束条件下多变量的优化方法等式约束条件下多变量的优化方法 3.3.3 不等式约束条件下多变量的优化方法不等式约束条件下多变量的优化方法 一、数学模型一、数学模型3.3.1 无约束条件下多变量的优化方法无约束条件下多变量的优化方法 ) , , , ,()(min321nnxxxxXEXXf，二、优化方法二、优化方法 变量轮换法、单纯形加速法、一阶梯度法、共轭变量轮换法、单纯形加速法、一阶梯度法、共轭梯度法等。梯度法等。3.3.1.1 变量轮换法变量轮换法 一、基本思想一

2、、基本思想 把多变量的优化问题转化为一系列单变量的优化问把多变量的优化问题转化为一系列单变量的优化问题方法。题方法。 二、基本原理二、基本原理 沿着沿着坐标轴的方向坐标轴的方向轮流进行轮流进行搜索，搜索，直至直至最优点最优点。又。又称称坐标轮换法坐标轮换法。 三、计算方法（两种计算方法）三、计算方法（两种计算方法）（一）第一种计算方法（一）第一种计算方法1 以以 二元函数情况为例二元函数情况为例 设二元函数设二元函数f(X)=f(x1，x2) ，区间，区间a1 x1b1， a2 x2b2，初始点，初始点X(0)=(x1(0) ，x2(0) ， f(X(0) 。 (1) 令令x1=x1(0) 不

3、动，变动不动，变动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(2)，得，得f(X(3)，如此反复搜索，直到，如此反复搜索，直到满足精度为止。满足精度为止。 x1x2b1a1b2a2x1(0)x1(1)x2(0

4、)x2(1)X(0)X(1)X(2)X(3)x2(2)例：例：用变量轮换法求函数用变量轮换法求函数f(x)=6010 x14x2x12+ 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 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

5、)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)=3610 x2+ 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)=(0，0)0 函数值函数值xj单变量函数单变量函数f(xj)固定固定xin解解:2 多元函数情况多元函数情况 设函数设函数f(X)=f(x1，x2 ， xn) ，区间，区间ai

6、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(0)(i 3)不动不动 ， f(X)= f(x2) ，求以，求以x2为为单变量的函数最优值单变量的函数最优值X0(2)=(x1(1)，x2(1) ，x3(0) ， ， xn (0)，得得f(X0(2) ，每次固定

7、，每次固定n1个变量，只对一个变量寻优，个变量，只对一个变量寻优，对对n个变量寻优后，才完成第一轮；个变量寻优后，才完成第一轮；(3)若若 f(X(k)f(X(k1) 成立，成立， 则停止搜索，否则进入则停止搜索，否则进入下一轮寻优，直至满足精度为止。下一轮寻优，直至满足精度为止。3 程序框图程序框图f(X) ，X0 ，k=1， f(X)=minf(Xki) f(Xki)f(Xki1) i nX0 =Xknk=k+1ENDENDY YNNNNY Y（二）第二种计算方法（二）第二种计算方法设设ei为第为第i个坐标轴的单位矢量，个坐标轴的单位矢量， ei=(0，0，1，0)T 。 第第i 行行(1

8、) 给定初始点给定初始点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)，将其代入，将其代入f(X)= f(x1，x2，x3，xn) 中只有一个变量中只有一个变量 ，只有当，只有当 取取最小，最小，f(X)才能取到最小，才能取到最小，也就是说也就是说 1为沿第一坐标为沿第一坐标轴方向上的最优步长，轴方向上的最优步长，X(2)为沿第一坐标轴方向上的为沿第一

9、坐标轴方向上的最优点。最优点。(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)=X(n) nen，f(X(n1)=f(X(n) nen)=minf(X(n) en)。这样，。这样，从初始点从初始点X(1)经经n次搜索得到新点次搜索得到新点X(n1)，完成一轮迭代。，完成一轮迭代。(4)若若 f(X(k)f(X(k1) 成立，成立， 则停止搜索，否则进入则停止搜索，否则进入下一

10、轮寻优（令下一轮寻优（令X(1) = X(n1) ），直至满足精度为止。），直至满足精度为止。程序框图程序框图f(X) ，X1 ，k=1，e， f(X)=minf(Xki iei) f(Xki)f(Xki1) i nX1 =Xknk=k+1ENDENDY YNNNNY Y例：例：用变量轮换法求函数用变量轮换法求函数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方向搜索。方向搜索。13)( ) 3 , 2

11、, 0(10220142)(321001)2()2(121)1()1( xfxfexfxT（2）从）从x(2)=(0，2，3)T出发，沿着出发，沿着e2方向搜索。方向搜索。9)( )3 , 0 , 0(20420134)(320010)3()3(222)2()2(xfxfexfxT（3）从）从x(3)=(0，0，3)T出发，沿着出发，沿着e3方向搜索。方向搜索。0)( )0 , 0 , 0(3062096)(30000)4()4(323)3()3(xfxfexfxT四、变量轮换法讨论四、变量轮换法讨论1、变量轮换法搜索速度的快慢，取决于目标函数的性质。、变量轮换法搜索速度的快慢，取决于目标函数

12、的性质。（1）若目标函数的等高线为圆形（二维）、球形（三维）若目标函数的等高线为圆形（二维）、球形（三维）或长短轴都平行于坐标轴的椭圆形（椭球形），这种方法或长短轴都平行于坐标轴的椭圆形（椭球形），这种方法搜索最快。这种情况下，变量之间无交互作用。搜索最快。这种情况下，变量之间无交互作用。（2）若目标函数的等高线类似于椭圆形（椭球形），且长）若目标函数的等高线类似于椭圆形（椭球形），且长短轴不平行于坐标轴，这种方法必须经过多次迭代才能到短轴不平行于坐标轴，这种方法必须经过多次迭代才能到达极值点。这种情况下，变量之间存在弱交互作用。达极值点。这种情况下，变量之间存在弱交互作用。x1x2b1a1b

13、2a2x1(0)x1(1)x2(0)x2(1)X(0)X(1)X(2)X(3)x2(2)（3）若目标函数的等高线出现山脊时，这种方法完全无效。）若目标函数的等高线出现山脊时，这种方法完全无效。这种情况下，变量之间存在强交互作用。因为这种方法的这种情况下，变量之间存在强交互作用。因为这种方法的搜索方向总是平行于一坐标轴，不能斜向搜索，因此遇到搜索方向总是平行于一坐标轴，不能斜向搜索，因此遇到山脊时，不能继续搜索。山脊时，不能继续搜索。x1x22、变量轮换法的基本思想认为坐标轴方向为有利的搜索方、变量轮换法的基本思想认为坐标轴方向为有利的搜索方向，因此，在搜索时总是沿着互相垂直的坐标轴方向，并向，因此，在搜索时总是沿着互相垂直的坐标轴方向，并变换多次，才能达到极值点。搜索效率低，且越接近极值变换多次，才能达到极值点。搜索效率低，且越接近极值点，搜索速度越慢。点，搜索速度越慢。