当前位置：文档之家 › 11《运筹学》(第四版)非线性规划变尺度法

11《运筹学》(第四版)非线性规划变尺度法

  • 格式：pdf
  • 大小：1.85 MB
  • 文档页数：38

下载文档原格式

  / 38

合集下载

非线性规划

非线性规划

1. 非线性规划我们讨论过线性规划,其目标函数和约束条件都是自变量的线性函数。

如果目标函数是非线性函数或至少有一个约束条件是非线性等式(不等式),则这一类数学规划就称为非线性规划。

在科学管理和其他领域中，很多实际问题可以归结为线性规划，但还有另一些问题属于非线性规划。

由于非线性规划含有深刻的背景和丰富的内容，已发展为运筹学的重要分支，并且在最优设计,管理科学,风险管理,系统控制,求解均衡模型,以及数据拟合等领域得到越来越广泛的应用。

非线性规划的研究始于三十年代末,是由W.卡鲁什首次进行的，40年代后期进入系统研究，1951年.库恩和.塔克提出带约束条件非线性规划最优化的判别条件,从而奠定了非线性规划的理论基础,后来在理论研究和实用算法方面都有很大的发展。

非线性规划求解方法可分为无约束问题和带约束问题来讨论，前者实际上就是多元函数的极值问题，是后一问题的基础。

无约束问题的求解方法有最陡下降法、共轭梯度法、变尺度法和鲍威尔直接法等。

关于带约束非线性规划的情况比较复杂，因为在迭代过程中除了要使目标函数下降外，还要考虑近似解的可行性。

总的原则是设法将约束问题化为无约束问题；把非线性问题化为线性问题从而使复杂问题简单化。

求解方法有可行方向法、约束集法、制约函数法、简约梯度法、约束变尺度法、二次规划法等。

虽然这些方法都有较好的效果，但是尚未找到可以用于解决所有非线性规划的统一算法。

非线性规划举例[库存管理问题] 考虑首都名酒专卖商店关于啤酒库存的年管理策略。

假设该商店啤酒的年销售量为A 箱,每箱啤酒的平均库存成本为H 元,每次订货成本都为F 元。

如果补货方式是可以在瞬间完成的,那么为了降低年库存管理费用,商店必须决定每年需要定多少次货,以及每次订货量。

我们以Q 表示每次定货数量,那么年定货次数可以为QA,年订货成本为Q A F ⨯。

由于平均库存量为2Q,所以,年持有成本为2Q H ⨯,年库存成本可以表示为:Q HQ A F Q C ⨯+⨯=2)( 将它表示为数学规划问题:min Q H Q A F Q C ⋅+⋅=2)( ..t s 0≥Q其中Q 为决策变量,因为目标函数是非线性的,约束条件是非负约束,所以这是带约束条件的非线性规划问题。

非线性规划管理运筹学李军

非线性规划管理运筹学李军

2024/10/16
9
1.3 非线性规划问题的图示
x2 6
3 2
0
23
f(X)=4 f(X)=2
x1 6
由左图可见,等值线 f (X)=2和约束条件直 线6-6相切，切点D即
为此问题的最优解， X*=(3, 3)，其目标函 数值 f (X*)=2。
2024/10/16
10
1.3 非线性规划问题的图示
lim ( X (k) X ) 0
k
则称X*为最优解。
2024/10/16
34
3.2 下降迭代算法
基本问题： 递推步骤的有限性，一般说很难得到精
确解，当满足所要求的精度时即可停止迭 代而得到一个近似解。
2024/10/16
35
3.2 下降迭代算法
下降算法： 若产生的解序列{X(k) }能使目标函数f (X(k)) 逐步减少，就称此算法为下降算法。“下 降”的要求很容易满足，因此它包括了很 多具体的算法。
2024/10/16
30
3. 凸规划
凸规划的定义 下降迭代算法
2024/10/16
31
3.1 凸规划的定义
考虑非线性规划：
min f (X ), X En g j (X ) 0,( j 1,2,,l)
假定其中 f (X)为凸函数， g j (X)为凹函 数（- g j (X)为凸函数），这样的非线性规 划称为凸规划。
凹函数
24
非凹非凸函数示意图
f (X) f (X(1)) f (X(2))
2024/10/16
X(1)
X(1) +(1-)X(2)
X(2)
X
非凸非凹函数
25

高级运筹学-非线性规划

高级运筹学-非线性规划
目标函数或约束函数中至少有一个是非线性的

应用背景
–有着最广泛的应用，应该说所有现实问题都是非线 性的，线性模型都是经过简化而来的。机械、电子 等行业的器件最优设计问题，如飞行器的结构优化。
决策论（decision theory)
著名经济学家西蒙有一句名言：“管理就
模型是现实的近似表达，要能抓住决策
问题的关键，在真实性和可用性之间取 得适当的平衡。
运筹学的分支

