当前位置：文档之家 › 第七章非线性规划 第二节 一维搜索(1)

第七章非线性规划 第二节 一维搜索(1)

  • 格式：pdf
  • 大小：854.32 KB
  • 文档页数：33

下载文档原格式

  / 33

合集下载

非线性最优化

非线性最优化

定理5 设S为n维欧氏空间 En 上的开凸集, f(X)在S上二次可微,若任意x∈S,Hesse矩阵正定,则f是S 上的严格凸函数.
例如 分析f(x1,x2)= 2x12 +x22 -2 x1x2+x1+1的凸性. 解: H=A为正定阵，所以f为严格凸函数.
f(x)1 2(x1,x2)4 222x x1 2x11
一维搜索在搜索方向上所得最优点处的 梯度和该搜索方向正交.
定理8 设目标函数f(X)∈C(1)，X(k+1)按下 述规则产生
λk : Minf(X(k)+λP(k)) X(k+1)= X(k)+λkP(k)
则有 ▽f(X(k+1))TP(k)=0. 证 设φ(λ)=f(X(k)+λP(k)),则由
注2.gj(X)≤0→-gj(X) ≥ 0 ; 注3.hi(X)=0→hi(X) ≥ 0 , -hi(X) ≥ 0 .
1.2 极值问题
设f(X)为定义在n维欧氏空间 En 的某一区
域S上的n元实函数，其中X=(x1 ,x2 … xn)T . 局部极小点(值)：对于 X* ∈S，如果存在
某ε>0,使所有与X* 的距离小于ε的X∈S,均满足不等式f(X)≥f(X* ),则称X* 为f(X)在S上的局部极小点, f(X* )为局部极小值。
用反证法证明定理6： 设X* ∈S是一个局部极小点,则存在ε>0,使得对 任意X∈S∩Nε(X* ),恒有 f(X)≥f(X* ). 假设X*非全局最小,则存在X’∈S,使得f(X*)>f(X’). 由S的凸性,对任意λ∈[0,1],λX’+(1- λ)X*∈S, 由X*≠X’,取λ∈(0,1).因为λ<<1时,可使

最优化方法-一维搜索

最优化方法-一维搜索
优点：按Ｆ法确定插入点的位置，所需使用的观测点的个数最少． Ｆ数列各数所表示的物理意义： Fn ：插入n个点后可以缩短为单位长度为一的区间的最大长度．
按任务方式插入n个观测点后，剩下的搜索区间的长度不少于原初始长 度的1／ Fn
令缩短后的长度为Ｓ，有： Ｓ （b-a）/ Fn
• Ｆibonacci数列：
• ＝b- (b-a)=a+(1- )(b-a)
• =a+ (b-a)
•
• 2 0.618法算法
设
值
(t)是单谷函数，［ a

t
与精确极小点
t*
0的，最b大0 ］绝是对初误始差搜t索 区t * 间 ， 要求精确极小点近似
记：a= a0,b= b0 , =0.618.
(1) =a+(1- )(b-a), 1 = ()
进退算法的基本步骤：
（（（t0１ ２ ３点 回）））及升：：：，首若若t则0先［＋tt任t00h0＋＋选点，hh一t的点点n个函］的的初数就函 函始值是数 数点．一值 值个下 上t0搜降 升，索， ，初区继 则始间续 从步，前长t算进0h法点,，进停退直到止到到．t某0t个＋0 －ht，h0点并点．计的算函数值
4= a4 +( F0 / F2
b4
)(
=
b4
3 /a4
=2.5 , 4= 3 = 1.625
)=0.75+1/2*1.75=1.625
这时，

＝
4

，（因为已到k=3=n-2)
4
K=4, 因此
(5取5 =)a=0t5.41＝＝=410.,.6542（(5＝b,515).＋5=6=02a.550,47b+6）50,.＝1＝=2(1.b.05476)2255>＝2(.55 )

非线性规划问题的求解方法[优质ppt]

非线性规划问题的求解方法[优质ppt]

