第三章:一维优化方法总结
1.一维优化方法介绍
求解以为目标函数f (x )最优解的过程,称为一维优化,所使用的方法称为一维优化方法。一维优化方法是优化方法中最简单、最基本的优化方法。他不仅用来解决一维目标函数的求最优问题,而且常用于多维优化问题在既定方向上寻求最优步长的一维搜索。
对于任一次迭代计算,总是希望从已知的点()k x 出发,沿给定的方向()k s 搜索该方向上到目标函数值最小的点(1)k +x 。这种在确定的搜索方向()k s 上按步长因子
()k α迭代使得目标函数在该方向上达到极小值的过程称为一维搜索优化计算方
法。
一维搜索最优化方法一般需要分两步进行:第一步是在()k s 方向上确定使得目标函数值取得最小值的步长因子()k α所在的区间;第二步是采用不同方法利用步长因子()k α求得近似解。
2.搜索区间的确定及matlab 编程
所谓搜索区间就是沿给定的搜索方向()k s 上找出一个单峰区间12[,]αα,即在该区间内目标函数值的变化只有一个峰值。本文选用进退法进行区间确定。这里直接以一维函数为例。设函数为()y f x =,给定初始点1x ,选定恰当的步长为0h ,求其最小点*x 。进退法分为三步:试探搜索、前进搜索和后退搜索。
第一步:试探搜索
由于最小点*x 的位置是未知的,所以首先要试探最小点*x 位于初始点1x 的左方还是右方,然后再确定包含*x 在内的搜索区间[,]a b 。
由初始点1x 沿Ox 轴正向到2x 点,210x x h =+,分别计算两点的函数值11()y f x =,
22()y f x =并比较1y 和2y 值的大小,可分为两种情况:
(1)若21y y <,则极小点必在点右方,应继续前进搜索;
(2)若21y y >,则极小点必在1x 点左方,应反向,即作后退搜索。第二步:前进搜索
由探索后的2x 点,沿Ox 正向继续前进搜索。令02h h =,取得前进方向的第三个点32x x h =+,对应的函数值33()y f x =,比较后两个点的函数值,有如下两种情况:
(1)若23y y <,则三个点123x x x 、、的函数值的关系为123y y y ><。此时函数()f x 在13[,]x x 区间内必有极小点,于是令1a x =,3b x =从而构成了搜索区间[,]a b 。
(2)若23y y >,则应该继续向前搜索,令12122323,,,x x y y x x y y ====,再将步长倍增,即2h h =,构成新点并计算其函数值3233,x x h y x =+=。比较2y 和3y 的值,若有23y y >则转(2),直到出现23y y <成立,转(1),确定搜索区间。
第三步:后退搜索
此时,需沿Ox 负方向搜索,因此令00h h =?,并将1x 和2x 点的位置调换,即令
3131
12122323
,,,x x y y x x y y x x y y ======进行这样的处理以后,后面的步骤和前进搜索的处理完全相同,只是最后确定搜索区间时,令31,a x b x ==。
Matlab 程序如下:
function [mina,maxb]=funab(f,xzero,hzero,eps)format long ;if nargin==3
eps=1e-6;end
x1=xzero;k=0;
h=hzero;while 1
x4=x1+h;k=k+1;
f4=subs(f,findsym(f),x4);
f1=subs(f,findsym(f),x1);if f4 x2=x1;x1=x4;f2=f1;f1=f4;h=2*h;else if k==1 h=-h;x2=x4;f2=f4;else x3=x2;x2=x1;x1=x4;break ;end end end mina=min(x1,x3);maxb=x1+x3-mina;format short ; 3.黄金分割法求极值的基本原理及matlab 编程 黄金分割法也称0.618法。本方法是通过对分割点函数值进行比较来逐次缩短区间的,属于应用序列消去原理的直接探索法。设有目标函数()f x ,给定初始搜索区间[,]a b ,收敛精度为ε。 首先,在初始搜索区间内取两个点1x 与2x ,12x x <且在区间内对称位置,两点对应的函数值分别为11()y f x =和22()y f x =,比较1y 与2y 的大小,有下面两种情况: (1)若有12y y <,极小点必在区间2[,]a x 内,此时令2b x =,实现区间的一次缩短; (2)若有12y y ≥,极小点必在区间1[,]x b 内,此时可令1a x =,缩短后的新区间为1[,]x b 。 经过多次用黄金分割法进行一维优化搜索,当满足迭代精度时即可停止计算,取最终收缩区间的中点为近似最优点,最优解为 ()()*0.5()*(*) k k x a b f f x ?=+? =?Matlab 程序如下: function [x,fval,xzero]=fun618(a,b)xzero=0; while abs(b-a)>1e-4 xzero=xzero+1; lambda=a+0.382*(b-a);mid=a+0.618*(b-a);[dy,f1]=funx(lambda);[dy,f2]=funx(mid);if f1>f2 a=lambda; disp([made the new search area is:['num2str(a)','num2str(b) '].']) else b=mid; disp(['the number'num2str(xzero)'iteration made the new search area is:['num2str(a)','num2str(b)'].']) end end x=(a+b)/2; [dy,fval]=funx(x); 4.算例 计算)2()(+=x x x f 的极小点。解:首先在matlab 中输入:>>syms x;>>f=x*(x+2);>>[a,b]=funab(f,0,1);得到结果:>>a a =-3>>b b=0 因此获得搜索区间[-3,0]。 然后进行黄金分割法计算。 编写程序: function[dy,fval]=funx(x) fval=x*(x+2); dy=2*x+2; end 然后输入: [x,fval,xzero]=fun618(-3,0) 得到如下结果: >>[x,fval,xzero]=fun618(-3,0) the number1iteration made the new search area is:[-1.854,0]. the number2iteration made the new search area is:[-1.854,-0.70823]. the number3iteration made the new search area is:[-1.4163,-0.70823]. the number4iteration made the new search area is:[-1.1458,-0.70823]. the number5iteration made the new search area is:[-1.1458,-0.87539]. the number6iteration made the new search area is:[-1.0425,-0.87539]. the number7iteration made the new search area is:[-1.0425,-0.93923]. the number8iteration made the new search area is:[-1.0425,-0.97869]. the number9iteration made the new search area is:[-1.0181,-0.97869]. the number10iteration made the new search area is:[-1.0181,-0.99376]. the number11iteration made the new search area is:[-1.0088,-0.99376]. the number12iteration made the new search area is:[-1.0031,-0.99376]. the number13iteration made the new search area is:[-1.0031,-0.99731]. the number14iteration made the new search area is:[-1.0009,-0.99731]. the number15iteration made the new search area is:[-1.0009,-0.99867]. the number16iteration made the new search area is:[-1.0009,-0.99951]. the number17iteration made the new search area is:[-1.0004,-0.99951]. the number18iteration made the new search area is:[-1.0004,-0.99983]. the number19iteration made the new search area is:[-1.0002,-0.99983]. the number20iteration made the new search area is:[-1.0002,-0.99996]. the number21iteration made the new search area is:[-1.0001,-0.99996]. the number22iteration made the new search area is:[-1,-0.99996]. x= -1.0000 fval= -1.0000 xzero = 22 即经过22次迭代,得到极小值点-1.0000。极小值为-1.0000。 5.对算例提出的问题 通过手算该算例,很容易得到)2()(+=x x x f 的极小值为(-1,-1)。但是通过迭代过程我们可以看到matlab 在接近极小值点附近时由于设置的精度过高(410?=ε)导致其需要反复迭代多次才能得到相应结果。因此我认为在日常计算应用时因选用合适精度才能更有效率地得到适当的近似解。 另外,在编制程序时还需要手动求得原函数的一阶导数并输入进funx (x )函数之中,比较麻烦。我们可以利用dy=diff(f,x)函数来进行求解。如下所示: >>syms dy f x;>>f=x*(x+2);>>dy=diff(f,x);>>dy dy = 2*x +2 一维优化方法 最优化设计数学模型中的基本概念: 1、设计变量 在机械设计中,区别不同的设计方案,通常是以一组取值不同的参数来表示。这些参 数可以是表示构件形状、大小、位置等的几何量,也可以是表示构件质量、速度、加速度、力、力矩等的物理量。在构成一项设计方案的全部参数中,可能有一部分参数根据实际情 况预先确定了数值,它们在优化设计过程中始终保持不变,这样的参数称为给定参数(或 叫预定参数)或设计常数。另一部分参数则是需要优选的参数,它们的数值在优化设计过 程中则是需要优选的参数,它们的数值在优化计算过程中是变化的,这类参数称为设计变量,它相当于数学上的独立自变量。一个优化问题如果有n个设计变量,而每个设计变量 用xi(i=1,2, ,n)表示,则可以把n个设计变量按一定的次序排列起来组成一个列阵或行 阵的转置,即写成 ??x1? x=?x? 2?=[x1,x2, ,xT ?? ?n] ?x? n? 我们把x定义为n维欧式空间的一个列向量,设计变量x1,x2, ,xn为向量x的n个 分量。以设计变量x1,x2, ,xn为坐标轴展成的空间称为n维欧式空间,用Rn表示。该空 间包含了该项设计所有可能的设计方案,且每一个设计方案就对应着设计空间上的一个设 计向量或者说一个设计点x。 2、目标函数 优化设计是在多种因素下欲寻求使设计者员满意、且适宜的一组参数。“最满意”、“最适宜”是针对某具体的设计问题,人们所追求的某一特定目标而言。在机械设计中, 人们总希望所设计的产品具有最好的使用性能、体积小、结构紧凑、重量最轻和最少的制 造成本以及最多的经济效益,即有关性能指标和经济指标方面最好。 在优化设计中,一般将所追求的目标(最优指标)用设计变量的函数形式表达,称该函 数为优化设计的目标函数。目标函数的值是评价设计方案优劣程度的标准,也可称为准则 函数。建立这个函数的过程称为建立目标函数。一般的表达式为 加步探索法 #include 对分法 #include 最优化方法结课作业 年级数学121班 学号201200144209 姓名李强 1、几种方法比较 无约束优化:不对定义域或值域做任何限制的情况下,求解目标函数的最小值。这是因为实际应用中,许多情形被抽象为函数形式后均为凸函数,对于凸函数来说局部最小值点即为全局最小值点,因此只要能求得这类函数的一个最小值点,该点一定为全局最小值。(直接法:又称数值方法,它只需计算目标函数驻点的函数数值,而不是求其倒数,如坐标轮换法,单纯型法等。间接法:又称解析法,是应用数学极值理论的解析方法。首先计算出目标函数的一阶或一阶、二阶导数,然后根据梯度及海赛矩阵提供的信息,构造何种算法,从而间接地求出目标函数的最优解,如牛顿法、最速下降法共轭梯度法及变尺度法。)在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。 一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。 一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。 在多变量函数的最优化中,迭代格式Xk+1=Xk+akdk其关键就是构造搜索方向dk和步长因子ak 设Φ(a)=f(xk+adk) 这样从凡出发,沿搜索方向dk,确定步长因子ak,使Φ(a)<Φ(0)的问题就是关于步长因子a 的一维搜索问题。其主要结构可作如下概括:首先确定包含问题最优解的搜索区间,然后采用某种分割技术或插值方法缩小这个区间,进行搜索求解。 一维搜索通常分为精确的和不精确的两类。如果求得ak使目标函数沿方向dk达到极小,即使得f (xk+akdk)=min f (xk+ adk) ( a>0)则称这样的一维搜索为最优一维搜索,或精确一维搜索,ak叫最优步长因子;如果选取ak使目标函数f得到可接受的下降量,即使得下降量f (xk)一f (xk+akdk)>0是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维搜索。由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的一维搜索需要付出较高的代价,而对加速收敛作用不大,因此花费计算量 无约束优化:不对定义域或值域做任何限制的情况下,求解目标函数的最小值。 这是因为实际应用中,许多情形被抽象为函数形式后均为凸函数,对于凸函数来说局部最小值点即为全局最小值点,因此只要能求得这类函数的一个最小值点,该点一定为全局最小值。 (直接法:又称数值方法,它只需计算目标函数驻点的函数数值,而不是求其倒数,如坐标轮换法,单纯型法等。 间接法:又称解析法,是应用数学极值理论的解析方法。首先计算出目标函数的一阶或一阶、二阶导数,然后根据梯度及海赛矩阵提供的信息,构造何种算法,从而间接地求出目标函数的最优解,如牛顿法、最速下降法共轭梯度法及变尺度法。) 在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。 一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。 一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。 在多变量函数的最优化中,迭代格式X k+1=X k+a k d k其关键就是构造搜索方向d k和步长因子a k 设Φ(a)=f(x k+ad k) 这样从凡出发,沿搜索方向d k,确定步长因子a k,使Φ(a)<Φ(0)的问题就是关于步长因子a的一维搜索问题。其主要结构可作如下概括:首先确定包含问题最优解的搜索区间,然后采用某种分割技术或插值方法缩小这个区间,进行搜索求解。 一维搜索通常分为精确的和不精确的两类。如果求得a k使目标函数沿方向d k达到 极小,即使得f (x k+a k d k)=min f (x k+ ad k) ( a>0) 则称这样的一维搜索为最优一维搜索,或精确一维搜索,a k叫最优步长因子; 如果选取a k使目标函数f得到可接受的下降量,即使得下降量f (x k)一f (x k+a k d k)>0是用 户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维 搜索。 由于在实际计算中,一般做不到精确的一维搜索,实际上也没有必要做到这一点,因为精确的 一维搜索方法应用比较 一、黄金分割法 (1)黄金分割法的起源 黄金分割在文艺复兴前后,经过阿拉伯人传入欧洲,受到了欧洲人的欢迎,他们称之为"金法",17世纪欧洲的一位数学家,甚至称它为"各种算法中最可宝贵的算法"。这种算法在印度称之为"三率法"或"三数法则",也就是我们现在常说的比例方法。 其实有关"黄金分割",我国也有记载。虽然没有古希腊的早,但它是我国古代数学家独立创造的,后来传入了印度。经考证。欧洲的比例算法是源于我国而经过印度由阿拉伯传入欧洲的,而不是直接从古希腊传入的。 因为它在造型艺术中具有美学价值,在工艺美术和日用品的长宽设计中,采用这一比值能够引起人们的美感,在实际生活中的应用也非常广泛,建筑物中某些线段的比就科学采用了黄金分割,舞台上的报幕员并不是站在舞台的正中央,而是偏在台上一侧,以站在舞台长度的黄金分割点的位置最美观,声音传播的最好。就连植物界也有采用黄金分割的地方,如果从一棵嫩枝的顶端向下看,就会看到叶子是按照黄金分割的规律排列着的。在很多科学实验中,选取方案常用一种0.618法,即优选法,它可以使我们合理地安排较少的试验次数找到合理的西方和合适的工艺条件。正因为它在建筑、文艺、工农业生产和科学实验中有着广泛而重要的应用,所以人们才珍贵地称它为"黄金分割"。我国数学家华罗庚曾致力于推广优选法中的"0.618法",把黄金分割应用于生活实际及科学应用中。 黄金分割〔Golden Section〕是一种数学上的比例关系。黄金分割具有严格的比例性、艺术性、和谐性,蕴藏着丰富的美学价值。应用时一般取0.618 ,就像圆周率在应用时取3.14一样。 由于公元前6世纪古希腊的毕达哥拉斯学派研究过正五边形和正十边形的作图,因此现代数学家们推断当时毕达哥拉斯学派已经触及甚至掌握了黄金分割。 公元前4世纪,古希腊数学家欧多克索斯第一个系统研究了这一问题,并建立起比例理论。 公元前300年前后欧几里得撰写《几何原本》时吸收了欧多克索斯的研究成果,进一步系统论述了黄金分割,成为最早的有关黄金分割的论著。 中世纪后,黄金分割被披上神秘的外衣,意大利数家帕乔利称中末比为神圣比例,并专门为此著书立说。德国天文学家开普勒称黄金分割为神圣分割。 到19世纪黄金分割这一名称才逐渐通行。黄金分割数有许多有趣的性质,人类对它的实际应用也很广泛。最著名的例子是优选学中的黄金分割法或0.618法,是由美国数学家基弗于1953年首先提出的,70年代在中国推广。 第三章 常用一维搜索方法 第节维搜索概述 第一节 一维搜索概述一、下降迭代算法的基本思想、下降迭代算法的基本思想 不失一般性,考虑如下的优化问题 min ()x S f x ∈ (3.1) 其中:n f S R R ?→. 下降迭代算法的的基本思想:给定一个初始点1n x R ∈,按 }k 使得当}k 是有限点列时照某种迭代规则产生一个点列{x ,使得当{x 其最后一个点是最优化问题的最优解;当{}k x 是无穷点列时,它有极限点,且其极限点是优化问题的最优解. 设已迭代到点k x 处,则下一次迭代会出现以下两种情况之一: (1) 从k x 出发沿任何方向移动,目标函数不再下降; 出发至少存在个方向使标数有所 (2)从k x 出发至少存在一个方向使目标函数()f x 有所下降.这时,从中选取一个下降方向k d ,即k d 满足 ()0k T k f x d ?<,然后在直线 k k x x d λ=+上适当的确定一个新点 1k k k k x x d λ+=+,使得1()()()k k k k k f x f x d f x λ+=+<,此时就说完成了第1k +次迭代. 基本迭代格式 1k k k k x x d λ+=+ 本代格式 k d ------搜索方向 k λ-----步长因子或搜索步长 最优化问题的求解步骤 最优化问题的求解步骤:(1)选取初始点1x ,令1k =; (2)构造搜索方向k d .依照一定的规则,构造()f x 在点 k x 处的下降方向或可行下降方向作为搜索方向k d ; (3)确定搜索步长k λ.以k x 为起点沿搜索方向k d 选取的 λ适当步长k ,使得目标函数值有某种意义的下降,通常使 ()()k k k k f x d f x λ+<. 1k +令1k k k + (4)求出新的迭代点x .令k x x d λ=+(5)检验终止条件.判定1 k x +是否满足终止条件,若满足 停止迭代输出近似最优解否则令转 停止迭代,输出近似最优解1k x +;否则,令:1k k =+,转(2). 现代设计一维优化方法——黄金分割法c程序 该程序是现代设计优化方法,黄金分割法的c语言源代码 该程序无错误,已经调试,后面附有实例,仅供参考 希望对你有所帮助………… #include "stdio.h" #include "math.h" #include "conio.h" #define e 0.001 #define tt 0.01 double function(double x) { double y; y=8*pow(x,3)-2*pow(x,2)-7*x+3; return(y); } void searching(double a[3],double f[3]) {double t=tt,a1,f1,ia; int i; a[0]=0; f[0]=function(a[0]); for(i=0;;i++) {a[1]=a[0]+t; f[1]=function(a[1]); if(f[1] } if(a[0]>a[2]) { a1=a[0];f1=f[0]; a[0]=a[2];f[0]=f[2]; a[2]=a1;f[2]=f1; } return; } double gold(double *ff) { double a1[3],f1[3],a[4],f[4]; double aa; int i; searching(a1,f1); a[0]=a1[0];f[0]=f1[0]; a[3]=a1[2];f[3]=f1[2]; a[1]=a[0]+0.382*(a[3]-a[0]); a[2]=a[0]+0.618*(a[3]-a[0]); f[1]=function(a[1]); f[2]=function(a[2]); for(i=0;;i++) { if(f[1]>=f[2]) {a[0]=a[1];f[0]=f[1]; a[1]=a[2];f[1]=f[2]; a[2]=a[0]+0.618*(a[3]-a[0]); f[2]=function(a[2]); } else{ a[3]=a[2];f[3]=f[2]; a[2]=a[1];f[2]=f[1]; a[1]=a[0]+0.382*(a[3]-a[0]); f[1]=function(a[1]); } if(a[3]-a[0]一维优化方法
最优化方法一维搜索法C++程序
最优化方法,汇总
常用一维搜索算法
黄金分割法 二次插值 牛顿 matlab 程序一维搜索方法比较
第三章 一维搜索
现代设计一维优化方法——黄金分割法c程序源代码