最优化理论与算法（数学专业研究生）
第一章 引论
§1.1 引言
一、历史与现状
最优化理论最早可追溯到古老的极值问题，但成为一门独立的学科则是在20世纪四十年代末至五十年代初。其奠基性工作包括Fritz John 最优性条件（1948），Kuhn-Tucker 最优性条件（1951），和Karush 最优性条件(1939)。近几十年来最优化理论与算法发展十分迅速，应用也越来越广泛。现在已形成一个相当庞大的研究领域。关于最优化理论与方法，狭义的主要指非线性规划的相关内容，而广义的则涵盖：线性规划、非线性规划、动态规划、整数规划、几何规划、多目标规划、随机规划甚至还包括变分、最优控制等动态优化内容。本课程所涉及的内容属于前者。 二、最优化问题的一般形式 1、无约束最优化问题
min ()n
x R
f x ∈ （1.1）
2、约束最优化问题
m in ()
()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）
1
1
n
i i x
x ==
∑
（1l 范数） （1.4）
12
22
1
()n
i i x
x ==∑ （2l 范数） （1.5）
11
()n
p
p
i p
i x
x ==∑ （p l 范数） （1.6） 1
2()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 相协调（相容）的方阵范数。若令
m ax
x Ax A x
≠= （这里x 是某一向量范数） （1.8）
可证这样定义的范数是与向量范数 相协调的，通常称之为由向量范数 诱导的方阵范数。特别地，对方阵()ij n n A a ?=，有：
1
1
m ax n
ij j
i A
a ==∑（列和的最大者） （1.9）
1m ax n
ij i
j A
a ∞
==∑（行和的最大者） （1.10）
1
2
2
()
T A A A
λ=（T
A
A
λ表示T
A A 的特征值的最大者） (1.11) 称为谱范数（注：方阵A 的特征值的模的最大者称为A 的谱半径，记为()A ρ）。
对于由向量诱导的方阵范数，总有：
1
1m in
x A
Ax x
-≠=
，1I =（I 为单位阵）
对于方阵范数，除了上述由向量范数诱导的范数之外，还有常用的Frobenius 范数，简称F -范数：
11
22
21
1
()[tr()]n
n
T
ij
F
i j A
a
A A ====∑
∑ (1.12)
及加权Frobenius 范数和加权2l 范数:
,M F
F
A MAM = (1.13)
,22
M A
MAM
= (1.14)
其中M 为对称正定矩阵。 3. 范数的等价性
定义1.2 设α 与β 是n R 上的两个范数，若存在12,0μμ>，使得
12x
x
x
α
β
α
μμ≤≤， n x R ?∈ (1.15)
则称范数α 与β 是等价的。 容易证明：
2
1
2
x x ≤≤
(1.16) 2x
x
∞∞
≤≤
(1.17)
1
x x n x
∞
∞
≤≤ (1.18)
2
1x
x
x ∞≤≤
(1.19)
2
2
A
x ≤≤
(1.20)
其中1λ是A 的最大特征值，而n λ是A 的最小特征值。由此可见，n R 中的常用向量范数均等价，事实上还可证明：n R 中所有向量范数均等价。 4. 关于范数的几个重要不等式。
① Cauchy-Schwarz 不等式
T
x y x
y ≤（当且仅当x 和y 线性相关时，等式成立） (1.21)
② 设A 是正定矩阵，则
T
A
A
x Ay x
y
≤（当且仅当x 与y 线性相关时，等式成立） (1.22)
由(,)T x y x Ay =是一种内积，以及一般内积的Cauchy-Schwarz 不等式即得。 ③ 设A 是n n ?正定矩阵，则
1
T
A
A
x y x
y
-≤（仅当x 与1A y -线性相关时，等式成立） (1.23)
1
1
1
T
T
A
A
A
A
x y x AA y x
A y
x
y
---=≤= (1.24)
其中的不等号由②可得。
④ Y oung 不等式：假定p 与q 都是大于1的实数，且满足
111p q
+=，则,x y R +
?∈，有
p
q
x
y
xy p
q
≤
+
， (1.25)
当且仅当p q x y = 时，等式成立。其证明由算术－几何不等式直接给出，事实上
1
1()()p
q
p
q
p
q
x
y
xy x y p
q
=
+
≤
（算术－几何不等式）
⑤ H?lder 不等式
1
1
1
1
()(
)p
q n
n
p
q
T
i
i p
q
i i x y x
y
x y ==≤=∑∑
(1.26)
其中p 与q 都是大于1的实数，且满足
111p
q
+
=，其证明利用Y oung 不等式可得。
⑥ Minkowski 不等式
p
p
p
x y
x
y
+=≤+，（1p ≥） (1.27)
后面将利用凸函数理论予以证明。
二、矩阵求逆与广义逆 1. Von-Neumann 引理
定理1.3 (V on-Neumann 引理) 设n n E R ?∈，n n I R ?∈是单位阵， 是满足1I =的相容矩阵范数。如果1E <，则()I E -非奇异，且
1
()
k
K I E E ∞
-=-=
∑
， 1
1()
1I E E
--≤
-
若A 非奇异，1()A A B --1<,则B 非奇异，且
1
1
1
()k k B
I A
B A
∞
---==
-∑， 1
1
1
1()
A
B
A A
B ---≤
--.
证明：因为1E <，故 2k k S I E E E =++++ 定义了一个Cauchy 序列，因而收敛。由 1()k k S I E I E +-=- 可得 1
lim ()lim ()k k k k S I E I E
I +→∞
→∞
-=-=
故有 10
lim ()k k k k E S I E ∞
-→∞
===-∑
进一步有 1
1()
1k
k I E E
E
∞
-=-≤
≤
-∑
。
再令 1E I A B -=-，
知 11()1E I A B A A B --=-=-< 由上面结论可得，
1
11
1
0()
()
()k
k I E A B I A
B ∞
----=-==
-∑
所以有 1
1
1
()k
k B
I A
B A
∞
---==
-∑
进一步有 1
1
1
1
1
1
1
()
1()
k
k
k k A
B
I A B
A
A A
B A
A A
B -∞
∞
------==≤
-=
-≤
--∑
∑
。
注：这个定理表明，若B 充分接近一个可逆矩阵A ，则B 也可逆，且逆矩阵可由A 的逆矩阵来表示。
上述定理还可以写成下面形式：
定理1.4 设A ,n n B R ?∈，A 可逆，1A α-≤。若A B β-≤，且1αβ<，则B 可逆，且
1
1B ααβ
-≤
-。
证明：只需注意到11()1A B A A B A αβ---≤-≤<，再由上述V on-Neumann 引理即得。
2. 广义逆
定义1.5 设m n A C ?∈，若n m A C +?∈满足：
*
*
,()
,()
,AA A A A AA A AA AA A A A A +
+
+
+
+
+++
===
=
(1.28)
则称A +是A 的广义逆。其中*A 是A 的共轭转置。 广义逆的求法
① 设m n A C ?∈，秩()A r =，若A 直交分解为*A Q RP =，其中Q ，P 分别为,m m n n ??酉矩阵，
m n
R C
?∈，11000R R ??
=
???
，其中11R 是r r ?非奇异的上三角矩阵。则A 的广义逆为： *A P R Q ++
= 其中 11100
0R R -+
??
=
???
(1.29) ② 若A 的奇异值分解为*A UDV =，其中U ，V 均为酉矩阵，00
0m n
D C
?∑??=∈
???
，而1(,,),0r i diag σσσ=>∑ 是A 的非零奇异值，则A 的广义逆为：
*
A VD U ++=，其中100
0D -+
??
∑=
???
(1.30) ③ 若A 的最大秩分解为A B C =，则A 的广义逆为：
*
*
1
*
1
*
()()A C C C B B B +
--=. (1.31)
三、 矩阵的Rayleigh 商
定义1.6 A 是n n ? Hermite 矩阵，n
u C ∈，则称
*
*()u Au R u u u
λ=
（0u ≠） (1.32)
为矩阵A 的Rayleigh 商
定理1.7 设A 是n n ? Hermite 矩阵，则Rayleigh 商具有下列性质： 1) 齐次性： ()()R u R u λλα= （0α≠）
2) 极性： 2
*
*
1*
10
m ax m ax
u
u u Au u Au u u
λ=≠==
2
*
*
*
10
min min
n u
u u Au u Au u u
λ=≠==
这里1λ，n λ分别对应于矩阵A 的最大与最小特征值。这表明Rayleigh 商具有有界性： 1()n R u λλλ≤≤ 3）极小残量性质：对任意n u C ∈，
(())()A R u I u A I u λμ-≤-，R μ?∈。
证明：1）由定义直接可得。
2）由A 是Hermite 矩阵，故存在酉矩阵T ，使1*
n T AT λλ??
?=Λ=
? ? ??
?
又令 u Ty =，且2
1u
=，故2
1y
=
则 2
2
*
*
*
*
11n n u Au y T ATy y y y y λλ==Λ=++
当取(1,0,,0)y = 时达到最大值1λ，当取(0,0,0,1)y = 时，达到最小值n λ。
3）令()()s u Au R u u λ=-，(0)u ≠，则()()Au s u R u u λ=+，可直接验证
(),()0s u R u u λ=，
由于 **
((),)((),)()0s u u Au R u u u u Au R u u u λλ=-=-=
注意到()R u u λ是与u 共线的，故()s u 与()R u u λ正交。即()R u u λ与()s u 是A u 的正交分解。因而
()R u u λ是A u 在{}L u =上的直交投影，因而具有极小残量性质。
四、矩阵的秩一校正
当矩阵A 变到T
A uv +时，即在A 上加了一个秩为1的矩阵，称为秩一校正。下面讨论如何求秩一校正的逆，行列式，特征值及矩阵分解。
定理1.8 设m n A R ?∈是非奇异的，,n
u v R ∈是任意向量。若10T v Au +≠，则A 的秩一校正T
A uv
+非奇异，其逆矩阵可以表示为
11
1
1
1
()
1T T T
A uv A
A uv A
v A u
-----+=-
+ (1.33)
证明：可直接验证。
上述定理的可进一步推广为：
定理1.9 设A 是非奇异矩阵，,U V 是n m ?矩阵，若*1I V A U -+可逆，则*A UV +可逆，且
*
1
1
1*11*1
()
()A U V A
A U I V A U V A
------+=-+ (1.34)
下面介绍关于秩一校正的行列式定理 定理1.10 1）det()1T T I uv v u +=+
2）123412341423det()(1)(1)()()T T T T T T I u u u u u u u u u u u u ++=++-
证明： 1）若0u =，则结论显然成立；若0u ≠，设w 是()T I uv +的特征向量。则
()T
I uv w w λ+=
易见w 要么与v 垂直，要么与u 平行。若与v 垂直，则特征值为1；若与u 平行，则对应特征值为
1T
v u +。
进一步，平行于u 的特征向量只有一个（线性无关），而垂直于v 的线性无关的向量有1n -个，它们均为T I uv +属于特征值1的特征向量，即特征值1是(1)n -重根， 而1T v u +是单根。
故有 11det()1(1)1T n T T
n I uv v u v u λλ-+==+=+ 。
2） 对11234121234()()T T T T T
I u u u u I u u I I u u u u -??++=+++??
使用上面结果，故有：
1
1234124123det()()1()T T T T T I u u u u I u u u I u u u -??++=+++??
=12124312(1)1()1T
T
T
T
u u u u u I u u u ??++-??+??
=
12341423(1)(1)()()T
T
T
T
u u u u u u u u ++-。
关于秩一校正矩阵的特征值定理。
定理 1.11设A 是对称矩阵，其特征值为12n λλλ≥≥≥ ，又设T
A A u u σ=+，其特征值为
12n λλλ≥≥≥ ，那么
1） 若0σ>，则1122n n λλλλλλ≥≥≥≥≥
2） 若0σ<，则1122n n λλλλλλ≥≥≥≥≥
五、函数与微分
1.多元函数的梯度与H essian 矩阵 梯度 1
()(
,,
)T
n
f f f x x x ???=?? (1.35)
Hessian 矩阵 2
2
2
1
122
2
2
1
()n n n f f x x x f x f f x x x ??
?? ??? ?
?
?=
? ?
?? ??? ?
?
?
(1.36) 方向导数：（设d 为一方向向量，即长度为1的单位向量，显然与范数的取法有关）
()()
lim ()T
f f x d f x f x d x
θθθ
+
→?+-==?? (1.37)
注：对欧氏范数（2－范数）而言，梯度方向是函数上升最快的方向，而负梯度方向则是函数下降最快的方向。正因为这个原因，使得梯度在最优化理论与算法中占有特殊重要的地位。
若:n f R R →在开凸集D 上连续可微，则有
1
()()()()()T T
f x d f x f x td ddt f x f d ξ+=+
?+=+??
（1.38）
其中(,)x x d ξ∈+。上式也可改写为：
()()(())()T
f y f x f x t y x y x =+?+-- (0,1)t ∈
或 ()()()()()T
f y f x f x y x o y x =+?-+-
若f 在D 上二阶连续可微，则对于任何,x x d D +∈，存在(,)x x d ξ∈+，使得
2
1()()()()2!T
T f x d f x f x d d f d ξ+=+?+
? 2
2
1()()()()2!
T T
f x f x d d f x d o d
=+?+
?+
2.向量函数的微分
设:n m
F R R →是一个向量函数，若其每个分量(1,,)i f i m = 都连续可微，则称()F x 连续可
微。()F x 在x 处的导数记为：
111
1
()()n m m n f f x x F x J x f f x x ??
?? ??? ?
?'=
= ? ?
?? ??? ?
?
?
（1.39） 称之为()F x 在x 处的Jacobi 矩阵，而称()(())T F x F x '?=为向量函数()F x 在x 处的梯度。
若:n m F R R →在开凸集D 上连续可微，则对任何,x x d D +∈，有：
1
()()()F x d F x F x td ddt '+-=
+?
定义1.12 :n m n G R R ?→在n x D R ∈?处称为Lipschitz 连续的，若v D ?∈，都有
()()G v G x v x γ-≤-。
若在D 中每一点均Lipschitz 连续，则称G 在D 上Lipschitz 连续，记为Lip ()G D γ∈。其中，γ称为Lipschitz 常数。
定理1.13 （向量函数线性化近似的误差估计）设:n m F R R →在开凸集D 上连续可微，()F x '在x 的邻域D 中Lipschitz 连续，则对于任何x d D +∈，有
2
()()()2
F x d F x F x d d
γ
'+--≤
.
证明： 1
'
()()()()()F x d F x F x d F x d dd F x d αα''+--=
+-?
[]1
()()F x d F x dd αα''=
+-?
从而 [
]1
()()()()()F x d F x F x d
F x d F
x d d
αα'''
+--=+-? 1
1
00
(()())()()F x d F x d d F x d F x d d αααα''''≤+-≤
+-?
?
112
2
1.2
d d d d
d d
γααγααγ≤
==?
?
注：在上述证明过程中的第一个不等式并不平凡，它实际上要求，对一般向量函数的积分，下述命题成立。
命题：对可积向量函数12()((),(),,())T
n f t f t f t f t =
，有()()b b a
a
f t dt f t dt ≤
?
?
.
证明：对于1l 范数上述命题是成立的，这是因为：
121
()()()()b b b b n a
a
a
a
f t dt
f t dt f t dt f t dt =
+
++
?
?
?
?
1212()()()(()()())b b b b n n a a
a
a
f t dt f t dt f t dt f t f t f t dt ≤+
++
=
+++?
?
?
?
1
()b a
f t dt =
?
对于2l 范数上述命题也成立。事实上，
2
2
1
11
2
2
()(())()()(()())()(())
n
n
b b b b i i i a
a
a
a
i i n
b b
b b i i a
a
a
a
i b b b a
a
a
a
f t dt
f t dt f t f s dtds
f t f s dtds f t dt dt ====
=
=
≤
=
==∑∑?
?
??
∑
????
?
?
?
?
对于一般范数，需借助于Banach 空间弱Riemann 积分理论进行证明。 定理1.13给出了线性近似的误差界，下面考虑二次近似的误差界。
定理1.14 设:n f R R →在开凸集n D R ?上二次连续可微，2()f x ?在x 的邻域D 上Lipschitz 连续。则对于任何x d D +∈有：
3
21()()()()26T
T f x d f x f x d d f x d d
γ??+-+?+?≤????
证明： 2
1()()()()
2
T
T f x d f x f x d d f x d +--?-
? 11
2
2
()()t t T T d f x d dd dt d f x dd dt ααα=
?+-
???
??
12
2
0()()t
T
T
d f x d d d f x d d dt αα≤
?+-???
1
12
3
3
16
t t d
d d dt d
d dt d
γααγααγ≤
==
??
??
定理1.15 设:n
m
F R R →在开凸集n D R ?上连续可微，则对任何,,x u v D ∈，有
01()()()()sup (())()t F u F v F x u v F v t u v F x u v ≤≤??
'''---≤+---????
，
若进一步F '在D 中Lipschitz 连续，则有：
()()()()2
u x v x
F u F v F x u v u v γ
-+-'---≤-.
证明：[]1
()()()()(())()()F u F v F x u v F v t u v F x u v dt
'''---=
+---?
1
(())()F v t u v F x u v dt ''≤
+---?
（由此式即可得第一部分结论）
1
1
()(1)()()v t u v x u v dt t v x t u x u v dt γ
γ
≤+---=--+--?
?
11
0(1)2
u x v x
u v v x
t dt u x
tdt u v γγ-+-??≤---+-=-??
?
??
?.
定理 1.16设,F F '满足上面定理条件，假定矩阵[]1
()F x -'存在（这蕴含着()F x '是方阵，即():n
n
F x R R →）
。则存在0,0εβα>>>，使得,u v D ?∈，当{}max ,
u x v x
ε--≤
时，有：
()()u v F u F v u v
αβ
-≤
-
≤- 证明：()()()()()()()()F u F v F x u v F u F v F x u v ''-≤-+---
()()2F x u x v x u v γ??
'≤+-+--????
()F x u v γε'≤?+?-?? u v β=- （令()F x βγε'=+） 从而右边不等式得证。另一方面，注意到：
1
1
()()()()
()()u v F x F x u v F x F x u v --''''-=-≤-）
故有
()()()()()()()()
F u F v F x u v F u F v F x u v ''-≥----- 1
1()2()u x v x u v F x γ
-????≥--+--'???? 1
1
()u v u v F x γεα-????≥--=-'????
因此，若取1
1()
F x εγ
-<
'，且令1
1 (0)()
F x αγε-=
->'，则得左边不等式结论。
由111()()()()F x F x F x F x --''''=≤，可得
1
1
()()
F x F x -'≤'，从而有0βα>>。
六、差商（偏差商）
设1()((),,())T
m F x f x f x = 是一个向量函数，其Jacobi 矩阵的第i 行j 列元素可用差商（偏差
商）
()()
i j i ij f x he f x a h
+-=
近似。由偏差商构成的矩阵()ij m n A a ?=称为()F x 的差商矩阵。显然差商矩阵的第j 列为
()()
j j F x he F x A h
+-=
关于差商矩阵与Jacobi 矩阵有如下误差估计式
定理1.17 设:n m F R R →在开凸集D 上连续可微，()F x '在D 中Lipschitz 连续，则
()2
j j A J x h γ
-≤ 若采用的范数是1l 范数，则有：1
()
2
A J x h γ
-≤
证明： 将定理1.13中的d 取为j h e ，则有
2
2
()()()()()()2
2
j j j j j
F x he F x J x he F x he F x J x h he h γ
γ
+--=+--≤
=
两边同除h ，则有
()2j j A J x h γ
-≤
.
类似地，也可以用中心差分来近似梯度和Hessian 矩阵，并有如下误差估计结果。
定理1.18 设:n f R R →在开凸集D 上二次连续可微，2
()f x ?在D 上Lipschitz 连续，又设所采用的范数满足1j e =，(1,,)i n = ，定义()f x 在x 处的中心偏差商为：
()()
2i i i f x he f x he a h
+--=
则 2
()6
i i a f x h γ
-?≤
如采用l ∞范数，则2
()6
a f x h γ
-?≤ ，其中1(,,)T
n a a a = .
证明：由定理1.14有：
2
1()()()()
2
T
T f x d f x f x d d f x d +--?-
?3
6
d
γ
≤
令i d he =，则有
22
31()()()()2
6
i i ii f x he f x h f x h f x h γ
+--?-
?≤
再令i d he =-，又有
2
2
31()()()()2
6
i i ii f x he f x h f x h f x h γ
--+?-?≤
令上两式中左端绝对值内的部分分别为,αβ，则有 3
()()2()3
i i i f x h e f x h e h f x h
γ
αβαβ-=+---?≤
+
≤
由此即得：
2
()()
()()26
i i i i i f x he f x he f x a f x h h
γ
+---?=-?≤
由l ∞范数的定义，有
2
()
6
a f x h γ
∞
-?≤
.
定理1.19 设()f x 在开凸集D 上二次连续可微，2()f x ?在D 上Lipschitz 连续，采用的范数满足
1j e =，(1,,)i n = ，假定,,,i j i j x x he x he x he he D ++++∈(,1,,)i j n = 。定义：
2
()()()()
i j i j ij f x he he f x he f x he f x a h
++-+-++=
则有： 2
5()3
ij ij a f x h γ-?≤
若采用矩阵范数是1,l l ∞或F-范数，则 2
5()3
A f x hn γ-?≤
（这里()ij A a =是Hessian 矩阵的离散形式）。
证明：令2
1()()()()()()()2
T
T i j i j i j i j f x he he f x he he f x he he f x he he α=++--+?-
+?+
2
1()()()()()()(
)
2
T
T i i i i f x he f x
he f x he f x he β=+--?-? 2
1()()()()()()()2
T
T
j j j j f x he f x he f x he f x he η=+--?-
?
经简单计算有： 2
2
(())
i j i j a f x h
αβη
--=-?
又由定理1.14有， 3
3
86
6
i j
he he h γ
αγ≤
+≤
3
316
6i he h γ
βγ≤=
3
316
6
j
he h γ
ηγ≤
=
进而有 22
2
1105()()6
3
ij ij a f x h h h
h
αβη
αβηγγ---?=
≤
++=
=
再由矩阵1,l l ∞及F-范数的定义立即可得：
2
5()3
A f x hn γ-?≤
§1.3 凸集与凸函数
一、凸集（Convex Set ） 1．凸集的概念
定义1.20 设n S R ?，若12,x x S ?∈，都有
12(1)x x S αα+-∈ []0,1α?∈ 则称S 是凸集。
定理1.21 n R 的子集S 为凸集的充分必要条件是12,,,m x x x S ?∈ 有
1
m
i
i i x S α
=∈∑
其中0 (1,,)i i m α≥= 且1
1m
i i α==∑。
凸集的例子：n 维球、半空间、超平面、{},0x Ax b x =≥等均为凸集。 定理1.22 若12,S S 是n R 中的凸集，则
1） 12S S 是凸集；（事实上，任意多个凸集的交仍为凸集） 2） {}121211,22S S x x x S x S ±=±∈∈也是凸集 2．凸包 集合S 的凸包的定义如下： 1
1
Conv(),,1,0,1,2,m
m
i i i i i i i S x x x x S m ααα==?
?==
∈=≥=???
?
∑∑
由定义知，集合S 的凸包由S 中元素所有可能的凸组合构成。还可证明：它是所有包含集合S 的凸
集的交，即它是包含集合S 的最小凸集。 3．锥、凸锥
定义 1.23 设n K R ?，若,0x K λ?∈?>，有x K λ∈，则称K 为锥；若锥K 还是凸集，则称之为凸锥。
容易证明：K 是凸锥的充要条件是，K 对正组合运算封闭。 定理1.23 若n C R ?是凸集，则C 的闭包C 也是凸集。 证明：,x y C ?∈，则存在序列{}{},k k x y C ?，使得
lim k k x x →∞
=，lim k k y y →∞
=
从而有 l i m ((1))(1k k k x y x y λλλλ→∞
+
-=+
-，[]0,1λ?∈
注意到 {}(1)k k x y C λλ+-?及C 的闭性，可知
(1)x y C λλ+-∈
这就证明了C 是凸集。 4．极点与极方向
定义1.24 设n S R ?是非空凸集，x S ∈，若x 不在S 中任何线段的内部，则称x 是凸集S 的极点。 显然，多边形顶点、圆周上的点均为极点。
定义1.25 设n
S R ?是闭凸集，d 为非零向量，若对任意x S ∈，当0λ≥时，总有x d S λ+∈，
则称d 为S 的方向；若S 中的某方向d 不能表示为该集合的两个不同方向的正的线性组合，则称d 为S 的极方向。
极点与极方向是凸多面体中非常重要的概念，在线性规划中有重要应用，关于这些方面的详细讨论，可参阅有关线性规划教材。
二、凸函数
定义1.26 设n
S R ?是非空凸集，f 是定义在S 上的函数，若对任意的12,x x S ∈都有：
1
212((1))()(1)()f x x f x f x αααα
+-≤+- (0,1)
α?∈ 则称f 是S 上的凸函数。凸函数的另一等价定义是：
1
1
()()n n
i i i
i i i f x f x λλ
==≤
∑∑
其中，1
1,0n
i i i λλ==≥∑。若12x x ≠时，不等式严格成立，则称f 在S 上是严格凸的。若f -在S 上
是凸（严格凸），则称f 在S 上是凹（严格凹）。 定理1.27 设()f x 是定义在凸集S 上的凸函数，
1） 若0α≥，则()f x α是S 上的凸函数；
2） 若12,f f 是S 上的凸函数，则12f f +也是凸函数。
由此立即可得：若1,,m f f 是S 上的凸函数，1,,0m αα≥ ，则1
m
i i i f α=∑也是S 上的凸函数。
凸函数的一阶特征
定理 1.28 设n S R ?是非空开凸集，f 是定义在S 上的可微函数，则f 为凸函数的充要条件是：
()()()()T
f y f x f x y x ≥+?- ,x y S ?∈
证明：必要性，设f 是凸函数，则对任意的(0,1)α∈，有 ((1))()(1)(
f y x f y f x αααα+-≤+- 因此有
(())()
()()
f x y x f x f y f x αα
+--
≤-
令0α→得 ()()()(
T
f x y x f y f x ?-≤
-
即 ()()()(T
f y f x f x y x ≥+?-
必要性得证。
充分性： 设()()()()T
f y f x f x y x ≥+?-，,x y S ?∈成立。
任取12,x x S ∈及(0,1)α∈，令12(1)x x x αα=+-，于是有：
11()()()()T
f x f x f x x x ≥+?-
22()()()()T
f x f x f x x x ≥+?-
于是有 []12
12
()(1)()()()(1
)T
f x f x f x f
x
x x x
αααα+-≥+?+--
12()((1))f x f x x αα==+- 即 1212((1))()(1)()
f x x f x f x
αααα
+-≤+- 亦即()f x 是凸函数，充分性得证。
● 几何解释：凸函数图像位于割线之下，切线之上。 凸函数的二阶特征
定理1.29 设n S R ?是非空开凸集，f 是定义在S 上的二次可微函数，则f 为凸函数的充要条件是
S 上的每一点的Hessian 矩阵半正定。
证明：充分性， 设 2()f x ?在每一点x S ∈均半正定。任取,x y S ∈，由中值定理有：
2
12
()()()()()()()
T
T
f y f x f x y x y x f y x ξ
=+?-+-?- ()()()T
f x f x y x ≥+?-，（其中ξ在以,x y 为端点的线段上）
所以，()f x 是凸函数。
必要性，设()f x 是凸函数，则任取x S ∈，对任意的n p R ∈，λ充分小时有 ()()()T
f x p f x f x p
λλ+≥
+?
另一方面 2
2
2
()()()()
0(
)
2
T
T f x p f x f x p p f x p p λ
λλλ+=+?+
?+ 故
2
2
2
()0()02
T
p f x p p λ
λ?+≥
两边除以2
λ并令0λ→，则有
2
()0T p f x p ?≥
即 2
()f x ?半正定。
注：对严格凸函数有类似的一阶与二阶特征，但要注意一些细微的差别。
定理1.30 设n
S R ?是非空开凸集，f 是定义在S 上的可微函数，则f 为严格凸的充要条件是 ()()()(T
f y f x f x y x >
+?-， ,,x y S x y ?∈≠
证明：充分性证明与前述凸函数情形完全类似，故从略。必要性的证明如下：
设()f x 在S 上严格凸，,x y S ?∈且x y ≠，令112
2
z x y =+
，则显然z S ∈。由于()f x 严格凸，
故有 11()()()22f z f x f y <+
及 ()()()(T
f z f x f x z x
≥+?- 由上两式有 11()()()()()22T
f x f y f x f x z x +>+?-
111()()()()
22
2
T
f y f x f x y x >
+
?- 因此有 ()()()()T f y f x f x y x >+?-.
定理1.31设n S R ?是非空开凸集，f 是定义在S 上的二次可微函数，若2,()x S f x ?∈?正定，则
()f x 为严格凸函数。
注：严格凸不能推出2()f x ?正定，因此2()f x ?正定是严格凸的充分条件，但不是必要条件。如
4()f x x =，2
()12f x x ''=，(0)0f ''= 不正定，但它是严格凸的。
定理 1.32 设n S R ?是非空开凸集，f 是定义在S 上的凸函数，α是一个实数，则水平集
{},()L x x S f x αα=∈≤是凸集。
证明： 略
进一步，若()f x 是连续凸函数，则L α是闭凸集。事实上，设{}k x L α?，且lim k k x x →∞
=
那么 ()(l i m )l i m ()
k
k k k f x f x f x α→∞
→∞
==≤ 所以 x L α∈，故L α为闭集。
定理1.33 设()f x 是n
S R ?上二次连续可微的凸函数，且存在常数0m >，使得
2
2
()T u f x u m u
?≥ 0()x L x ?∈，n
u R ∈
则水平集{}00(),()()L x x x S f x f x =∈≤是有界闭凸集。
证明：由上面讨论可知，0()L x 是闭凸集，因而仅需 证明0()L x 是有界的。由于0()L x 是凸的， 因而 0,()x y L x ?∈，0()(1)()x y x y x L x ααα+-=+-∈， 从而有 2
2
()(())()T
y x f x y x y x m y x
α-?+--≥- 由Taylor 展开式，
12
0()()()()()(())()t
T
T f y f x f x y x y x f x y x y x d dt αα=+?-+
-?+--??
1
2
()()()t
T
f x f x y x m y x
d dt α≥+?-+
-??
2
1
()()()2
T
f x f x y x m
y x
=+?-+
- 可知，00(),y L x y x ?∈≠，有
2
00001()()()()2
T
f y f x f x y x m y x -≥?-+
-
2
000
1()
2
f x y x m y x ≥-?-+-
再由 0()()0f y f x -≤，
故有 001()02
f x m y x -?+-≤
即 002()y x f x m -≤
?
由y 是0()L x 中任一向量， 所以0()L x 有界，因而0 ()L x 是有界闭凸集。 定理1.34 （Minkowski 不等式） 对1p ≥，有p
p
p
x y
x
y
+≤+，即：
1
1
1
1
1
1
()
()
()
n
n
n
p
p
p
p
p
p
i i
i i i i i x y x y ===+≤+∑∑∑ .
证明：当x 或y 为零向量时，结论显然成立。当1p =时，也易证明。以下设,0x y ≠，且>1p 。
考虑函数 ()p
t t ?=， 0t >
由于 2
()(1)0p t p p t ?-''=->
，故()t ?严格凸。
注意到
1p
p
p
p
p
p
x y x
y
x
y
+
=++
由函数()t ?的凸性，于是有，
p
p
p
p
p
p
p
i i i
i
p
p
p
p
p
p
p
p
p p
p
p x
y x
y
x y x
y
x y
x
x
y
y
x y
x
x y
y
?
????? ? ? ?+
≤+ ? ? ?++++?
?
??
??
因此，
1
1
1
1
p
p
p
p
n
n
n
n
p
p
i i
i i
i
i
i i i i p p
p p
p
p
p p
p
p x
y
x y
x y
x
y
x y
x y
x y
x
x y
y
====??
??
????++
?
? ? ?≤≤+ ? ? ? ?++++?
?
?
?
??
??
∑
∑
∑
∑
计算机应用基础公开课教案 授课人：袁涛授课对象：机电工程系2011级学生 时间：2011年12月8日星期四上午一、二节 课题：excel中数据的基本处理 一、教学目标： （一）知识与技能 1、掌握一些常见函数的使用方法 2、会对一组数据排序、筛选 （二）过程与方法 1、锻炼学生恰当、自如地使用函数的能力； 2、培养学生收集、分析、处理数据的能力； 3、培养自主探索，合作交流能力。 （三）情感态度价值观 这课堂，通过情境的创设，使学生明确探究目标，给学生思维以方向，同时产生强烈的探究兴趣和欲望，给思维以动力。通过利用EXCEL工具软件制作出数据图表，提升学生对使用计算机软件的热情。 二、教学重点： 1、基本函数的使用方法 2、自动筛选和高级筛选 三、教学难点： 1、用公式进行计算 2、高级筛选
四、教学方法 讲授法、演示法、练习法 五、教学过程： （一）复习导入 前面我们学习了工作簿、工作标的基本操作和数据的格式化，然而在我们学习和工作中知道这些是远远不够的，那么我们接下来一些常见函数的使用和如何对一组数据进行简单的处理。 （二）实例引课 实例： 1、基本函数的使用 （1）讲述Sum函数的功能和使用方法，演示使用sum函数求和（附带讲述自动求和）； （2）讲述Average函数的功能和使用方，演示使用average函数求平均值； （3）讲述Max函数的功能和使用方法，演示使用max函数求最高分；（4）讲述Min函数的功能和使用方法，演示使用min函数求最低分。
2、如何用公式对数据进行相应的计算 3、数据的排序和筛选 （1）排序 功能：按要求对一组数据进行排序 操作步骤：选定将要排序的数据区域→数据菜单→选择关键字和排序方式 演示：对实例进行排序操作 （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 +==?? ≥=?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 * 。
此文档下载后即可编辑 计算机应用基础公开课教案 授课人：袁涛授课对象：机电工程系2011级学生 时间：2011年12月8日星期四上午一、二节 课题：excel中数据的基本处理 一、教学目标： （一）知识与技能 1、掌握一些常见函数的使用方法 2、会对一组数据排序、筛选 （二）过程与方法 1、锻炼学生恰当、自如地使用函数的能力； 2、培养学生收集、分析、处理数据的能力； 3、培养自主探索，合作交流能力。 （三）情感态度价值观 这课堂，通过情境的创设，使学生明确探究目标，给学生思维以方向，同时产生强烈的探究兴趣和欲望，给思维以动力。通过利用EXCEL工具软件制作出数据图表，提升学生对使用计算机软件的热情。 二、教学重点： 1、基本函数的使用方法 2、自动筛选和高级筛选 三、教学难点： 1、用公式进行计算 2、高级筛选 四、教学方法 讲授法、演示法、练习法 五、教学过程： （一）复习导入
前面我们学习了工作簿、工作标的基本操作和数据的格式化，然而在我们学习和工作中知道这些是远远不够的，那么我们接下来一些常见函数的使用和如何对一组数据进行简单的处理。（二）实例引课 实例： 1、基本函数的使用 （1）讲述Sum函数的功能和使用方法，演示使用sum函数求和（附带讲述自动求和）； （2）讲述Average函数的功能和使用方，演示使用average函数求平均值； （3）讲述Max函数的功能和使用方法，演示使用max函数求最
高分； （4）讲述Min函数的功能和使用方法，演示使用min函数求最低分。 2、如何用公式对数据进行相应的计算 3、数据的排序和筛选 （1）排序 功能：按要求对一组数据进行排序 操作步骤：选定将要排序的数据区域→数据菜单→选择关键字和排序方式 演示：对实例进行排序操作 （2）数据的筛选 功能：按要求把符合条件的数据筛选出来 自动筛选：选定所要筛选的数据→数据菜单→筛选→自动筛选→筛选项目→筛选条件 演示对实例进行自动筛选 高级筛选：数据菜单→筛选→高级筛选→筛选方式→列表区域（所要筛选的数据区域）→条件区域→筛选结果所放区域演示对实例进行高级筛选 （三）学生练习 结合上节课和本节课的内容，按要求对下列数据进行处理
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 λ=，
计算机基础公开课教案 章节名称：第一章 Windows XP基础 教学目标 1、知识目标 1）了解操作系统的概念、基本功能及类型。 2）了解Windows XP桌面的组成元素和“开始”菜单。 2、技能目标 1）认识Windows XP的桌面及程序窗口。 2）掌握任务栏的使用方法。 3）掌握[开始]菜单属性的设置。 3、情感目标 激发学生学习Windows XP的热情。 教学重点 1、Windows XP桌面和程序窗口的组成。 2、Windows任务栏的基本操作。 教学难点 任务栏菜单属性的设置。 教学方法 1、教法： 直观演示、任务驱动 2、学法： 分组法、游戏法、实践操作 教学手段 采用课件演示、投影演示、多媒体电子教室同步演示。 素材准备 自制课件、拼图FLASH资源、课堂操作题。 教学过程 一、新课导入 对前两章内容的复习 计硬件系统 算 机 系系统软件 统软件系统 应用软件 问题：在软件系统中，最重要且最基本的是什么？ 什么是操作系统？它有什么作用？ 二、新课展开 1、引入操作系统、操作系统概念、操作系统作用（由学生分组讨论回答） 1）什么是操作系统
操作系统（Operating System，简称OS）是一管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。 这里所谓的“资源”当然不是指自然资源，而是指计算机系统内可利用的各种能力。比如计算机运行程序的能力，存储能力，打印机的打印能力等，可以说计算机系统各种资源能够相互协调，有效地进行工作，都依赖于操作系统的统一控制，因此，一台电脑只有安装了操作系统，才能进入最基本的工作状态。用户通过操作系统来操纵计算机，可以省去很多具体细节，从而获得良好的应用环境。 2）操作系统的基本功能 CPU管理、存储管理、设备管理、文件管理、用户接口 3）介绍操作系统的种类 2、观看Windows发展视频 教师问：同学们经常使用的操作系统有哪些？ 3 4 教师：讨论完作用，我们就来具体操作一下 教学说明: 任务1、3需未锁定任务栏。（可在学生尝试失败后再提出） 任务2 小结时要突出介绍“命令选项的特殊标记√”的作用。 任务4 小结时可讨论隐藏的作用或演示任务栏属性对话框中“分组相似任务栏按钮”的作用。
最优化理论与算法笔记 在老师的指导下，我学习了最优化理论与算法这门课程。最优化理论与算法是一个重要的数学分支，它所研究的问题是讨论在众多方案中什么样的方案最优以及怎样找出最优方案。 由于生产和科学研究突飞猛进的发展，特别是计算机的广泛应用，使最优化问题的研究不仅成为了一种迫切的需要，而且有了求解的有力工具，因此迅速发展起来形成一个新的学科。至今已出现了线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分支。 整个学习安排如下，首先介绍线性与非线性规划问题，凸集和凸函数等基本知识及线性规划的基本性质；然后再这个基础上学习各种算法，包括单纯形法、两阶段法、大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）的局部严格极小点。
《计算机应用基础》公开课教案 时间：20XX年3月12日上午第一节课 班级：高职二班 地点：网络中心 主讲教师：徐剑 教学课题：Excel工作表中的数据筛选 教学课型：新授课 教学目标： 1. 知识目标：掌握数据的筛选方法（自动筛选及高级筛选），并能应用于实际工作中 2. 能力目标：培养学生的观察能力和自主学习能力 教学重点：如何对数据进行筛选 教学难点：如何用高级筛选的方法对数据进行筛选 教学方法：演示法、实验法、任务驱动法 实验及教具：实例、多媒体 教学课时：第一学时（总共2学时） 教学过程： 通过完成四个具体任务，来达到对两种数据筛选方法的掌握。 一、展示任务，查看数据表（2分钟） 1、请找出计算机成绩表中的文秘专业考试成绩最高的女同学 2、请在计算机成绩表中找出财会专业或计算机专业姓李的同学 3、请在学生信息表（1）中找出家住水口的电子专业的同学信息，结果存放在以H2为左上角单元格的区域 4、请在学生信息表（2）中找出性别为男或年龄大于18岁的同学，在原有区域显示结果 1. 任务1：请找出计算机成绩表中的文秘专业考试成绩最高的女同学（4分钟） 操作步骤： 1. 单击数据区域任何一个单元格 单击“数据”菜单“筛选”命令的“自动筛选”项，数据表的每个字段名旁 边出现下拉按钮“▼”，单击“专业”字段的下拉按钮“▼”，在出现的下 拉列表中选择“文秘”，单击“性别”字段的下拉按钮“▼”，在出现的下 拉列表中选择“女” 很明显筛选后所显示的记录远远少于先前的记录数，可以直接在这些记录中 找到最高分的同学，也可以再进行一次排序，直接看到文秘专业最高分的女 同学 2. 学生操作，完成第一个任务，教师检查完成情况。（2分钟）
第十章 罚函数法 罚函数是利用目标函数与约束函数一起构成的具有惩罚性质的函数。当约束条件被破坏时，施以惩罚，可以想象，当这种惩罚很大时，将迫使迭代点趋于可行点。 §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 ρ）。 对于由向量诱导的方阵范数，总有：