3、问题：
4.1、外点法（外部惩罚函数法）：
如何将此算法模块化？
外点法框图： kk1
初始 x(0),1 0,1 0,k1
以x(k)为初始点 , 解
min f ( x) k p( x)
得到 x (k 1)
No
k1k
kp(x(k1)) yes
停 x (k 1) f22=subs(fx2x2); if(double(sqrt(f1^2+f2^2))<=0.002)
a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f)); break; else X=[x1 x2]'-inv([f11 f12;f21 f22])*[f1 f2]'; x1=X(1,1);x2=X(2,1); end end if(double(sqrt((a(k+1)-a(k))^2+(b(k+1)b(k))^2))<=0.001)&&(double(abs((f0(k+1)-f0(k))/f0(k)))<=0.001) a(k+1) b(k+1) k f0(k+1) break; else m(k+1)=c*m(k);
非线性规划问题的求解方法
Content
无约束非线性规划问题 有约束非线性规划问题 Matlab求解有约束非线性规划问题
一.无约束问题
• 一维搜索
指寻求一元函数在某区间上的最优值点的方法。这类方法不仅有实用 价值，而且大量多维最优化方法都依赖于一系列的一维最优化。
逐次插值逼近法 近似黄金分割法（又称0.618法） • 无约束最优化

一维搜索-最优化方法

一维搜索-最优化方法

������2=0.538， ƒ2 = 1.751， ������1=������3+������������23 ������3 − ������3 =0.231
则ƒ2 = 1.822， ƒ1 > ƒ2，故得新区间为 [������4，������4]=[0.231， 0.846]
第五次迭代：
取������2=0.538， ƒ2 = 1.751， ������1=������2 − 0.1 ������4 − ������4 =0.477
问题3：按什么方式取点，求n次函数值之后多长的原始区间 缩短为最终区间长度为1？
• １：Ｆibonacci数列：
• F0 =1 ;
F1 = 1 ;
F 迭代公式：Fn2 ＝ Fn1 ＋ n
•
；n 非负整数
n
0
1
2
3
4
5
6
7
…..
1
1
23ຫໍສະໝຸດ 5813 21 …..
Fn
设Ln表示试点个数为n，最终区间长度为1时的原始区间[a ,b] 的最大可能的长度，现在找出Ln的一个上界。设最初的两个 试点为x1,x2,且且x1< x2 。如果极小点位于[a , x1]内，则我们 至多还有n-2个试点，因此x1-a≤Ln-2；如果极小点位于[x1 , b] 内，则包括x2在内还可以有n-1个试点，因此b- x1≦Ln-1。
t （１中）任若设取［两 (a点t,1b)］t1<是<单(tt2谷2) ，函，则数那搜么(索t有) 区的：间一可个缩已短知为搜*［索a区, 间t2］，.在［a,b］
( 2 ) 若 (t1 ) (t2 )，则搜索区间可缩短为［ t1，b］

《一维搜索方法》课件

《一维搜索方法》课件

02
线性搜索
线性搜索的定义
线性搜索是一种基本的搜索算法，它 从列表的第一个元素开始，逐个检查 每个元素，直到找到目标元素或遍历 完整个列表。
在线性搜索过程中，我们假设列表中 的元素是按顺序排列的，并且我们不 知道目标元素的确切位置，只知道它 存在于列表中。
线性搜索的步骤
初始化
选择一个起始位置，通常为列表的第一个元素。
抛物线搜索的步骤
3. 比较中间元素与目标值
2. 计算当前区间的中间元 素。
1. 初始化当前搜索区间为 整个数组。
01
03 02
抛物线搜索的步骤
01 如果中间元素等于目标值，返回该位置。
02
如果目标值小于中间元素，将左半部分区 间作为新的当前区间。
03
如果目标值大于中间元素，将右半部分区 间作为新的当前区间。
04
4. 重复步骤2和3，直到找到目标值或当前 区间为空。
抛物线搜索的时间复杂度
最坏情况下，抛物线搜索的时间复杂度为O(n)，其中n为数 组长度。
平均情况下，由于每次比较都可以将搜索区间缩小一半，因 此时间复杂度为O(log n)。
THANKS
THANK YOU FOR YOUR WATCHING
的单峰函数。
一维搜索方法的重要性
解决实际问题
一维搜索方法广泛应用于各种实 际问题中，如参数优化、函数逼 近、插值等。
算法基础
一维搜索方法是许多算法的基础 ，如梯度下降法、牛顿法等都需 要用到一维搜索方法来寻找迭代 步长。
理论分析
一维搜索方法在数学分析中也有 重要应用，如中值定理、单调函 数性质等都需要用到一维搜索方 法。
常用的一维搜索方法
线性搜索

