【精品】基于单片机的无约束优化直接法

多变量无约束最优化方法－－直接法丁媛媛多变量无约束最优化方法概述Af(X)=4x16例如： 求解下述下列的非线性规划目标函数： min f(X) =(x1－2)2+(x2－2)2约束条件： h(X) =x1+x2－6=0显然， 与直线AB相切的点必为最优解。 右图中的D点即为最优点， 此时目 标函数值为： f(X*) =2，D点即为最优点， 此时目 标函数值为： f(X ) 2，x1*=x*2=3(X)=2x23202 36BCD但当约束条件为： h(X) =x1+x2－6≤0时， 显然， 此时的最优解为C点(x1*=x2*=2 ， f(X*) =0) ， 该点落在可行域内部， 其边界约束失去作用。 因此， 现实问题中的确存在无约束问题， 而且在求解有约束问题的解时， 我们也常常通过某种变换， 把有约束问题变成一系列无约束的问题进行求解。多变量无约束最优化方法意义在求解有约束问题的解时， 有一大类解法是通过某种变换， 把有约束问题变成一系列无约束的问题进行求解。1同时， 研究无约束优化问题的解， 也为研究约束化问题的解打下基础。在实际问题中， 某些实际问题的数学模型本身也可能是一个无约束优化问题。

３2无约束优化问题的数学模型：min(F X其中X按照是否用到函数的导数， 无约束优化算法数， 无约束优化算法主要分为两类：多变量无约束最优化方法分类)12[...]TnnxxxR??( )? ?0( )( )A和鲍威尔方法等* * ( ),? ?? ?,()()* * ()(1)mm AkAAXm XXkXk???????? ???直接法： 即不用导数信息的算法， 它只需进行函数值的计算与比较， 来确定迭代方向和步长， 如直接搜索法， 单纯形法间接法： 即使用导数信息的算法间接法： 即使用导数信息的算法， 它需要利用函数的一阶或二阶偏导数矩阵， 来确定迭代方向和步长， 如梯度法、 牛顿法和变尺度法等它需要直接法、 间接法比较： 直接法， 又称最优化搜索法， 一般情况， 利用导数迭代寻优的间接法比直接法速度快。 然而利用导数寻优常常面临两个困难：?在多变量或复杂函数中， 求导困难。?执行方法前准备工作太多。因此， 对使用者来说， 非导数型搜索法还是常用的。唯一极小(全局极小)2122212121322)(xxxxxxxxf?????多局部极小298.0?f0?f298.0?f直接法分类直接搜索法－步长加速法直接搜索法－坐标轮换法法（鲍威尔法）改进单纯形法－可变多面体法单纯形法－正多面体法直接搜索法－坐标轮换法该法主要思路是在寻优过程中中，每次先让其它变量不变直线搜索方法,无约束优化方法,约束优化方法，轮流的顺次令某一个变量变化并取函数f(X)极小点（或极大点） 。

每起始 点 为 X(0)， 先沿第1个坐标方向e1进行搜索， 得最佳步长?(0)及最优 点X(1)， 使满足：f(X(0)+?e1)=f(X(0)+?(0)e1)=f (X(1))即 X(1)= X(0)+ ?(0)e1然后以X(1)为起点，沿e2坐标搜索， 得最 优 解 X(2)，( X(1)+ ?e2)= f(X(2))，∴X(2)= X(1)+ ?(1)e2经上步可得X(n)：f(X(n － 1)+?en)=f(X(n － 1)+ ?(n －1))min即┇直到en为止1)en)=f(X(n))即 X(n)= X(n－1)+?(n－1)en‖ X(n)X(0)‖ <?1， 则停止 ， 得 最 优 解X(n)=X*，以 X(n)为 起 点（ 令X(0)= X(n)）重 新 按 上 述 步若－否 则 ，骤搜索。坐标轮换法搜索路径坐标轮换法的优缺点坐标轮换法简单、 直观， 我们可以从上图看到该法只能轮流沿n坐标方向前进， 因而效率低下， 特别是维数较高或目标函数性态不好的情况下， 收敛速度很慢。 而且对于山脊形函数或自变量间有大的交互作用不适用， 例如上图的（c） 。返回直接搜索法－步长加速法? 步长加速法(Hooke and Jeeves method) ， 也称为模式搜索法（Pattern Search method） ， 该法为改进坐标轮换法而设计， 方法搜索简单（不在某方向上取极值点） 。

