机械优化设计第4章 无约束优化方法Powell例题

《机械优化设计》§4-8 鲍威尔(Powell)方法¾基本思想：把n维无约束优化问题转化为n个沿坐标轴方向e 1,e 2……e n 的一维优化问题来求解。

坐标轮换法坐标轮换法：1e s x¾特点：z 方法简单，思路简明z 收敛速度太慢，效率太低鲍威尔算法的流程图{n次搜索判定并确定下轮方向组{构造新方向并一维搜索{计算条件参数准备信息判断终止条件5. 鲍威尔法的特点：（1）收敛速度快，可靠性高；（2）对非正定函数，也很有效；（3）计算步骤较复杂。

6. 鲍威尔法与坐标轮换法的主要区别：（1）每轮的搜索次数；（2）每轮的搜索方向组的构造方式。

0.01ε=的最优解。

迭代精度。

z例题（书P85）：用改进的鲍威尔法求目标函数22121212(,)10(5)()f x x x x x x =+−+−解：（一）第1轮迭代计算1）从出发，沿e 1方向进行一维搜索：(1)1100/22 4.5455α==得：(1)1[4.54550]T=x 初始点(1)0[00]T=x 12[10];[01]T T ==e e (1)(1)1120(5)20f ααα′=−+=min :(1)1()f x (1)0x (1)(1)(1)1011α=+x x e (1)2(1)2(1)11110(5)()()f ααα=−+=选取基本搜索方向组：(1)(1)1101;000αα⎡⎤⎡⎤⎡⎤=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦2）从出发，沿e 2方向进行一维搜索：(1)20.826α=得：(1)2[4.54550.826]T=x (1)(1)2220(0.455)2( 4.545)0f ααα′=−+−=min :(1)(1)2(1)2(1)2222()10(4.5455)(4.545)()f f ααα=+−+−=x (1)1x (1)(1)(1)(1)21222(1)24.5454.5450;01ααα⎡⎤⎡⎤⎡⎤=+=+=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦xx e (1)2()15.215f =x (1)(1)212()()22.72715.2157.512f f Δ=−=−=x x 3）计算函数值以及下降量(1)0()250f =x (1)1()22.727f =x (1)(1)101()()25022.727227.27f f Δ=−=−=x x (1)()if x i Δ4）求最大下降量121max{,}227.723m Δ=ΔΔ=Δ=mΔ5）计算映射点及其函数值(1)()f x (1)x (1)(1)(1)24.545509.09220.82640 1.653⎡⎤⎡⎤⎡⎤=−=−=⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦x x x (1)00()250F f ==x (1)()385.239f =x 6）计算判别条件式(1)22()15.215F f ==x (1)3()385.239F f ==x 30?F F <故不满足鲍威尔条件，则下一轮仍用原方向组。

数学与计算科学学院实验报告
实验项目名称powell法求解无约束优化问题
所属课程名称最优化方法
实验类型算法编程
实验日期
班级
学号
姓名
成绩
附录1：源程序
附录2：实验报告填写说明
1．实验项目名称：要求与实验教学大纲一致。

2．实验目的：目的要明确，要抓住重点，符合实验教学大纲要求。

3．实验原理：简要说明本实验项目所涉及的理论知识。

4．实验环境：实验用的软、硬件环境。

5．实验方案（思路、步骤和方法等）：这是实验报告极其重要的内容。

概括整个实验过程。

对于验证性实验，要写明依据何种原理、操作方法进行实验，要写明需要经过哪几个步骤来实现其操作。

对于设计性和综合性实验，在上述内容基础上还应该画出流程图、设计思路和设计方法，再配以相应的文字说明。

对于创新性实验，还应注明其创新点、特色。

6．实验过程（实验中涉及的记录、数据、分析）：写明具体实验方案的具体实施步骤，包括实验过程中的记录、数据和相应的分析。

7．实验结论（结果）：根据实验过程中得到的结果，做出结论。

8．实验小结：本次实验心得体会、思考和建议。

9．指导教师评语及成绩：指导教师依据学生的实际报告内容，给出本次实验报告的评价。

内容•单变量优化计算方法；•多变量优化计算的非梯度方法（坐标轮换法；powell法；单纯形法；）•多变量优化计算的梯度法（梯度法；共轭梯度法；牛顿迭代法；变尺度法）4.1 引言nRxxf)(min一、无约束问题的一般形式：求其最优解X*和f(X*)的方法，称为无约束优化计算方法。

4、无约束优化计算方法从第一章列举的机械设计问题，大多数实际问题是约束优化问题。

约束优化问题的求解——转化为一系列的无约束优化问题实现的。

因此，无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。

无约束优化问题的极值条件()*0f x ∇=解析法数值法数学模型复杂时不便求解可以处理复杂函数及没有数学表达式的优化设计问题1k k kk xx a d +=+搜索方向问题是无约束优化方法的关键。

二、无约束优化问题的分类：一般按照是否求梯度分类•梯度法：要计算目标函数一、二阶导数的方法；•非梯度法:仅计算目标函数的值，不必计算其导数两类方法均为迭代方法，只是迭代的格式及其判的方法；定条件有差异。

三、无约束优化问题意义：•约束优化问题可以转化为无约束优化问题求解；•有些约束优化方法，也可以借助于无约束优化问题的策略来构造；4.2 一维搜索优化计算方法一维搜索优化方法（亦称一维搜索法）是指一元函数求极值问题的数值迭代法。

它是优化方法中最简单、最基本的方法。

虽然，在实际优化问题中，设计变量仅有一个的情况并不多，但在求多维优化问题时，很多算法最终都要归结为反复进行一维问题的求解。

因此，一维搜索方法的效率和稳定性对最优化问题整个算法的求解速度和可靠性影响较大。

4.2 一维搜索优化计算方法一、一维搜索优化问题意义及迭代定义：求一维目标函数的极小点和极小值的数值迭代方法称为一维搜索方法。

意义：不仅解决一维目标函数的优化问题，而且更常用于多维优化问题中在既定方向上最优步长的搜索。

在既定的X K 和S K 下寻求最优步长αK ，使迭代产生的新点X K+1的函数值最小，故实质求单变量α，使：()()()()()k k x f sx f k αα+=+min 11k k k k x x a d +=+采用数学规划法求函数极值点的迭代计算：K+1次迭代的搜索方向搜索的最佳步长因子当搜索方向给定，求最佳步长k a kd 就是求一元函数的极值。

第四章 无约束优化方法——最速下降法，牛顿型方法概述在求解目标函数的极小值的过程中，假如对设计变量的取值X 围不加限制，如此称这种最优化问题为无约束优化问题。

尽管对于机械的优化设计问题，多数是有约束的，无约束最优化方法仍然是最优化设计的根本组成局部。

因为约束最优化问题可以通过对约束条件的处理，转化为无约束最优化问题来求解。

为什么要研究无约束优化问题?〔1〕有些实际问题，其数学模型本身就是一个无约束优化问题。

〔2〕通过熟悉它的解法可以为研究约束优化问题打下良好的根底。

〔3〕约束优化问题的求解可以通过一系列无约束优化方法来达到。

所以无约束优化问题的解法是优化设计方法的根本组成局部，也是优化方法的根底。

根据构成搜索方向所使用的信息性质的不同，无约束优化方法可以分为两类。

一：间接法——要使用导数的无约束优化方法，如梯度法、〔阻尼〕牛顿法、变尺度法、共轭梯度法等。

二：直接法——只利用目标函数值的无约束优化问题，如坐标轮换法、鲍威尔法单纯形法等。

无约束优化问题的一般形式可描述为：求n 维设计变量 []12Tn n X x x x R =∈ 使目标函数()min f X ⇒目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差异。

无约束优化问题的求解：1、解析法可以利用无约束优化问题的极值条件求得。

即将求目标函数的极值问题变成求方程0)(min *=X f的解。

也就是求Ｘ＊使其满足解上述方程组，求得驻点后，再根据极值点所需满足的充分条件来判定是否为极小值点。

但上式是一个含有ｎ个未知量，ｎ个方程的方程组，在实际问题中一般是非线性的，很难用解析法求解，要用数值计算的方法。

由第二章的讲述我们知道，优化问题的一般解法是数值迭代的方法。

因此，与其用数值方法求解非线性方程组，还不如用数值迭代的方法直接求解无约束极值问题。

2、数值方法 数值迭代法的根本思想是从一个初始点)0(X 出发，按照一个可行的搜索方向)0(d 搜索，确定最优的步长0α使函数值沿)0(d 方向下降最大，得到)1(X 点。

用Powell法编程求解无约束优化问题题目：用Powell法编程求解无约束优化问题min ，要求：（1）程序流程图（2）源程序清单（3）运行结果求解过程：流程图....程序清单源程序由以下几个部分组成：（1）目标函数程序清单：建立函数f（）以f.m存盘%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%函数名：f（），参数2个%函数作用：带入参数，求解目标函数f（）%可以更改目标函数为任意二维函数，结果由m返回%作者：WYH 学号：xxxxxxxx %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function m=f(x1,x2)m=x1^2+x2^2-x1*x2-10*x1-4*x2+60; %目标函数（2）关于α的目标函数清单：建立函数y（）以y.m存盘%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%函数名：y（），参数5个%函数作用：带入参数，求解关于α的一元函数y（α），根据原目标函数更改此函数，%其中原目标函数变量X1＝x1+alpha*d1，X2＝x2+alpha*d2结果由m返回%作者：WYH 学号：xxxxxxxx %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function m=y(x1,x2,d1,d2,alpha)m=(x1+alpha*d1)^2+(x2+alpha*d2)^2-(x1+alpha*d1)*(x2+alpha*d2)-10*(x1+alpha*d1)-4*(x2+ alpha*d2)+60; %含α的目标函数，其形式与原目标函数f（x）＝x1^2+x2^2-x1*x2-10*x1-4*x2+60一致（3）外推法求解一元函数最小值区间：建立函数section（）以sextion.m存盘%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%函数名：section（），参数4个%函数作用：利用外推法求解关于α的函数y（α）的极小点α*所在的区间【a，b】，%结果由a、b返回%作者：WYH 学号：xxxxxxxx %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function [a,b]=section(x1,x2,d1,d2)x11=x1; %给出起始点坐标x1，x2和搜索方向d1，d2x22=x2;d11=d1;d22=d2;h0=1; %初始化h=h0;alpha1=0;y1=y(x11,x22,d11,d22,alpha1); %代入α1求解y1alpha2=h;y2=y(x11,x22,d11,d22,alpha2);t=0;if y2>y1h=-h;alpha3=alpha1;y3=y1;t=1; %如果y2>y1，则改变搜索方向endwhile(1)if t==1alpha1=alpha2;y1=y2; %实现交换alpha2=alpha3;y2=y3;else t=1;endalpha3=alpha2+h;y3=y(x11,x22,d11,d22,alpha3);if y3<y2h=2*h; %改变搜索步长，将其加倍elsebreak;endendif alpha1>alpha3tem=alpha1;alpha1=alpha3;alpha3=tem; %比较大小，保证输出区间为【a，b】a=alpha1;b=alpha3;else a=alpha1;b=alpha3;end（1）黄金分割法求解区间已知的一元函数最小值：建立函数ALPHA（）以ALPHA.m 存盘%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%函数名：ALPHA（），参数6个%函数作用：利用黄金分割法求解关于α的函数y（α）的极小点α*，已知α所在的%区间【A，B】，结果由α返回%作者：WYH 学号：xxxxxxxx %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% function alpha=ALPHA(x1,x2,d1,d2,A,B)x11=x1;x22=x2; %给出起始点坐标x1，x2和搜索方向d1，d2d11=d1;d22=d2;a=A;b=B; %获取区间epsilon=0.000001; %初始化，给定进度r=0.618;alpha1=b-r*(b-a);y1=y(x11,x22,d11,d22,alpha1); %代入α1求解y1alpha2=a+r*(b-a);y2=y(x11,x22,d11,d22,alpha2);while(1)if y1>=y2 %根据区间消去法原理缩短搜索空间a=alpha1;alpha1=alpha2;alpha2=a+r*(b-a);y2=y(x11,x22,d11,d22,alpha2);elseb=alpha2;alpha2=alpha1;y2=y1;alpha1=b-r*(b-a);y1=y(x11,x22,d11,d22,alpha1);endif abs(b-a)<epsilon & abs(y2-y1)<epsilon %判断是否满足进度要求break; %满足进度要求则退出循环迭代过程endendalpha=0.5*(a+b); %返回值（2）主程序，建立Powell.m存盘，运行程序%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%程序名：powell法求解二维函数的极小值，主程序%程序作用：根据无约束优化方法中的Powell法原理，在二维空间求解f（x1，x2）的%最小点，结果返回最小点变量坐标（x1，x2）及最小值fmin%作者：WYH 学号：xxxxxxxx %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%clear allclck=0;n=2;x=[0;0;];ff(1)=f(x(1),x(2)); %初始化epsilon=0.00001;d=[1;0;0;1;];while(1)x00=[x(1);x(2);];for i=1:n[a(i),b(i)]=section(x(2*i-1),x(2*i),d(2*i-1),d(2*i)); %调用section（）函数求解一元函数有y （α）最小值时的区间alpha(i)=ALPHA(x(2*i-1),x(2*i),d(2*i-1),d(2*i),a(i),b(i)); %调用ALPHA（）函数求解y（α）最小值点α*x(2*i+1)=x(2*i-1)+alpha(i)*d(2*i-1); %沿di方向搜索x(2*i+2)=x(2*i)+alpha(i)*d(2*i);ff(i+1)=f(x(2*i+1),x(2*i+2)); %搜索到的点对应的函数值endDelta(i)=ff(i)-ff(i+1);enddelta=max(Delta); %求出函数值之差的最大值for i=1:n %寻找函数值之差最大值的下标if delta==Delta(i)m=i;break;endendd(2*n+1)=x(2*n+1)-x(1); %求出反射点搜索方向dn+1d(2*n+2)=x(2*n+2)-x(2);x(2*n+3)=2*x(2*n+1)-x(1); %搜索到反射点Xn+1x(2*n+4)=2*x(2*n+2)-x(2);ff(n+2)=f(x(2*n+3),x(2*n+4)); %反射点所对应的函数值f0=ff(1);f2=ff(n+1);f3=ff(n+2);k=k+1; %记录迭代次数R(k,:)=[k,x',d',ff]; %保存迭代过程的中间运算结果if f3<f0 & (f0-2*f2+f3)*(f0-f2-delta)^2<0.5*delta*(f0-f3)^2 %判断是否需要对原方向组进行替换[a(n+1),b(n+1)]=section(x(2*n+1),x(2*n+2),d(2*n+1),d(2*n+2));alpha(n+1)=ALPHA(x(2*n+1),x(2*n+2),d(2*n+1),d(2*n+2),a(n+1),b(n+1));x(1)=x(2*n+1)+alpha(n+1)*d(2*n+1); %沿反射方向进行搜索，将搜索结果作为下一轮迭代的始点x(2)=x(2*n+2)+alpha(n+1)*d(2*n+2);for i=m:n %根据函数值之差最大值的下标值m，对原方向组进行替换d(2*i-1)=d(2*i+1);d(2*i)=d(2*i+2);endelseif f2<f3 %如果不需要对原方向组进行替换，选取终点及反射点中函数值较小者作为下一轮迭代的始点x(1)=x(2*n+1);x(2)=x(2*n+2);elsex(1)=x(2*n+3);x(2)=x(2*n+4);endendRR(k,:)=alpha; %保存迭代过程的中间运算结果ff(1)=f(x(1),x(2)); %计算下一轮迭代过程需要的f0值if (((x(2*n+1)-x00(1))^2+(x(2*n+2)-x00(2))^2)^(1/2))<epsilon %判断是否满足精度要求break; %满足进度要求则退出循环迭代过程endendxx=[x(1);x(2)]fmin=f(x(1),x(2)) %显示最小值及其所对应的坐标二、运行结果xx =8.00006.0000fmin =8.0000。