数学规划
– 线性规划 √ – 非线性规划 – 整数规划 √ – 动态规划





图与网络流 √ 网络计划 库存论 排队论 对策论 决策论 。。。。。
优化问题的分类

确定性、静态优化问题
1.1 相关的数学知识
四、Hessian 矩阵（二阶导数矩阵） 几个常用的公式 五、正定矩阵 定义 正定二次函数 六、多元函数的Taylor展开
Transportation Science
运筹学软件

LINDO是一种专门用于求解数学规划问题的软件包。由于 LINDO执行速度很快、易于方便输入、求解和分析数学规 划问题。因此在数学、科研和工业界得到广泛应用。 LINDO主要用于解线性规划、非线性规划、二次规划和整 数规划等问题。也可以用于一些非线性和线性方程组的求 解以及代数方程求根等。LINDO中包含了一种建模语言和 许多常用的数学函数，可供使用者建立规划问题时调用。 一般用LINDO（Linear Interactive and Discrete Optimizer） 解决线性规划（LP—Linear Programming）。整数规划（ IP—Integer Programming）问题。其中LINDO 6 .1 学生版 至多可求解多达300个变量和150个约束的规划问题。其正 式版（标准版）则可求解的变量和约束在1量级以上。

运筹学(第四版)清华大学出版社《运筹学》教材编写组-第3章

运筹学(第四版)清华大学出版社《运筹学》教材编写组-第3章

第2节 改进单纯形法
由此得到新的基
B2 P 1 ,P 4 ,P 2 1 P 4 1 0
主元素
1 B2 E2 B11
0 1 1 2 4 E2 4 1 0 0 0 0 0 1 0 1 / 2 1 4 1 0 0 1 0 0 0 1 0 0 1/ 4 0 1 0 1 / 2 2 1/ 4
清华大学出版社
19
第2节 改进单纯形法
而后以第2列的
(1) a22
为主元素，进行变换
(1) 12 (1) 22
a / a (1) 1 / a22 (1) P2 2 (2) (1) (1) am 2 / a22
20
清华大学出版社
第2节 改进单纯形法
二 线性规划与目标规划
第 1 章
第2章
第3章 第4章
线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 目标规划
1
清华大学出版社
第3章 对偶理论和灵敏度分析
第1节
单纯形法的矩阵描述 第2节 改进单纯形法 第3节 对偶问题的提出 第4节 线性规划的对偶理论 第5节 对偶问题的经济解释——影子价格 第6节 对偶单纯形法 第7节 灵敏度分析 第8节* 参数线性规划
12
清华大学出版社
第1节 单纯形法的矩阵描述
单纯形表中的数据
基变量 非基变量 等式右边
XB
系数矩阵
XN B 1N1
1
Xs B 1
1
RHS B 1b CB B b
13
检验数
B B 1 0
1
C N1 C B B N 1 C B B

运筹学(第四版)：第4章 目标规划

运筹学(第四版)：第4章 目标规划