? 其主要分两步进行：? 其主要分两步进行：１ 、 探测性搜索： 环绕基点的“探测搜索” ， 称I型搜索。其目的是探求一个沿各坐标方向的新点并得到一个“有前途” 的方向；２ 、 模式性搜索： 在选择的极小化方向上的“模式搜索”称II型搜索， 其目的是沿上述“有前途” 方向加速搜索。步长加速法流程先给出X的初始值X(0)及每步增量ΔX值， 然后按增量变化， 求出下一个较好点。（都以求极小点为例）先 令 x1(0)改变△ x1(0), 即 x1(1)=x1(0)+△x1(0)， 若f[X]↓ ， 则 以x1(0)+△x1(0)作为X新元素分量；否则， 令x1(1)= x1(0)－△x1(0)， 若f[X]↓就令x1(0)－△x1(0)为新元素分量；若都不能使ff[X]↓， 就仍令原X(0)为新元素。然后按同样方法把X(0)试采改变然后按同样方法把X2(0)试采改变一个△X2(0)值， 直到变化n次， 找到一个新点X(1)， 便完成了“探测搜索” 。个△X(0)值直到变化完成若模式搜索成功， 继续向前搜索； 否则，返回上一点， 缩小步长继续探测搜索。以新点为基点， 连接按此矢量方向进行模式搜索或加速移步， 模式搜索得到X(2)后， 再，进行II型探搜索， 就得到新点X(3)，若f[X(3)<[f[X(1)]]， 说明模式搜索成功， 否则失败。

)1 ()0(XX123x2X(0)?????X(1)X(2)??X(3)例求解下述无约束极值问题max f[X]=max步长加速法举例222211) 1?) 1?((1xxxx???-3-2-1?-3??? ?X(4)X(5)X(7)X(6)x1基矢量X(b)成功失败探测搜索步骤模式搜索步骤成功失败起始点选X(0)=[2.00， 2.80]T， 初始△X选为[0.60， 0.84]Tf[X(0)]=f[2.00， 2.80]=0.059该例题求解过程如右图所示。模式搜索法步长加速法算法框图初始x, α ,y(0)=x, ε>0计算f=f(x)f1=f(y(0)),i=1y(i)=y(i-1)+ αe(i)yy计算f2=f(y(i));f1?f1=f2i<n?yesyes1Noi=i+1Noy(i)=y(i-1)+ (-α)e(i)计算f2=f(y(i))f2<f1?y(i)=y(i-1)yesNo第五章 5.6 直接算法1f1<f?Noyesㄡ =y(n), y(0)=2ㄡ -xx=ㄡ ,f=f(x)y(n)=x?Noy(0)=x2步长加速法算法框图α<ε ?YesNoα=0.1 α停； x为解返回10911x2单纯形法－正多面体法正多面体法：例如右图所示， 已知两维变量函数f(X)的等位线示， 内圈比外圈函数低。

其主要思路如下：极小化f(X)时得到的正单纯形序列首先取3个点（n+1=2+1） ：X(1)， X(2)，X(3)，并计算函数值：f(X(1))， f(X(2))，f(X(3))。然后比较大小（ 这三个点称为初始正多面体 ）。f(X(3))最大， 舍去f(X(3))， 找出余下两点X(1)和X(2)的形心点，连结X(3)与形心点并延长找出X(3)关于形心点的对称点X(4)。发 现再用X(1)， X(2)和 X(4)构 成 新的正多面体，继续前述步骤，直到找出极小点为止。 上图中描绘了寻找f(X)极小 点的正多面体序列。返回改进单纯形法－可变多面体法该法在迭代过程中， 不保持每步都为正多面体， 而是根据情况改变形状， 故称可变多面体法。其算法步骤如下：Xi(k)=[xi1(k)， …， xij(k)， …， xin(k)]T，是搜索第k阶段（k=0， 1， …） 上n维欧氏空间的第i个顶点， 其目标函数为f[Xi(k)]设i=1， …， n+1首先计算n+1个顶点函数值并找出函数最大及最小的点Xh和Xl， 即：f[Xh(k)]=max{ f[X1(k)]， …， f[Xn+1(k)]}f[Xl(k)]=min{ f[X1(k)]， …， f[Xn+1(k)]}找出去掉Xh后的n个项点的形心坐标????nj=1， 2， …， n其中， j — 各坐标方向。

????????????)(hj11)(ij1knikjxxx－可变多面体法)(max) 1 (xxxy????)(max) 1 (xxxyf(y(1)) > f(y(2)) , 那么y(2)取代xmax; 否则, y(1)取代xmax。(2) 若max{f(x(i)) | x(i)≠xmax} ≥ f(y(1)) ≥ f(x)f(y( )) ≥ f(xmin) , y( )取代xmax。????ii)扩大设第k步迭代得到n+1个点：x(0),x(1),…, x(n) ， 得到x max,xmin及通过下列4步操作选新迭代点：i)反射取反射系数α >0,(单纯形法中α =1)) 1 (xy???给定扩展系数γ>1,计算。（加速）y(1) 若f(y(1)) <f(xmin) , 则: 若y(1)取代x)() 1 () 2 (xyx????)(maxxx?)减半iii) 收缩算法停机准则若f(y(1)) > f(xmax), 重新取各点， 使x(i)= x min+1?2(x(i)- xmin) 得到新单纯形。经验上：α =1, 0. 4≤β ≤0. 6, 2. 3≤γ ≤3. 0有人建议: α =1, β =0. 5，γ =2 。

