最优化方法(一维搜索)

最优化方法实验报告（1）最优化方法实验报告Numerical Linear Algebra And Its Applications学生所在学院：理学院学生所在班级：计算数学10-1学生姓名：甘纯指导教师：单锐教务处2013年5月实验一实验名称：熟悉matlab基本功能实验时间: 2013年05月10日星期三实验成绩：一、实验目的：在本次实验中，通过亲临使用MATLAB，对该软件做一全面了解并掌握重点内容。

二、实验内容：1. 全面了解MATLAB系统2. 实验常用工具的具体操作和功能实验二实验名称：一维搜索方法的MATLAB实现实验时间: 2013年05月10日星期三实验成绩：一、实验目的：通过上机利用Matlab数学软件进行一维搜索，并学会对具体问题进行分析。

并且熟悉Matlab软件的实用方法，并且做到学习与使用并存，增加学习的实际动手性，不再让学习局限于书本和纸上，而是利用计算机学习来增加我们的学习兴趣。

二、实验背景：(一）0.618法（黄金分割法），它是一种基于区间收缩的极小点搜索算法，当用进退法确定搜索区间后，我们只知道极小点包含于搜索区间内，但是具体哪个点，无法得知。

1、算法原理黄金分割法的思想很直接，既然极小点包含于搜索区间内，那么可以不断的缩小搜索区间，就可以使搜索区间的端点逼近到极小点。

2、算法步骤用黄金分割法求无约束问题min (),f x x R ∈的基本步骤如下：（1）选定初始区间11[,]a b 及精度0ε>，计算试探点：11110.382*()a b a λ=+-11110.618*()a b a μ=+-。

（2）若k k b a ε-<，则停止计算。

否则当()()k k f f λμ>时转步骤（3）。

当()()k k f f λμ≤转步骤（4）。

（3）置11111110.382*()k kk k k k k k k k a b b a b a λλμμ+++++++=??=??=??=+-?转步骤（5）（4）置11111110.382*()k k k k k k k k k k a a b a b a μμλλ+++++++=??=??=??=+-?转步骤（5）（5）令1k k =+，转步骤（2）。

一维搜索:1精确一维搜索精确一维搜索可以分为三类：区间收缩法、函数逼近法（插值法）、以及求根法。

区间收缩法：用某种分割技术缩小最优解所在的区间(称为搜索区间)。

包括：黄金分割法、成功失败法、斐波那契法、对分搜索法以及三点等间隔搜索法等。

优化算法通常具有局部性质，通常的迭代需要在单峰区间进行操作以保证算法收敛。

确定初始区间的方法：进退法①已知搜索起点和初始步长；②然后从起点开始以初始步长向前试探，如果函数值变大，则改变步长方向；③如果函数值下降，则维持原来的试探方向，并将步长加倍。

1.1黄金分割法：黄金分割法是一种区间收缩方法(或分割方法)，其基本思想是通过取试探点和进行函数值比较，使包含极小点的搜索区间不断缩短以逼近极小值点。

具有对称性以及保持缩减比原则。

优点：不要求函数可微，除过第一次外，每次迭代只需计算一个函数值，计算量小，程序简单；缺点：收敛速度慢；函数逼近法（插值法）：用比较简单函数的极小值点近似代替原函数的极小值点。

从几何上看是用比较简单的曲线近似代替原的曲线，用简单曲线的极小值点代替原曲线的极小点。

1.2牛顿法：将目标函数二阶泰勒展开，略去高阶项后近似的替代目标函数，然后用二次函数的极小点作为目标函数的近似极小点。

牛顿法的优点是收敛速度快，缺点是需要计算二阶导数，要求初始点选的好，否则可能不收敛。

1.2抛物线法：抛物线法的基本思想就是用二次函数抛物线来近似的代替目标函数，并以它的极小点作为目标函数的近似极小点。

在一定条件下，抛物线法是超线性收敛的。

1.3三次插值法：三次插值法是用两点处的函数值和导数值来构造差值多项式，以该曲线的极小点来逼近目标函数的极小点。

一般来说，三次插值法比抛物线法的收敛速度要快。

精确一维搜索的方法选择：1如目标函数能求二阶导数：用Newton法，收敛快。

2如目标函数能求一阶导数：1如果导数容易求出，考虑用三次插值法，收敛较快；2对分法、收敛速度慢，但可靠；3只需计算函数值的方法：1二次插值法, 收敛快，但对函数单峰依赖较强；2黄金分割法收敛速度较慢，但实用性强，可靠；4减少总体计算时间：非精确一维搜索方法更加有效。

项目一 一维搜索算法（一）[实验目的]编写加步探索法、对分法、Newton 法的程序。

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

[实验内容及步骤] 编程解决以下问题：1．用加步探索法确定一维最优化问题的搜索区间，要求选取．加步探索法算法的计算步骤： (1)选取初始点，计算．给出初始步长，加步系数，令。

(2) 比较目标函数值．令k k k h t t +=+1，计算 )(11++=k k t ϕϕ，若k k ϕϕ<+1，转(3)，否则转(4)。

(3) 加大探索步长．令，同时，令，转(2)。

(4) 反向探索．若，转换探索方向，令，转（2）。

否则，停止迭代，令。

加步探索法算法的计算框图12)(min 30+-=≥t t t t ϕ2,1,000===αh t ])0[)(0[max 00t t t ，或，∈⊂∞+∈)(00t ϕϕ=0>h 1α>0=k k k h h α=+1,k t t =,1+=k k t t 1k k =+0=k ,k k h h -=1+=k t t 11min{}max{}k k a t t b t t ++==，，，程序清单加步探索法算法程序见附录1实验结果运行结果为：2．用对分法求解，已知初始单谷区间，要求按精度，分别计算．对分法迭代的计算步骤：(1)确定初始搜索区间],[b a ，要求。

(2) 计算],[b a 的中点)(21b ac +=． (3) 若0)(<'c ϕ，则c a = ，转(4)；若0)(='c ϕ，则c t =*，转(5)；若0)(>'c ϕ，则c b = ，转(4)．)2()(min +=t t t ϕ]5,3[],[-=b a 3.0=ε001.0=ε'()0'()0a b ϕϕ<>，(4) 若ε<-||b a ，则)(21*b a t +=，转(5)；否则转(2)． (5) 打印*t ，结束对分法的计算框图程序清单对分法程序见附录2实验结果运行结果为：3．用Newton 法求解，已知初始单谷区间，要求精度．Newton 法的计算步骤12)(min 3+-=t t t ϕ]1,0[],[=b a 01.0=ε(1) 确定初始搜索区间],[b a ，要求 (2) 选定0t(3) 计算(4) 若 ε≥-||0t t ，则t t =0，转（3）；否则转（5）． (5) 打印 ，结束．Newton 法的计算框图程序清单Newton 法程序见附录3实验结果运行结果为：'()0'()0a b ϕϕ<>，000'()/"()t t t t ϕϕ=-()t t ϕ，项目二 一维搜索算法（二）[实验目的]编写黄金分割法、抛物线插值法的程序。

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

无约束优化：不对定义域或值域做任何限制的情况下，求解目标函数的最小值。

这是因为实际应用中，许多情形被抽象为函数形式后均为凸函数，对于凸函数来说局部最小值点即为全局最小值点，因此只要能求得这类函数的一个最小值点，该点一定为全局最小值。

（直接法：又称数值方法，它只需计算目标函数驻点的函数数值，而不是求其倒数，如坐标轮换法，单纯型法等。

间接法：又称解析法，是应用数学极值理论的解析方法。

首先计算出目标函数的一阶或一阶、二阶导数，然后根据梯度及海赛矩阵提供的信息，构造何种算法，从而间接地求出目标函数的最优解，如牛顿法、最速下降法共轭梯度法及变尺度法。

）在优化算法中保证整体收敛的重要方法就是线搜索法与信赖域法,这两种算法既相似又有所不同。

根据不同的线搜索准则就延伸出不同的线搜索算法,譬如比较常见和经典的最速下降法,牛顿法,拟牛顿法以及共辄梯度法等。

一维搜索又称线性搜索(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.初始化区间的上下界，确定迭代终止条件；2.计算黄金分割点的位置；3.根据黄金分割点分割区间；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

斐波那契法是另一种常用的一维算法。

该算法通过斐波那契数列的性质，不断缩小区间来逼近最优解。

斐波那契法的具体步骤如下：1.初始化斐波那契数列，确定迭代终止条件；2.计算斐波那契点的位置；3.根据斐波那契点分割区间；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

插值法是一种基于函数插值的一维算法。

该算法通过插值函数来拟合原函数，并通过求解插值函数的最小值或最大值来近似求解原函数的最小值或最大值。

插值法的具体步骤如下：1.初始化区间的上下界，确定迭代终止条件；2.根据插值函数拟合原函数，得到插值函数的表达式；3.求解插值函数的最小值或最大值；4.更新区间的上下界；5.判断是否满足迭代终止条件，如果满足，则输出最优解；如果不满足，则返回第2步。

除了上述算法，还存在其他一维算法，如割线法、牛顿法等。

这些算法各有特点，适用于不同类型的最优化问题。

一维算法的优势在于其计算简单、耗时少的特点。

然而，一维算法也存在一些缺点，例如容易陷入局部最优解、收敛速度较慢等。

因此，对于一些复杂的最优化问题，可能需要使用更高维度的算法进行求解。

总之，一维是最优化问题求解中常用的一种算法。

通过在给定的区间内不断迭代，可以逼近最优解。

短后的区间不大于区间[0,10]的5% 。

解：由题意=δ5%，由斐波那契数列δ1≥n F ，则n=7， 00=a ，100=b1t =0b )(0076a b F F --=2180 , 21130)(00760'1=-+=a b F F a t , 将1t 和'1t 代入函数，比较大小有)()('11t f t f <则有001==a a ，21801'2==t t ，21130'11==t b ，2150)(116512=--=a b F F b t ， 将2t 和'2t 代入函数，比较大小有)()('22t f t f < ,则有012==a a ，21502'3==t t ，2180'22==t b ，2130)(225423=--=a b F F b t ， 将3t 和'3t 代入函数，比较大小有)()('33t f t f >， 则有213033==t a ，2150'34==t t ，218023==b b ，2160)(33433'4=-+=a b F F a t ， 将4t 和'4t 代入函数，比较大小有)()('44t f t f >， 则有215044==t a ,2160'45==t t ,218034==b b ,2170)(44324'5=-+=a b F F a t ， 将5t 和'5t 代入函数，比较大小有)()('55t f t f >， 则有216055==t a ，2170'56==t t ，218045==b b ， 则令105351)21602180()01.05.0(2160))((55215'6=-⨯++=-++=a b F F a t ε， 将6t 和'6t 代入函数，比较大小有)()('66t f t f <，则216056==a a ，105351'66==t b ，区间为：⎥⎦⎤⎢⎣⎡105351,2160 所以选择6t 为极小点，=)(6t f 89.6)2170(-=f 。