第五章 拟牛顿法
§5.1 拟牛顿法
牛顿法具有收敛速度快的优点，但需要计算Hesse 矩阵的逆，计算量大。本章介绍的拟牛顿法将用较简单的方式得到Hesse 矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速度，这类算法是无约束最优化问题最重要的求解方法。
一、拟牛顿条件
设()f x 在n
R 上二次可微，为了获得Hesse 矩阵2
()()G x f x =?在1k x +处的近似，先研究如下
问题。考虑()f x 在1k x +附近的二次近似：
1111111
)()()()2
()(T
T k k k k k k g x x G x f x f x x x x +++++++-+
--≈. 两边求导，有 111()()k k k g x g G x x +++≈+- 令k x x =，有 111()k k k k k g g G x x +++≈+- 再令 1k k k s x x +≈-，1k k k y g g +≈-
则有 1k k k y G s +≈ 或 1
1k k k
G y s -+≈. 因此，我们要求构造出的Hesse 矩阵的近似1k B +或Hesse 矩阵逆的近似1k H +应分别满足：
1k k k B s y += 或 1k k
k H y s += （5.1）
它们均称之为拟牛顿条件。
二、一般拟牛顿算法
1） 给出初始点0x R ∈，0H I =，0ε>，:0k =.
2） 若k g ε≤，停止；否则，计算k k k d H g =-（拟牛顿方向）.
3） 沿方向k d 进行线性搜索，0k α>（可以是精确，也可非精确）.令1k k k k x x d α+=+. 4） 校正k H 产生1k H +，使拟牛顿条件满足. 5） :1k k =+， 转2）
拟牛顿法较之牛顿法有下述优点： 1） 仅需梯度（牛顿法需Hesse 矩阵）；
2） k H 保持正定，因而方向具有下降性质（而牛顿法中k G 可能不定）； 3） 每次迭代需2()O n 次运算，而牛顿法需3()O n 次运算。
注： 正如牛顿法中牛顿方向1
k k g G --是在椭球范数k
G 下的最速下降方向一样，k k H g -也可看成
是在椭球范数1k
H - 下的最速下降方向，也就是在空间某种特定度量（尺度）意义下的最速下降方向。
由于每次迭代k H 都在变化，因而度量（尺度）也在变化。正因为如此，常称拟牛顿算法为变尺度法。从这个意义上讲，牛顿法本身也是变尺度法。
三、对称秩一校正公式（SRI 校正）
设k H 是第k 次迭代的Hesse 逆的近似，希望对k H 校正得到1k H +，即
1k k k H H E +=+
若设k E 是一个秩一矩阵，则 1T k k uv H H +=+. （5.2） 由拟牛顿条件： 1()T
k k k k k k H y H y u v y s +=+= 得 k k k T
k
s H y u v y -=
（取v ，使0T
k v y ≠） （5.3） 将（5.3）代入（5.2）得 11
()T k k k k k T
k
H H s H y v v y +=+- （5.4） 称之为一般Broyden 秩一校正公式
特别地，取k v y =时，称为Broyden 秩一校正公式。
一般地，上述1k H +不对称，由于Hesse 矩阵是对称的，故希望1k H +也对称，因而取
()k k k v s H y =-
从而得 1()()()T
k k k k k k k k T k k k k
s H y s H y H H s H y y +--=+- （5.5）
称之为对称秩一校正。对称秩一校正法在用于正定二次函数时，不需要进行一维搜索，具有有限终止性质。
定理5.1 设011,,,n s s s - 线性无关，那么对于正定二次函数，对称秩一校正方法至多1n +步终止，即1
n H G -=。
证明：首先用归纳法证明拟牛顿条件的遗传性质，即
i j j H y s = 0,1,,1j i =- 。
当1i =时，直接由（5.5）可知结论成立。若假定结论对1i ≥成立，现考虑1i +情形，此时
1()()()T i i i i i i j
i j i j T
i i i i
s H y s H y y H y H y s H y y +--=+
-
1）当j i <时，由归纳法假设，有
() 0
T T T T T i i i j i j i i j i j i j T
T i
j i
j s H y y s y y H y s y y s s Gs s Gs -=-=-=-=
故当j i <时， 1i j i j j H y H y s +==。 2）当j i =时，直接由（5.5）可得。
再根据以上所得遗传性质，有
n j j H y s =，n j j H Gs s =（0,1,,1j i =- ） 由j s 线性无关，故有n H G I =，即1
n H G -=。
注：1）证明中对i s 除了要求线性无关外，没有其他条件，因而简单取i i i s H g =-也是可以的。这样
完全不用一维搜索，并且由1
n n n n s H g G g -=-=-，得到最优解。
2）SRI 校正的缺点是不能保证k H 的正定性，除非始终保持()0T
k k k k s H y y ->。当用于一般函数时，由k k k d H g =-算出的搜索方向不能保证是下降方向，这在一定程度上妨碍了它的应用。
四、DFP 校正
考虑对称秩二校正
1T
T
k k H H auu bvv +=++ 由 1k k k H y s +=
得 T
T k k k k k H y auu y bvv y s ++=
取 k u s =，k k v H y = 即有 1T
k au y =， 1T
k b v y =-
11T T k k k a u y s y =
=，11
T T
k k k k
b v y y H y =-=- 得校正公式： 1T T
k k k k k k
k k T T
k k k k k
s s H y y H H H s y y H y +=+- （5.6） 称之为DFP 公式（由Davidon,Fletcher,Powell 提出）。DFP 公式是最重要的拟牛顿校正公式，有很多重要性质。
对于正定二次函数（若采用精确一维搜索） 1） 具有有限终止性； 2） 拟牛顿条件具有遗传性质；
3） 当0H I =时，产生共轭方向和共轭梯度。 对于一般函数
4）校正保持正定性，因而算法具有下降性质； 5）方法具有超线性收敛速度；
6）当采用精确一维搜索时，对于凸函数，算法具有总体收敛性。 定理5.2 当且仅当0T
k k s y >时，DFP 校正公式保持正定性。
证明：用归纳法。由初始选择，0H 显然正定。设结论对k 成立，即k H 正定，并记k H 的Cholesky 分解为T
k H LL =。下面考虑1k +时的情形，设
, T T k a L z b L y ==
则 221()()()[]T T T
T T
T
T T
k k k k k k k k k T
T T T k k k k k k k
H y y H s s s z a b z H z z H z z z a a y H y s y b b s y +=-+=-+ 由Cauchy 不等式知：
2
()0T T
T a b a a b b
-≥ （*）
又由题设0T
k k s y >，故有
10T k z H z +≥
由于0z ≠，而（*）中等式成立当且仅当a 与b 平行，亦即当且仅当z 与k y 平行。而当z 与k y 平行时，便有,0k z y ββ=≠。此时
22()0T T
k k k T
k k
s z s y s y β=> 因而，对任何0z ≠，均有10T
k z H z +>，定理于是证毕。 注：上面定理中，条件0T
k k s y >是可以满足的。事实上， 由 k k k d H g =-，k k k s d α=
有 0T
T
T
k k k k k k k k k s g d g g H g αα==-< （k H 正定） 而 11()T
T
T
T
k k k k k k k k k s y s g g s g s g ++=-=-。
当采用精确一维搜索时，有10T
k k g s +=，从而0T
k k s y >。
而当采用非精确一维搜索（如Wolfe-Powell 准则）时，只要适当提高搜索精度，就可使1T
k k s g +小到所要求的程度，从而有0T
k k s y >。
定理5.3 （DFP 方法的二次终止性）设()f x 是二次正定函数，若采用精确一维搜索，那么DFP 方法具有遗传性质和方向共轭性质，即对于0,1,,1i m =- ，有
1i j j H y s +=，0,1,,j i = （遗传性质）
0T
i j s Gs =，0,1,,1j i =- （方向共轭性质） 方法在1m n ≤-步迭代后终止。若1m n =-，则1
n H G -=。 证明： 对两组式子同时用归纳法证明。
当0i =时，结论显然成立。设结论对i 成立，现证明1i +时结论亦成立。注意到10i g +≠，由精确一维搜索及归纳法假设，对于j i ≤，有
1111
11
1
() 00
i
T
T
T
i j j j
k k
j k j i
i
T T T
j j k j k
j
k j k j g s g s g
g s g s y s s Gs
+++=++=+=+=+-=+
=+
=∑∑
∑
由111111i i i i i i s d H g αα++++++=-=-及j j Gs y =，得
1111110T T T i j i i i j i i j s Gs g H y g s αα++++++=-=-=
这就证明了定理中的第一组式子。下证第二组式子，即
2i j j H y s +=，0,1,,1j i =+ 。
由DFP 公式立即可得
211i i i H y s +++=
而对于j i ≤，由
110T T i j i j s y s Gs ++==
11110T T T i i j i j i j y H y y s s Gs ++++===
有 11111121111
1
11
T T i i j i i i i j
i j i j i j j T
T i i i i i s s y H y y H y H y H y H y s s y
y H y ++++++++++++++=+-
==
定理证毕。
由此定理可知，DFP 拟牛顿法是共轭方向法。若取0H I =，则初始方向为负梯度方向，此时方法变成共轭梯度法。DFP 算法是一个在理论分析和实际应用中都起重要作用的算法。
五、BFGS 校正和PSB 校正
我们知道拟牛顿条件有两个：
1k k k H y s += （Hesse 逆近似） 1k k k B s y += （Hesse 近似）
在上一段中，得到了关于k H 的DFP 校正公式：
()1
T T DFP k k k k k k
k k T T k k k k k
s s H y y H H
H s y y H y +=+- （5.7）
若在上式中实行代换：k k H B ?，k k s y ?，即可得到关于k B 的校正公式 ()
1
T T BFGS k k k k k k
k k T T k k k k k
y y B s s B B
B y s s B s +=+- （5.8）
称之为k B 的BFGS （Broyden,Flecther,Goldforb,Shanno ）校正公式。
对上式应用秩一校正的求逆公式，又得到k H 的BFGS 校正公式：
()1
(1T T T T BFGS k k k k k k k k k k k
k k T T T
k k k k k k y H y s s s y H H y s H
H s y s y s y ++=++-） （5.9a ） 2
()()()()T
T T T
k k k k k k k k k k k k k k k T T k k k k s H y s s s H y s H y y H s s s y s y -+--=+- (5.9b) ()()T T T
k k k k k k
k T T T k k k k k k
s y y s s s I H I s y s y s y =--+ (5.9c)
再将上式中k k H B ?，k k s y ?，得k B 的DFP 公式 ()
1
(1T T T T DFP k k k k k k k k k k k
k k T T T
k k k k k k s B s y y y s B B s y B
B y s y s y s ++=++-） （5.10a ） 2
()()()()T
T T T
k k k k k k k k k k k k k k k T T k k k k y B s y y y B s y B s s B y y y s y s -+--=+- (5.10b) ()()T T T
k k k k k k
k T T T k k k k k k
y s s y y y I B I y s y s y s =--+ (5.10c)
以上讨论告诉我们，对一个给定的拟牛顿校正公式1k H +，通过交换k k H B ?，k k s y ?可得到关于k B 的对偶校正()
1D k B +，再利用秩一求逆公式，又得()
1D k H +（对偶校正）。而对()
1D k H +再实施上述对偶操作，还可恢复到原来的1k H +。从这种观点看()
1
BFGS k H +是()
1
DFP k H +的对偶校正公式。
对SRI 校正公式()
1SRI k H + ()
1
()()()T
SRI k k k k k k k k T
k k k k
s H y s H y H
H s H y y +--=+- （5.11） 进行交换后得： 1()()()T
k k k k k k k k T k k k k
y B s y B s B B y B s s +--=+- （5.12）
再利用秩一求逆公式，得()
1SRI k H +的对偶仍为其自身，因而SRI 校正是自对偶的。
BFGS 校正是迄今为止最好的拟牛顿公式，它不仅具有DFP 校正所拥有的各种性质，而且当采用非精确一维搜索时，对于一般函数也具有总体收敛性，但这一结论对DFP 校正尚未获得证明。
Powell 对一般的Broyden 秩一校正公式采用对称化改造，得到了PSB 公式。其基本思想是：在一般Broyden 秩一校正公式的基础上，构造一个不断满足对称性和拟牛顿条件的矩阵序列，然后求出这个矩阵序列的极限，则该极限矩阵是一个满足对称性和拟牛顿条件的矩阵，从而产生出一个校正公式。
设n n B R ?∈是对称矩阵，令
1()T
T y Bs c C B c s
-=+
， 一般地， 1C 不一定对称，因而将其对称化，令
1122
T
C C C +=
2C 虽然对称，却不一定满足拟牛顿条件。因而重复以上过程，产生序列{}k C ：
221221
21
22()2
T
k k k T T
k k k y C s c C C c s
C C C ++++-=+
+=
可证明这个矩阵序列是收敛的，其极限为
2
()()()()T T T T
T T y Bs c c y Bs y Bs s B B cc c s c s -+--=+-
加上下标，则得到一类秩二校正公式
12
()()()()
T T T
T
k k k k k k k k k k k k k k k k T T k k k k y B s c c y B s y B s s B B c c c s c s +-+--=+- （5.13） 这个校正类包括了很多的校正公式，在（5.13）式中，若令
k k k k c y B s =-
则得到关于k B 的对称秩一校正公式（SR1公式）；若令k k c y =，则得到关于k B 的DFP 校正公式；若令 1
11
k k k k k k k w c y B s w w =
+++ 其中T T
k k k k k k w y s s B s =
，则得到关于k B 的BFGS 校正；若令k k c s =，则得到PSB 校正：
12
()()()()
T T T
T
k k k k k k k k k k k k k k k k T T k k k k y B s s s y B s y B s s B B s s s s s s +-+--=+- （5.14） 这个校正在理论研究和实际计算中是十分重要的，其缺点是不能保证校正矩阵的正定性。值得指出的是，通过交换k k H B ?，k k y s ?，可得到关于1k H +的类似校正公式。
前面介绍了一些拟牛顿校正公式，以及派生新的拟牛顿法校正公式的方法（如对偶方法，对称技术等）。有时候，还可利用一些特殊的附加条件推出校正公式。
1）BFGS 校正是由DFP 校正公式经过替换与秩一矩阵求逆得到的校正公式。事实上对其它校正公式也可采用类似方法获得新的校正公式，这些新的派生公式称为原公式的对偶，对偶方法是产生新校正公式的一种重要方法。若一个校正公式的对偶还等于其自身，则称之为自对偶。
2）将一般的Broyden 秩一校正公式反复采用对称化、应用秩一校正使其满足拟牛顿条件，生成一迭代序列，其极限构成一类新的秩一校正公式，而且很多常见的校正公式都含在这个类中，特别地得到PSB 校正公式。
3）有时我们得到的校正公式是一类，在这一类中通常需附加上另外的条件而得到具体的校正公式。这种附加条件有各种提法，若让1k H +（或1k B +）最靠近k H （对应地k B ），由此种条件导出的校正公式称为最小改变割线校正，一些重要的校正公式在适当选取的范数下均具有这种性质。
§5.2 Broyden 族
上节讨论的DFP 校正和BFGS 校正都是对称秩二校正，且都是通过k y ，k s ，k H 来获得校正矩阵1k H +。下面考虑DFP 与BFGS 的加权组合：
111(1)DFP BFGS
k k k H H H φφφ+++=-+ （φ是参数）
显然，这样得到的校正公式必满足拟牛顿条件。这就得到以φ为参数的一大类校正公式，称之为Broyden 族校正公式。，容易看到
111(1)DFP T BFGS T k k k k k k k H H v v H v v φφφ+++=+=+- （5.15）
其中12
()[
]T k k k
k k
k k T T
k k k k k
s H y v y H y s y y H y =-。 当0φ=时，得DFP 校正；1φ=时，得BFGS 校正；()T k k
T
k k k k
s y s H y y φ=-时，得SRI 校正；而1
1(/)
T T
k k k k k y H y s y φ=
时，得Hoshino 校正。 类似地，有关于k B 的Broyden 族校正：
111(1)DFP BFGS k k k B B B θθθ+++=+-11(1)BFGS T DFP T k k k k k k B w w B w w θθ++=+=+- （5.16）
其中12
()[
]T k k k
k k
k k T T
k k k k k
y B s w s B s s y s B s =-。 注：由于0T
k k v y =和0T
k k w s =，也可以直接验证Broyden 族校正对任意的φ和θ都满足拟牛顿条件。 Broyden 族的二次终止性和正定性
定理5.4 （Broyden 族校正二次终止性定理）设()f x 是正定二次函数，G 是其Hesse 矩阵，那么当采用精确线性搜索时，Broyden 族校正具有遗传性质和方向共轭性质，即对于0,1,,1i m =- ，有： 1i j j H y s +=，0,1,,j i = （遗传性质） 0T
i j s Gs =，0,1,,1j i =- （方向共轭性质） 方法在1m n ≤-步迭代后终止。若1m n =-，则1
n H G -=。 证明：证明与定理5.3类似，略。
定理5.5 （Broyden 族校正的正定性）设参数0φ≥，当且仅当0T
k k s y >时，Broyden 族校正公式保持正定性。
§5.3 Huang 族
Huang 族是比Broyden 族更广泛的一类校正公式。在Broyden 族中，{}k H 是对称的且满足拟牛顿条件 1k k k H y s +=。
但在Huang 族中取消了对k H 对称的限制，并将拟牛顿条件进一步放松为
1k k k H y s ρ+= （5.17）
称之为广义拟牛顿条件，其中ρ是一个参数。为了使Huang 族拟牛顿法用于二次正定函数时，所产生的搜索方向共轭，进而具有二次终止性。设Huang 族校正公式的形式为（详细分析可参见徐成贤等著《近代优化方法》或袁亚湘等著《最优化理论与方法》）：
1T T
k k k k k k k H H s u H y v +=++
其中k u ,k v 满足： 1112T k k k k u a s a H y =+，T
k k u y ρ=
2122T k k k k v a s a H y =+，1T k k v y =-
在上面的方程组中，含有三个自由参数。特别地，令1ρ=,1221a a =，则只含一个自由参数，若取11
a
为自由参数，则有：
1T T T k k k k k k
k k k k T T k k k k k s s H y y H H H v v s y y H y ?+=+-+ （5.18）
其中1
2
()[
]T k k k
k k
k k T T
k k k k k
s H y v y H y s y y H y =-，正好蜕变为Broyden 族校正公式，这表明Broyden 族是Huang 族的子族。一般地，Huang 族中含有三个自由参数，可产生丰富的校正公式。
注：1）若采用精确一维搜索，对于正定二次函数，所有Huang 族变尺度算法产生相同的迭代点列；
对一般函数产生的点列只依赖于ρ。
2) 另外，当极小化正定二次函数时，若取0H I =，则Huang 族校正公式产生的搜索方向与F-R 共轭梯度法相同，因而也是共轭方向法。
§5.4 拟牛顿法的局部收敛速度
一、一般拟牛顿算法超线性收敛的特征
假设1：1）设()f x 在开凸集n
D R ?中二阶连续可微；
2）()f x 存在一个严格局部极小点*x D ∈，且2*
()f x ?正定； 3）存在*
x 的一个邻域*
(,)N x ε，使得
22*()(), , (,)f x f x x x x x N x γε?-?≤-?∈。
定理5.6 （不带步长因子的拟牛顿算法超线性收敛的充要条件）设()f x 满足假设1中的1）与2），又设{}k B 为一非奇异矩阵序列。假定对某0x D ∈，迭代序列
11()k k k k x x B f x -+=-?
恒在D 中且*
(0)k x x k ≠?≥，又设该序列收敛于*
x 。则当且仅当
2*11[()]()
lim
0k k k k k k
B f x x x x x +→+∞
+-?-=-
时，序列{}k x 超线性收敛到*
x 。
定理5.7 （带步长因子的拟牛顿算法超线性收敛的充要条件）设()f x 满足定理5.6中的假设，又设{}k B 为一非奇异矩阵序列。假定对某0x D ∈，迭代序列
11()k k k k k x x B f x α-+=-?
恒在D 中且*
(0)k x x k ≠?≥，又设该序列收敛于*
x 。如果
2*11[()]()
lim
0k k k k k k
B f x x x x x +→+∞
+-?-=-
成立，那么序列{}k x 超线性收敛到*
x 且*
()0f x ?=的充要条件是{}k α收敛到1。 注：1）要使算法超线性收敛，步长因子k α必趋近于1；
2）拟牛顿算法超线性收敛的几何特征是：其位移k s 在长度与方向上都必趋近于牛顿方向N
k s 。 定理5.8 （基于精确搜索的拟牛顿法的超线性收敛性）设()f x 满足假设1中的1）与2），又设{}k B 为一非奇异矩阵序列。假定对某0x D ∈，迭代序列
11()k k k k k x x B f x α-+=-?
恒在D 中且*
(0)k x x k ≠?≥，又设该序列收敛于*
x 。k α由精确线性搜索产生，则当
2*11[()]()
lim
0k k k k k k
B f x x x x x +→+∞
+-?-=-
成立时，一定有1k α→和*
()0f x ?=，从而序列{}k x 超线性收敛到*
x 。
定理5.9 （基于Wolfe-Powell 准则的拟牛顿法的超线性收敛条件）设()f x 满足假设1中的1）与2），又设{}k B 为一非奇异矩阵序列。假定对某0x D ∈，迭代序列
11()k k k k k x x B f x α-+=-?
恒在D 中且*
(0)k x x k ≠?≥，又设该序列收敛于*
x 。k α由不精确线性搜索的Wolfe-Powell 准则产
生，则当
2*11[()]()
lim
0k k k k k k
B f x x x x x +→+∞
+-?-=-
成立时，一定有1k α→和*
()0f x ?=，从而序列{}k x 超线性收敛到*
x 。
二、Broyden 秩一校正的局部超线性收敛性
定理5.10 （关于Hesse 近似）设()f x 满足假设1，又设存在正常数,εδ，使得
*0x x ε-< 和 2*10(())H f x δ--?<
则由Broyden 秩一方法
111()()k k k k T k k k k k k T
k k x x B f x y B s s B B s s -++?=-???-=+??
产生的迭代序列{}k x 是有定义的，且超线性收敛到*
x 。
定理5.11（关于Hesse 逆近似）设()f x 满足假设1，又设存在正常数,εδ，使得
*0x x ε-< 和 2*0()B f x δ-?<
则由Hesse 逆Broyden 秩一方法
11
()
()k k k k T
k k k k k k T k k x x H f x s H y y H H s y ++=-???-?
=+??
产生的迭代序列{}k x 是有定义的，且超线性收敛到*
x 。
三、DFP 和BFGS 算法的局部超线性收敛性
定理5.12 设()f x 满足假设1，又设在*
x 的一个邻域内，
11
(,)3
k k x x μγσ+≤
其中，2
*1
()f x μ-=?，**
11(,)max{,}k k k k x x x x x x σ++=-- 。于是，存在0ε>和 0δ>，
使得对于 *0x x
ε-<和2*0()
DFP
B f x δ-?<，DFP 方法
1112
()()()()()k k k k T T T T
k k k k k k k k k k k k k k k k
T T k k k k x x B f x y B s y y y B s y B s s B B y y y s y s -++?=-???-+--=+-??
产生的迭代序列{}k x 是有定义的，且超线性收敛到*
x 。
类似于Hesse 近似形式的DFP 方法，可以建立对Hesse 拟近似的BFGS 方法的局部收敛性定理。 定理5.13 设()f x 满足假设1，又设在*
x 的一个邻域内，
11(,)3
k k x x μγσ+≤
其中，2
*1
()f x μ-=?，**
11(,)max{,}k k k k x x x x x x σ++=-- 。于是，存在0ε>和 0δ>，
使得对于 *0x x
ε-<和2*1
0()BFGS
H f x δ--?<，BFGS 方法
112()()()()()k k k k T
T T T
k k k k k k k k k k k k k k k k
T T k k k k x x H f x s H y s s s H y s H y s H H s s s y s y ++=-???-+--?=+-??
有定义，产生的序列{}k x 线性收敛。如果
*0
k k x x ∞
=-<+∞∑
，那么序列超线性收敛到*x 。
Byrd ，Nocedal ，Yuan 于1987证明了Broyden 族的超线性收敛性。
定理5.14 设()f x 在开凸集n
D R ?上二阶连续可微且一致凸，又存在*
x 的一个邻域*
(,)N x ε，使
得 22*
()(), , (,)f x f x x x x x N x γε?-?≤-?∈
成立。则对于任何正定矩阵0B ，当线性搜索满足Wolfe-Powell 准则时，Broyden 族算法（[0,1)θ∈，即不包含DFP 算法）所产生的极小化序列{}k x ，超线性收敛到*
x 。
定理5.15 设()f x 在开凸集n
D R ?上二阶连续可微且一致凸，又存在*
x 的一个邻域*
(,)N x ε，使
得 22*
()(), , (,)f x f x x x x x N x γε?-?≤-?∈
成立。则对于任何正定矩阵0B ，当采用精确线性搜索时，Broyden 族算法所产生的极小化序列{}k x 超线性收敛到*
x 。
§5.5 拟牛顿法的总体收敛性
一、精确搜索条件的总体收敛性
Powell 于1971年证明了当目标函数()f x 是二阶连续可微且一致凸函数时，采用精确搜索的DFP 方法的全局收敛性及2
()f x ?满足Lipschitz 条件时的超线性收敛性。1976年，证明了()f x 为凸函数时，采用Wolfe-Powell 准则的BFGS 方法的全局收敛性和超线性收敛性。1987年Byrd ，Nocedal ，Yuan 将Powell 的结果推广到除DFP 以外的所有限制Broyden 族算法（即[0,1)θ∈），证明了全局收敛性及超线性收敛性。
定理5.16 （DFP 方法的总体收敛性Powell ，1971）设()f x 在水平集0(){()()}L x x f x f x =≤上二阶连续可微且一致凸，则在精确线性搜索的条件下，DFP 方法产生的点列{}k x 收敛到极小点*
x 。 定理 5.17 设0x 和0B 为任意给定的初始点和初始正定矩阵，又设()f x 在水平集
0(){()()}L x x f x f x =≤上二阶连续可微且一致凸，则在不精确线性搜索Wolfe-Powell 准则下，
Broyden 族算法（当[0,1)θ∈时）产生的点列{}k x 收敛到极小点*
x 。
注：拟牛顿算法中Broyden 族具有二次终止性和超线性收敛性，对于中，小规模问题这是一类最有效的求解方法，但由于求解过程要存贮一个n n ?矩阵，求迭代方向要解一个线代数方程组，使算法效率受影响，而共轭梯度法克服了这些缺陷，故常称共轭梯度法是大规模无约束的最优化算法。
第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=?L L （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 {} 1()0 (1,,);()0 ,,i e i e X x c x i m c x i m m +===≥=L L ，称之为可行域（约束域）。 {}1,,e E m =L ，{}1,,e I m m +=L ，{}()()0 i I x i c x i I ==∈ 称()E I x U 是在x X ∈处的积极约束的指标集。积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x * *=U ，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。
function [a,b,n,x]=fibonacci(fname,a,b,d,L) % fname函数句柄，d辨别常数，L最终区间长度a(1)=a; b(1)=b; F=zeros(1,10); %选择fibonacci数列k值为10，可任意更改 F(1)=1; F(2)=2; for k=2:10 %k取到10，生成fibonacci数列 F(k+1)=F(k)+F(k-1); F(k); end Fn=(b(1)-a(1))/L; Fk=[F Fn]; N=sort(Fk); n=find(Fn==N); %查找计算函数值的次数n t(1)=a(1)+F(n-2)*(b(1)-a(1))/F(n); %计算试探点t(1),u(1) u(1)=a(1)+F(n-1)*(b(1)-a(1))/F(n); for k=1:n-2 ft=feval(fname,t(k)); fu=feval(fname,u(k)); if ft>fu a(k+1)=t(k); b(k+1)=b(k); t(k+1)=u(k); u(k+1)=a(k+1)+F(n-k-1)*(b(k+1)-a(k+1))/F(n-k); while k==n-2 t(n)=t(n-1); u(n)=t(n-1)+d; ft=feval(fname,t(n)); fu=feval(fname,u(n)); if ft>fu a(n)=t(n); b(n)=b(n-1); else a(n)=a(n-1); b(n)=t(n); end end else a(k+1)=a(k); b(k+1)=u(k); u(k+1)=t(k); if k~=n-2 t(k+1)=a(k+1)+F(n-k-2)*(b(k+1)-a(k+1))/F(n-k); ft=feval(fname,t(k));
优化理论与方法
全局及个性化web服务组合可信度的动态规划评估方法 摘要：随着Internet的快速发展,web服务作为一种软件构造形式其应用越来越广泛。单个web服务无法满足日益复杂的用户需求,web服务组合有效地解决了这个问题。然而,随着功能相似的web服务实例的不断出现,如何选择可信的web服务组合成为了人们关注的热点。服务选择依赖于web服务组合的评估结果,因此,本文主要从web服务组合着手,对其可信性进行研究,提供一种可信web服务组合评估方法。：针对web服务组合的全局及个性化问题,提出了基于全局的个性化web服务组合可信评估方法。从全局角度动态地调整评估模型;同时引入用户业务关注度来描述原子web服务对服务组合可信性的影响程度;结合前文的度量及评估方法,构建一个全局的个性化服务组合可信评估模型;并分析了模型的相关应用,给出了改进的动态规划模型。 关键字：web服务组合可信评价；全局个性化；动态规划； 0.引言 随着软件系统规模的日趋复杂，运行环境的不断开放，软件的可信性要求日益增加，可信软件成为了研究的热点。据《中国互联网发展状况统计报告》统计显示，截至2014年12月底，我国网民数量突破8亿，全年新增网民5580万。互联网普及率较上年底提升4个百分点，达到38。3%。因此，随着Internet 的广泛应用和网络技术的快速发展，面向服务的软件体系结构（SOA）作为一种新型的网络化软件应用模式已经被工业界和学术界广为接受。同时，网民对互联网电子商务类应用稳步发展，网络购物、网上支付、网上银行和在线旅游预订等应用的用户规模全面增长。因而，对web服务的可信性要求更高。单个web服务的功能有限，往往难以满足复杂的业务需求，只有通过对已有web服务进行组合，才能真正发挥其潜力。在现有的web服务基础上，通过服务组装或者Mashup方式生成新web服务作为一种新型的软件构造方式，已成为近年的研究热点之一。web服务组合并不是多个原子web服务的简单累加，各原子web服务之间有着较强的联系。因此对web服务组合的可信需求更高。目前大量的研究工作着重于如何实现原子web服务间的有效组合，对服务组合的可信评估研究较少。如今，随着web服务资源快速发展，出现了大量功能相同或相似的web服务，对web服务组合而言，选择可信的web服务变得越来越难。在大量的功能相似的原子web服务中，如何选出一组可信的web服务组合，成为了人们关注的热点问题。本文将从web服务组合着手，对其可信性进行研究，旨在提供一种可信web服务组合评估方法，为web服务组合的选择提供依据。web服务组合的可信度主要包括以下三个部分： 1）基于领域本体的web服务可信度量模型。 2）基于偏好推荐的原子web服务可信评估方法。 3）基于全局的个性化web服务组合可信评估方法。 研究思路： 本文主要研究基于全局的个性化web服务组合的可信评估方法，其研究思路可以大致如下：基于领域本体的web服务可信度和基于偏好推荐的原子web 服务可信评估方法。针对web服务组合的四种基本组合结构模式，主要研究如
第三章 牛顿法 §3.1 最速下降法 一、最速下降法 在极小化算法中，若每次都以迭代点处的负梯度方向为搜索方向，产生的算法称为最速下降法，它是无约束最优化算法中最简单、最基本的算法。 算法描述： 1） 给出初始点0n x R ∈，允许误差0ε>，0k =； 2） 计算k k d g =-，若k g ε≤，Stop 令 * k x x ≈； 3） 由一维搜索确定步长因子k α，使得 ()min ()k k k k k f x d f x d ααα≥+=+ 4） 令1k k k k x x d α+=+，1k k =+，go to 2). 的每个聚点均为驻点。 令{}1 k K d 有界，且 2 ()(())()0T f x f x f x ?-?=-?= 故有 ()0f x ?=。 定理 3.2 设()f x 二次连续可微，且2()f x M ?≤，则对任何给定的初始点0n x R ∈，最速下降算法或有限终止，或lim ()k k f x →∞ =-∞，或lim ()0k k f x →∞ ?=。
证明：不妨设k ?，()0k f x ?≠。由定理2.5有 2 11()()()2k k k f x f x f x M +-≥ ? 于是 []1 2 010 1 ()()()()()2k k k i i i i i f x f x f x f x f x M -+==-=-≥ ?∑∑ 令k →∞，由{()}k f x 为单调下降序列，则要么 lim ()k k f x →∞ =-∞，要么 lim k →∞ ?定理3.3 设1 f C ∈证明：直接由定理2.14可得。 注：1) 2 1λ，n λ分别为G 的 ≤ ()k k I G x α- 其中k α使 (())(())k k k f I G x f I G x αα-≤-， 0α?≥ 若设 ()1k P t t α=-，()Q t ut λ=- 其中,u R λ∈。则有 ()Q G I uG λ=-，而(0)Q λ=，
最优化理论与算法笔记 在老师的指导下，我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。 由于生产和科学研究突飞猛进的发展，特别是计算机的广泛应用，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。 整个学习安排如下，首先介绍线性与非线性规划问题，凸集和凸函数等基本知识及线性规划的基本性质；然后再这个基础上学习各种算法，包括单纯形法、两阶段法、大M 法、最速下降法、牛顿法、共轭梯度法等，以及各种算法相关的定理和结论；最后了解各种算法的实际应用。 主要学习的基础知识： 1、一般线性规划问题的标准形式 1min n j j j c x =∑ 1 .., 1,...,, 0, 1,...,. n ij j i j j s t a x b i m x j n ===≥=∑ 学会引入松弛变量将一般问题化为标准问题；同时掌握基本可行解的存在问题，通过学习容易发现线性规划问题的求解，可归结为求最优基本可行解的问题。 2、熟练掌握单纯形法、两阶段法和大M 法的概念及其计算步骤。 单纯形法是一种是用方便、行之有效的重要算法，它已成为线性规划的中心内容。其计算步骤如下： 1）解,B Bx b =求得1B x B b b -==，令0,N x =计算目标函数值B B f c x =；
2)求单纯形乘子ω，解B B c ω= ，得到1B c B ω-=； 3)解k k By p =，若0k y ≤，即k y 的每个分量均非正数，则停止计算，问 题不存在有限最优解，否则，进行步骤（4）； 4)确定下标r ，使min{0}r r rk rk rk b b y y y =>，得到新的基矩阵B ，返回第一 步。 两阶段法：第一阶段是用单纯形法消去人工变量，即把人工变量都变换成非基变量，求出原来问题的一个基本可行解；第二阶段是从得到的基本可行解出发，用单纯形法求线性规划的最优解。 大M 法：在约束中增加人工变量a x ，同时修改目标函数，加上罚项T a Me x ，其中M 是很大的正数，这样，在极小化目标函数的过程中，由于M 的存在，将迫使人工变量离基。 3、掌握最速下降法的概念及其算法，并且能够讨论最速下降算法的收敛性。掌握牛顿法，能够熟练运用牛顿迭代公式：(1) ()2()()()()k k k k x x f x x x +=-?- ，掌 握共轭梯度法及其相关结论，以及其收敛性的讨论，掌握最小二乘法及其基本步骤。 最速下降法：迭代公式为(1) ()()k k k k x x d λ+=-。 计算步骤：1）给定点(1)n x R ∈，允许误差0,ε>臵1k =； 2）计算搜索方向() ()()k k d f x =-?； 3）若() k d ε≤，则停止计算，否则，从()k x 出发，沿()k d 进行一维搜索，求k λ，使()()()() ()min ()k k k k k f x d f x d λλλ≥+=+； 4）令(1) ()()k k k k x x d λ+=-，臵:1k k =+，转步骤（2）。
最优化理论与算法（数学专业研究生） 第一章 引论 § 引言 一、历史与现状 最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题 min ()n x R f x ∈ （） 2、约束最优化问题 min () ()0, ..()0, i i f x c x i E s t c x i I =∈?? ≥∈? （） 这里E 和I 均为指标集。 §数学基础 一、 范数 1. 向量范数 max i x x ∞= （l ∞范数） （） 11n i i x x ==∑ （1l 范数） （） 122 21 ()n i i x x ==∑ （2l 范数） （）
11 ()n p p i p i x x ==∑ （p l 范数） （） 12 ()T A x x Ax = （A 正定） （椭球范数） （） 事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。 2．矩阵范数 定义 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ p p Ax A x ≤ 则称之为与向量范数p g 相协调（相容）的方阵范数。若令 max x Ax A x ≠= （这里x 是某一向量范数） （） 可证这样定义的范数是与向量范数g 相协调的，通常称之为由向量范数g 诱导的方阵范数。特别地，对方阵()ij n n A a ?=，有： 11max n ij j i A a ==∑（列和的最大者） （） 1 max n ij i j A a ∞ ==∑（行和的最大者） （） 1 22()T A A A λ=（T A A λ表示T A A 的特征值的最大者） 称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。 对于由向量诱导的方阵范数，总有：
第九章 二次规划 §9.1 二次规划问题 称形如 1m in ()2 T T Q x x H x g x = + 1,,. 1,,T i i e T i i e a x b i m s t a x b i m m ?==??≥=+?? （9.1） 的非线性规划问题为二次规划问题。对二次规划问题，有如下的最优性条件。 定理9.1 设x *是（9.1）的局部极小点，则必存在乘子(1,,)i i m λ*= ，使得 1 0 1,, 0 1,,m i i i T i i i e i e g H x a a x b i m m i m m λλλ**=*** ?+=? ?? ??-==+????≥=+??? ∑ （9.2） 且对于一切满足于： 0, ()T i d a i E I x * =∈ 的n d R ∈，都有0T d Hd ≥。 注：1）上述定理的前后两部分分别对应于一、二阶的必要条件； 2）满足上述条件的d ，都有(,)d S x λ* * ∈； 3）当约束条件均为线性函数时，容易证明： (,)(,) (,F D x X S F D x X L F D x X * * *= =及(,)(,)S x G x λλ**** = 上面给出的是二次规划的必要性条件，下面给出充分性条件。 定理9.2 设x * 是K-T 点，λ* 是相应的Lagrange 乘子，如果对满足 0 0 () 0 () 0 T i T i T i i d a i E d a i I x d a i I x λ* **?=∈?≥∈??=∈>? 且 （9.3） 的一切非零向量n d R ∈，都有0T d Hd >，则x * 是（9.1）的局部严格极小点。
第十章 罚函数法 罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数。当约束条件被破坏时，施以惩罚，可以想象，当这种惩罚很大时，将迫使迭代点趋于可行点。 §10.1 外罚函数法 对一般非线性规划问题： 1min ()()01,,. ()0 ,,i e i e f x c x i m s t c x i m m +==?? ≥=? （10.1） 定义违反约束度函数： ()()()1,i i e c x c x i m -== （10.2） ()1()min{0,()} ,m i i e c x c x i m -+== 。 （10.3） 罚函数一般表示为： () ()()(())P x f x h c x -=+ （10.4） 其中() (())h c x -是惩罚项，这个函数一般具有 (0)0h =，lim ()c h c →+∞ =+∞。 较常用的形式为： () ()()() P x f x c x α σ-=+ （0σ>称为罚因子） （10.5） 注：1) 在上式中，范数常取为2 ，若取为∞ 或1 会导致()P x 不光滑。 2) 当取2 和1α>时，()P x 的光滑性可由 ()22(())(min{0,()})i c x c x -= 直接验证。事实上，在“转折点”处，可证得左、右导数均为0，由此可得() 2(())c x -光滑性，从而 ()P x 光滑。 Courant 函数是最早使用的罚函数，也是最方便最重要的一种罚函数。其形式为 2 () 2 (,)()()p x f x c x σσ-=+ 1 2 21` ()()(min{0,()})e e m m i i i m f x c x c x σσ+==++∑∑ （10.6）
内点法基本原理 摘要：内点法是求解含不等式约束最优化问题的一种十分有效的算法。内点法通过构造障碍函数，求解一系列只含等式约束最优化问题，逐步得到原问题的最优解，具有找初始点容易、线性收敛、迭代次数少等特点。本文主要介绍了内点法的基本原理，障碍方法的一般步骤并分析了该方法的优缺点，进行了算例实践。 关键词：内点法；障碍方法；Newton法 The Theory of Interior Point Method Abstract: Interior point method is a very effective algorithm for solving optimization problems with inequality constrained. Interior point method is constructed to solve a series of optimization problems with equality constraints, and the optimal solution of the original problem is obtained, which has the characteristics of finding the initial point easier, linear convergence, less iteration number and so on. This paper mainly introduces the theory of interior point method, the general steps of barrier method and analyzing the advantages and disadvantages of the method. Key words: interior point method; barrier method;Newton method
《最优化理论与方法》讲义 (上) 第一章绪论 1.1 学科简介 最优化这一数学分支，为这些问题的解决提供了理论基础和求解方法。最优化就是在一切可能的方案中选择一个最好的方案以达到最优目标的学科。 1.1.1 优化的含义 优化是从处理各种事物的一切可能的方案中，寻求最优的方案。 （1）来源：优化一语来自英文Optimization，其本意是寻优的过程； （2）优化过程：是寻找约束空间下给定函数取极大值（以max 表示)或极小(以min表示)的过程。 1.2 发展概况 第一阶段—人类智能优化 第二阶段—数学规划方法优化 第三阶段—工程优化 第四阶段—现代优化方法 1.3研究意义 研究意义：最优化在本质上是一门交叉学科，它对许多学科产生了重大影响，并已成为不同领域中很多工作都不可或缺的工具。 应用范围：信息工程及设计、经济规划、生产管理、交通运输、
国防工业以及科学研究等诸多领域。 总之，它是一门应用性相当广泛的学科，讨论决策的问题具有最佳选择之特性。它寻找最佳的计算方法，研究这些计算方法的理论性质及其实际计算表现。 1.4 示例 例1 资源分配问题 某工厂生产A 和B 两种产品，A 产品单位价格为A P 万元，B 产品单位价格为B P 万元。每生产一个单位A 产品需消耗煤C a 吨，电E a 度，人工L a 个人日；每生产一个单位B 产品需消耗煤C b 吨，电E b 度，人工L b 个人日。现有可利用生产资源煤C 吨，电E 度，劳动力L 个人日，欲找出其最优分配方案，使产值最大。分析：(1)产值的表达式；(2)优化变量确定：A 产品A x ，B 产品B x ；(3)优化约束条件： ①生产资源煤约束； ②生产资源电约束； ③生产资源劳动力约束。 例2 指派问题 设有四项任务1B 、2B 、3B 、4B 派四个人1A 、2A 、3A 、4A 去完成。每个人都可以承担四项任务中的任何一项，但所消耗的资金不同。设 i A 完成j B 所需资金为ij c 。如何分配任务，使总支出最少? 分析：设变量?????=任务完成不指派， 任务完成指派j j i ij B A B A x 0,1
第五章 拟牛顿法 §5.1 拟牛顿法 牛顿法具有收敛速度快的优点，但需要计算Hesse 矩阵的逆，计算量大。本章介绍的拟牛顿法将用较简单的方式得到Hesse 矩阵或其逆的近似，一方面计算量不大，另一方面具有较快的收敛速度，这类算法是无约束最优化问题最重要的求解方法。 一、拟牛顿条件 设()f x 在n R 上二次可微，为了获得Hesse 矩阵2 ()()G x f x =?在1k x +处的近似，先研究如下 问题。考虑()f x 在1k x +附近的二次近似： 1111111 )()()()2 ()(T T k k k k k k g x x G x f x f x x x x +++++++-+ --≈. 两边求导，有 111()()k k k g x g G x x +++≈+- 令k x x =，有 111()k k k k k g g G x x +++≈+- 再令 1k k k s x x +≈-，1k k k y g g +≈- 则有 1k k k y G s +≈ 或 1 1k k k G y s -+≈. 因此，我们要求构造出的Hesse 矩阵的近似1k B +或Hesse 矩阵逆的近似1k H +应分别满足： 1k k k B s y += 或 1k k k H y s += （5.1） 它们均称之为拟牛顿条件。 二、一般拟牛顿算法 1） 给出初始点0x R ∈，0H I =，0ε>，:0k =. 2） 若k g ε≤，停止；否则，计算k k k d H g =-（拟牛顿方向）. 3） 沿方向k d 进行线性搜索，0k α>（可以是精确，也可非精确）.令1k k k k x x d α+=+. 4） 校正k H 产生1k H +，使拟牛顿条件满足. 5） :1k k =+， 转2）
最优化理论与方法心得体会 摘要：最优化方法作为研究各种系统的优化途径及方案，为决策者提供科学决策的依据。该文简单叙述了最优化方法及其处理问题的步骤和在各领域的应用，在一个学期的自学，讨论的课程之后，总结对最优化问题的理解和认识，思考优化理论在现实生活的应用，如何解决实际问题，以及自我学习过程的感想与实践。 关键字：优化；应用；感想
在生产过程、科学实验以及日常生活中，人们总希望用最少的人力、物力、财力和时间去办更多的事，获得最大的效益，在管理学中被看作是生产者的利润最大化和消费者的效用最大化，如果从数学的角度来看就被看作是“最优化问题”。在最优化的研究生教学中我们所说的最优化问题一般是在某些特定的“约束条件”下寻找某个“目标函数”的最大(或最小)值，其解法称为最优化方法。最优化方法（也称做运筹学方法）是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种有组织系统的管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为现代管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。本章将介绍最优化方法的研究对象、特点，以及最优化方法模型的建立和模型的分析、求解、应用。主要是线性规划问题的模型、求解（线性规划问题的单纯形解法）及其应用――运输问题；以及动态规划的模型、求解、应用――资源分配问题。简单点，从数学意义上说从数学意义上说，最优化方法是一种求极值的方法，即在一组约束为等式或不等式的条件下，使系统的目标函数达到极值，即最大值或最小值。从经济意义上说，是在一定的人力、物力和财力资源条件下，使经济效果达到最大（如产值、利润），或者在完成规定的生产或经济任务下，使投入的人力、物力和财力等资源为最少。不同类型的最优化问题可以有不同的最优化方法，即使同一类型的问题也可有多种最优化方法。反之,某些最优化方法可适用于不同类型的模型。最优化问题的求解方法一般可以分成解析法、直接法、数值计算法和其他方法。 ①解析法：这种方法只适用于目标函数和约束条件有明显的解析表达式的情况。求解方法是：先求出最优的必要条件，得到一组方程或不等式，再求解这组方程或不等式，一般是用求导数的方法或变分法求出必要条件，通过必要条件将问题简化，因此也称间接法。②直接法：当目标函数较为复杂或者不能用变量显函数描述时，无法用解析法求必要条件。此时可采用直接搜索的方法经过若干次迭代搜索到最优点。这种方法常常根据经验或通过试验得到所需结果。对于一维搜索(单变量极值问题)，主要用消去法或多项式插值法；对于多维搜索问题(多变量极值问题)主要应用爬山法。③数值计算法：这种方法也是一种直接法。它以梯度法为基础，所以是一种解析与数值计算相结合的方法。④其他方法：如网络最优化方法等。
第八章 约束优化最优性条件 §8.1 约束优化问题 一、 问题基本形式 min ()f x 1()0 1,,.. ()0 ,,i e i e c x i m s t c x i m m +==?? ≥=? （8.1） 特别地，当()f x 为二次函数，而约束是线性约束时，称为二次规划。 记 { }1()0 (1, ,);()0 , ,i e i e X x c x i m c x i m m +===≥=，称之为可行域（约束域） 。 {}1, ,e E m =，{}1, ,e I m m +=，{}()()0 i I x i c x i I ==∈ 称()E I x 是在x X ∈处的积极约束的指标集。 积极约束也称有效约束，起作用约束或紧约束（active constraints or binding constraints ）。 应该指出的是，如果x * 是（1）的局部最优解，且有某个0i I ∈，使得 0()0i c x *> 则将此约束去掉，x * 仍是余下问题的局部最优解。 事实上，若x *不是去掉此约束后所得问题的局部极小点，则意味着0δ?>，存在x δ，使得 x x δδ*-<，且()()f x f x δ*<，这里x δ满足新问题的全部约束。注意到当δ充分小时，由0() i c x 的连续性，必有0()0i c x δ≥，由此知x δ是原问题的可行解，但()()f x f x δ*<，这与x * 是局部极小 点矛盾。 因此如果有某种方式，可以知道在最优解x * 处的积极约束指标集()()A x E I x **=，则问题 可转化为等式的约束问题： min ()f x .. ()0i s t c x = ()i A x *∈ （8.2） 一般地，这个问题较原问题（8.1）要简单，但遗憾的是，我们无法预先知道()A x * 。
第四章 共轭梯度法 §4.1 共轭方向法 共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。 一、共轭方向 定义4.1 设G 是n n ?对称正定矩阵，1d ，2d 是n 维非零向量，若 120T d Gd = （4.1） 则称1d ，2d 是G －共轭的。类似地，设1,,m d d L 是n R 中一组非零向量。若 0T i j d Gd =()i j ≠ （4.2） 则称向量组1,,m d d L 是G －共轭的。 注：(1) 当G I =时，共轭性就变为正交性，故共轭是正交概念的推广。 (2) 若1,,m d d L G －共轭，则它们必线性无关。 二、共轭方向法 共轭方向法就是按照一组彼此共轭方向依次搜索。 模式算法： 1）给出初始点0x ，计算00()g g x =，计算0d ，使000T d g <，:0k = （初始共轭方向）； 2）计算k α和1k x +，使得0 ()min ()k k k k k f x d f x d ααα≥+=+，令1k k k k x x d α+=+； 3）计算1k d +，使10T k j d Gd +=，0,1,,j k =L ，令:1k k =+，转2）。
三、共轭方向法的基本定理 共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。 定理4.2 对于正定二次函数，共轭方向法至多经过n 步精确搜索终止；且对每个1i x +，都是()f x 在 线性流形00,i j j j j x x x d αα=???? =+??????? ∑中的极小点。 证明：首先证明对所有的1i n ≤-，都有 10T i j g d +=，0,1,,j i =L （即每个迭代点处的梯度与以前的搜索方向均正交） 事实上，由于目标函数是二次函数，因而有 ()11k k k k k k g g G x x Gd α++-=-= 1）当j i <时， () 1 1 11i T T T i j j j k k j k j g d g d g g d +++=+=+ -∑ 1 1 0i T T j j k k j k j g d d Gd α+=+=+ =∑ 2）当j i =时，由精确搜索性质知： 10T i j g d += 综上所述，有 10T i j g d += (0,1,,)j i =L 。 再证算法的有限终止结论。若有某个10i g +=（1i n <-），则结论已知。若不然，那么由上面已证则必有： 0T n j g d = (0,,1)j n =-L 。 而由于01,,n d d -L 是n R 的一组基，由此可得0n g =。故至多经过n 次精确一维搜索即可获得最优解。 下面证明定理的后半部分。由于 1()2 T T f x x Gx b x c = ++ 是正定二次函数，那么可以证明
盛年不重来，一日难再晨。及时宜自勉，岁月不待人。 最优化理论与算法（数学专业研究生） 第一章 引论 §1.1 引言 一、历史与现状 最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题 min ()n x R f x ∈ （1.1） 2、约束最优化问题 min () ()0, ..()0, i i f x c x i E s t c x i I =∈?? ≥∈? （1.2） 这里E 和I 均为指标集。 §1.2数学基础 一、 范数 1. 向量范数 max i x x ∞= （l ∞范数） （1.3） 11n i i x x ==∑ （1l 范数） （1.4）
122 21 ()n i i x x ==∑ （2l 范数） （1.5） 11 ()n p p i p i x x ==∑ （p l 范数） （1.6） 12 ()T A x x Ax = （A 正定） （椭球范数） （1.7） 事实上1－范数、2－范数与∞-范数分别是 p －范数当 p ＝1、2和p →∞时情形。 2．矩阵范数 定义1.1 方阵A 的范数是指与A 相关联并记做A 的一个非负数，它具有下列性质： ① 对于0A ≠都有0A >，而0A =时0A =； ② 对于任意k R ∈，都有kA k A =； ③ A B A B +≤+； ④ AB A B ≤； 若还进一步满足： ⑤ p p Ax A x ≤ 则称之为与向量范数p g 相协调（相容）的方阵范数。若令 max x Ax A x ≠= （这里x 是某一向量范数） （1.8） 可证这样定义的范数是与向量范数g 相协调的，通常称之为由向量范数g 诱导的方阵范数。特别地，对方阵()ij n n A a ?=，有： 11max n ij j i A a ==∑（列和的最大者） （1.9） 1 max n ij i j A a ∞ ==∑（行和的最大者） （1.10） 1 22()T A A A λ=（T A A λ表示T A A 的特征值的最大者） (1.11) 称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。 对于由向量诱导的方阵范数，总有：