?????1?niixfxfn02min)()]()([1若f(xmax) > f(y(1)) > f(x(i)) , x(i)≠xmax, 计算以y(3)取代xmax。) 1 , 0 ()() 1 () 3 (y??????xyx返回Powell法（鲍威尔）?鲍威尔方法是直接利用函数值来构造共轭方向的一种共轭方向法。 是一种不依赖于目标函数梯度的直接搜索法。 它逐步构造共轭方向并作为搜索方向， 因此Powell方法也是一种共轭方向法。 这种方法是在研究具有正定矩阵 H 的二次函数：12()F XX HXb Xc???极小化的基础上形成的。它解决了优化问题中的两大关键问题：（１ ） 在每一轮迭代完成并产生共轭方向后， 先对共轭方向的好坏进行判别， 检测它是否与其它方向线性相关。 若共轭方向不好， 则不用它作为下一轮的迭代方向， 而仍采用原来的一组迭代方向；（２ ） 若共轭方向好， 则可用它替换前一轮迭代中使函数值下降最多的一个方向， 而不一定替换第一个迭代方向。极小化的基础上形成的TT?4.5.1? ?? ?2显然， 当????21,, 2 , 1?,,,,,,, 1,;0, 01,,,,,21212121????????imjTiTnnnmhhmihIAAhhhmjijiAhhAhhAhhARRARhhh????具有以下性质具有以下性质：共轭向量组共轭向量组情况。

此， 正交是共轭的特殊是一组正交的向量。 因时，共轭的向量组。是则称若共轭的；是和则称向量若为对称正定。定义：Powell法（鲍威尔） 相关定义??0)(?, 2 , 1?0Ti,, 2 , 1?1,, 2 , 1?,22?112211????,?????mmTimmiihhhAh?hhhmihmi??m??,?, 2 , 1?????得0事实上， 由因为线性无关。： 共轭向量组性质????????????????为凸f若和有为搜索方向的搜索方法向量共轭， 则相继以设性质可知的正定性。 即??由共轭， 故有xxxfhxfxfhhhnihmimiAhhAiAhhmihnnkkkniiiiTiiii110120,min??,,,,, 2 , 1?. 2,, 2 , 1?0,, 2 , 1?0,??????????????????Powell法（鲍威尔）kHkT?kxTk+1F(xk+1)012(0,1)(1,0)(0,1)-1-1.75-0.875(2,1)(0.25,1)(0.25,0.125)70.8750.1090 .8 7 5它的基本过程如下：Powell 方法解题过程0x2 ?? ?x?2 , 2?? ,?1001,2?002121?2221方则作为搜索方向， 取取两单位标准向量例， 设PowellxeefT?????????????????????????. 0?它必然指向极小点。

作为搜索方向故若取，即：共轭的，是与可以发现，A1321301021141125. 0225xxhexx????????????????????????5 . 00 . 15 . 10 . 25 . 0?0 . 1?5 . 1?1 . 00 . 11x2x3x1?Powell搜索路径5.02.5:法解题过程如右图所示Powell法（鲍威尔）?, 0??u?? ?1iiiiPPniniunP??方向作一维极小??10:,,, 2 , 1,, 2 , 10 ,, 0 , 1 , 0 ,?值搜索， 令极值点为PP???0min沿对个单位方向并且令给定一点???? ?P??? ?2? ?3? ?P??nnnnnniiiiiiiiiiuPffuPPPPuniuuuPffu????min?????????????????0000111,1,, 2 , 1,使得求令?Powell法计算过程（鲍威尔）00Pn u0P1u1P2 u2P3u3P4 u?1 ? iPiuiP?3?nP3?n u2?nP2?n u1 ?nP1 ?n unPn u1012nPPun???1nP1001????nnnnnnnnPPu??11u11P12 u12P13u13P14 u?11 ? iP1iu1iP?13?n u31?nP12?nP12?n u11 ?nP11 ?n u1nP1n u1012nPPun??nP0u1nP1nu2nP2nu3nP3nu4 ?niP1 ?niuniP?nn u3?n?nP3nn u22?n?nPnn u1 ?nnP1 ?nn unnP??????????????1???, 2 , 1; 1,, 2 , 1,1jniuujijiPowell法（鲍威尔）?循环上面(1)--(3)， 直至P0点函数值不再减 小为止。

?当循环k次(k?n)以后， un与它前面的k-1个 向量 un-k+1,?,un-1共轭。 因此对于二次函数， 理论上只要循环n次即可求得极小值。 即具 有二次收敛性。 事实上， 因为P0和Pn是沿相同方向un求得的极小值， 所以Pn?P0与un方向共轭。n un u以n=2为例,其迭代过程为 ： ?nP10P1nP共轭方向Powell法（鲍威尔）? ? ?x??极小点为??????0 , 0 , 0?果为果为方法计算的第一循环结方法计算的第用用Powell， 搜索方向取它是一正定函数， 整体例： 设PowelleeuueueuPPfTT,,21, 1 ,2103?2021010232121322321????????,????????????????????kuk0Pk0f(Pk0)0123e1e2e3TTT????????????????????251,331,22121, 1 ,2121, 1 ,213222Powell方法第一次循环计算结果右表所示：循环结32T??????18,31,2128142?0 , 1 , 0??1 , 0 , 0?。1不能替换进行。 故的平面上以后的搜索肯定在线性相关。

，，显然索方向应是据算法， 第二循环的搜于是0311312111312110321,92,32, 0??,,92320ePPuuuuuuPPTTTT???????????????????????但是， 实际计算中对二次函数也不能保证n步内达到极小值点。因为每一循环都用Pn--P0“挤掉” u1,所以新的向量系ui(I=1,…,n)有可能线性相关，例如， 某一循环中， 如果?1?０ 则n????Powell法（鲍威尔）这样， u2, u3, …, Pn--P0是线性相关的。当发生这种情况时， 以后的搜索就在n 维的子空间中进行。最后的解就不正确。 解决的办法是Pn--P0不是挤掉u1。 而是挤掉ur, 而?r?０ 。 一般取最大下降方向（the Direction of the Largest Decrease) 。 这是因为最大下降方向ur已经在平均方向Pn-P0中得到最充分的体现。??020PPuPPniiin?平均方向?Powell法（鲍威尔）? ?? ??2f?, 0??0max1?i11000?????????f??????iinrrnnnffffPPff?PffPff令：?这一简单的思想有两种例外情况： 此时并不修改方向。

nPE P如果：因为下列两个原因之一成立：a)Pn-P0方向的下降主要不是因为?f.b)Pn-P0方向上二阶导数很大， 这表明在Pn附近有可能有极小点。? ? xf0ff?nf1fEf0P1P函数变化的影响? ?1? ?2?????????fffffffffPPnffEnEnnE?????????202000022,已不是好的方向。个方向， 因为保持原来的Powell法（鲍威尔）返回LOGO your company slogan...

（编辑：海南站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!