目标函数：
min
z
P1d1
P2
(d
2
d2 )
P3d3
2x1 x2 11
x1
x2
d1
d1
0
满足约束条件：
x1
2x2
d2
d
2
10
8x1
10x2
d3
d3
56
x1, x2, di, di 0, i 1,2,3
10
第1节 目标规划的数学模型
目标规划的一般数学模型为
L
K
目标函数： min z
0
(4,3)
4
第1节 目标规划的数学模型
实际上，工厂在作决策时，需要考虑包括市场因素在内 等一系列条件。例如:
(1) 根据市场信息，产品Ⅰ的销售量有下降的趋势，因而希望产 品Ⅰ的产量不应大于产品Ⅱ。
(2) 应尽可能充分利用设备台时，但不希望加班。 (3) 应尽可能达到并超过计划利润指标：56元。
5
第1节 目标规划的数学模型
这样的产品决策问题便构成了一个多目标决策问题，目 标规划方法正是解这类决策问题的方法之一。下面引入 与目标规划模型有关的概念。
1.设x1，x2为决策变量，引入正、负偏差变量d+，d−。 正偏差变量d＋表示决策值超过目标值的部分； 负偏差变量d−表示决策值未达到目标值的部分。
13
第2节 解目标规划的图解法
例3 某电视机厂装配黑白和彩色两种电视机，每装配一台电 视机需占用装配线1小时，装配线每周计划开动40小时。预 计市场每周彩色电视机的销量是24台，每台可获利80元；黑 白电视机的销量是30台，每台可获利40元。该厂确定的目标 为：
第一优先级：充分利用装配线每周计划开动40小时； 第二优先级：允许装配线加班；但加班时间每周尽量不超过10小

运筹学非线性规划

运筹学非线性规划

二 、模型的解及相关概念
1.可行解与最优解
★可行解：约束集D中的X。
★最优解：如果有 X * D，对于任意的 X D ， 都有 f ( X *) f ( X ) ，则称 X *为（NLP）的最优
解，也称为全局最小值点。
★局部最优解：如果对于 X 0 D ，使得在 X 0的邻 域 B(X 0, ) {X |P X X 0 P } 中的任意 X D 都有f (X 0 ) f (X ) ，则称 X 0 为（NLP）的局部最
: 风险系数；ij : 第i种与第j种股票收益的协方差
n
nn
max f (x) j xj
xi x j
j 1i1 j1源自s.t.n j 1Pj x j
B
x
j
0
2.模型
min f ( X )
(
NLP
)s.t.
hi
g
( X ) 0,i j ( X ) 0,
1,L , j 1,L
f
(X
)＝f
(X0
)
f
(X0
)（T X－X0）
1 2
(X
X0
)T
H
( X0 )(
X
X0)
o(P X－X 0 P2)
其中：o(P X
X0
P2 )是当X
X
时
0
PX
X0
P2
的高阶无穷小。
例2：写出 f ( X ) 3x12 sin x2 在X 0 [0, 0]T 点的二阶泰勒展开式
解: f ( X ) [6x1 cos x2 ]T , f ( X 0 ) [0 1]T
0
解得：＝－f (Xk )T Pk
PkT H ( X k )Pk

非线性规划

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

09《运筹学》(第四版)非线性规划一维搜索

