一维无约束优化

2023/2/111.约束极值存在的条件：(K—T条件)

2.迭代算法迭代格式：使得

3.收敛准则①点距准则②目标函数下降量准则③

梯度准则④K-T条件准则知识点回顾2023/2/12第4章一维无约束优化方法2023/2/134.二次插值法（抛物线法）

1.确定初始区间的进退法2.黄金分割法(0.618法）3.牛顿法掌握其基本思想、特点2023/2/14

工程实际中，所有设计问题几乎都是约束问题。

约束优化设计问题→无约束问题来求解。此外，有些约束优化设计方法，也可以借助于无约束优化方法的策略思想来构造。

引言第4章一维无约束优化方法2023/2/15引言数值迭代格式给定求一个变量一维函数的极值问题机械最优化设计虽大都为多维问题，但在数值迭代计算中要进行一维搜索，即把多维问题转化为一维问题来处理，一维搜索是优化方法的基础。第4章一维无约束优化方法2023/2/16一维搜索方法分两步：（1）确定初始搜索区间；（2）求出该区间内的最优步长因子。第4章一维无约束优化方法2023/2/17一维优化方法分为两类：（1）直接法——按照某种规律取若干点计算其函数值，然后通过直接比较函数值的大小来确定最优解，常用的有黄金分割法,Fibonaui（分数法）（2）间接法——利用函数的一阶导数、二阶导数来求解，故又称解析法，常用的有牛顿法和二次插值法等。第4章一维无约束优化方法2023/2/184.1确定初始区间的进退法探索区间的确定方法有外推法及进退法，常用的是进退法。2023/2/194.1确定初始区间的进退法搜索区间内函数具有单峰性，也就是在区间[a，b]中函数是凸函数，具有高—低—高的特性。在区间上具有唯一的极小值。即当时，有2023/2/1104.1确定初始区间的进退法4.1.1方法的建立给定初始点和初始步长步骤：（1）令⇒⇒计算，（2）比较、函数值大小。

2023/2/1114.1确定初始区间的进退法4.1.1方法的建立前进运算a.前进运算：

方向正确，作前进运算。计算三点的函数值满足高—低—高的特性若则搜索区间为

否则，将步长再加倍，重复上述运算，直至函数值满足高—低—高的特性。2023/2/1124.1确定初始区间的进退法4.1.1方法的建立b.后退运算：方向不正确，作后退运算，即反向搜索。否则，将步长再加倍继续后退，直至函数值满足高—低—高的特性。若计算三点的函数值满足高—低—高的特性搜索区间为2023/2/1134.1确定初始区间的进退法4.1.2程序框图①前进运算

③②前进运算

2023/2/1144.1确定初始区间的进退法4.1.2程序框图前进运算

和依次往右赶，始终比较和作代换，计算2023/2/1154.1确定初始区间的进退法4.1.2程序框图后退运算

①②③2023/2/1164.1确定初始区间的进退法4.1.2程序框图后退运算计算作代换无论前进还是后退运算，都是左边的点为，右边的点为和依次往左赶，2023/2/1174.2黄金分割法Fibonaui（分数法）和黄金分割法都是应用序列消去原理的直接搜索方法。2023/2/1184.2黄金分割法4.2.1序列消去原理基本思想：在搜索区间内选取计算点并比较其函数值，消去部分区间，以缩短搜索区间。消去在缩短了的探索区间内保留了一个点，再取一个新点，比较此两点的函数值大小，进一步将新区间缩短，直至区间长度小于某一给定的精度ε，则认为找到了极值点。探索区间

2023/2/1194.2黄金分割法4.2.1序列消去原理消去

探索区间在缩短的区间内取两个点，比较其函数值，才能进一步缩短搜索区间，为了与前两种情况一至，便简化迭代程序，将第（3）种情况和（1）、（2）种情况合并，只按以下两种情况考虑：为缩短后的探索区间。为缩短后的探索区间。消去

消去

2023/2/1204.2.2黄金分割法的基本思想通过计算和比较单峰区间内两点的函数值，不断舍弃单峰区间的左端或右端的一部分，使探索区间按等比例等速缩小，直至极小点所在区间缩小到某一给定的精度ε，而得到近似最优解，又称它为0.618法。2023/2/1214.2.2黄金分割法的基本思想黄金分割法在探索区间的插入点有以下规律：（1）首轮在区间内插入的两个点与区间两端点的距离相等，即相距两端点具有对称性。2023/2/1224.2.2黄金分割法的基本思想黄金分割法在探索区间的插入点有以下规律：（2）在缩短后的区间内插入一个点，新区间的三段和原区间的三段具有相同的比例分布。如果把区间长度看作是1，则有：解上式得：最长段与较长段之比相等2023/2/1234.2.3黄金分割法的迭代过程①在初始区间取两个试点

②计算函数值③比较

迭代过程2023/2/1244.2.3黄金分割法的迭代过程③比较求新区间增加一个新点

（a）

2023/2/1254.2.3黄金分割法的迭代过程③比较（b）求（b）新区间增加一个新点

④新区间小于给定的精度ε时，终止迭代，所求的最优点

否则转第3步继续迭代。2023/2/1264.2.4程序框图开始结束TTFF给定a,b,ε2023/2/1272023/2/1282023/2/1296次迭代达最优点2023/2/130练习

1.试用黄金分割法求函数的最优解。初始区间[a,b]=[1,7],精度ε=0.01.最优解：2023/2/131重点内容1、搜索区间内函数应具有什么性质？2、黄金分割法的基本思想是什么？3、黄金分割法的区间缩短实质上采用的是什么原理？4、黄金分割法首轮搜索区间插入点具有什么特点？2023/2/132知识点回顾1.用进退法确定初始区间时，搜索区间内函数具有什么性质？2.用进退法确定初始区间，直至函数满足什么特性时停止搜索？

3.黄金分割法的基本思想是什么？4.黄金分割法中的0.618的含义是什么？本次课的内容一维牛顿法（切线法）二次插值法（抛物线法）1、基本思想

2、迭代公式和迭代步骤3、程序框图4、特点2023/2/1344.3一维牛顿法（1）牛顿法的基本思想

用二次函数逐点近似原目标函数，以二次函数的极小点来近似原目标函数的极小点，用切线代替弧线逐渐逼近函数的根值。2023/2/135（1）牛顿法的基本思想

当目标函数有一阶连续导数，且二阶导数大于零时，函数的极小值点应满足极值存在的必要条件，所以求函数的极小值点也就是求解方程的根。在曲线上作一系列切线，使之与轴的交点逐渐逼近方程的根。4.3一维牛顿法2023/2/136（2）牛顿法的迭代公式与轴的交点为推广到k步得迭代公式过点的切线方程为

4.3一维牛顿法2023/2/137（2）牛顿法的迭代公式迭代公式也可由Taylor公式展开得到：

在点附近用二次函数来逼近原目标函数，故在点用Taylor公式展开，保留到二次项。令4.3一维牛顿法2023/2/1384.3一维牛顿法（3）牛顿法的迭代步骤给定搜索区间，初始点，迭代精度ε，令1）计算

2）求

3）终止条件判断

若满足条件，则得近似解停止计算，否则转步骤4）4）令转步骤1）。自己列出程序框图2023/2/139（4）牛顿法的程序框图

给定x(0),a,b,εk=0TF结束开始4.3一维牛顿法2023/2/1402023/2/1412次迭代达最优点2023/2/1424.3牛顿法1）

优点是收敛速度快，2）缺点是需要计算函数的一阶和二阶导数，增加了每次迭代的工作量。如果用数值微分计算函数的二阶导数，其舍入误差将严重影响牛顿法的收敛速度，的值越小问题越严重。3）牛顿法要求初始点离极值点不太远，否则有可能使极小化序列发散或收敛到非极小点。（5）牛顿法的特点2023/2/1434.4二次插值法（抛物线法）4.4.1二次插值法基本思想利用目标函数在三个点的信息:

构造一个与目标函数值相接近的插值多项式，用该多项式的最优解作为原目标函数的近似最优解，随着搜索区间的逐次缩短，多项式的最优点与原函数最优点的距离逐渐减小，直至满足精度要求。2023/2/1444.4.2二次插值法的公式推导设函数极值点所在区间内有三个点其函数值为满足，即满足高—低—高特性。构造二次插值多项式多项式的最优解（x2,f2)作为原目标函数的近似最优解2023/2/1454.4.2二次插值法的公式推导构造二次插值多项式：（4-3）——待定系数对（4-3）式求导，令导数等于零，得插值多项式的极小点：极小点：2023/2/1464.4.2二次插值法的公式推导构造二次插值多项式：（4-3）将三点的值代入（4-3）即可求待定系数（4-4）2023/2/1474.4.2二次插值法的公式推导由（4-4）可以求得（4-6）

（4-7）将代入得极小点（4-8）2023/2/1484.4.3二次插值法的迭代过程

①确定初始搜索区间给定初始插值点迭代精度ε。②计算

③计算插值多项式的极小点2023/2/1494.4.3二次插值法的迭代过程④终止判断a.若便可得到极小点

b.若

必须缩小搜索区间根据区间消去原理，先比较和的大小，然后确定从四点中舍去得到新三点，然后再转步骤③。2023/2/150

4.4.4二次插值法的程序框图A=0停（失败）TFFTFT必须缩短搜索区间2023/2/151

4.4.4二次插值法的程序框图求2023/2/152

4.4.4二次插值法的程序框图求xm2023/2/153

4.4.4二次插值法的程序框图A=0停（失败）TFFTFT采用序列消去原理缩短探索区间2023/2/1544.4.5二次插值法的特点

抛物线法充分利用了函数的性态。对于二次函数用二次插值法求解，在理论上一次迭代可达到最优点。对于非二次函数，在极值点附近函数呈现二次性态，因而收敛速度也较快。4.4.6各种一维优化方法的比较

牛顿法收敛快，但