一维搜索

一维搜索

非线性规划非线性规划问题是比线性规划问题更一般的数学规划问题，它的目标函数或约束函数中至少含有一个非线性函数，非线性规划就是研究非线性规划问题的有关理论和方法的学科。

非线性规划是运筹学的一个重要分支，它在军事、经济、工程、管理以及最优设计等方面都有着广泛的应用。

本部分介绍无约束非线性规划和约束非线性规划的基本理论和方法。

第三章 无约束优化方法无约束非线性规划问题是指可行域是整个决策空间的非线性规划问题。

本章首先分析无约束非线性规划问题的一阶和二阶最优性条件，包括必要条件和充分条件，然后讨论一维搜索问题，最后介绍无约束优化的求解方法，包括最速下降法，Newton 法共轭梯度法和拟Newton 法等。

补充：最优性条件现在考虑无约束非线性规划问题)(min x xf (UNP)其中决策变量n R ∈x ，目标函数1:R R f n →。

我们先引进下降方向的概念，并研究其充分条件，由此建立(UNP)的一阶和二阶最优性条件。

补.1 下降方向定义补.1 设函数1:R R f n →，n R ∈x ，nR ∈s 是非零方向。

若存在δ>0，使()(f f λ+<x s x ，(0,)λδ∀∈则称s 是f 在x 处的下降方向。

注补.1 设*x 是(UNP)的局部最优解，则f 在*x 处不存在下降方向。

定理补.1 设)(x f 在x 处可微，nR ∈s 是非零方向。

若()Tf ∇x s <0，则s 是f 在x 处的下降方向。

证明：对任意的λ>0，因为)(x f 在x 处可微，故由)(x f 在x 处的一阶Taylor 展开式知，()()()()()[()()/]T T f f f o f f o λλλλλλ+=+∇+=+∇+x s x x s x x s (补.1)根据条件()Tf ∇x s <0和0()lim0o λλλ→=知，存在δ>0，使()()0T o f λλ∇+<x s ，(0,)λδ∀∈代入(补.1)并由λ>0得到，()(f f λ+<x s x ，(0,)λδ∀∈由此知s 是f 在x 处的下降方向。

非线性规划

非线性规划

非线性规划（nonlinear programming）1.非线性规划概念非线性规划是具有非线性约束条件或目标函数的数学规划，是运筹学的一个重要分支。

非线性规划研究一个n元实函数在一组等式或不等式的约束条件下的极值问题，且目标函数和约束条件至少有一个是未知量的非线性函数。

目标函数和约束条件都是线性函数的情形则属于线性规划。

2.非线性规划发展史公元前500年古希腊在讨论建筑美学中就已发现了长方形长与宽的最佳比例为0.618,称为黄金分割比。

其倒数至今在优选法中仍得到广泛应用。

在微积分出现以前，已有许多学者开始研究用数学方法解决最优化问题。

例如阿基米德证明：给定周长，圆所包围的面积为最大。

这就是欧洲古代城堡几乎都建成圆形的原因。

但是最优化方法真正形成为科学方法则在17世纪以后。

17世纪，I.牛顿和G.W.莱布尼茨在他们所创建的微积分中，提出求解具有多个自变量的实值函数的最大值和最小值的方法。

以后又进一步讨论具有未知函数的函数极值，从而形成变分法。

这一时期的最优化方法可以称为古典最优化方法。

最优化方法不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。

反之,某些最优化方法可适用于不同类型的模型。

最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。

(1)解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。

求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。

(2)直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。

此时可采用直接搜索的方法经过若干次迭代搜索到最优点。

这种方法常常根据经验或通过试验得到所需结果。

对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。

2一维搜索

2一维搜索
B. 当 f1> f2 时，极小点必在[x1, b]中，则
x1 a,x2 x1,f2f1, x2a0.61(b8 a),f2f(x2)
（4）判断是否满足精度要求。若新区间已缩短至预
定精度要求，即 ba，则转第5）步；否则
转第3）步，进行下一次迭代计算。 （5）输出最终区间的中点作为近似最优点，其对应
（1）选定初始点a1 , 初始步长h＝h0，计算 y1＝f(a1)， y2＝f(a1＋h)。
（2）比较y1和y2。 （a）如y1>y2,向右前进；转（3）向前； （b）如y1=<y2, 向左后退；h＝－ h0， 将a1与a2，y1与y2的 值互换。转（3）向后探测；
（3）产生新的探测点a3＝a1＋h，y3＝f(a3); （4）比较函数值 y2与y3：
f(x )f(x x ) ,x 0；区间 x*,x2
上的任意x，有 f(x )f(x x ) ,x 0
x1
x* x2 x
则称闭区间 x1,x2为函数f(x)的单峰区间。
单峰区间的特点：
▪ 单峰区间内，在极小点的左边，函数是严格减少 的，在极小点的右边，函数是严格增加的；
▪ 如果区间 a,b 是一个单峰区间，x是区间内的一
对“一维”的理 解
▪ “一维”是指 “一个方向”d (k（)
）；
▪ 寻找目标函数在指定方向上的极小点，在计算上 就是从 X 沿 (k) d (k ) 前进多少的问题，即求步长因子 (k) 的问题。从这个意义上讲，一维搜索是一个求
解关于 的单元目标函数的过程。
一维搜索
寻找合适的 (k ) ，使 最小 f(X(k) (k)d(k))
点，则 f(x)f(a )和 f(x)f(b )两个不等式中必有 一个成立；

非线性规划

非线性规划

非线性规划什么是非线性规划？非线性规划（Nonlinear Programming，简称NLP）是一种数学优化方法，用于求解包含非线性约束条件的优化问题。

与线性规划不同，非线性规划中的目标函数和约束条件都可以是非线性的。

非线性规划的数学表达式一般来说，非线性规划可以表示为以下数学模型：minimize f(x)subject to g_i(x) <= 0, i = 1, 2, ..., mh_j(x) = 0, j = 1, 2, ..., px ∈ R^n其中，f(x)是目标函数，g_i(x)和h_j(x)分别是m个不等式约束和p个等式约束，x是优化变量，属于n维实数空间。

非线性规划的解法由于非线性规划问题比线性规划问题更为复杂，因此解决非线性规划问题的方法也更多样。

以下列举了几种常用的非线性规划求解方法：1. 数值方法数值方法是最常用的非线性规划求解方法之一。

它基于迭代的思想，通过不断优化目标函数的近似解来逼近问题的最优解。

常见的数值方法有梯度下降法、牛顿法、拟牛顿法等。

2. 优化软件优化软件是一类针对非线性规划问题开发的专用软件，它集成了各种求解算法和优化工具，可以方便地求解各种类型的非线性规划问题。

常见的优化软件有MATLAB、GAMS、AMPL等。

3. 线性化方法线性化方法是一种将非线性规划问题转化为等价的线性规划问题的求解方法。

它通过线性化目标函数和约束条件，将非线性规划问题转化为线性规划问题，然后利用线性规划的求解方法求解得到最优解。

4. 分类方法分类方法是一种将非线性规划问题分解为若干个子问题求解的方法。

它将原始的非线性规划问题分解为多个子问题，然后将每个子问题分别求解，并逐步逼近原始问题的最优解。

以上仅是非线性规划求解方法的一小部分，实际上还有很多其他的方法和技巧可供选择。

在实际应用中，选择合适的方法和工具是非常重要的。

非线性规划的应用非线性规划在实际生活和工程中有着广泛的应用。

非线性规划

非线性规划

: 风险系数； ij : 第i种与第j种股票收益的协方差
max f ( x ) j x j xi x j
j 1 i 1 j 1 n n n
n Pj x j B s.t. j 1 x 0 j
2.模型
min f ( X ) hi ( X ) 0, i 1, , m ( NLP ) s.t. g j ( X ) 0, j 1, , l 其中X [ x1 , , xn ]T 记D { X R n | hi ( X ) 0, g j ( X ) 0} 则（NLP）也可以表示为 min f ( X )
X D
其中D称为（NLP）的约束集或可行域。 当D＝R n时，（NLP）称做无约束极值问题； 当D R n时，（NLP）称做约束极值问题。
二 、模型的解及相关概念
1.可行解与最优解
★可行解：约束集D中的X。 ★最优解：如果有 X * D，对于任意的 X D ， 都有 f ( X * ) f ( X ) ，则称 X *为（NLP）的最优 解，也称为全局最小值点。 ★局部最优解：如果对于 X D ，使得在 X 的邻
因此，本模型是凸规划。
计算
说明 f ( X )是凸函数，g1 ( X )、g 2 ( X )、g3 ( X )是凹函数
第二节 无约束极值问题
★一般模型：
min f ( X )
其中X R n
★求解（f(X)可微）：应用极值条件求解，往往得到一个非线
性的方程组，求解十分困难。因此，求 解无约束问题一般 采用迭代法，称为下降类算法。
几何意义： 梯度是过X 0点且与f ( X )在X 0的切平面垂直的向量， 梯度向量的方向是函数值在该点增加最快的方向。

一维搜索法

一维搜索法

第二章 一维搜索法● 概述● 确定初始单谷区间的进退法 ● 一维搜索法分类 ● 区间消去法 ● 函数逼近法概述求一元函数()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 的单谷区域。

常用一维搜索算法

常用一维搜索算法

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

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

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

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

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

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

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

一维搜索又称线性搜索(Line Search),就是指单变量函数的最优化,它是多变量函数最优化的基础,是求解无约束非线性规划问题的基本方法之一。

一维搜索技术既可独立的用于求解单变量最优化问题,同时又是求解多变量最优化问题常用的手段,虽然求解单变量最优化问题相对比较简单,但其中也贯穿了求解最优化问题的基本思想。

由于一维搜索的使用频率较高,因此努力提高求解单变量问题算法的计算效率具有重要的实际意义。

在多变量函数的最优化中,迭代格式Xk+1=Xk+akdk其关键就是构造搜索方向dk和步长因子ak设Φ(a)=f(xk+adk)这样从凡出发,沿搜索方向dk,确定步长因子ak,使Φ(a)<Φ(0)的问题就是关于步长因子a的一维搜索问题。

其主要结构可作如下概括:首先确定包含问题最优解的搜索区间，然后采用某种分割技术或插值方法缩小这个区间，进行搜索求解。

一维搜索通常分为精确的和不精确的两类。

如果求得ak使目标函数沿方向dk达到极小,即使得f (xk+akdk)=minf(xk+adk) (a>0)则称这样的一维搜索为最优一维搜索,或精确一维搜索,ak叫最优步长因子;如果选取ak使目标函数f得到可接受的下降量,即使得下降量f(xk)一f(xk+akdk)>0是用户可接受的,则称这样的一维搜索为近似一维搜索,或不精确一维搜索,或可接受一维搜索。

非线性规划问题的求解方法[优质ppt]

非线性规划问题的求解方法[优质ppt]

4.2、内点法（内部惩罚函数法）： min F ( x, )
s.t. x S
算法： （ 1） 给 定 初 始 内 点 x (0) S ， 允 许 误 差 e>0，
障 碍 参 数 (1) ， 缩 小 系 数 b (0 ,1) ， 置 k= 1 ；
（ 2） 以 x (k1) 为 初 始 点 ， 求 解 下 列 规 划 问 题 ：
f21=subs(fx2x1); f22=subs(fx2x2); if(double(sqrt(f1^2+f2^2))<=0.002)
a(k+1)=double(x1);b(k+1)=double(x2);f0(k+1)=double(subs(f)); break; else X=[x1 x2]'-inv([f11 f12;f21 f22])*[f1 f2]'; x1=X(1,1);x2=X(2,1); end end if(double(sqrt((a(k+1)-a(k))^2+(b(k+1)b(k))^2))<=0.001)&&(double(abs((f0(k+1)-f0(k))/f0(k)))<=0.001) a(k+1) b(k+1) k f0(k+1) break; else m(k+1)=c*m(k);
min f ( x ) ( k ) B ( x )
s.t. x S
， 令 x (k) 为 所 求 极 小 点
（ 3） 如 果 (k)B (x (k) ) e ， 则 停 止 计 算 ， 得 到 结 果x (k) ，
(k 1) b (k )

一维搜索

一维搜索
种简单的曲线逼近本来的函数曲线，通过求逼近函数的极 小点来估计目标函数的极小点。
这两类方法一般只能求得极小点的近似值。
3.一维搜索的基本框架
一维搜索实际上是一元函数的极值问题，其基本的解决框 架是:
（1）确定包含最优解的初始搜索区间；
（2）采用某些区间分割技术或插值方法不断缩小搜索区 间，最后得到解。
5
0.056 0.348 0.168 0.236 -1.112 -1.125
6
0.168 0.348 0.236 0.279 -1.125 -1.123
7
0.168 0.279
函数逼近法
函数逼近法
谢谢！
一维搜索
一.一维搜索的基本概念 二. 试探法 三.函数逼近法
一维搜索的基本概念
一维搜索的基本概念
一维搜索的基本概念
2.一维搜索的方法有哪些？
一维搜索的方法有很多大体可以分成两类： 一类是试探法。采用这类方法，需要按照某种方式找
试探点，通过一系列试探点来确定极小点。 另一类是函数逼近法，或称插值法。这类方法是用某
确定初始区间
确定初始搜索区间的进退法
单峰函数的定义
缩小搜பைடு நூலகம்区间
下面定理表明，对单峰函数，可以通过简单地比较函数值，缩小搜索 区间。 定理：
试探法
一维搜索常见方法中0.618法，Fibonacci法，二分法等基本 思想都是通过取试探点并进行函数值比较，然后不断缩小搜索 区间，当区间长度缩到一定程度后，区间内各点均可作为近似 解。这类方法仅需计算函数值，十分简便，尤其适合于非光滑 及导数表达式复杂或写不出的情形，用途广泛。 这里主要介绍0.618法。
试探法
试探法
试探法

非线性规划

非线性规划
标函数曲线上的3点 (x1 f1) (x2 f2) (x3 f3) 作为二次插值
多项式 p(x) ax2 bx c 的插值结点。 这里a b c为待定系数.可用下述线形方程组确定.
p(x1 ) ax12 bx1 c f1
p(x2 )

axBiblioteka 2 2 bx2c

f2
p(x3 ) ax32 bx3 c f3
x1 a
计算函数值
x3 x3 b
x2

1 2
( x1

x3 )
f1 f (x1) f2 f (x2 ) f3 f (x3 )
ⅲ插值计算
x
* p
(a)若分母为零即 (x2 x3 ) f1 (x3 x1) f2 (x1 x2 ) f3 0 即
f2 f1 f3 f1 则说明三个插值点(x1, f1) (x2, f2 ) (x3, f3)在同一
向量化表示
令
g( x) ( g1 ( x),..., g p ( x))T
h( x) (h1 ( x),..., hp ( x))T ，
其中， g : R n R p , h : R n Rq ，那么(MP)可简记为
min f ( x)

s.t .

g(x) 0 或者min f ( x) x X
x b 2a
x*p

1 2
(x22 x32 ) f1 (x32 x12 ) f2 (x12 x22 ) f3 (x2 x3 ) f1 (x3 x1 ) f2 (x1 x2 ) f3
c1

f3 x3
f1 x1
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

长度为 3 的区间缩短到 1 需要插入 3 个点。 长度为 2 的区间缩短到 1 需要插入 2 个点。
F2 =2：插入 2 个点可使长度缩短为 1 的最大原区间长度为 2
长度为 4 的区间需要插入几个点才能缩短为 1? 对称搜索法
中间点 ①
0
1 4
3 4
4
3 区间缩小为 3，然后可采取长度为 3 的插入方法再插入3个点
0
0
一维搜索
F ( ) 考虑一元函数极小化问题： min R
思想: 首先定出一个包含 F ( ) 的极小点的区间，然后不 断缩小区间的长度，当区间充分小时，取其中的一点 作为近似极小点。
主要方法：（1）斐波那契法 （2）0.618法
一、斐波那契法（分数法）
设 y=f(x) 是区间 [a , b] 上的下单峰函数，在此区间 内，有唯一极小点 t *。
6. 算法步骤 第一步： 确定试点的个数 n 。 根据相对精度δ的要求，利用公式（1/Fn≤δ）算出 Fn，然后根 据斐波那契数表确定最小的试点个数 n 。 例1 试用斐波那契法求函数 f(t)= t2 – t + 2的近似极小点和极小值 ，要求缩短后的区间长度不大于区间 [-1 , 3] 的 0.08 倍。
斐波那契数
6 13 7 21 8 34 9 55 10 89 11 144 12 233
2. 缩短率 最大长度为 Fn 的区间经过插入 n 个点并比较其函数值后可缩短为 1 ，称 1 / Fn 为最大缩短率。
3. 相对精度 区间 [a0 , b0] 插入 n 个点并比较其函数值后缩短为[an-1,bn-1]，如要 求缩短后的区间 [an-1,bn-1] 不长于原来区间 [a0,b0] 的 δ 倍， δ 称为区间 缩短的相对精度。 b a (b a )
长度为 8 的区间缩短到 1也只需要插入 5 个点。
长度为 4 的区间缩短到 1 需要插入 4 个点。 长度为 5 的区间缩短到 1 需要插入 4 个点。 长度为 6 的区间缩短到 1 需要插入 5 个点。 长度为 7 的区间缩短到 1 需要插入 5 个点。 长度为 8 的区间缩短到 1 需要插入 5 个点。
例1 试用斐波那契法求函数 f(t)= t2 – t + 2的近似极小点和极小值 ，要求缩短后的区间长度不大于区间 [-1 , 3] 的 0.08 倍。 解：根据二阶条件，f(t) 的海赛矩阵 H(t) 为 H ( t ) 2
a
a1
b1
b
第二次在新的 [a,b] 内插入一点同 上次保留下来的点值 比较，从而使搜索区 间进一步缩小：
假设f(a2) >f(b2)
a
a2 b2 a
b
第三次在新的 [a,b] 内插入一点同 上次保留下来的点值 比较，从而使搜索区间 进一步缩小：
假设f(a3) <f(b3)
a3 b3 b
a 4 b4
第四次在新的 [a,b] 内插入一点同 上次保留下来的点值 比较，从而使搜索区间 进一步缩小：
假设f(a4) >f(b4)
a
b
按照上述方法，随着计算函数值次数的增加，区间变得越 来越小，从而越接近极小点。 因此：区间缩短率和函数值计算次数之间存在一定的关系。
下面来讨论区间缩短率和函数值计算次数之间的关系。
F4 =5：插入 4 个点可使长度缩短为 1 的原区间最大长度为 5 。 F5 =8：插入 5 个点可使长度缩短为 1 的原区间最大长度为 8 。
F0=1 小结： F =1 1 F2=2 F3 =3 F4=5 F5=8
n Fn 0 1 1 1 2 2 3 3 4 5 5 8
Fn=Fn-1+Fn-2，n≥2
因要求缩短后的区间[an-1,bn-1]不长于原来区间[a0,b0]的 0.08 倍 ，故δ= 0.08 。 1 1 1 Fn 12.5 Fn 0.08
查斐波那契数表，可知 n=6 。
n Fn 0 1 1 1 2 2 3 3 4 5 5 8 6 13 7 21 8 34 9 55 10 89 11 144 12 233
区间 [a , b] 上的上单峰函数。
在区间 [a , b]内任取两点 a1 和 b1 ，a1 < b1，并计算函数值 f(a1) 和 f(b1)，可能出现两种情况： f(a1) ≥ f(b1)， f(a1) < f(b1)， a1一定在 t*的左端 。 b1一定在 t*的右端。
f(x)
X R

0
p0 X 0
X 0 p0
一维搜索性质：在搜索方向上所得到的最优点处的梯度和该 搜索方向正交。
min F ( )
Rபைடு நூலகம்
min f (X) n
X R
p1 f ( X 1 )
X X 1 p
2
1
1
p f ( X ) 搜索方向
0 0
X0
1
0
0
0
X 0 0 p 0 X 1
第三步：计算函数值 f(t1) 和 f(t’1)，并比较它们的大小。
Fn-2
) 若 f ( t1 ) f ( t 1
Fn-3
t2
t1 中间点 t1 2
a0
] [a1 , b1 ] [a0 , t1
) 若 f ( t1 ) f ( t 1
中间点
b0
Fn 2 t 2 b1 (a1 b1 ) Fn1
长度为 4 的区间缩短到 1 需要插入 4 个点。 长度为 3 的区间缩短到 1 需要插入 3 个点。 F3 =3：插入 3 个点可使长度缩短为 1 的最大原区间长度为 3
长度为 5 的区间需要插入几个点才能缩短为 1？
中间点
对称搜索法
①
0
2 5
3 5
5
3 区间缩小为 3，然后可采取长度为 3 的插入方法再插入3个点
第六章 非线性规划
第二节 一维搜索
在迭代法中确定搜索步长 需要一维搜索： 一维搜索要求沿射线 X(k+1)=X(k)+ λkP(k) 搜索，使目标函数 f(X) 极小：
k： min f ( X ( k ) P ( k ) )

R
一维搜索是求解一元函数的无约束极值问题 min F ( ) 的数值解法。它是求解n元函数的无约束极值问题 的重要组成部分。 min f ( X ) n
n1 n1
1 Fn
bn1 an1 b0 a0
0
0
4. 绝对精度 区间 [a0 , b0]，插入 n 个点并比较其函数值后缩短为[an-1,bn-1]，其长度不长于 η ，η 称为区间缩短的绝对精度。 bn-1-an-1≤ η
5. 相对精度和绝对精度的关系
η = (b0-a0)δ
第二步：选取前两个试点的位置。
Fn-2
Fn-1
t1 中间点 t1
a0
Fn-1 Fn Fn-2
b0
t1 a0 t a 1 0
Fn 2 Fn1 (b0 a0 ) b0 (a0 b0 ) Fn Fn Fn1 (b0 a0 ) Fn
长度为 5 的区间缩短到 1 也只需要插入 4 个点。 长度为 6 的区间需要插入几个点才能缩短为 1?
中间点 ①
0
2 6
4 6
6
4 区间缩小为 4，然后可采取长度为 4的插入方法再插入4个点
长度为 6 的区间缩短到 1 需要插入 5 个点。
长度为 7 的区间需要插入几个点才能缩短为 1？
中间点 ①
0
a1
b1
2
[a,b1] [a1,b] [a,b1]+[a1,b] > [a,b] 说明缩小后的区间一般要大于原区间的一半
但是可以把计算函数值的点选得尽量靠近[a,b]的中点，对于长度为2 的单位长度的区间，缩短后的区间长度等于单位长度的（1+ε）倍， 从而使缩短后的区间长度接近于1个单位长度。
对称搜索法
在区间 [a1 , b] 内
只要在区间 [a , b]内任取两个不同点，并算出它们的函数值 加以比较，就可以把搜索区间缩小为 [a1 , b] 或 [a , b1] 。 要进一步缩小搜索区间，只需在缩小后的区间内再取一点 ，并与 f(a1)或 f(b1)比较函数值大小。 第一次插入两个点： 假设f(a1) < f(b1)
Fn-3 Fn-2
t1 t2
Fn-1
t1中间点 t1 2
t2
a0
[a1 , b1 ] [t1 , b0 ]
中间点
b0
t 2 t1
Fn 2 a1 t2 (b1 a1 ) Fn1
Fn-1
第四步：计算函数值 f(t3) 或 f(t’3)，并比较大小，如此迭代。
f ( X 2 ) f ( X 1 ) f ( X 0 )
0 0 min f ( X p ) f ( X ) f ( X 0 p ) 0 min F0 ( )
f (X k )
Xk X
f ( X 2 ) f ( X 1 1 p1 ) min f ( X 1 p1 ) min F1 ( ) 0
0
中间点 ② ①
a1 中间点-ε
中间点+ε
b1
2
[a,b1]
[a1,b]
ε足够小，缩小后的区间可接近原区间的一半
长度为 2 的区间缩短到 1 需要插入 2 个点。
长度为 3 的区间需要插入几个点才能缩短为 1？ 对称搜索法
中间点 中间点 ①
0
②
1 ③ 3
2 3
3
2 区间缩小为 2，可采取区间长度为 2 的插入方法 缩小后的区间可接近 1