最优化方法的应用资料.docx
《最优化方法的应用资料.docx》由会员分享，可在线阅读，更多相关《最优化方法的应用资料.docx（12页珍藏版）》请在冰点文库上搜索。
最优化方法的应用资料
最优化方法
姓名张炯
学号201200144423
一、一维搜索方法的分类
为了每次缩短区间，只需要在区间内再插入一点并计算其函数值。
然而，对于插入点的位置，是可以用不同的方法来确定的。
•黄金分割法
•一类称作解析法或函数逼近法：
构造一个插值函数来逼近原来函数，用插值函数的极小点作为区间的插入点
–牛顿法、二次插值法等
黄金分割法
黄金分割法要求插入点1、2的位置相对于原区间[a,b]的两端点具有对称性，即
黄金分割法的搜索过程
2出初始搜索区间[a,b]及收敛精度，将赋以0.618
⑵按前页中坐标点比例公式计算1和2，并计算其对应的函数值f
（1）和f
（2）。
⑶比较函数值，利用进退法缩短搜索区间
⑷检查区间是否缩短到足够小和函数值是否收敛到足够近，如果条件不满足则返回到步骤⑵
⑸如果条件满足则取最后两试验点的平均值作为极小点的数值近似值
黄金分割法程序框图
牛顿法
对于一维搜索函数，假定已给出极小点的一个较好的近似点a0，因为一个连续可微的函数在极小点附近与一个二次函数很接近，所以可以在a0点附近用一个二次函数来逼近函数，即在点a0将f（a）进行泰勒展开，并保留到二次项，有
然后以二次函数的极小点作为极小点的一个新近似点，根据极值必要条件
得
得
牛顿法的计算步骤
⑴给定初始点a0，控制误差，令k=0
⑵计算f（x）在ak点的一阶和二阶导数
⑶利用牛顿法迭代公式求ak+1
⑷若|ak+1-ak|≤，则求得近似解a*=ak+1，停止计算，否则作第⑸步
⑸令k=k+1，然后转第⑵步
牛顿法的优缺点
最大优点是收敛速度快
缺点
每一点处都要计算函数的导数和二阶导数，因而增加了每次迭代的工作量
用数值微分代替二阶导数时，舍入误差会影响牛顿法的收敛速度，当二阶导数很小时问题更严重
牛顿法要求初始点选得比较好，即不能离极小点太远，否则在可能使极小化序列发散或收敛到非极小点
二次插值法
二次插值法又称抛物线法，它的基本思路是：
在寻求函数f（α）极小点的搜索区间内，取三个点的函数值来构造一个二次插值多项式p（α）,用它的极小点（第四个点）近似地作为原目标函数的极小点。
若近似程度不满足精度要求时，可以反复使用此法，从四个点中选取三个点，使函数值呈现“高-低-高”变化的前提下逐渐的缩短搜索区间，二次插值多项式的极小点就逼近原目标函数的极小点。
二次插值法区间缩短的4种情况
二次插值法的流程图
二、牛顿迭代法详解
牛顿迭代法（Newton'smethod）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphsonmethod），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
牛顿迭代法（Newton'smethod）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphsonmethod），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。
方法使用函数f（x）的泰勒级数的前面几项来寻找方程f（x）=0的根。
牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f（x）=0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。
另外该方法广泛用于计算机编程中。
设r是的根，选取作为r的初始近似值，过点做曲线的切线L，L的方程为，求出L与x轴交点的横坐标，称x1为r的一次近似值。
过点做曲线的切线，并求该切线与x轴交点的横坐标，称为r的二次近似值。
重复以上过程，得r的近似值序列，其中，称为r的次近似值，上式称为牛顿迭代公式。
用牛顿迭代法解非线性方程，是把非线性方程线性化的一种近似方法。
把在点的某邻域内展开成泰勒级数，取其线性部分（即泰勒展开的前两项），并令其等于0，即，以此作为非线性方程的近似方程，若，则其解为，这样，得到牛顿迭代法的一个迭代关系式：
。
已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。
并且，如果不为0,那么牛顿法将具有平方收敛的性能.粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。
[1]
军人在进攻时常采用交替掩护进攻的方式，若在数轴上的点表示A，B两人的位置，规定在前面的数大于后面的数，则是A>B，B>A交替出现。
但现在假设军中有一个胆小鬼，同时大家又都很照顾他，每次冲锋都是让他跟在后面，每当前面的人占据一个新的位置，就把位置交给他，然后其他人再往前占领新的位置。
也就是A始终在B的前面，A向前迈进，B跟上，A把自己的位置交给B（即执行B=A），然后A再前进占领新的位置，B再跟上，直到占领所有的阵地，前进结束。
像这种两个数一前一后逐步向某个位置逼近的方法称为迭代法。
迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法（或者称为一次解法），即一次性解决问题。
迭代算法是用计算机解决问题的一种基本方法。
它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值。
利用迭代算法解决问题，需要做好以下三个方面的工作：
一、确定迭代变量
在可以用迭代算法解决的问题中，至少存在一个可直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。
二、建立迭代关系式
所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式（或关系）。
迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。
三、对迭代过程进行控制
在什么时候结束迭代过程？
这是编写迭代程序必须考虑的问题。
不能让迭代过程无休止地执行下去。
迭代过程的控制通常可分为两种情况：
一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。
对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析得出可用来结束迭代过程的条件。
关于牛顿迭代法有一个很典型的例子是斐波那契（Fibonacci）数列。
斐波那契数列为：
0、1、1、2、3、5、8、13、21、…，即fib⑴=0;fib⑵=1;fib（n）=fib（n-1）+fib（n-2）（当n>2时）。
在n>2时，fib（n）总可以由fib（n-1）和fib（n-2）得到，由旧值递推出新值，这是一个典型的迭代关系，所以我们可以考虑迭代算法。
intFib（intn）//斐波那契（Fibonacci）数列
{
if（n<1）/*预防错误*/
return0;
if（n==1||n==2）/*特殊值，无需迭代*/
return1;
intf1=1,f2=1,fn;/*迭代变量*/
inti;
for（i=3;i<=n;++i）/*用i的值来限制迭代的次数*/
{
fn=f1+f2;/*迭代关系式*/
f1=f2;//f1和f2迭代前进，其中f2在f1的前面
f2=fn;
}
returnfn;
}
三、牛顿迭代法的程序实现
牛顿迭代法Matlab程序（带下山因子）
本文程序可用于求解线性和非线性方程组，在使用牛顿迭代法的同时，加入了下山因子，加入下山因子后，对于初值的选取更为宽泛。
使用方法：
请将本文function所定义的函数存为m文件，将matlab路径改为存储newton函数的路径，然后参照本文例子的格式定义变量、表达式、初值、收敛阈值、迭代次数后，输入X=newton（f,x,x0,esp,N）
即可求解。
%%%%%%%%%%%%%%%%%%%%
例子
symsx1x2x3%定义变量名称
f1=x1+x2+x3+3;
f2=2*x1-x2-x3;
f3=x1+2*x2-2*x3-3;%定义方程表达式（方程全都移到等号左边的表达式）
f=[f1;f2;f3];
x=[x1;x2;x3];
x0=[0;0;0];%设定初值
esp=[0.00001;0.00001;0.00001];%阈值
N=1000;%迭代次数
X=newton（f,x,x0,esp,N）%求解
%%%%真值为-10-2
%%%%%%%%%%%%%%%%%%%%
functionx1=newton（f,x,x0,esp,N）%此函数用于解非线性方程，方法为牛顿下山法。
R=jacobian（f,x）;
ph=size（f,1）;
ty（1:
ph,1）=1;
coo=1;
whileabs（coo-1）<1e-6%这代表coo==1
coo=0;
R1=subs（R,x,x0）;%%%
f1=subs（f,x,x0）;
x1=x0-ty.*（R1\f1）;
f11=subs（f,x,x1）;
f12=double（f1）;
f112=double（f11）;
fori=1:
size（f12,1）;
j=i;
clc
j
ifabs（f112（i））>abs（f12（i））
ty（i）=ty（i）/2;
coo=1;
end
end
end
fori=1:
N
clc
i
R1=subs（R,x,x0）;%%%
f1=subs（f,x,x0）;
x1=x0-ty.*（R1\f1）;
xx=abs（x1-x0）;
ifxxbreak
else
x0=x1;
end
end
升级会员 