最优化方法-一维搜索法

第二章 一维搜索法● 概述● 确定初始单谷区间的进退法 ● 一维搜索法分类 ● 区间消去法 ● 函数逼近法概述求一元函数()F x 的极小点和极小值问题就是一维最优化问题。

求解一维优化问题的方法称为一维优化方法，又称一维搜索法。

一维搜索法是优化问题中最简单、最基本方法。

因为它不仅可以解决单变量目标函数的最优化问题，而且在求多变量目标函数的最优值时，大多数方法都要反复多次地进行一维搜索，用到一维优化法。

一般多维优化计算的迭代的基本格式：从一个已知点()k x 出发（()k x由上次迭代获得，开始时就是起始点(0)x），沿某一优化方法所规定的是目标函数值下降的搜索方向()k S，选择一个步长因子α，求得下一个新迭代点(1)k x +，(1)()()k k k xx S α+=+并且满足1()()k k F x F x +≤，即新点必须能够使目标函数值有所下降，这个新点就是下一次迭代的出发点，如此重复，直到求出目标函数的最优解为止。

理想步长kα可以通过()()()()k k F F x S αα=+的极小点获得min ()F α，使得目标函数达到最小()()min ()k k F x S α+，这种在第k 次迭代中求理想步长k α的过程，就是一维搜索过程。

大致分为两个步骤：1. 确定初始搜索区域[a,b]，该区域应该包括一维函数极小点在内的单谷区域；2. 在单谷区域[a,b]上寻找极小点。

寻找极小点kα可以采用解析解和数值解等方法。

确定初始单谷区间的进退法单谷区域的定义：设函数()F x 在区域12[,]x x 内有定义，且（1） 在区域12[,]x x 内存在极小值x *，既有min ()()F x F x *=，12[,]x x x ∈； （2） 对区域1[,]x x *上任意自变量x ，有()()F x F x x >+∆，0x ∆>；对区域2[,]x x *上任意自变量x ，有()()F x F x x <+∆，0x ∆>；则称12[,]x x 为函数()F x 的单谷区域。

《最优化方法及其应用》课 程 实 验 报 告一、 实验内容项目一 一维搜索算法（一） [实验目的]编写加步探索法、对分法、Newton 法的程序。

[实验学时]2学时[实验准备]1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤；2．掌握对分法的思想及迭代步骤；3．掌握Newton 法的思想及迭代步骤。