水电与数字化工程学院 莫 莉
4.2 一维搜索方法
1 绝对误差 X
( k 1 )
0
2 0 相对 ( k ) X
(k )
f ( X ( k 1 ) ) f ( X ( k ) ) 2
3 4
30 f ( X )的模 f ( X ） 5
第二章 非线性规划(Nonlinear Programming)
主讲人：莫 莉
moli@ 2015 年 5 月
水电与数字化工程学院 莫 莉
前节回顾
非线性规划：目标函数和约束条件中至少有一个 是x的非线性函数。
非线性规划的数学模型也可以表示为：
min f ( X ), X E n
水电与数字化工程学院
莫 莉
前节回顾
温
基本概念 最优性条件
故
如何求解
知
新
下降迭代算法 斐波那契法 黄金分割法
凸函数和凸规划
水电与数字化工程学院
莫 莉
第二章 非线性规划
1 2 3 4 5 6
水电与数字化工程学院
基本概念 最优性条件 凸函数和凸规划 一维搜索方法★ 无约束最优化方法 约束最优化方法
水电与数字化工程学院 莫 莉

4.3 斐波那契法
斐波那契法的步骤
第1步 根据缩短率δ，计算Fn ，求出最小的n。
第2步 由前面公式求前两个测试点 t1 和 t1 ) 第3步 计算 f (t1 ) 和 f (t1
)，则 a1 : a0 , b1 : t1 , t2 : t1 若f ( t 1 ) f ( t 1 Fn 2 并且令 t 2 b1 (a1 b1 ) Fn1 )，则 t1 : a1 , b1 : b0 , t 2 : t1 若f ( t1 ) f ( t1 Fn 2 a1 并且令 t 2 (b1 a1 ) Fn1 水电与数字化工程学院

13《运筹学》(第四版)非线性规划罚函数法


f ( X (0) ) (4)2 (4)2 32
2
所以X(0)不是(近似)极小点。
水电与数字化工程学院 莫 莉
6.4 可行方向法
现取搜索方向
从而
X
(1)
D(0) f ( X (0) ) (4, 4)T
X
(0)
λD
(0)
0 4 4λ λ 0 4 4λ
水电与数字化工程学院 莫 莉
前节回顾
5、二次规划的转化：
对二次规划问题进行修正，从而得到如下线性规划问题：
min
(Z ) z j
j 1
n
a
i 1 n
m
ij
yn i y j c j k xk sgn(c j ) z j c j , j 1, 2,
其最优解为：y1 2, y2 3/10, y3 4 /10, y4 y5 y6 0, y7 17 /10
y3 4 /10 ，搜索方向 从而得到，
D
水电与数字化工程学院

,l

(6) 令
X ( k 1) X ( k ) λ k D ( k ) k : k 1
转回第(2)步。
水电与数字化工程学院 莫 莉
6.4 可行方向法
例 用可行方向法解下述非线性规划问题
2 max f ( X ) 4 x1 4 x2 x12 x2 x1 2 x2 4
易见在r的边界上即至少有一个根据上述分析即可将非线性规划73式转化为一系列无约束极小化问题其中831832834833出发按无约束极小化方法对831式进行迭代在进行一维搜索时要适当控制步长以免迭代点跑到r的逐步减小即障碍项所起的作用也越来越小因而求出的也逐步逼近原问题83式的极小解若原来问题的极小解在可行域的边界上则随着r的的减小障碍作用逐步降低所求出的障碍函数的极小解不断靠近边界直至满足某一精度要求为止

非线性规划方法


➢（2）简记形式： 引入向量函数符号：
h( x)(h1( x), ,hq ( x))T g( x)( g1( x), ,g p( x))T
X
x
Rn
gi ( x) 0, i hi ( x) 0, j
1, 1,
, p , q
min f ( x)
s.t .
gi ( x) 0, i 1, , p
定义 对于非线性规划（MP）, 若x* X , 并且存在x*的邻域
N ( x* ) x Rn x x* 使
f ( x* ) f ( x)，xN ( x* ) X 则称 x* 是(MP)的局部最优解或局部极小解,
称f ( x* )是（MP）的局部最优值或局部极小值
如果有 f ( x* ) f ( x)，xN ( x* ) X , x x* 称x*是（MP）的严格局部最优解或严格局部极小点 f ( x* )是（MP）的严格局部最优值或严格局部极小值。
例1 min f(x1,x2)=-2x1-6x2+x12-2x1x2+2x22
s.t. x1+x2≤2
-x1+2x2≤2
x1≥0, x2≥0
1、写成标准形式：min
z
(
x1,
x2
)
1 1
-21
x1 x2
2 6
T
x1 x2
2、 输入命令：
s.t.
1 1
21
x1 x2
2 2
0 0
x1 x2
{xk}有限
{xk}无限
{xk}的最后一点为最优解
{xk}收敛于最优解
➢迭代格式
xk pk
xk+1
x k
xk1 xk xk
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

取 p k f ( x k )
x k 1 x k k p , k : k 1, 第2步。
用最速下降法求得最优解是目标函数的一个驻点。
水电与数字化工程学院 莫 莉
0 k
前节回顾
共轭梯度法的步骤
第1步 选取初始点x0,给定终止误差 ε>0； 第2步 计算
f ( x 0 ) 若 || f ( x 0 ) || ，停止迭代，
前节回顾
定理 1 设 f : R n R 在点 x R n 处可微。若存在 p R n ，使 f ( x )T p 0 则向量 p 是 f 在点 x 处的下降方向。
定理 2 设 f : R n R 在点 x R n 处可微。若 x * 是(UMP)的局部最 优解，则 f ( x * ) 0
对于非二次函数，仿照二次函数的情形 ，要求其海赛矩阵的逆 阵的第 k + 1 次近似矩阵 H ( k 1) 满足
( k 1) (k ) X ( k 1) X ( k ) H ( k 1) f ( X ) f ( X )
此式就是拟牛顿条件。若令
(k ) ( k 1) ) f ( X ( k ) ) G f ( X (k ) ( k 1) (k ) X X X
莫 莉
故
水电与数字化工程学院
前节回顾
于是
T 2 5 12 26 38 , 4 17 6 17 17
X
(1)
X
(0)
Hale Waihona Puke λ0 P(0)f ( X (1) ) (6 /17,12 /17)T
6 12 6 /17 , (1) T (1) f ( X ) f ( X ) 17 17 12 /17 1 0 f (X (0) )T f ( X (0) ) 289 12 (12,6) 6
这就是说，应使
(Q( k ) )T G ( k ) (W ( k ) )T G( k ) 1
由于 H (k)
应为对称阵，最简单的办法就是取
(k ) (k ) Q k X (k ) (k ) (k ) W k H G
由此可得
k (X ( k ) )T G( k ) k (G( k ) )T H ( k ) G( k ) 1
见教材详细步骤，最终得最优解 水电与数字化工程学院 ：
莫 莉
无约束问题最优性条件
二分法
前节回顾
确定有根区间，将区间二等分，通过判断F(x)的符号 和单调性，逐步将有根区间缩小，直至有根区间在 所求范围内，便可求出满足精度要求的近似根。 对于在区间[a,b]上连续不断，且满足f(a)f(b)<0的函 数y=f(x)，通过不断地把函数f(x)的零点所在的区间 二等分，使区间的两个端点逐步逼近零点，进而得 到零点近似值的方法叫做二分法。
f ( X ( k 1) ) f ( X ( k ) ) A( X ( k 1) X ( k ) )
或
( k 1) (k ) X ( k 1) X ( k ) A1 f ( X ) f ( X )
水电与数字化工程学院
莫 莉
5.6 拟牛顿法
矩阵及其求逆过程，又比最速下降法的收敛速度快，特别
是对高维问题具有显著的优越性，因而使变尺度法获得了
很高的声誉，至今仍被公认为求解无约束极值问题最有效 的算法之一。
水电与数字化工程学院
莫 莉
5.5 牛顿法
设目标函数f(X)二阶连续可微.
基本思想：用 f(X)在探索点X(k)处的二阶Taylor展开 式近似替代。
H ( k ) X ( k ) (Q( k ) )T H ( k ) G ( k ) (W ( k ) )T
式中 Q( k ) 和 W ( k ) 为两个待定向量。
水电与数字化工程学院 莫 莉
5.6 拟牛顿法
将表达式代入得
X ( k ) (Q( k ) )T G ( k ) H ( k ) G ( k ) (W ( k ) )T G ( k ) X ( k ) H ( k ) G ( k )
第二章 非线性规划(Nonlinear Programming)
主讲人：莫 莉
moli@
2015 年 5 月
水电与数字化工程学院 莫 莉
前节回顾
温
最速下降法
故
无约束优化
知
牛顿法
新
共轭方向法
共轭梯度法
拟牛顿法
DFP变尺度法
水电与数字化工程学院
莫 莉
无约束问题最优性条件
H ( X ( k ) )1 f ( X ( k ) )
为搜索方向，即
P ( k ) H ( X ( k ) ) 1 f ( X ( k ) ) ( k 1) X (k ) λk P(k ) X (k ) (k ) λ : min f ( X λ P ) k λ
按照上述方法求函数f(X) 的极小点的方法，称作牛顿法。
水电与数字化工程学院 莫 莉
5.6 拟牛顿法
P ( k ) H ( X ( k ) ) 1 f ( X ( k ) ) ( k 1) X (k ) λk P(k ) X (k ) (k ) λ : min f ( X λ P ) k λ
水电与数字化工程学院 莫 莉
5.5 牛顿法
如果f(X)是二次函数，则H(X)为常数阵。这时，近似式是准确的。在这种情 况下，从任一点X(k)出发，只要一步即可求出f(x)的极小点。
当f(X)不是二次函数时，近似式仅是f(X)在X(k)点附近的近似表达式。这时，
按(求得的极小点，只是f(X)的极小点的近似。在这种情况下，常取
( k 1) 应满足拟牛顿条件，即要求 上式中 H ( k ) 为第k次校正矩阵，H
X ( k ) ( H ( k ) H ( k ) )G ( k )
或
H ( k ) G ( k ) X ( k ) H ( k ) G ( k )
(k ) 由此可以设想 H
的一种较简单形式为
输出x 0，否则转第3步；
0 0 取 p f ( x )，令k : 0; 第 3步
第4步 进行一维搜索，求 λk使得
f ( x k k p k ) min f ( x k p k )
t 0
令xk 1 xk k p k；
水电与数字化工程学院
莫 莉
前节回顾
第5步 计算 f ( x k 1 ) 若 || f ( x k 1 ) || ，停止迭代，
f (X ) f (X
(k )
) f ( X
(k )
1 )X X T H ( X ( k ) )X 2
用f(X)的最小点作为新的探测点。因此，
令 f ( X ) f ( X ( k ) ) H ( X ( k ) )X 0
得
X X ( k ) H ( X ( k ) )1 f ( X ( k ) )
输出x k 1，否则转第6步；
第6步 若k 1 n, 令x 0 : x n , 转第3步; 否则，转第7步； 第7步 用F-R公式取
p
k 1
f ( x
k 1
) k p
k
|| f ( x k 1 ) ||2 其中 k || f ( x k ) ||2
令k : k 1, 转第4步;
则拟牛顿条件变为 X ( k ) H ( k 1) G ( k ) ★拟牛顿法一般是超线性收敛的
水电与数字化工程学院 莫 莉
5.6 拟牛顿法
( k 1) (k ) (k ) ( k 1) 现设 H 已知，并用下式求 H (假定 H 和 H 都为对称正定阵)：
H ( k 1) H ( k ) H ( k )
f ( X (0) ) ( 12,6) T P (0) f ( X (0) ) (12, 6) T f ( X (0) ) T P (0) λ0 ( P (0) ) T AP (0) 12 ( 12, 6) 6 180 5 3 1 12 612 17 (12, 6) 1 6 1
水电与数字化工程学院 莫 莉
无约束问题最优性条件
二分法
前节回顾
斐波那契查找详解 /yunzhongguwu005/article/details/9341761
关于斐波那契查找， 如果要查找的记录在右侧，则左侧的数据都不用再 判断了，不断反复进行下去，对处于当众的大部分数据，其工作效率要 高一些。所以尽管斐波那契查找的时间复杂度也为O(logn)，但就平均性 能来说，斐波那契查找要优于折半查找。可惜如果是最坏的情况，比如 这里key=1，那么始终都处于左侧在查找，则查找效率低于折半查找。 还有关键一点，折半查找是进行加法与除法运算的mid=(low+high)/2）， 插值查找则进行更复杂的四则运算（mid = low + (high - low) * ((key a[low]) / (a[high] - a[low]))），而斐波那契查找只进行最简单的加减法运 算（mid = low + F[k-1] - 1），在海量数据的查找过程中，这种细微的差 别可能会影响最终的效率。
水电与数字化工程学院
莫 莉
前节回顾
例 试用共轭梯度法求下述二次函数的极小点：
f (X ) 3 2 1 2 x1 x2 x1 x2 2 x1 2 2
解：将f(X)化成二次函数的标准形式，得
3 A 1 1 1
T
现从 X (0) (2, 4)T 开始，由于
f ( X ) (3x1 x2 2), ( x2 x1 )