第二章 优化方法的数学基础
§ 2-1 方向导数与梯度
§ 2-2 凸集、凸函数与凸规划
§ 2-3 二次函数及正定矩阵
§ 2-4 无约束优化问题的极值条件
§ 2-5 有约束优化问题的极值条件
§ 2-1 方向导数与梯度
0
1 0 1 2 0 2 1 0 2 0
0
(,) (,)l im
S
F F x x x x F x x
ss
x
0 00
12
12
c o s c o sF F F
s x x
x xx
一、方向导数二元函数在点 x0处沿某一方向 s的 方向导数方向导数是偏导数概念的推广。
方向导数与偏导数之间的数量关系是
n元函数在点 x0处沿 s方向的方向导数 0 0 0 0
0
12
12
1
c o s c o s c o s
c o s
n
n
n
i
i i
F F F F
s x x x
F
x
x x x x
x
O
x2
x1x10
x20 x0?x
1
x2?s
x
S
1
2
图 2-1
二,梯度二元函数的梯度
0 00
12
12
c o s c o sF F F
s x x
x xx
0
1
212
c os
c os
FF
xx
x
0
0
1
0
12
2
()
T
F
x FF
F
F xx
x
x
x
x
为函数 F(x1,x2)
在 x0点处的梯度。
梯度的模：
1
212
c o s
c o s
c o s,T
F F F
s x x
F s F s F s
22
12
FFF
xx
设 1
2
c o s
c o ss
梯度方向和 s方向重合时，方向导数值最大。
1
2
co s
co s
s
O
x 2
x 1
x 0
变化率为零的方向最速下降方向下降方向上升 方向最速 上升 方向
－? f (x 0 )
f (x 0 )
梯度方向是函数值变化最快的方向,而梯度的模就是函数变化率的最大值 。
图 2-2 梯度方向与等值线的关系
0 00
( ) ( ) c o s(,)TF F s F F ss x xx
设：
则有为单位向量。
多元函数的梯度
0
0
1
20
12
()
T
n
n
F
x
F
F F F
xF
x x x
F
x
x
x
x
00 001
c os ( ) ( ) c os(,)
n
T
i
i i
FF F F F s
sx
xx x d x
0
1
2
2
0
1
( ) ( )
n
i i
FF
x?
x
x
函数的梯度方向与函数等值面相垂直，也就是和等值面上过 x0的一切曲线相垂直。
由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种 局部性质 。
0()F? x?梯度 模：
梯度两个重要性质：
性质一 函数在某点的梯度不为零，则必与过该点的等值面垂直；
性质二 梯度方向是函数具有最大变化率的方向。
O
x 2
x 1
x 0
变化率为零的方向最速下降方向下降方向上升 方向最速 上升 方向
－? f (x 0 )
f (x 0 )
图 2-2 梯度方向与等值面的关系例题 2-1
求函数 在点 [3,2]T 的 梯度。221 2 1( ) 4 4f x x xx 1 1
2
2
24
()
2
f
x x
f
xf
x
x
( 1 )
1( 1 )
2
24 2()
2 4x
xf
x
x
在点 x(1)=[3,2]T处的梯度为：
解：
1 2 1 2
12
6 4,4 2f X f Xx x x xxx
1
2
1
2
1 120
0
12
1
0
2
1
64 4
42 2x
x
x
x
fX
x xx
P f X
xxfX
x
例 2-2：试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。
22212121 43,xxxxxxf0 0,1 TX?
0 0,1 TX?则函数在 处的最速下降方向是解,由于
10
2255
0 55
1 1 15 1 5
55
X X e
0
0 22
4 2 5
2 5
142 5
5
fXe
fX
01 2 21 1 2 2 263 4 | 2 55Xf X x x x x
新点是这个方向上的单位向量是：
几个常用的梯度公式：
1,0 0
2,,
3,2,
4,2
T
T
T
f X C f X C
f X b X f X b
f X X X f X X
Q f X X Q X f X Q X
常 数 则,即,
则,
则,
对 称 矩 阵 。 则,
当极值点 X*能使 f（ X*） 在整个可行域中为最小值时,即在整个可行域中对任一 X都有 f（ X） ≥ f（ X*） 时,则 X*就是最优点,
且称为 全域最优点或整体最优点 。 若 f（ X*） 为局部可行域中的极小值而不是整个可行域中的最小值时,则称 X*为 局部最优点或相对最优点 。 最优化设计的目标是全域最优点 。 为了判断某一极值点是否为全域最优点,研究一下函数的凸性很有必要 。
函数的凸性表现为单峰性。对于具有凸性特点的函数来说，
其极值点只有一个，因而该点既是局部最优点亦为全域最优点。
为了研究函数的凸性，现引入凸集的概念：
§ 2-2 凸集、凸函数与凸规划一、凸集设 D为 n维欧氏空间中的一个集合,若其中任意两点
X(1),X(2)之间的联接直线都属于 D,则称这种集合 D为 n维欧氏空间的一个凸集 。 图 2-3（ a） 是二维空间的一个凸集,
而图 2-3（ b） 不是凸集 。
图 2-3 二维空间的凸集与非凸集
X（ 1）,X（ 2） 两点之间的联接直线,可用数学式表达为,
( 1 ) ( 2 )( 1 )X X X
式中 为由 0到 1（ 0≤ ≤1 ）间的任意实数。?
凸集的性质：
1） 若 D为凸集,是一个实数,则集合 D仍是凸集；
2） 若 D和 F均为凸集,则其和 （ 或并 ） 仍是凸集；
3） 任何一组凸集的积 （ 或交 ） 仍是凸集 。
二、凸函数具有凸性 （ 表现为单峰性 ） 或只有唯一的局部最优值亦即全域最优值的函数,称为 凸 函数 或单峰函数 。 其数学定义是,
设 f（ X）为定义在 n维欧氏空间中的一个凸集 D上的函数，如果对任何实数 a（ 0<a<1）以及对 D中任意两点 X(1)、
X(2)恒有,
( 1 ) ( 2 ) ( 1 ) ( 2 )( ( 1 ) ) ( ) ( 1 ) ( )f X X f X f X
则 f（ X）为 D上的 凸函数,若不满足上式，则为 凹函数 。
凸函数 的集合意义如图 2-4所示：
图 2-4 一元凸函数的几何意义在凸函数曲线上取任意两点（对应于 X轴上的坐标 X(1)、
X（ 2） ）联成一直线线段，则该线段上任一点（对应于 X轴上的 X(k)点）的纵坐标 Y值必大于或等于该点（ X(k)）处的原函数值 f(X(k))。
凸函数的一些性质：
1） 若 f（ X） 为定义在凸集 D上的一个凸函数,且 a是一个正数 （ a > 0）,则 af（ X） 也必是定义在凸集 D上的凸函数；
3） 若 f1(X）,f2(X)为定义在凸集 D上的两个凸函数,α 和 β
为两个任意正数,则函数 afl（ X） ＋ β f2(X)仍为 D上的凸函数 。
2） 定义在凸集 D上的两个凸函数 f1(X）,f2(X),其和
f（ X） =f1（ X） 十 f2（ X） 亦必为该凸集上的一个凸函数 。
4） 若 f（ X） 为定义在凸集 D上且具有连续一阶导数的函数,则 f（ X） 为凸函数的充分必要条件为：
对任意两点 X（ 1）,X（ 2）,不等式
( 2 ) ( 1 ) ( 2 ) ( 1 ) ( 1 )( ) ( ) ( ) ( )Tf X f X X X f X恒成立三、凸规划对于约束优化问题
12m in ( ) ( ),
.,( ) 0 1,2,,
n
n
j
F X F x x x X R
s t g X j m
，,,
式中若 F（ X）,均 为凸函数,则称此问题为 凸规划 。()jgX
凸规划的一些性质：
2） 凸规划问题中的任何局部最优解都是全局最优解 ；
**( ) ( ) 0TF X X X
1） 可行域 为凸集；( ) 0 1,2,,jD X g X j m
3） 若 F（ X） 可微,则 X*为凸 规划问题 的 最优解的 充分必要条件为：
对任意,满足XD?
不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，
就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。
注意：
cxaxxxf
n
i
iin
1
21?
n
T
a
a
a
a
2
1
外，最简单最重要的一类就是二次函数。
在 n元函数中，除了线形函数：
或 f(X)=aX+c
§ 2-3 二次函数及正定矩阵
cxbxxgxxxf n
i
ii
n
i
n
j
jiijn
11 1
21 2
1,,?
其中 均为常数。cbg iij,,
jiij gg?
若,X≠0,均有 ＞ 0,则称矩阵 Q是 正定 的。nXR TX QX
在代数学中将特殊的二次函数 称为 二次型 。
对于二次函数，我们更关心的是 Q为正定矩阵的情形。
12 Tf X X Q X?
12 TTf X X Q X b X c
若,且 X≠0，均有 ＜ 0，则称 Q是 负定 的。nXR TX QX
定义：设 Q为 n× n对称矩阵
nnnn
n
n
ggg
ggg
ggg
21
22221
11211
nb
b
b
2
1
其中 Q= b= Q为对称矩阵其向量矩阵表示形式是：
二次函数的一般形式为：
6 6 0
63
30
32
6 3 1
3 2 0 1 0 0
1 0 4
解：对称矩阵 Q的三个主子式依次为：
401
023
136
例：判定矩阵 Q= 是否正定一个 n× n对称矩阵 Q是正定矩阵的充要条件是矩阵 Q的各阶主子式都是正的。
一个 n× n对称矩阵 Q是负定矩阵的充要条件是矩阵 Q的各阶主子式的值负、正相间。
因此知矩阵 Q是正定的。
12 Tf Z X Q X b X c定理,若二次函数 中 Q正定，则它的等值面是同心椭球面族，且中心为 *1X Q b
证明：作变换,代入二次函数式中：1X Y Q b
bQYfY 1
cbQYbbQYQbQY TT 11121
cbQbQYY TT 12121
根据解析几何知识,Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。
由于上式中的 是常数，所以 的等值面也是以 =0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。
QYY T21
0Y
11
2
Tb Q b cY?
Y
*1X Q b
前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。
因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于 Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。
特别地若算法对于 Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。
另外，这族椭球面的中心 恰是二次目标函数的唯一极小点。*1X Q b
例：把二次函数 化为矩阵向量形式并检验 Q是否正定，如正定，试用公式求这个函数的极小点。
2 2 21 2 3 1 2 3 1 2 1 3 1 2,,3 2 3 4 5f x x x x x x x x x x x x
*1X Q b
1 2 3 12 TTf x x x X Q Z b X
10
3
10
3
10
2
10
3
10
23
10
12
10
2
10
12
10
8
1Q
极小点是 = =*X bQ 1
70
76
82
解：展开
3
2
1
321
3
2
1
333231
232221
131211
321,,,,2
1
x
x
x
bbb
x
x
x
ggg
ggg
ggg
xxx=
332211322331132112233322222111 2
12121 xbxbxbxxgxxgxxgxgxgxg=
401
023
136
0
5
4
与题中函数比较各项系数为,Q= b=
由前例知 Q正定一,多元函数的泰勒展开
21( ) ( ) ( ) ( )
2
k k T T kF F F Fx x x x x x x
22
2
1 1 22
0 22
2
2 1 2
()
FF
x x x
F
FF
x x x
x
1 11
2 22
k
k
x xx
x xx
x
§ 2-4 无约束优化问题的极值条件二 元函数,
二 元函数：在点 Xk处多元函数泰勒展开
12
( ) [ ] kkT
n
F F FF
x x x
xx
2 2 2
2
1 1 2 1
2 2 2
22
2 1 2 2
2 2 2
2
12
( ) ( )
n
kk
n
n n n
F F F
x x x x x
F F F
x x x x xF H x
F F F
x x x x x
x
海色矩阵
（ Hessian）
21( ) ( ) ( ) ( )
2
k k T T kF F F Fx x x x x x x
对二次函数：
12 TTf X X Q X b X c
Q 为二次函数的 海色（ Hessian）矩阵，常量矩阵。
kkf X Q X b二次函数的梯度为：
220
222
022
2 Xf
2,2,2
0,2,2
2
3
2
32
2
2
2
2
31
2
21
2
2
1
2
x
f
xx
f
x
f
xx
f
xx
f
x
f
TxxxxxxxXf 2331221 22,3222,22
23
3
22 xxx Xf
21
1
22 xxxXf 3222 312
2
xxxx Xf
2221 2 3 1 2 2 3 32 2 3x x x x x x x x例：求目标函数 f（ X） =
的梯度和 Hesse矩阵。
解：因为则又因为,故 Hesse阵为：
( 1 )
12 ( 1 )
2
6 6 0 1 2 0
()
0 6 6 00
x
f
x
x
x
例题,
( 1 )( ) 3fx
( 1 )
2
11( 1 )
2
22
03 6 9
()
336
xx
f
xx
x
x
3 3 2 21 2 1 2 1( ) 3 3 9f x x x x xx?用泰勒展开将函数
( 1 ) [ 1,1 ] T?x在点 简化成线性函数与二次函数。
(1)x解：函数在点 的函数值、梯度和二阶导数矩阵：
11( 1)
22
11
11
xx
xx
xx
简化的线性函数
( 1) ( 1) ( 1)
22
( ) ( ) ( ) [ ]
3 3 ( 1 ) 3 6
Tf f f
xx
x x x x x
简化的二次函数
( 1 ) ( 1 ) ( 1 ) ( 1 ) 2 ( 1 ) ( 1 )1( ) ( ) ( ) [ ] [ ] ( ) [ ]
2
TTf f f x fx x x x x x x x x
2
21
2
1 1 2
3 6 6 ( 1 )
6 1 2 3
xx
x x x
二、无约束优化问题的极值条件
12
( ) [ ] 0T
n
F F FF
x x x?
x
x
1.F(x)在 处取得极值，其必要条件是,*x
即在极值点处函数的梯度为 n维零向量。
例,在 处梯度为
但 只是双曲抛物面的鞍点，而不是极小点。
1 2 1 2,.f x x x x* 0,0 TX 00,0 0f
*X
x
函数的梯度为零的条件仅为必要的，而不是充分的。
则称 为 f的 驻点 。*X
* 0fX定义：设 是 D的内点，若:,nf D R? *X
根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。
*x
为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。
*x
2,处取得极值充分条件
2 2 2
2
1 1 2 1
2 2 2
22*
2 1 2 2
2 2 2
2
12 *
()
n
n
n n n
F F F
x x x x x
F F F
x x x x xF
F F F
x x x x x
正 定 或 负 定
x
x
海色（ Hessian）矩阵 正定,即各阶主子式均大于零，则 X*为 极小点 。
()H?x
*x
海色（ Hessian）矩阵 负定,即各阶主子式负、正相间，则 X*为 极大点 。
()H?x
§ 2-5 有约束优化问题的极值条件
不等式约束的多元函数极值的必要条件是著名的库恩 --塔克（ Kuhn-Tucker）条件，它是非线性优化问题的重要理论
（ 1）库恩 — 塔克条件 (K-T条件）
对于多元函数不等式的约束优化问题：
m in ( )F x
.,( ) 0 ( 1,2,,)js t g j mx
K-T条件 **
1
*
()()
0 ( 1,2,,)
( ) 0 ( 1,2,,)
0 ( 1,2,,)
m
j
j
j
ii
jj
j
gF
in
xx
g j m
jm
xx
x
库恩 — 塔克条件表明：如点 是函数 的极值点，要么 （此时 ）*( ) 0Fx 0
j
x ()F x
要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。0
j
O
x1
x2
极值点处于等值线的中心极值点处于两个约束曲线的交点上
x﹡
g1 (x)＝ 0
g2 (x)＝ 0
g3 (x)＝ 0
O
x1
x2
x﹡
g1(x)＝ 0
g2(x)＝ 0
起作用约束：
( * ) { | ( * ) 0,
1,2,}
jJ j g
jm
xx
库恩 — 塔克条件的几何意义是,在约束极小值点 处，
函数 的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。
x
()F x
( ) ( ) 0
m
jj
jJ
Fg
xx
x1
x2
O
g2(x)=0
g1(x)=0
F (x)=C
g2(xk)
g1(xk)
－?F(xk)
xk
可行域点 xk处的切平面
x1
x2
O
g2(x)=0g
1(x)=0
F (x)=C
g2(xk)?g1(xk)
－?F(xk)
xk
可行域点 xk处的切平面
(a) (b)
同时具有等式和不等式约束的优化问题,
m in ( )F x
.,( ) 0 ( 1,2,,)js t g j mx
( ) 0 ( 1,2,,)kh k lx
1
0 ( 1,2,,)
( ) 0 ( )
0 ( )
l
j k
jk
j J k
i i i
j
j
g hF
in
x x x
g j J
jJ
x
K-T条件：
K-T条件 是多元函数取得约束极值的 必要条件,以用来作为约束极值的判断条件，
又可以来直接求解较简单的约束优化问题。
对于目标函数和约束函数都是凸函数的情况,符合 K-T条件的点一定是全局最优点。 这种情况 K-T条件即为多元函数取得约束极值的充分必要条件。
K-T条件是多元函数取得约束极值的必要条件,
以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。
例库恩 — 塔克（ K-T）条件应用举例
22
12( ) ( 2 ) m i nf x xx
2
1 1 2
22
31
( ) 1 0
( ) 0
( ) 0
g x x
gx
gx
x
x
x
s.t
判断 [1 0]T是否为约束最优点。
1
2
1
12
0
2 ( 2 ) 2
()
02 x
x
x
f
x?
x
1
2
1
1
0
22()
11i x
x
xg
x
2
0()
1g
x
(1)当前点 为可行点，因满足约束条件( 1 ) [1 0 ]T?x
( 1)
1
( 1)
2
( 1)
3
( ) 0
( ) 0
( ) 1 0
g
g
g
x
x
x
(3) 各函数的梯度：
（ 2）在 起作用约束为 g1和 g2,因( 1 ) [1 0 ]T?x (1)3 ( ) 0g?x
1 1 2 2( ) ( ) ( )f g gx x x
12
2 2 0
0 1 1
1
2
10
10
（ 4）求拉格朗日乘子
由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足 K-T条件。
( 1 ) [1 0 ]T?x
2212m i n ( ) ( 2 )f x xx
2
1 1 2
22
31
( ) 1 0
( ) 0
( ) 0
g x x
gx
gx
x
x
x
s.t
x
1
f ＝ 0,2 5
g
3
( x ) ＝ 0
g
3
0
1 2
x
2
f ＝ 5
f ＝ 4
f ＝ 2,2 5
f ＝ 1
g
1
( x ) ＝ 0
g
2
( x ) ＝ 0
g
1
g
2
－? f
－? f
C
g
2
g
3
g
1
A
B
－? f
图 8 应用库恩 — 塔克条件寻找约束极值点
§ 2-1 方向导数与梯度
§ 2-2 凸集、凸函数与凸规划
§ 2-3 二次函数及正定矩阵
§ 2-4 无约束优化问题的极值条件
§ 2-5 有约束优化问题的极值条件
§ 2-1 方向导数与梯度
0
1 0 1 2 0 2 1 0 2 0
0
(,) (,)l im
S
F F x x x x F x x
ss
x
0 00
12
12
c o s c o sF F F
s x x
x xx
一、方向导数二元函数在点 x0处沿某一方向 s的 方向导数方向导数是偏导数概念的推广。
方向导数与偏导数之间的数量关系是
n元函数在点 x0处沿 s方向的方向导数 0 0 0 0
0
12
12
1
c o s c o s c o s
c o s
n
n
n
i
i i
F F F F
s x x x
F
x
x x x x
x
O
x2
x1x10
x20 x0?x
1
x2?s
x
S
1
2
图 2-1
二,梯度二元函数的梯度
0 00
12
12
c o s c o sF F F
s x x
x xx
0
1
212
c os
c os
FF
xx
x
0
0
1
0
12
2
()
T
F
x FF
F
F xx
x
x
x
x
为函数 F(x1,x2)
在 x0点处的梯度。
梯度的模：
1
212
c o s
c o s
c o s,T
F F F
s x x
F s F s F s
22
12
FFF
xx
设 1
2
c o s
c o ss
梯度方向和 s方向重合时，方向导数值最大。
1
2
co s
co s
s
O
x 2
x 1
x 0
变化率为零的方向最速下降方向下降方向上升 方向最速 上升 方向
－? f (x 0 )
f (x 0 )
梯度方向是函数值变化最快的方向,而梯度的模就是函数变化率的最大值 。
图 2-2 梯度方向与等值线的关系
0 00
( ) ( ) c o s(,)TF F s F F ss x xx
设：
则有为单位向量。
多元函数的梯度
0
0
1
20
12
()
T
n
n
F
x
F
F F F
xF
x x x
F
x
x
x
x
00 001
c os ( ) ( ) c os(,)
n
T
i
i i
FF F F F s
sx
xx x d x
0
1
2
2
0
1
( ) ( )
n
i i
FF
x?
x
x
函数的梯度方向与函数等值面相垂直，也就是和等值面上过 x0的一切曲线相垂直。
由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种 局部性质 。
0()F? x?梯度 模：
梯度两个重要性质：
性质一 函数在某点的梯度不为零，则必与过该点的等值面垂直；
性质二 梯度方向是函数具有最大变化率的方向。
O
x 2
x 1
x 0
变化率为零的方向最速下降方向下降方向上升 方向最速 上升 方向
－? f (x 0 )
f (x 0 )
图 2-2 梯度方向与等值面的关系例题 2-1
求函数 在点 [3,2]T 的 梯度。221 2 1( ) 4 4f x x xx 1 1
2
2
24
()
2
f
x x
f
xf
x
x
( 1 )
1( 1 )
2
24 2()
2 4x
xf
x
x
在点 x(1)=[3,2]T处的梯度为：
解：
1 2 1 2
12
6 4,4 2f X f Xx x x xxx
1
2
1
2
1 120
0
12
1
0
2
1
64 4
42 2x
x
x
x
fX
x xx
P f X
xxfX
x
例 2-2：试求目标函数 在点 处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。
22212121 43,xxxxxxf0 0,1 TX?
0 0,1 TX?则函数在 处的最速下降方向是解,由于
10
2255
0 55
1 1 15 1 5
55
X X e
0
0 22
4 2 5
2 5
142 5
5
fXe
fX
01 2 21 1 2 2 263 4 | 2 55Xf X x x x x
新点是这个方向上的单位向量是：
几个常用的梯度公式：
1,0 0
2,,
3,2,
4,2
T
T
T
f X C f X C
f X b X f X b
f X X X f X X
Q f X X Q X f X Q X
常 数 则,即,
则,
则,
对 称 矩 阵 。 则,
当极值点 X*能使 f（ X*） 在整个可行域中为最小值时,即在整个可行域中对任一 X都有 f（ X） ≥ f（ X*） 时,则 X*就是最优点,
且称为 全域最优点或整体最优点 。 若 f（ X*） 为局部可行域中的极小值而不是整个可行域中的最小值时,则称 X*为 局部最优点或相对最优点 。 最优化设计的目标是全域最优点 。 为了判断某一极值点是否为全域最优点,研究一下函数的凸性很有必要 。
函数的凸性表现为单峰性。对于具有凸性特点的函数来说，
其极值点只有一个，因而该点既是局部最优点亦为全域最优点。
为了研究函数的凸性，现引入凸集的概念：
§ 2-2 凸集、凸函数与凸规划一、凸集设 D为 n维欧氏空间中的一个集合,若其中任意两点
X(1),X(2)之间的联接直线都属于 D,则称这种集合 D为 n维欧氏空间的一个凸集 。 图 2-3（ a） 是二维空间的一个凸集,
而图 2-3（ b） 不是凸集 。
图 2-3 二维空间的凸集与非凸集
X（ 1）,X（ 2） 两点之间的联接直线,可用数学式表达为,
( 1 ) ( 2 )( 1 )X X X
式中 为由 0到 1（ 0≤ ≤1 ）间的任意实数。?
凸集的性质：
1） 若 D为凸集,是一个实数,则集合 D仍是凸集；
2） 若 D和 F均为凸集,则其和 （ 或并 ） 仍是凸集；
3） 任何一组凸集的积 （ 或交 ） 仍是凸集 。
二、凸函数具有凸性 （ 表现为单峰性 ） 或只有唯一的局部最优值亦即全域最优值的函数,称为 凸 函数 或单峰函数 。 其数学定义是,
设 f（ X）为定义在 n维欧氏空间中的一个凸集 D上的函数，如果对任何实数 a（ 0<a<1）以及对 D中任意两点 X(1)、
X(2)恒有,
( 1 ) ( 2 ) ( 1 ) ( 2 )( ( 1 ) ) ( ) ( 1 ) ( )f X X f X f X
则 f（ X）为 D上的 凸函数,若不满足上式，则为 凹函数 。
凸函数 的集合意义如图 2-4所示：
图 2-4 一元凸函数的几何意义在凸函数曲线上取任意两点（对应于 X轴上的坐标 X(1)、
X（ 2） ）联成一直线线段，则该线段上任一点（对应于 X轴上的 X(k)点）的纵坐标 Y值必大于或等于该点（ X(k)）处的原函数值 f(X(k))。
凸函数的一些性质：
1） 若 f（ X） 为定义在凸集 D上的一个凸函数,且 a是一个正数 （ a > 0）,则 af（ X） 也必是定义在凸集 D上的凸函数；
3） 若 f1(X）,f2(X)为定义在凸集 D上的两个凸函数,α 和 β
为两个任意正数,则函数 afl（ X） ＋ β f2(X)仍为 D上的凸函数 。
2） 定义在凸集 D上的两个凸函数 f1(X）,f2(X),其和
f（ X） =f1（ X） 十 f2（ X） 亦必为该凸集上的一个凸函数 。
4） 若 f（ X） 为定义在凸集 D上且具有连续一阶导数的函数,则 f（ X） 为凸函数的充分必要条件为：
对任意两点 X（ 1）,X（ 2）,不等式
( 2 ) ( 1 ) ( 2 ) ( 1 ) ( 1 )( ) ( ) ( ) ( )Tf X f X X X f X恒成立三、凸规划对于约束优化问题
12m in ( ) ( ),
.,( ) 0 1,2,,
n
n
j
F X F x x x X R
s t g X j m
，,,
式中若 F（ X）,均 为凸函数,则称此问题为 凸规划 。()jgX
凸规划的一些性质：
2） 凸规划问题中的任何局部最优解都是全局最优解 ；
**( ) ( ) 0TF X X X
1） 可行域 为凸集；( ) 0 1,2,,jD X g X j m
3） 若 F（ X） 可微,则 X*为凸 规划问题 的 最优解的 充分必要条件为：
对任意,满足XD?
不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，
就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。
注意：
cxaxxxf
n
i
iin
1
21?
n
T
a
a
a
a
2
1
外，最简单最重要的一类就是二次函数。
在 n元函数中，除了线形函数：
或 f(X)=aX+c
§ 2-3 二次函数及正定矩阵
cxbxxgxxxf n
i
ii
n
i
n
j
jiijn
11 1
21 2
1,,?
其中 均为常数。cbg iij,,
jiij gg?
若,X≠0,均有 ＞ 0,则称矩阵 Q是 正定 的。nXR TX QX
在代数学中将特殊的二次函数 称为 二次型 。
对于二次函数，我们更关心的是 Q为正定矩阵的情形。
12 Tf X X Q X?
12 TTf X X Q X b X c
若,且 X≠0，均有 ＜ 0，则称 Q是 负定 的。nXR TX QX
定义：设 Q为 n× n对称矩阵
nnnn
n
n
ggg
ggg
ggg
21
22221
11211
nb
b
b
2
1
其中 Q= b= Q为对称矩阵其向量矩阵表示形式是：
二次函数的一般形式为：
6 6 0
63
30
32
6 3 1
3 2 0 1 0 0
1 0 4
解：对称矩阵 Q的三个主子式依次为：
401
023
136
例：判定矩阵 Q= 是否正定一个 n× n对称矩阵 Q是正定矩阵的充要条件是矩阵 Q的各阶主子式都是正的。
一个 n× n对称矩阵 Q是负定矩阵的充要条件是矩阵 Q的各阶主子式的值负、正相间。
因此知矩阵 Q是正定的。
12 Tf Z X Q X b X c定理,若二次函数 中 Q正定，则它的等值面是同心椭球面族，且中心为 *1X Q b
证明：作变换,代入二次函数式中：1X Y Q b
bQYfY 1
cbQYbbQYQbQY TT 11121
cbQbQYY TT 12121
根据解析几何知识,Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。
由于上式中的 是常数，所以 的等值面也是以 =0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。
QYY T21
0Y
11
2
Tb Q b cY?
Y
*1X Q b
前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。
因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于 Q为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。
特别地若算法对于 Q为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。
另外，这族椭球面的中心 恰是二次目标函数的唯一极小点。*1X Q b
例：把二次函数 化为矩阵向量形式并检验 Q是否正定，如正定，试用公式求这个函数的极小点。
2 2 21 2 3 1 2 3 1 2 1 3 1 2,,3 2 3 4 5f x x x x x x x x x x x x
*1X Q b
1 2 3 12 TTf x x x X Q Z b X
10
3
10
3
10
2
10
3
10
23
10
12
10
2
10
12
10
8
1Q
极小点是 = =*X bQ 1
70
76
82
解：展开
3
2
1
321
3
2
1
333231
232221
131211
321,,,,2
1
x
x
x
bbb
x
x
x
ggg
ggg
ggg
xxx=
332211322331132112233322222111 2
12121 xbxbxbxxgxxgxxgxgxgxg=
401
023
136
0
5
4
与题中函数比较各项系数为,Q= b=
由前例知 Q正定一,多元函数的泰勒展开
21( ) ( ) ( ) ( )
2
k k T T kF F F Fx x x x x x x
22
2
1 1 22
0 22
2
2 1 2
()
FF
x x x
F
FF
x x x
x
1 11
2 22
k
k
x xx
x xx
x
§ 2-4 无约束优化问题的极值条件二 元函数,
二 元函数：在点 Xk处多元函数泰勒展开
12
( ) [ ] kkT
n
F F FF
x x x
xx
2 2 2
2
1 1 2 1
2 2 2
22
2 1 2 2
2 2 2
2
12
( ) ( )
n
kk
n
n n n
F F F
x x x x x
F F F
x x x x xF H x
F F F
x x x x x
x
海色矩阵
（ Hessian）
21( ) ( ) ( ) ( )
2
k k T T kF F F Fx x x x x x x
对二次函数：
12 TTf X X Q X b X c
Q 为二次函数的 海色（ Hessian）矩阵，常量矩阵。
kkf X Q X b二次函数的梯度为：
220
222
022
2 Xf
2,2,2
0,2,2
2
3
2
32
2
2
2
2
31
2
21
2
2
1
2
x
f
xx
f
x
f
xx
f
xx
f
x
f
TxxxxxxxXf 2331221 22,3222,22
23
3
22 xxx Xf
21
1
22 xxxXf 3222 312
2
xxxx Xf
2221 2 3 1 2 2 3 32 2 3x x x x x x x x例：求目标函数 f（ X） =
的梯度和 Hesse矩阵。
解：因为则又因为,故 Hesse阵为：
( 1 )
12 ( 1 )
2
6 6 0 1 2 0
()
0 6 6 00
x
f
x
x
x
例题,
( 1 )( ) 3fx
( 1 )
2
11( 1 )
2
22
03 6 9
()
336
xx
f
xx
x
x
3 3 2 21 2 1 2 1( ) 3 3 9f x x x x xx?用泰勒展开将函数
( 1 ) [ 1,1 ] T?x在点 简化成线性函数与二次函数。
(1)x解：函数在点 的函数值、梯度和二阶导数矩阵：
11( 1)
22
11
11
xx
xx
xx
简化的线性函数
( 1) ( 1) ( 1)
22
( ) ( ) ( ) [ ]
3 3 ( 1 ) 3 6
Tf f f
xx
x x x x x
简化的二次函数
( 1 ) ( 1 ) ( 1 ) ( 1 ) 2 ( 1 ) ( 1 )1( ) ( ) ( ) [ ] [ ] ( ) [ ]
2
TTf f f x fx x x x x x x x x
2
21
2
1 1 2
3 6 6 ( 1 )
6 1 2 3
xx
x x x
二、无约束优化问题的极值条件
12
( ) [ ] 0T
n
F F FF
x x x?
x
x
1.F(x)在 处取得极值，其必要条件是,*x
即在极值点处函数的梯度为 n维零向量。
例,在 处梯度为
但 只是双曲抛物面的鞍点，而不是极小点。
1 2 1 2,.f x x x x* 0,0 TX 00,0 0f
*X
x
函数的梯度为零的条件仅为必要的，而不是充分的。
则称 为 f的 驻点 。*X
* 0fX定义：设 是 D的内点，若:,nf D R? *X
根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。
*x
为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。
*x
2,处取得极值充分条件
2 2 2
2
1 1 2 1
2 2 2
22*
2 1 2 2
2 2 2
2
12 *
()
n
n
n n n
F F F
x x x x x
F F F
x x x x xF
F F F
x x x x x
正 定 或 负 定
x
x
海色（ Hessian）矩阵 正定,即各阶主子式均大于零，则 X*为 极小点 。
()H?x
*x
海色（ Hessian）矩阵 负定,即各阶主子式负、正相间，则 X*为 极大点 。
()H?x
§ 2-5 有约束优化问题的极值条件
不等式约束的多元函数极值的必要条件是著名的库恩 --塔克（ Kuhn-Tucker）条件，它是非线性优化问题的重要理论
（ 1）库恩 — 塔克条件 (K-T条件）
对于多元函数不等式的约束优化问题：
m in ( )F x
.,( ) 0 ( 1,2,,)js t g j mx
K-T条件 **
1
*
()()
0 ( 1,2,,)
( ) 0 ( 1,2,,)
0 ( 1,2,,)
m
j
j
j
ii
jj
j
gF
in
xx
g j m
jm
xx
x
库恩 — 塔克条件表明：如点 是函数 的极值点，要么 （此时 ）*( ) 0Fx 0
j
x ()F x
要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。0
j
O
x1
x2
极值点处于等值线的中心极值点处于两个约束曲线的交点上
x﹡
g1 (x)＝ 0
g2 (x)＝ 0
g3 (x)＝ 0
O
x1
x2
x﹡
g1(x)＝ 0
g2(x)＝ 0
起作用约束：
( * ) { | ( * ) 0,
1,2,}
jJ j g
jm
xx
库恩 — 塔克条件的几何意义是,在约束极小值点 处，
函数 的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。
x
()F x
( ) ( ) 0
m
jj
jJ
Fg
xx
x1
x2
O
g2(x)=0
g1(x)=0
F (x)=C
g2(xk)
g1(xk)
－?F(xk)
xk
可行域点 xk处的切平面
x1
x2
O
g2(x)=0g
1(x)=0
F (x)=C
g2(xk)?g1(xk)
－?F(xk)
xk
可行域点 xk处的切平面
(a) (b)
同时具有等式和不等式约束的优化问题,
m in ( )F x
.,( ) 0 ( 1,2,,)js t g j mx
( ) 0 ( 1,2,,)kh k lx
1
0 ( 1,2,,)
( ) 0 ( )
0 ( )
l
j k
jk
j J k
i i i
j
j
g hF
in
x x x
g j J
jJ
x
K-T条件：
K-T条件 是多元函数取得约束极值的 必要条件,以用来作为约束极值的判断条件，
又可以来直接求解较简单的约束优化问题。
对于目标函数和约束函数都是凸函数的情况,符合 K-T条件的点一定是全局最优点。 这种情况 K-T条件即为多元函数取得约束极值的充分必要条件。
K-T条件是多元函数取得约束极值的必要条件,
以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。
例库恩 — 塔克（ K-T）条件应用举例
22
12( ) ( 2 ) m i nf x xx
2
1 1 2
22
31
( ) 1 0
( ) 0
( ) 0
g x x
gx
gx
x
x
x
s.t
判断 [1 0]T是否为约束最优点。
1
2
1
12
0
2 ( 2 ) 2
()
02 x
x
x
f
x?
x
1
2
1
1
0
22()
11i x
x
xg
x
2
0()
1g
x
(1)当前点 为可行点，因满足约束条件( 1 ) [1 0 ]T?x
( 1)
1
( 1)
2
( 1)
3
( ) 0
( ) 0
( ) 1 0
g
g
g
x
x
x
(3) 各函数的梯度：
（ 2）在 起作用约束为 g1和 g2,因( 1 ) [1 0 ]T?x (1)3 ( ) 0g?x
1 1 2 2( ) ( ) ( )f g gx x x
12
2 2 0
0 1 1
1
2
10
10
（ 4）求拉格朗日乘子
由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足 K-T条件。
( 1 ) [1 0 ]T?x
2212m i n ( ) ( 2 )f x xx
2
1 1 2
22
31
( ) 1 0
( ) 0
( ) 0
g x x
gx
gx
x
x
x
s.t
x
1
f ＝ 0,2 5
g
3
( x ) ＝ 0
g
3
0
1 2
x
2
f ＝ 5
f ＝ 4
f ＝ 2,2 5
f ＝ 1
g
1
( x ) ＝ 0
g
2
( x ) ＝ 0
g
1
g
2
－? f
－? f
C
g
2
g
3
g
1
A
B
－? f
图 8 应用库恩 — 塔克条件寻找约束极值点