[实验内容及步骤]编程解决以下问题：1．用加步探索法确定一维最优化问题12)(min 30+-=≥t t t t ϕ的搜索区间，要求选取2,1,000===αh t ．2．用对分法求解)2()(min +=t t t ϕ，已知初始单谷区间]5,3[],[-=b a ，要求按精度3.0=ε，001.0=ε分别计算．3．用Newton 法求解12)(min 3+-=t t t ϕ，已知初始单谷区间]1,0[],[=b a ，要求精度01.0=ε．项目二 一维搜索算法（二）[实验目的]编写黄金分割法、抛物线插值法的程序。

[实验学时]2学时[实验准备]1．掌握黄金分割法的思想及迭代步骤；2．掌握抛物线插值法的思想及迭代步骤。

[实验内容及步骤]编程解决以下问题：1．用黄金分割法求解)2()(min +=t t t ϕ，已知初始单谷区间]5,3[],[-=b a ，要求精度001.0=ε．2．用抛物线插值法求解3728)(min 23+--=x x x x f ，已知初始单谷区间001.0]20[][==ε，，，b a ．项目三 常用无约束最优化方法（一）[实验目的]编写最速下降法、Newton 法（修正Newton 法）的程序。

[实验学时]2学时[实验准备]1．掌握最速下降法的思想及迭代步骤。

2．掌握Newton 法的思想及迭代步骤；3．掌握修正Newton 法的思想及迭代步骤。

[实验内容及步骤]编程解决以下问题：1．用最速下降法求22120min ()25[22]0.01T f X x x X ε=+==，，，．2．用Newton 法求22121212min ()60104f X x x x x x x =--++-，初始点0[00]0.01T X ε==，，． 3．用修正Newton 求221212min ()4(1)2(1)10f X x x x x =++-+++，初始点0[00]0.01T X ε==，，．项目四 常用无约束最优化方法（二）[实验目的]编写共轭梯度法、变尺度法（DFP 法和BFGS 法）程序。

精品资料最优化方法一维搜索法C++程序........................................加步探索法#include<iostream>#include<math.h>using namespace std;double fun(double t){return (t*t*t-2*t+1);}double max(double a,double b){if(a>b)return a;else return b;}double min(double a,double b){if(a>b)return b;else return a;}double Addstep(double(*pfun)(double t)){int k=0;double t0=0,h=1,r=2,t,a=0,b=0;t=t0+h;do{if(fun(t)<fun(t0)){h=r*h;t0=t;t=t0+h;k++;}else{if(k=0){h=-h;k++;}else{a=min(t0,t);b=max(t0,t);return a;return b;}}}while(a=b);cout<<" 探索区间为："<<"["<<min(t0,t)<<","<<max(t0,t)<<"]"<<endl; }int main(){Addstep(fun);return 0;}对分法#include<iostream>#include<math.h>using namespace std;double fun(double t){return (t*t-3*t);}double dfun(double t){return (2*t-3);}void Dichotomous(double(*pfun)(double t),double (*pdfun)(double t)) {int maxflag=1000,k=1;double a=-3,b=5,c,err=0.1,t;do{c=(a+b)/2;if(dfun(c)<0){a=c;}else {if(dfun(c)>0){b=c;}else{a=c;b=c;}}k++;}while(fabs(a-b)>err&&k<maxflag);if(k>=maxflag)cout<<endl<<"对分法迭代失败!迭代次数为k="<<k<<endl;else{cout<<endl<<" 对分法迭代成功!迭代次数为k="<<k-1<<endl; cout<<"迭代结果：近似根为root="<<t<<endl;cout<<" 函数值近似为：f(root)="<<fun(t)<<endl;}}int main(){Dichotomous(fun,dfun);return 0;}Newton切线法#include<iostream>#include<math.h>using namespace std;double fun(double t){return (t*t*t-2*t+1);}double dfun(double t){return (3*t*t-2);}void NewtonIterative(double(*pfun)(double t),double (*pdfun)(double t)) {int maxflag=1000,k=1;double t0=1,err=0.01,t;do{t0=t;t=t0-pfun(t0)/pdfun(t0);k++;}while(fabs(t-t0)>err&&k<maxflag);if(k>=maxflag)cout<<endl<<" 牛顿迭代失败!迭代次数为k="<<k<<endl;else{cout<<endl<<" 牛顿迭代成功!迭代次数为k="<<k-1<<endl;cout<<" 迭代结果：近似根为root="<<t<<endl; cout<<" 函数值近似为：f(root)="<<fun(t)<<endl; }}int main(){NewtonIterative(fun,dfun);return 0;}黄金分割法#include<iostream>#include<math.h>using namespace std;double fun(double t){return (t*t+2*t);}void Goldensection(double(*pfun)(double t)){int maxflag=1000,k=1;double a=-3,b=5,err=0.001,t,t1,t2;do{t1=a+0.618*(b-a);t2=b-0.618*(b-a);if(t1=t2){a=t2;b=t1;}else {if(t1<t2){a=t2;}else{b=t1;}}k++;}while(fabs(a-b)>err&&k<maxflag);if(k>=maxflag)cout<<endl<<"黄金分割法迭代失败!迭代次数为k="<<k<<endl; else{t=(a+b)/2;cout<<endl<<" 黄金分割法迭代成功!迭代次数为k="<<k-1<<endl; cout<<" 迭代结果：近似根为root="<<t<<endl;cout<<" 函数值近似为：f(root)="<<fun(t)<<endl;}}int main(){Goldensection(fun);return 0;}抛物线插值法#include<iostream>#include<math.h>using namespace std;double fun(double x){return (8*x*x*x-2*x*x-7*x+3);}double max(double a,double b){if(a>b)return a;else return b;}double min(double a,double b){if(a>b)return b;else return a;}void Parainterpolation(double(*pfun)(double x)){double a=0,b=2,err=0.001,x=0,x0=1,f,f0;do{x=((x0*x0-b*b)*fun(a)+(b*b-a*a)*fun(x0)+(a*a-x0*x0)*fun(b))/(2*((x0-b)*fun(a)+(b-a)*fun(x0)+(a-x0)*fun(b)));f0=fun(x0);f=fun(x);if(f=f0){a=min(x,x0);b=max(x,x0);x0=(a+b)/2;}else {if((fun(x)-f0)*(x-x0)>0){b=max(x,x0);x0=min(x,x0);}else{a=min(x,x0);x0=max(x,x0);}}}while(fabs(x-x0)>err);x=(x+x0)/2;cout<<" 迭代结果：近似根为root="<<x<<endl;cout<<" 函数值近似为：f(root)="<<fun(x)<<endl;}int main(){Parainterpolation(fun);return 0;}。