最优化 问题数学基础为了便于学习最优化方法，本章将对与优化方法密切有关的数学知识作一简要介绍而有些数学知识将在讲解各种算法时，随之介绍．
§ 1.1 二次型与正定矩阵一,二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛．应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题,二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题．推广到 n维空间中，二次超曲面的一般方程为
，
，，，
n
i
n
j
jiij
nnnnnnn
nn
nnn
xxa
xaxxaxxa
xxaxaxxa
xxaxxaxaxxxf
1 1
2
2211
22
2
2221221
112112
2
11121
)(
用矩阵表示为其中，矩阵 A的元素 正是二次型的项的系数的一半,是二次型的 项的系数．因此，二次型和它的矩阵 A是相互唯一决定的，且,
，
，，，，，，
AXX
x
x
x
Axxxxxaxxxf
T
n
i
n
j
n
njiijn
1 1
2
1
2121
][)(
)( jiaa jiij
jixx
iia 2ix
TAA?
二、正定矩阵
定义 2.1 如果二次型
对于任何一组不全为零的数 恒有
则称 正定，且二次型矩阵 A也称为正定．
简言之，一个对称矩阵 A如果是正定的，则二次型
对于所有非零向量 X其值总为正．类似可以给出定义，若二次型
则 A为半正定矩阵；若,则 A为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵 A为不定的．
n
i
n
j
T
jiijn AXXxxaxxxf
1 1
21 )(,，,?
nxxx,，,?21
0)( 21 AXXxxxf Tn，，,?
)( 21 nxxxf,，,?
)( 21 nxxxf,，,? AXX T?
0)( 21 AXXxxxf Tn，，,?
0?AXX T
矩阵 A为正定的充要条件是它的行列式的顺序主子式全部大于零，即
由此可见，正定矩阵必然是非奇异的．
例 2.1 判断矩阵 是否正定．
解 ∵,
∴ A是正定的．
11 12 1
21 22 211 12
11
21 22
12
0 0 0
n
n
n n nn
a a a
a a aaa
a
aa
a a a
，,,
201
032
124
A
4 2 1
424 0 8 0 2 3 0 13 0
23 102
，,
一、方向导数
所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率．
定义 2.2 设 在点 处可微,P是固定不变的非零向量,是方向 P上的单位向量，则称极限
(2.1)
为函数 在点 处沿 P方向的方向导数，式中是它的记号．
§ 2.2 方向导数与梯度
1,RRf n? 0X
e
t
XfteXf
P
Xf
t
)()(lim)( 00
0
0
)(Xf 0X
P
Xf
)( 0
定义 2.3 设 是连续函数，,
且,若存在,当 时都有，
则称 P为在点处的下降方
向．若,则称 P为在点处的上升方向．
由以上两个定义可立刻得到如下的结论：
若,则 从 出发在 附近沿 P
方向是下降；若,则从出发在附近沿 P方向是上升．
1,RRf n? 0X
0?P 0 ),0(t
)()( 00 XftPXf
)()( 00 XftPXf
0)( 0 PXf )(Xf 0X 0X
0)( 0 PXf
二、梯度
定义 2.4 以 的 n个偏导数为分量的向量称为 在 X处的梯度，
记为
,
梯度也可以称为函数 关于向量 的一阶导数．
以下几个特殊类型函数的梯度公式是常用的：
（ 1）若 （常数），则,即 ；
（ 2）,
证 设,则
于是 的第 个分量是
,
所以
（ 3）,
（ 4）若 Q是对称矩阵，则
)(Xf )(Xf
12
( ) ( ) ( )() T
n
f X f X f XfX
x x x
，,,
)(Xf X
cXf?)( 0)( Xf 0c
bXbT )(
1 2 1 2[ ] [ ]TTnnb b b b X x x x，,,,,,,?
n
i
iiT xbXb
1)( XbT? j
1
( ) ( ) 1 2nT i i j
ijj
b X b x b j nxx
,,,,
bXbT )(
XXX T 2)(
QXQXX T 2)(
三、梯度与方向导数之间的关系
定理 2.1 设 在点 处可微，则
,
其中 是 方向上的单位向量,
由这个定理容易得到下列结论：
(1)若,则 P的方向是函数在点 处的下降方向；
(2) 若,则 的方向是函数在点处的上升方向．
方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，
升降的速度就越快，即
1,RRf n? 0X
eXfPXf T)()( 00
e P
0)( 0 PXf T
0)( 0 PXf T
0X
0XP
= ·1·
上式中的等号，当且仅当的方向与的方向相同时才成立．
由此可得如下重要结论 (如图 2.1所示）：
(1)梯度方向是函数值的最速上升方向；
(2)函数在与其梯度正交的方向上变化率为零；
(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；
(4)梯度反方向是函数值最速下降方向．
0 0() () TfX f X eP 0()fX? 00( c o s ( ( ),) ) ( )f X e f X
·1·
对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度 -----图 2.1的方向，这样才能使函数值下降的最快．
例 2.2 试求目标函数在点处的最速下降方向，
并求沿这个方向移动一个单位长后新点的目标函数值．
解 因为
所以最速下降方向是－ = =,
这个方向上的单位向量是
故新点是
对应目标函数值为
1
1
2f xx 2
2
2f xx
0()fX?
1
2
1
02
3
2
2 x
x
x
x?
0
6
0
0
0()
1()
fXe
fX
10
0 0 0
3 1 2X X e
221( ) 0 2 1 5fX
§ 2.3 海色矩阵及泰勒展式
一、海色（ Hesse）矩阵
前面说过，梯度 是 关于 的一阶导数，现在要问 关于 的二阶导数是什么？
定义 2.5 设：,,,如果在点
处对于自变量的各分量的二阶偏导数
都存在，则称函数在点处二阶可导，并且称矩阵
()fX?
()fX X
()fXX
f 1RR n? nRX?
0
0X
是 在点 处的 Hesse矩阵．
在数学分析中已经知道，当 在点 处的所有二阶偏导数为连续时有
因此，在这种情况下 Hesse矩阵是对称的．
2 2 2
0 0 0
2
1 1 2 1
2 2 2
0 0 0
2 2
0 2 1 2 2
2 2 2
0 0 0
2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
n
n n n
f X f X f X
x x x x x
f X f X f X
fX x x x x x
f X f X f X
x x x x x
f 0X
f 0X
22
00( ) ( ) 12
i j j i
f X f X i j n
x x x x
,,,,
例 2.3 求目标函数 的梯度和 Hesse矩阵．
解 因为
所以
23132221233241 432)( xxxxxxxxxXf
232131
1
24 xxxxxf
32122
2
46 xxxxf
3123
3
246 xxxxxf
3123
3
2
1
2
2
2
321
3
1
246
46
24
)(
xxxx
xxx
xxxx
Xf
又因为
所以
2 2 2
2
1 2 1 32
1 1 2 1 3
2 2 2
2122
2 2 3 3
12 2 2 2
12 4 6 2
f f f
x x x x
x x x x x
f f f
xx
x x x x
，,,
，,,
13
21
312
2
1
2
2642
4122
22212
)(
xx
xx
xxxx
Xf
例 2.4 设,求线性函数在任意点 X处的梯度和 Hesse矩阵,
解,设,则
（ 2.2）
∴
由式（ 2.2）进而知
∴ （阶零矩阵）．
1,,RbRXRa nn bXaXf T)(
1 2 1 2[ ] [ ]TTnna a a a X x x x，,,,,,,
12
1
() nn i i
i
f x x x a x b
，,,
12i
i
f a i n
x
,,,,
aaaaXf Tn ],,,[)( 21?
2
0 1 2
ij
f i j n
xx
,,,,,
OXf )(2
例 2.5 设 是对称矩阵，,求二次函数在任意点处的梯度和 Hesse矩阵．
解 设 则将它对各变量 求偏导数，得
∴
nnRa 1RcRb n,()fX?
12 TTX A X b X c
1 2 1 2( ) [ ] [ ]TTij n n n nA a X x x x b b b b，,,,,,,,
12
1 1 1
1()
2
n n n
n i j i j i i
i j i
f x x x a x x b x c
，,,
( 1 2 )ix i n?,,,
1 1 1
1111
11
()
()
()
nn
j j j j
jj
nn
n
nj j n nj j
jjn
fX
a x b a x
xb
fX
f X b
a x b a x
x
bAXXf )(
在上式中显然再对它们求偏导数得
∴
以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，
其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵,最后介绍在今后的计算中要用到的向量函数的导数．
1
() 12n
i j j i
ji
fX a x b i n
x?
,,,,
2 ()
12ij
ij
fX a i j n
xx
,,,,,
A
aaa
aaa
aaa
Xf
nnnn
n
n
21
22221
11211
2 )(
定义 2.6 设,记
如果 在点 处于自变量 的各分量的偏导数 都存在，则称向量函数
在点 处是一阶可导的，并且称矩阵
1 0 1 0 1 0
12
2 0 2 0 2 0
120
0 0 0
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nmn
m m m
n
h X h X h X
x x x
h X h X h X
x x xHX
h X h X h X
x x x
nmn RXRRH 0，,1( ) [ ( ) ( ) ] TmH X h X h X?,,
( 1 2 )ih i m?,,,0X TnxxxX ],,,[ 21
0() ( 1 2 )i
j
hX jnx,,,
)(XH 0X
是在点处的一阶导数或 Jacobi矩阵，简记为
由于 n元函数 的梯度是向量函数
所以 的一阶导数或 Jacobi矩阵为
00( ) ( )mnH X H X
1RRf n?：
1
( ) ( )() T
n
f X f XfX
xx
，,
)(Xf?
1 1 2 1 1
1 2 2 2 2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nn n
n n n n
f X f X f X
x x x x x x
f X f X f X
fX x x x x x x
f X f X f X
x x x x x x
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 X f X f X
x x x x x
f X f X f X
fXx x x x x
f X f X f X
x x x x x
，
得到
1 1 2 1 1
1 2 2 2 2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nn n
n n n n
f X f X f X
x x x x x x
f X f X f X
fX x x x x x x
f X f X f X
x x x x x x
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 X f X f X
x x x x x
f X f X f X
fXx x x x x
f X f X f X
x x x x x
，
)()( 2 XfXfnn
据此，从上式得知，函数梯度的 Jacobi矩阵即为此函数的 Hesse矩阵．
下面给出今后要用到的几个公式：
（ 1）,其中 是分量全为常数的 维向量，是
阶零矩阵．
（ 2）,其中 是维向量，是 阶单位矩阵．
（ 3）,其中 是 阶矩阵．
（ 4）设,其中,则
Oc c n O
nn?
IX X I nn?
()AX A A nm?
)()( 0 tPXft 1 1 1nf R R R R：,,
PtPXfPtPtPXft TT )()(,)()( 020
二、泰勒展开式
多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是从它出发，这里给出泰勒展开定理及其证明．
定理 2.2 设 具有二阶连续偏导数，则
（ 2.3）
其中,而,
证 设,于是
,
对 按一元函数在 点展开，得到
其中,令,于是 (2.4)
1RRf n?：
PXfPPXfXfPXf TT )(21)()()( 2
PXX 10
)()( tPXft
( 0 ) ( ) (1 ) ( )f X f X P，
)(t? 0?t
2)(
2
1)0()0()( tttt
10 1?t )(
2
1)0()0()1(
又因为
代入式（ 2.4）中，所以
式（ 2.3）还可以写成
2(0 ) ( ) ( ) ( )TTf X P P f X P P，
PPXfPPXfXfPXf TT )(21)()()( 2
)||( | |)(21)()()( 22 PoPXfPPXfXfPXf TT
§ 2.4 极小点的判定条件
函数在局部极小点应满足什么条件？反之，满足什么条件的是局部极小点？这是我们关心的基本问题．
下面针对多元函数的情形给出各类极小点的定义．
定义 2.7 对于任意给定的实数,满足不等式
集合称为点的邻域，记为
定义 2.8 设,若存在点 和数,
都有,则称 为 局部极小点
（非严格）．
0 |||| 0XX
}0,|||||{),( 00 XXXXN
1RRDf n,DX?* 0
X *(,)N X D? )()( * XfXf? *X )(Xf
定义 2.9 设,若存在点和数,但,都有,则称 为 的严格局部极小点．
定义 2.10 设,若存在点和数,都有,则称为 在 D上的全局极小点（非严格）．
定义 2.11 设,若存在点,
但,都有,则称 为
在 D上的严格全局极小点．
1RRDf n,DX?*
0X *(,)N X D? *XX?
)()( * XfXf? *X )(Xf
1RRDf n,DX?*
0 DX )()( * XfXf? *X
)(Xf
1RRDf n,DX?*
DX *XX? )()( * XfXf? *X
)(Xf
由以上定义看到，是局部极小点，是指在以为中心的一个邻域中在点处取得最小的值；而是全局极小点，是指在定义域 D中在点处取得最小的值．全局极小点可能在某个局部极小点处取得，也可能在 D的边界上取得．实际问题通常是求全局极小点，但是直到目前为止，最优化中绝大多数方法都是求局部极小点的，
解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点．
定理 2.3 设 具有连续的一阶偏导数．若 是 的局部极小点并且是
D的内点，则
（ 2.5）
证 设 是任意单位向量，因为 是 的局部极小点，所以存在,当 或
时总有
,（ 2.6）
引入辅助一元函数,此时，
由式（ 2.6）得,又因
1RRDf n：
*X )(Xf
0)( * Xf
e *X )(Xf
0|| t
),( **?XNteX
)()( ** XfteXf
)()( * teXft
)0()(t *X
是 D的内点，所以与它对应的 是的局部极小点．又根据一元函数极小点的必要条件，得到,即 再由单位向量 的任意性得,
这里条件（ 2.5）仅仅是必要的，而不是充分的．例如 在点 处的梯度是,但 是双曲面的鞍点，而不是极小点（如图 2.2所示）．
0?t )(t?
0)0( 0)( * eXf T
e 0)( * Xf
2121 ),( xxxxf? * [ 0,0 ]TX?
Tf ]0,0[)0,0( TX ]0,0[*?
定义 2.12 设 是 D的内点．若,则称 为 的驻点．
定理 2.4 设 具有连续二阶偏导数,是 D的一个内点．若,
并且 是正定的，则 是 的严格局部极小点．
*1 XRRDf n,,
0)( * Xf *X )(Xf
1RRDf n：
*X 0)( * Xf
)( *2 Xf? *X )(Xf
证 因为 是正定矩阵，则必存在,使得对于所有的 都有
（参看高等代数二次型理论）．现在将
在点 处按泰勒公式展开，并注意到,于是可得
)( *2 Xf?
0 nRP?
2*2 ||||)( PPXfP T
)(Xf *X
0)( * Xf
* * 2 * * * 2
* 2 * 2
1
( ) ( ) ( ) ( ) ( ) ( || || )
2
|| || ( || || )
2
Tf X f X X X f X X X o X X
X X o X X
,
当 充分接近 （但 ）时，上式左端的符号取决于右端第一项，因此
一般说来，这个定理仅具有理论意义．因为对于复杂的目标函数,Hesse矩阵不易求得，它的正定性就更难判定了．
X *X *XX?
)()( *XfXf?
定理 2.5 若多元函数在其极小点处的 Hesse矩阵是正定的，则它在这个极小点附近的等值面近似地呈现为同心椭球面族．
证 设 是多元函数的极小点，并设 是充分靠近极小点 的一个等值面，即 充分小．把 在点 展成泰勒表达式，即
右端第二项因 是极小点有 而消失．如果略去第 4项,那么
又因为,所以
（ 2.7）
按假设 正定，由二次型理论知式（ 2.7）
是以 为中心的椭球面方程．
*X)(Xf
*X |||| *XX?
)(Xf *X
* * *
* 2 * * * 2
( ) ( ) ( ) ( )
1 ( ) ( ) ( ) ( || || )
2
T
T
f X f X f X X X
X X f X X X o X X
,
*X 0)( * Xf
))(()(21)()( **2** XXXfXXXfXf T
)( Xf * * 2 * *1( ) ( ) ( ) ( )2 Tf X X X f X X X
* 2 * * *( ) ( ) ( ) 2 ( ( ) ) ( )TX X f X X X f X c 为 常 数
)( *2 Xf?
*X
§ 2.5 锥、凸集、凸锥
在本节中，给出维 Euclid空间 中的锥、凸集和凸锥的定义，以及与其相关的一些概念和性质．
一、定义与简单性质
定义 2.13 集合,若,及任意的数,均有,则称 C为锥．
定义 2.14 设 是 中的 个已知点．若对于某点 存在常数 且 使得,则称 是 的凸组合．若
且,则称 是 的严格凸组合,
nR
nRC? CX
0 CX
lXXX,，,?21
nR l
nRX? 12 0l，,,?
l
i
i
1
1?
l
i
ii XX
1
X lXXX,，,?21
12 0l，,,?
l
i
i
1
1?
X lXXX,，,?21
定义 2.15 集合,若 和,
以及任 意的数,均有则称 C为凸集．
定义 2.16 设 且,,则集合
称为 中的半空间．
特别地，规定：空集是凸集．容易验证，
空间,半空间、超平面、直线、点、
球都是凸集．
nRC? CX 1 CX 2
[0 1],
12(1 )X X C
nRa? 0a? 1Rb?
}|{ nRXbaXX,nR
nR
定理 2.6 任意一组凸集的交仍然是凸集．
证 设,其中 I是 的下标集,都是凸集．任取，则对于任意都是．任取
且,因 是凸集,有
于是,即 C是凸集．
若集合 C为锥,C又为凸集，则称 C为凸锥．若 C为凸集，也为闭集，则称 C为闭凸集．若 C为凸锥，也为闭集，则称 C为闭凸锥．
iIi CC
}{ iC iC
CXX?21,121
iC
iCXX 2211
1 1 2 2 iiIX X C C
由数学归纳法不难证明如下的定理 2.7和
2.8．
定理 2.7 集合 C为凸集的充分必要条件是,及任意数 （ ）
,有
定理 2.8 集合 C为凸锥的充分必要条件是,及任意数,( )，
均有
定义 2.17 有限个半空间的交 称为多面集,其中 为 矩阵，为 向量
CX i 0?i? 1 2 2i k k，,,,
k
i
i
1
1
k
i
ii CX
1
CX i 0
i 1 2 2i k k，,,,
1
k
ii
i
XC?
{}X A X b?
nm?A b m
例 2.6 集合
为多面集，其几何表示如图 2.3画斜线部分．
图 2.3在多面集的表达式中，若,则多面集 也是凸锥，称为多面锥．
在有关凸集的理论及应用中，极点和极方向的概念有着重要作用．
}0142{ 212121 xxxxxxXS,，，
0b?
0X AX?
定义 2.18 设 C为非空凸集，,若 不能表示成 C 中两个不同点的凸组合；换言之，若设,
必推得,则称 是凸集 C的极点．
按此定义，图 2.4(a)中多边形的顶点,,,和 是极点，而 和 不是极点．图 2.4(b)中圆周上的点均为极点,由图 2.4可以看出，在给定的两个凸集中，任何一点都能表示成极点的凸组合．
CX? X
12( 1 )X X X )10(,
21 XXX X
1X 2X 3X 4X 5X 6X 7X
定义 2.19 设 C为 中的闭凸集,P为非零向量，
如果对 C中的每一个,都有射线,
则称向量 P为 C的方向．又设 和 是的两个方向，
若对任何正数,有,则称 和 是两个不同的方向．若 C的方向 P不能表示成该集合的两个不同方向的正的线性组合，则称 p为 c的极方向．
nR
X
CPX }0{
1P
2P
21 PP
1P
2P
概括起来，有下列定理：
定理 2.9 （ Representation Theorem）
设 为非空多面集，则有
（ 1）极点集非空，且存在有限个极点
（ 2）极方向集合为空集的充要条件是 C
有界．若无界，则存在有限个极方向
（ 3） 的充要条件是
其中
}0,{ XbAXXC
CX
k
j
l
j jjjj
PXX
1 1
k
j
j
1
1? )21(0 kjj,，,
)21(0 ljj,，,
二、凸集分离定理
凸集分离定理是凸分析中最重要的定理之一，
它在最优化理论和模型当中具有重要的应用．
所谓集合的分离是指对于两个集合 C1和 C2存在一个超平面 H，使得 C1在 H的一边，而 C2在 H
的另一边．如果超平面方程为,那么对位于 H某一边的点必有,而对位于 H
另一边的必有,
定义 2.20 设 C1和 C2是 中的两个非空集合，
是超平面，若对于每一个 都有,对于每一个 都有 （或情况恰好相反），则称超平面 H分离集合 C1和
C2．
TPX
TPX
TPX
nR
{ | }TH X P X 1CX?
TPX 2CX? TPX
定理 2.10 若 C为闭凸集，,则存在
以及数,对,有
并且存在,使得,
定理 2.11 设 C为凸集，,则存在
使得,有
定理 2.12 设 C为闭凸集，则 C可表为所有包含 C
的半空间的交，即
其中
CX?0
nRa? 0a? 1R CX
0TTa X a X
CX?1
1TaX
CX?0 nRa?
0a? CX 0XaXa TT?
}|{?
XaXC T
La
1 | { | },0nTaL R X a X S a?
§ 2.6 凸函数
一、各类凸函数定义及性质
设函数 定义在凸集 R上，其中
定义 2.21 若存在常数,使得
以及,有
则称 为一致凸函数；有
则称为严格凸函数；有
则称为凸函数．
)(Xf
12() TnX x x x d?,,,
0 RXRX 21,
(0 1),
12( (1 ) )f X X 22121 ||||)1()()1()( XXXfXf
)(Xf
)()1()())1(( 2121 XfXfXXf
12( ( 1 ) )f X X )()1()( 21 XfXf
定义 2.22 设 为可微函数．若
满足
都有
则称 为伪凸函数．
定义 2.23 对,且,
以及,若
则称为严格拟凸函数；
定义 2.24 对,以及,若
则称为拟凸函数；
定义 2.25 对
则称为强拟凸函数．
)(Xf RXRX 21,
2 1 2( ) ( ) 0Tf X X X
1()fX? )( 2Xf
)(Xf
RXRX 21,)()( 21 XfXf?
)1,0( )}(),(m a x {))1((
2121 XfXfXXf
RXRX 21,)1,0(
12( ( 1 ) )f X X )}(),(m a x { 21 XfXf
RXRX 21,
)}(),(m a x {))1(( 2121 XfXfXXf
定理 2.13 若 为一致凸函数，则为严格凸函数．
证：设 为一致凸函数，
则,,,及,有
即为严格凸函数．
)(Xf
)(Xf
RX 1 RX 2 21 XX? (0 1),
12( (1 ) )f X X 22121 ||||)1()()1()( XXXX
)()1()( 21 XXf
定理 2.14 若为严格凸函数，则为凸函数．
定理 2.15 设为可微函数．若为凸函数，则为伪凸函数．
定理 2.16 设为伪凸函数，则为严格拟凸函数．
定理 2.17 设为下半连续的严格拟凸函数，则为拟凸函数．
定理 2.18 若为严格凸函数，则为强拟凸函数．
定理 2.19 设为强拟凸函数，则为严格拟凸函数．
凸函数与凸集之间有如下关系：
定理 2.20 设,其中 C为非空凸集．若 f是凸函数，则对于任意实数,水平集是凸集．
证 若 是空集，则 是凸集．以下设 非空，任取,则,设 且
,由 f是凸函数知
即,所以 是凸集,
判定一个函数是否为凸函数，一般说来是比较困难，
但当函数可微时，有如下几个定理可供使用．
1,RRCf n
},)(|{ CXXfXD
D?D?D
DXX?21, )(,)( 21 XfXf ]1,0[,21
121
1 2 2 1 1 2 2 1 2( ) ( ) ( )f X X f X f X
DXX 2211?D
定理 2.21 设 是可微函数，其中 C为凸集．则
（ 1）为凸函数的充要条件是，,都有
（ 2.11）
（ 2）为严格凸函数的充要条件是,且
都有
证 （ 1）必要性 已知 f是 C上的凸函数，要证式
（ 2.11）．由凸函数定义知，对满足 的任意数都有
令,则,代入上式中，经移项可得
1,RRCf n
CXX 21,
)()()()( 12112 XXXfXfXf T
CXX 21,21 XX?
)()()()( 12112 XXXfXfXf T
121
]1,0[,21 )()()( 22112211 XfXfXXf
t?2? t 11?
（ 2.12）
令,由 f的可微性，利用一阶泰勒展式、方向导数定义及式（ 2.12），可得
这就证明了式（ 2.11）．
充分性 任取一对数 且 考虑点,根据充分性假设，应有
)()()())(( 121121 XfXft XfXXtXf
0?t
)()()()( 12121 XfXfXXXf T
12 [0,1],121
2211 XXX
11( ) ( ) ( ) ( )Tf X f X f X X X
22( ) ( ) ( ) ( )Tf X f X f X X X
两式分别乘以 和 后相加，得到
由凸函数定义知,f是 C上的凸函数．
（ 2）充分性可依照（ 1）的充分性证得．
必要性 因为严格凸函数本身是凸函数，
所以 且,都有
以下证明式中只能取,>”号．假设存在,且,使得
（ 2.12）
1? 2?
1 1 2 2 1 1 2 2( ) ( ) ( ) ( ) ( )
Tf X f X f X f X X X X
1 1 2 2()f X X
CXX 21,21 XX? )()()()( 12112 XXXfXfXf T
CXX?21,21 XX?
)()()()( 12112 XXXfXfXf T
取,由的严格凸性，有
（ 2.13）
把式（ 2.12）代入式（ 2.13）中，经整理得
根据本定理（ 1）部分结论得知，此式与是凸函数相矛盾．
定理 2.22 设 是二次可微函数,C
为非空开凸集，则 f为 c上凸函数的充要条件是，
Hesse矩阵 在 C上到处半正定．
证明略．
213 2/12/1 XXX
)(21)(21)( 213 XfXfXf
)()()()( 13113 XXXfXfXf T
1RRCf n：
)(2 Xf?
定理 2.23 设 是二次可微函数,C
为非空凸集．若 Hesse矩阵在 C上到处正定，则
f在 C上为严格凸函数．
证明略，需要注意，该定理的逆命题不真．
例如 为严格凸函数，但是它的 Hesse
矩阵在点 x=0处是半正定的．
二、凸规划
定义 2.26 设,其中 C是非空凸集,f
是凸函数，则形式为 的问题称为凸规划问题．
4)( xxf?
1RRCf n：
1RRCf n：
m in ( )XC fX?
更进一步，设
若 都是 上的凸函数,都是
上的线性函数，则容易验证 C是凸集．事实上，因为 都是凸函数，根据定理 2.20集合
也都是凸集．此外，超平面,
也都是凸集．显然,C是 的交集，根据定理 2.6,C是凸集．于是，在这种情况下凸规划问题又可表示成如下形式：
{ | ( ) 0 1 2 ( ) 0 1 2 }nijC X g X i l h X j m X R，,,,；,,,,；
lggg,，,?21
nR mhhh,，,?21
nR
lggg,，,?21
{ | ( ) 0 } 1 2niiC X g X X R i l，,,,,
mjRXXhXP njj,,1},,0)(|{
,,,11 CC? mPP,,1?
m i n ( )
( ) 0 1 2
..
( ) 0 1 2
i
j
fX
g X i l
st
h X j m
，
，,,,,
，,,,,
定理 2.24 设 是凸规划问题的局部极小点，
（ 1）若 f是凸函数，则 是凸规划问题全局极小点；
（ 2）若 f是严格凸函数，则 是凸规划问题的唯一全局极小点．
证（ 1）使用反证法．假设 不是全局极小点，
则必存在 使得,对于 Z与
的任意凸组合,其中且,根据的凸性，有
由此看到，当 充分小时，充分接近,注意到此时也有,而这与 是局部极小点相矛盾．因此 必是全局极小点．
*X
*X
*X
*X
CZ? *( ) ( )f Z f X? *X
*21 XZX 12 ( 0 1 )，,
121
)()()()( *21*21 XfZfXZfXf )()()( **2*1 XfXfXf
01 X *X
)()( *XfXf? *X
*X
（ 2）假设 不是唯一全局极小点．必存在 但 使得 考虑中点,由 f的严格凸性，
有,此式与
为全局极小点相矛盾．这就证明了唯一性．
定义 2.27 形式为
（ 2.14）
的函数称为 n元二次函数，其中
*X
CX *XX )()( *XfXf
CXXX *2121
)()(21)(21)2121()( *** XfXfXfXXfXf
*X
CXbQXXXf TT 21)(
这里的 Q是对称矩阵，即．
若 Q为正定，则称（ 2.14）为正定二次函数．注意到
,由定理 2.23知，正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用．
定义 2.28 形式为
（ 2.15）
的问题称为二次规划问题，其中是矩阵，是矩阵．
若 Q为半正定或正定，则称（ 2.15）为二次凸规划问题．本书不作专门讨论
nnnnn
n
n
b
b
b
b
qqq
qqq
qqq
Q
2
1
21
22221
11211
，
QXf )(2
dCX
PAX
ts
cXbQXXXf TT
，
，
..
2
1
)(m i n
2.7约束问题的最优性条件
所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件．这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的．最优性必要条件是指，在最优点处满足哪些条件；
充分条件是指满足哪些条件的点是最优点．本节仅讲述最基本的结论．
一、约束最优解
对约束优化问题的求解，其目的是在由约束条件所规定的可行域内，寻求一个目标函数值最小的点及其函数值．这样的解称为约束最优解．约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同．
（一）约束优化问题的类型
约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：
（ 1）不等式约束优化问题（ IP型）
（ 2.16）
（ 2）等式约束优化问题（ EP型）
（ 3）一般约束优化问题（ GP型）
m i n ( ),
.,( ) 0 1 2i
fX
s t g X i l，,,,,
m in ( )
.,( ) 0 1 2j
fX
s t h X j m
，
，,,,,
m in ( )
( ) 0 1 2
..
( ) 0 1 2
i
j
fX
g X i l
st
h X j m
，
，,,,,
，,,,,
（二）约束优化问题的局部解与全局解
按一般约束优化问题，其可行域为
若对某可行点 存在,当 与它邻域的点之距离 时，总有 则称 为该约束优化问题的一个局部最优解．
下面以一个简单例子说明．设有
{ | ( ) 0 1 2 ( ) 0 1 2 }ijD X g X i l h X j m，,,,；,,,,
*X 0 *X X
|||| *XX )()( * XfXf? *X
．
，
，
09)2()(
02)(
..
)1()(m i n
2
2
2
1
2
2
2
2
1
xxXh
xXg
ts
xxXf
该问题的几何图形如图 2.8所示．从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解,,这是因为在 点邻域的任一满足约束的点,都有
同理，亦然．
TX ]0,1[*1 TX ]0,5[*2? *1X
X )()( *1XfXf?
*2X
对某些约束优化问题，局部解可能有多个．在所有的局部最优解中，目标函数值最小的那个解称为全局最优解．
在上例中，由于，所以全局最优解为．
由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解．这与无约束优化问题是相同的．
二、约束优化问题局部解的一阶必要条件
对于约束，我们现在进一步阐明起作用约束与不起作用约束的概念．一般的约束优化问题，
其约束包含不等式约束 和等式约束,在可行点 处，如写有
则该约束 称可行点 不起作用约束．对于等式约束，显然在一可行点的等式约束都是起作用约束．
在某个可行点 处，起作用约束在 的邻域内起到限制可行域范围的作用，而不起作用约束在 处的邻域内就不产生影响．因此，应把注意力集中在起作用约束上．
liXg i,,2,1,0)(
mjXh j,,2,1,0)( kX 0)(?
ki Xg
)(Xgi kX
0)(?Xhj
kX kX
kX
（一） IP型约束问题的一阶必要条件图 2.9所示具有三个不等式约束的二维最优化问题．
图 2.9（ a）是最优化在可行域内部的一种情况．在此种情形下，点的全部约束函数值均大于零，所以这组约束条件对其最优点都不起作用．换句话说，如果除掉全部约束，其最优点也仍是同一个点．因此这种约束优化问题与无约束优化问题是等价的．图 2.9（ b）所示的约束最优点在 的边界曲线与目标函数等值线的切点处．此时所以 是起作用约束，而其余的两个是不起作用约束．
*X )( *Xgi
)(1 Xg
0)( *1?Xg 0)( *2?Xg 0)( *3?Xg
)(1 Xg
§ 1.1 二次型与正定矩阵一,二次型与实对称矩阵二次型理论在最优化设计中应用十分广泛．应用矩阵的乘法运算，二次型与实对称矩阵紧密地联系在一起了，从而二次型的基本问题又可转化成实对称矩阵问题,二次型理论问题起源于化二次曲线和二次曲面的方程为标准形式的问题．推广到 n维空间中，二次超曲面的一般方程为
，
，，，
n
i
n
j
jiij
nnnnnnn
nn
nnn
xxa
xaxxaxxa
xxaxaxxa
xxaxxaxaxxxf
1 1
2
2211
22
2
2221221
112112
2
11121
)(
用矩阵表示为其中，矩阵 A的元素 正是二次型的项的系数的一半,是二次型的 项的系数．因此，二次型和它的矩阵 A是相互唯一决定的，且,
，
，，，，，，
AXX
x
x
x
Axxxxxaxxxf
T
n
i
n
j
n
njiijn
1 1
2
1
2121
][)(
)( jiaa jiij
jixx
iia 2ix
TAA?
二、正定矩阵
定义 2.1 如果二次型
对于任何一组不全为零的数 恒有
则称 正定，且二次型矩阵 A也称为正定．
简言之，一个对称矩阵 A如果是正定的，则二次型
对于所有非零向量 X其值总为正．类似可以给出定义，若二次型
则 A为半正定矩阵；若,则 A为半负定矩阵；若二次型既不是半正定又不是半负定，就称矩阵 A为不定的．
n
i
n
j
T
jiijn AXXxxaxxxf
1 1
21 )(,，,?
nxxx,，,?21
0)( 21 AXXxxxf Tn，，,?
)( 21 nxxxf,，,?
)( 21 nxxxf,，,? AXX T?
0)( 21 AXXxxxf Tn，，,?
0?AXX T
矩阵 A为正定的充要条件是它的行列式的顺序主子式全部大于零，即
由此可见，正定矩阵必然是非奇异的．
例 2.1 判断矩阵 是否正定．
解 ∵,
∴ A是正定的．
11 12 1
21 22 211 12
11
21 22
12
0 0 0
n
n
n n nn
a a a
a a aaa
a
aa
a a a
，,,
201
032
124
A
4 2 1
424 0 8 0 2 3 0 13 0
23 102
，,
一、方向导数
所谓方向导数的概念是作为偏导数的一个推广而引入，它主要研究函数沿任一给定方向的变化率．
定义 2.2 设 在点 处可微,P是固定不变的非零向量,是方向 P上的单位向量，则称极限
(2.1)
为函数 在点 处沿 P方向的方向导数，式中是它的记号．
§ 2.2 方向导数与梯度
1,RRf n? 0X
e
t
XfteXf
P
Xf
t
)()(lim)( 00
0
0
)(Xf 0X
P
Xf
)( 0
定义 2.3 设 是连续函数，,
且,若存在,当 时都有，
则称 P为在点处的下降方
向．若,则称 P为在点处的上升方向．
由以上两个定义可立刻得到如下的结论：
若,则 从 出发在 附近沿 P
方向是下降；若,则从出发在附近沿 P方向是上升．
1,RRf n? 0X
0?P 0 ),0(t
)()( 00 XftPXf
)()( 00 XftPXf
0)( 0 PXf )(Xf 0X 0X
0)( 0 PXf
二、梯度
定义 2.4 以 的 n个偏导数为分量的向量称为 在 X处的梯度，
记为
,
梯度也可以称为函数 关于向量 的一阶导数．
以下几个特殊类型函数的梯度公式是常用的：
（ 1）若 （常数），则,即 ；
（ 2）,
证 设,则
于是 的第 个分量是
,
所以
（ 3）,
（ 4）若 Q是对称矩阵，则
)(Xf )(Xf
12
( ) ( ) ( )() T
n
f X f X f XfX
x x x
，,,
)(Xf X
cXf?)( 0)( Xf 0c
bXbT )(
1 2 1 2[ ] [ ]TTnnb b b b X x x x，,,,,,,?
n
i
iiT xbXb
1)( XbT? j
1
( ) ( ) 1 2nT i i j
ijj
b X b x b j nxx
,,,,
bXbT )(
XXX T 2)(
QXQXX T 2)(
三、梯度与方向导数之间的关系
定理 2.1 设 在点 处可微，则
,
其中 是 方向上的单位向量,
由这个定理容易得到下列结论：
(1)若,则 P的方向是函数在点 处的下降方向；
(2) 若,则 的方向是函数在点处的上升方向．
方向导数的正负决定了函数值的升降，而升降的快慢就由它的绝对值大小决定．绝对值越大，
升降的速度就越快，即
1,RRf n? 0X
eXfPXf T)()( 00
e P
0)( 0 PXf T
0)( 0 PXf T
0X
0XP
= ·1·
上式中的等号，当且仅当的方向与的方向相同时才成立．
由此可得如下重要结论 (如图 2.1所示）：
(1)梯度方向是函数值的最速上升方向；
(2)函数在与其梯度正交的方向上变化率为零；
(3)函数在与其梯度成锐角的方向上是上升的，而在与其梯度成钝角的方向上是下降的；
(4)梯度反方向是函数值最速下降方向．
0 0() () TfX f X eP 0()fX? 00( c o s ( ( ),) ) ( )f X e f X
·1·
对于一个最优化问题，为了尽快得到最优解，在每一步迭代过程中所选取的搜索方向总是希望它等于或者是靠近于目标函数的负梯度 -----图 2.1的方向，这样才能使函数值下降的最快．
例 2.2 试求目标函数在点处的最速下降方向，
并求沿这个方向移动一个单位长后新点的目标函数值．
解 因为
所以最速下降方向是－ = =,
这个方向上的单位向量是
故新点是
对应目标函数值为
1
1
2f xx 2
2
2f xx
0()fX?
1
2
1
02
3
2
2 x
x
x
x?
0
6
0
0
0()
1()
fXe
fX
10
0 0 0
3 1 2X X e
221( ) 0 2 1 5fX
§ 2.3 海色矩阵及泰勒展式
一、海色（ Hesse）矩阵
前面说过，梯度 是 关于 的一阶导数，现在要问 关于 的二阶导数是什么？
定义 2.5 设：,,,如果在点
处对于自变量的各分量的二阶偏导数
都存在，则称函数在点处二阶可导，并且称矩阵
()fX?
()fX X
()fXX
f 1RR n? nRX?
0
0X
是 在点 处的 Hesse矩阵．
在数学分析中已经知道，当 在点 处的所有二阶偏导数为连续时有
因此，在这种情况下 Hesse矩阵是对称的．
2 2 2
0 0 0
2
1 1 2 1
2 2 2
0 0 0
2 2
0 2 1 2 2
2 2 2
0 0 0
2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
n
n n n
f X f X f X
x x x x x
f X f X f X
fX x x x x x
f X f X f X
x x x x x
f 0X
f 0X
22
00( ) ( ) 12
i j j i
f X f X i j n
x x x x
,,,,
例 2.3 求目标函数 的梯度和 Hesse矩阵．
解 因为
所以
23132221233241 432)( xxxxxxxxxXf
232131
1
24 xxxxxf
32122
2
46 xxxxf
3123
3
246 xxxxxf
3123
3
2
1
2
2
2
321
3
1
246
46
24
)(
xxxx
xxx
xxxx
Xf
又因为
所以
2 2 2
2
1 2 1 32
1 1 2 1 3
2 2 2
2122
2 2 3 3
12 2 2 2
12 4 6 2
f f f
x x x x
x x x x x
f f f
xx
x x x x
，,,
，,,
13
21
312
2
1
2
2642
4122
22212
)(
xx
xx
xxxx
Xf
例 2.4 设,求线性函数在任意点 X处的梯度和 Hesse矩阵,
解,设,则
（ 2.2）
∴
由式（ 2.2）进而知
∴ （阶零矩阵）．
1,,RbRXRa nn bXaXf T)(
1 2 1 2[ ] [ ]TTnna a a a X x x x，,,,,,,
12
1
() nn i i
i
f x x x a x b
，,,
12i
i
f a i n
x
,,,,
aaaaXf Tn ],,,[)( 21?
2
0 1 2
ij
f i j n
xx
,,,,,
OXf )(2
例 2.5 设 是对称矩阵，,求二次函数在任意点处的梯度和 Hesse矩阵．
解 设 则将它对各变量 求偏导数，得
∴
nnRa 1RcRb n,()fX?
12 TTX A X b X c
1 2 1 2( ) [ ] [ ]TTij n n n nA a X x x x b b b b，,,,,,,,
12
1 1 1
1()
2
n n n
n i j i j i i
i j i
f x x x a x x b x c
，,,
( 1 2 )ix i n?,,,
1 1 1
1111
11
()
()
()
nn
j j j j
jj
nn
n
nj j n nj j
jjn
fX
a x b a x
xb
fX
f X b
a x b a x
x
bAXXf )(
在上式中显然再对它们求偏导数得
∴
以上例子说明，元函数求导与一元函数的求导在形式上是一致的，即线性函数的一阶导数为常向量，
其二阶导数为零矩阵；而二次函数的一阶导数为线性向量函数，二阶导数为常矩阵,最后介绍在今后的计算中要用到的向量函数的导数．
1
() 12n
i j j i
ji
fX a x b i n
x?
,,,,
2 ()
12ij
ij
fX a i j n
xx
,,,,,
A
aaa
aaa
aaa
Xf
nnnn
n
n
21
22221
11211
2 )(
定义 2.6 设,记
如果 在点 处于自变量 的各分量的偏导数 都存在，则称向量函数
在点 处是一阶可导的，并且称矩阵
1 0 1 0 1 0
12
2 0 2 0 2 0
120
0 0 0
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nmn
m m m
n
h X h X h X
x x x
h X h X h X
x x xHX
h X h X h X
x x x
nmn RXRRH 0，,1( ) [ ( ) ( ) ] TmH X h X h X?,,
( 1 2 )ih i m?,,,0X TnxxxX ],,,[ 21
0() ( 1 2 )i
j
hX jnx,,,
)(XH 0X
是在点处的一阶导数或 Jacobi矩阵，简记为
由于 n元函数 的梯度是向量函数
所以 的一阶导数或 Jacobi矩阵为
00( ) ( )mnH X H X
1RRf n?：
1
( ) ( )() T
n
f X f XfX
xx
，,
)(Xf?
1 1 2 1 1
1 2 2 2 2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nn n
n n n n
f X f X f X
x x x x x x
f X f X f X
fX x x x x x x
f X f X f X
x x x x x x
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 X f X f X
x x x x x
f X f X f X
fXx x x x x
f X f X f X
x x x x x
，
得到
1 1 2 1 1
1 2 2 2 2
12
( ) ( ) ( )
( ) ( ) ( )
()
( ) ( ) ( )
n
nn n
n n n n
f X f X f X
x x x x x x
f X f X f X
fX x x x x x x
f X f X f X
x x x x x x
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 X f X f X
x x x x x
f X f X f X
fXx x x x x
f X f X f X
x x x x x
，
)()( 2 XfXfnn
据此，从上式得知，函数梯度的 Jacobi矩阵即为此函数的 Hesse矩阵．
下面给出今后要用到的几个公式：
（ 1）,其中 是分量全为常数的 维向量，是
阶零矩阵．
（ 2）,其中 是维向量，是 阶单位矩阵．
（ 3）,其中 是 阶矩阵．
（ 4）设,其中,则
Oc c n O
nn?
IX X I nn?
()AX A A nm?
)()( 0 tPXft 1 1 1nf R R R R：,,
PtPXfPtPtPXft TT )()(,)()( 020
二、泰勒展开式
多元函数的泰勒展开在最优化方法中十分重要，许多方法及其收敛性的证明是从它出发，这里给出泰勒展开定理及其证明．
定理 2.2 设 具有二阶连续偏导数，则
（ 2.3）
其中,而,
证 设,于是
,
对 按一元函数在 点展开，得到
其中,令,于是 (2.4)
1RRf n?：
PXfPPXfXfPXf TT )(21)()()( 2
PXX 10
)()( tPXft
( 0 ) ( ) (1 ) ( )f X f X P，
)(t? 0?t
2)(
2
1)0()0()( tttt
10 1?t )(
2
1)0()0()1(
又因为
代入式（ 2.4）中，所以
式（ 2.3）还可以写成
2(0 ) ( ) ( ) ( )TTf X P P f X P P，
PPXfPPXfXfPXf TT )(21)()()( 2
)||( | |)(21)()()( 22 PoPXfPPXfXfPXf TT
§ 2.4 极小点的判定条件
函数在局部极小点应满足什么条件？反之，满足什么条件的是局部极小点？这是我们关心的基本问题．
下面针对多元函数的情形给出各类极小点的定义．
定义 2.7 对于任意给定的实数,满足不等式
集合称为点的邻域，记为
定义 2.8 设,若存在点 和数,
都有,则称 为 局部极小点
（非严格）．
0 |||| 0XX
}0,|||||{),( 00 XXXXN
1RRDf n,DX?* 0
X *(,)N X D? )()( * XfXf? *X )(Xf
定义 2.9 设,若存在点和数,但,都有,则称 为 的严格局部极小点．
定义 2.10 设,若存在点和数,都有,则称为 在 D上的全局极小点（非严格）．
定义 2.11 设,若存在点,
但,都有,则称 为
在 D上的严格全局极小点．
1RRDf n,DX?*
0X *(,)N X D? *XX?
)()( * XfXf? *X )(Xf
1RRDf n,DX?*
0 DX )()( * XfXf? *X
)(Xf
1RRDf n,DX?*
DX *XX? )()( * XfXf? *X
)(Xf
由以上定义看到，是局部极小点，是指在以为中心的一个邻域中在点处取得最小的值；而是全局极小点，是指在定义域 D中在点处取得最小的值．全局极小点可能在某个局部极小点处取得，也可能在 D的边界上取得．实际问题通常是求全局极小点，但是直到目前为止，最优化中绝大多数方法都是求局部极小点的，
解决这一矛盾的一种方法是先求出所有的局部极小点，再求全局极小点．
定理 2.3 设 具有连续的一阶偏导数．若 是 的局部极小点并且是
D的内点，则
（ 2.5）
证 设 是任意单位向量，因为 是 的局部极小点，所以存在,当 或
时总有
,（ 2.6）
引入辅助一元函数,此时，
由式（ 2.6）得,又因
1RRDf n：
*X )(Xf
0)( * Xf
e *X )(Xf
0|| t
),( **?XNteX
)()( ** XfteXf
)()( * teXft
)0()(t *X
是 D的内点，所以与它对应的 是的局部极小点．又根据一元函数极小点的必要条件，得到,即 再由单位向量 的任意性得,
这里条件（ 2.5）仅仅是必要的，而不是充分的．例如 在点 处的梯度是,但 是双曲面的鞍点，而不是极小点（如图 2.2所示）．
0?t )(t?
0)0( 0)( * eXf T
e 0)( * Xf
2121 ),( xxxxf? * [ 0,0 ]TX?
Tf ]0,0[)0,0( TX ]0,0[*?
定义 2.12 设 是 D的内点．若,则称 为 的驻点．
定理 2.4 设 具有连续二阶偏导数,是 D的一个内点．若,
并且 是正定的，则 是 的严格局部极小点．
*1 XRRDf n,,
0)( * Xf *X )(Xf
1RRDf n：
*X 0)( * Xf
)( *2 Xf? *X )(Xf
证 因为 是正定矩阵，则必存在,使得对于所有的 都有
（参看高等代数二次型理论）．现在将
在点 处按泰勒公式展开，并注意到,于是可得
)( *2 Xf?
0 nRP?
2*2 ||||)( PPXfP T
)(Xf *X
0)( * Xf
* * 2 * * * 2
* 2 * 2
1
( ) ( ) ( ) ( ) ( ) ( || || )
2
|| || ( || || )
2
Tf X f X X X f X X X o X X
X X o X X
,
当 充分接近 （但 ）时，上式左端的符号取决于右端第一项，因此
一般说来，这个定理仅具有理论意义．因为对于复杂的目标函数,Hesse矩阵不易求得，它的正定性就更难判定了．
X *X *XX?
)()( *XfXf?
定理 2.5 若多元函数在其极小点处的 Hesse矩阵是正定的，则它在这个极小点附近的等值面近似地呈现为同心椭球面族．
证 设 是多元函数的极小点，并设 是充分靠近极小点 的一个等值面，即 充分小．把 在点 展成泰勒表达式，即
右端第二项因 是极小点有 而消失．如果略去第 4项,那么
又因为,所以
（ 2.7）
按假设 正定，由二次型理论知式（ 2.7）
是以 为中心的椭球面方程．
*X)(Xf
*X |||| *XX?
)(Xf *X
* * *
* 2 * * * 2
( ) ( ) ( ) ( )
1 ( ) ( ) ( ) ( || || )
2
T
T
f X f X f X X X
X X f X X X o X X
,
*X 0)( * Xf
))(()(21)()( **2** XXXfXXXfXf T
)( Xf * * 2 * *1( ) ( ) ( ) ( )2 Tf X X X f X X X
* 2 * * *( ) ( ) ( ) 2 ( ( ) ) ( )TX X f X X X f X c 为 常 数
)( *2 Xf?
*X
§ 2.5 锥、凸集、凸锥
在本节中，给出维 Euclid空间 中的锥、凸集和凸锥的定义，以及与其相关的一些概念和性质．
一、定义与简单性质
定义 2.13 集合,若,及任意的数,均有,则称 C为锥．
定义 2.14 设 是 中的 个已知点．若对于某点 存在常数 且 使得,则称 是 的凸组合．若
且,则称 是 的严格凸组合,
nR
nRC? CX
0 CX
lXXX,，,?21
nR l
nRX? 12 0l，,,?
l
i
i
1
1?
l
i
ii XX
1
X lXXX,，,?21
12 0l，,,?
l
i
i
1
1?
X lXXX,，,?21
定义 2.15 集合,若 和,
以及任 意的数,均有则称 C为凸集．
定义 2.16 设 且,,则集合
称为 中的半空间．
特别地，规定：空集是凸集．容易验证，
空间,半空间、超平面、直线、点、
球都是凸集．
nRC? CX 1 CX 2
[0 1],
12(1 )X X C
nRa? 0a? 1Rb?
}|{ nRXbaXX,nR
nR
定理 2.6 任意一组凸集的交仍然是凸集．
证 设,其中 I是 的下标集,都是凸集．任取，则对于任意都是．任取
且,因 是凸集,有
于是,即 C是凸集．
若集合 C为锥,C又为凸集，则称 C为凸锥．若 C为凸集，也为闭集，则称 C为闭凸集．若 C为凸锥，也为闭集，则称 C为闭凸锥．
iIi CC
}{ iC iC
CXX?21,121
iC
iCXX 2211
1 1 2 2 iiIX X C C
由数学归纳法不难证明如下的定理 2.7和
2.8．
定理 2.7 集合 C为凸集的充分必要条件是,及任意数 （ ）
,有
定理 2.8 集合 C为凸锥的充分必要条件是,及任意数,( )，
均有
定义 2.17 有限个半空间的交 称为多面集,其中 为 矩阵，为 向量
CX i 0?i? 1 2 2i k k，,,,
k
i
i
1
1
k
i
ii CX
1
CX i 0
i 1 2 2i k k，,,,
1
k
ii
i
XC?
{}X A X b?
nm?A b m
例 2.6 集合
为多面集，其几何表示如图 2.3画斜线部分．
图 2.3在多面集的表达式中，若,则多面集 也是凸锥，称为多面锥．
在有关凸集的理论及应用中，极点和极方向的概念有着重要作用．
}0142{ 212121 xxxxxxXS,，，
0b?
0X AX?
定义 2.18 设 C为非空凸集，,若 不能表示成 C 中两个不同点的凸组合；换言之，若设,
必推得,则称 是凸集 C的极点．
按此定义，图 2.4(a)中多边形的顶点,,,和 是极点，而 和 不是极点．图 2.4(b)中圆周上的点均为极点,由图 2.4可以看出，在给定的两个凸集中，任何一点都能表示成极点的凸组合．
CX? X
12( 1 )X X X )10(,
21 XXX X
1X 2X 3X 4X 5X 6X 7X
定义 2.19 设 C为 中的闭凸集,P为非零向量，
如果对 C中的每一个,都有射线,
则称向量 P为 C的方向．又设 和 是的两个方向，
若对任何正数,有,则称 和 是两个不同的方向．若 C的方向 P不能表示成该集合的两个不同方向的正的线性组合，则称 p为 c的极方向．
nR
X
CPX }0{
1P
2P
21 PP
1P
2P
概括起来，有下列定理：
定理 2.9 （ Representation Theorem）
设 为非空多面集，则有
（ 1）极点集非空，且存在有限个极点
（ 2）极方向集合为空集的充要条件是 C
有界．若无界，则存在有限个极方向
（ 3） 的充要条件是
其中
}0,{ XbAXXC
CX
k
j
l
j jjjj
PXX
1 1
k
j
j
1
1? )21(0 kjj,，,
)21(0 ljj,，,
二、凸集分离定理
凸集分离定理是凸分析中最重要的定理之一，
它在最优化理论和模型当中具有重要的应用．
所谓集合的分离是指对于两个集合 C1和 C2存在一个超平面 H，使得 C1在 H的一边，而 C2在 H
的另一边．如果超平面方程为,那么对位于 H某一边的点必有,而对位于 H
另一边的必有,
定义 2.20 设 C1和 C2是 中的两个非空集合，
是超平面，若对于每一个 都有,对于每一个 都有 （或情况恰好相反），则称超平面 H分离集合 C1和
C2．
TPX
TPX
TPX
nR
{ | }TH X P X 1CX?
TPX 2CX? TPX
定理 2.10 若 C为闭凸集，,则存在
以及数,对,有
并且存在,使得,
定理 2.11 设 C为凸集，,则存在
使得,有
定理 2.12 设 C为闭凸集，则 C可表为所有包含 C
的半空间的交，即
其中
CX?0
nRa? 0a? 1R CX
0TTa X a X
CX?1
1TaX
CX?0 nRa?
0a? CX 0XaXa TT?
}|{?
XaXC T
La
1 | { | },0nTaL R X a X S a?
§ 2.6 凸函数
一、各类凸函数定义及性质
设函数 定义在凸集 R上，其中
定义 2.21 若存在常数,使得
以及,有
则称 为一致凸函数；有
则称为严格凸函数；有
则称为凸函数．
)(Xf
12() TnX x x x d?,,,
0 RXRX 21,
(0 1),
12( (1 ) )f X X 22121 ||||)1()()1()( XXXfXf
)(Xf
)()1()())1(( 2121 XfXfXXf
12( ( 1 ) )f X X )()1()( 21 XfXf
定义 2.22 设 为可微函数．若
满足
都有
则称 为伪凸函数．
定义 2.23 对,且,
以及,若
则称为严格拟凸函数；
定义 2.24 对,以及,若
则称为拟凸函数；
定义 2.25 对
则称为强拟凸函数．
)(Xf RXRX 21,
2 1 2( ) ( ) 0Tf X X X
1()fX? )( 2Xf
)(Xf
RXRX 21,)()( 21 XfXf?
)1,0( )}(),(m a x {))1((
2121 XfXfXXf
RXRX 21,)1,0(
12( ( 1 ) )f X X )}(),(m a x { 21 XfXf
RXRX 21,
)}(),(m a x {))1(( 2121 XfXfXXf
定理 2.13 若 为一致凸函数，则为严格凸函数．
证：设 为一致凸函数，
则,,,及,有
即为严格凸函数．
)(Xf
)(Xf
RX 1 RX 2 21 XX? (0 1),
12( (1 ) )f X X 22121 ||||)1()()1()( XXXX
)()1()( 21 XXf
定理 2.14 若为严格凸函数，则为凸函数．
定理 2.15 设为可微函数．若为凸函数，则为伪凸函数．
定理 2.16 设为伪凸函数，则为严格拟凸函数．
定理 2.17 设为下半连续的严格拟凸函数，则为拟凸函数．
定理 2.18 若为严格凸函数，则为强拟凸函数．
定理 2.19 设为强拟凸函数，则为严格拟凸函数．
凸函数与凸集之间有如下关系：
定理 2.20 设,其中 C为非空凸集．若 f是凸函数，则对于任意实数,水平集是凸集．
证 若 是空集，则 是凸集．以下设 非空，任取,则,设 且
,由 f是凸函数知
即,所以 是凸集,
判定一个函数是否为凸函数，一般说来是比较困难，
但当函数可微时，有如下几个定理可供使用．
1,RRCf n
},)(|{ CXXfXD
D?D?D
DXX?21, )(,)( 21 XfXf ]1,0[,21
121
1 2 2 1 1 2 2 1 2( ) ( ) ( )f X X f X f X
DXX 2211?D
定理 2.21 设 是可微函数，其中 C为凸集．则
（ 1）为凸函数的充要条件是，,都有
（ 2.11）
（ 2）为严格凸函数的充要条件是,且
都有
证 （ 1）必要性 已知 f是 C上的凸函数，要证式
（ 2.11）．由凸函数定义知，对满足 的任意数都有
令,则,代入上式中，经移项可得
1,RRCf n
CXX 21,
)()()()( 12112 XXXfXfXf T
CXX 21,21 XX?
)()()()( 12112 XXXfXfXf T
121
]1,0[,21 )()()( 22112211 XfXfXXf
t?2? t 11?
（ 2.12）
令,由 f的可微性，利用一阶泰勒展式、方向导数定义及式（ 2.12），可得
这就证明了式（ 2.11）．
充分性 任取一对数 且 考虑点,根据充分性假设，应有
)()()())(( 121121 XfXft XfXXtXf
0?t
)()()()( 12121 XfXfXXXf T
12 [0,1],121
2211 XXX
11( ) ( ) ( ) ( )Tf X f X f X X X
22( ) ( ) ( ) ( )Tf X f X f X X X
两式分别乘以 和 后相加，得到
由凸函数定义知,f是 C上的凸函数．
（ 2）充分性可依照（ 1）的充分性证得．
必要性 因为严格凸函数本身是凸函数，
所以 且,都有
以下证明式中只能取,>”号．假设存在,且,使得
（ 2.12）
1? 2?
1 1 2 2 1 1 2 2( ) ( ) ( ) ( ) ( )
Tf X f X f X f X X X X
1 1 2 2()f X X
CXX 21,21 XX? )()()()( 12112 XXXfXfXf T
CXX?21,21 XX?
)()()()( 12112 XXXfXfXf T
取,由的严格凸性，有
（ 2.13）
把式（ 2.12）代入式（ 2.13）中，经整理得
根据本定理（ 1）部分结论得知，此式与是凸函数相矛盾．
定理 2.22 设 是二次可微函数,C
为非空开凸集，则 f为 c上凸函数的充要条件是，
Hesse矩阵 在 C上到处半正定．
证明略．
213 2/12/1 XXX
)(21)(21)( 213 XfXfXf
)()()()( 13113 XXXfXfXf T
1RRCf n：
)(2 Xf?
定理 2.23 设 是二次可微函数,C
为非空凸集．若 Hesse矩阵在 C上到处正定，则
f在 C上为严格凸函数．
证明略，需要注意，该定理的逆命题不真．
例如 为严格凸函数，但是它的 Hesse
矩阵在点 x=0处是半正定的．
二、凸规划
定义 2.26 设,其中 C是非空凸集,f
是凸函数，则形式为 的问题称为凸规划问题．
4)( xxf?
1RRCf n：
1RRCf n：
m in ( )XC fX?
更进一步，设
若 都是 上的凸函数,都是
上的线性函数，则容易验证 C是凸集．事实上，因为 都是凸函数，根据定理 2.20集合
也都是凸集．此外，超平面,
也都是凸集．显然,C是 的交集，根据定理 2.6,C是凸集．于是，在这种情况下凸规划问题又可表示成如下形式：
{ | ( ) 0 1 2 ( ) 0 1 2 }nijC X g X i l h X j m X R，,,,；,,,,；
lggg,，,?21
nR mhhh,，,?21
nR
lggg,，,?21
{ | ( ) 0 } 1 2niiC X g X X R i l，,,,,
mjRXXhXP njj,,1},,0)(|{
,,,11 CC? mPP,,1?
m i n ( )
( ) 0 1 2
..
( ) 0 1 2
i
j
fX
g X i l
st
h X j m
，
，,,,,
，,,,,
定理 2.24 设 是凸规划问题的局部极小点，
（ 1）若 f是凸函数，则 是凸规划问题全局极小点；
（ 2）若 f是严格凸函数，则 是凸规划问题的唯一全局极小点．
证（ 1）使用反证法．假设 不是全局极小点，
则必存在 使得,对于 Z与
的任意凸组合,其中且,根据的凸性，有
由此看到，当 充分小时，充分接近,注意到此时也有,而这与 是局部极小点相矛盾．因此 必是全局极小点．
*X
*X
*X
*X
CZ? *( ) ( )f Z f X? *X
*21 XZX 12 ( 0 1 )，,
121
)()()()( *21*21 XfZfXZfXf )()()( **2*1 XfXfXf
01 X *X
)()( *XfXf? *X
*X
（ 2）假设 不是唯一全局极小点．必存在 但 使得 考虑中点,由 f的严格凸性，
有,此式与
为全局极小点相矛盾．这就证明了唯一性．
定义 2.27 形式为
（ 2.14）
的函数称为 n元二次函数，其中
*X
CX *XX )()( *XfXf
CXXX *2121
)()(21)(21)2121()( *** XfXfXfXXfXf
*X
CXbQXXXf TT 21)(
这里的 Q是对称矩阵，即．
若 Q为正定，则称（ 2.14）为正定二次函数．注意到
,由定理 2.23知，正定二次函数是严格凸函数，在最优化算法构造中它起着特殊的作用．
定义 2.28 形式为
（ 2.15）
的问题称为二次规划问题，其中是矩阵，是矩阵．
若 Q为半正定或正定，则称（ 2.15）为二次凸规划问题．本书不作专门讨论
nnnnn
n
n
b
b
b
b
qqq
qqq
qqq
Q
2
1
21
22221
11211
，
QXf )(2
dCX
PAX
ts
cXbQXXXf TT
，
，
..
2
1
)(m i n
2.7约束问题的最优性条件
所谓最优性条件就是最优化问题的目标函数与约束函数在最优点处满足的充要条件．这种条件对于最优化算法的终止判定和最优化理论推证都是至关重要的．最优性必要条件是指，在最优点处满足哪些条件；
充分条件是指满足哪些条件的点是最优点．本节仅讲述最基本的结论．
一、约束最优解
对约束优化问题的求解，其目的是在由约束条件所规定的可行域内，寻求一个目标函数值最小的点及其函数值．这样的解称为约束最优解．约束最优点除了可能落在可行域内的情况外，更常常是在约束边界上或等式约束曲面上，因此它的定义及它的一阶必要条件与无约束优化问题不同．
（一）约束优化问题的类型
约束优化问题根据约束条件类型的不同分为三种，其数学模型如下：
（ 1）不等式约束优化问题（ IP型）
（ 2.16）
（ 2）等式约束优化问题（ EP型）
（ 3）一般约束优化问题（ GP型）
m i n ( ),
.,( ) 0 1 2i
fX
s t g X i l，,,,,
m in ( )
.,( ) 0 1 2j
fX
s t h X j m
，
，,,,,
m in ( )
( ) 0 1 2
..
( ) 0 1 2
i
j
fX
g X i l
st
h X j m
，
，,,,,
，,,,,
（二）约束优化问题的局部解与全局解
按一般约束优化问题，其可行域为
若对某可行点 存在,当 与它邻域的点之距离 时，总有 则称 为该约束优化问题的一个局部最优解．
下面以一个简单例子说明．设有
{ | ( ) 0 1 2 ( ) 0 1 2 }ijD X g X i l h X j m，,,,；,,,,
*X 0 *X X
|||| *XX )()( * XfXf? *X
．
，
，
09)2()(
02)(
..
)1()(m i n
2
2
2
1
2
2
2
2
1
xxXh
xXg
ts
xxXf
该问题的几何图形如图 2.8所示．从图上的目标函数等值线和不等式约束与等式约束的函数曲线可写出它的两个局部最优解,,这是因为在 点邻域的任一满足约束的点,都有
同理，亦然．
TX ]0,1[*1 TX ]0,5[*2? *1X
X )()( *1XfXf?
*2X
对某些约束优化问题，局部解可能有多个．在所有的局部最优解中，目标函数值最小的那个解称为全局最优解．
在上例中，由于，所以全局最优解为．
由此可知，约束优化问题全局解一定是局部解，而局部解不一定是全局解．这与无约束优化问题是相同的．
二、约束优化问题局部解的一阶必要条件
对于约束，我们现在进一步阐明起作用约束与不起作用约束的概念．一般的约束优化问题，
其约束包含不等式约束 和等式约束,在可行点 处，如写有
则该约束 称可行点 不起作用约束．对于等式约束，显然在一可行点的等式约束都是起作用约束．
在某个可行点 处，起作用约束在 的邻域内起到限制可行域范围的作用，而不起作用约束在 处的邻域内就不产生影响．因此，应把注意力集中在起作用约束上．
liXg i,,2,1,0)(
mjXh j,,2,1,0)( kX 0)(?
ki Xg
)(Xgi kX
0)(?Xhj
kX kX
kX
（一） IP型约束问题的一阶必要条件图 2.9所示具有三个不等式约束的二维最优化问题．
图 2.9（ a）是最优化在可行域内部的一种情况．在此种情形下，点的全部约束函数值均大于零，所以这组约束条件对其最优点都不起作用．换句话说，如果除掉全部约束，其最优点也仍是同一个点．因此这种约束优化问题与无约束优化问题是等价的．图 2.9（ b）所示的约束最优点在 的边界曲线与目标函数等值线的切点处．此时所以 是起作用约束，而其余的两个是不起作用约束．
*X )( *Xgi
)(1 Xg
0)( *1?Xg 0)( *2?Xg 0)( *3?Xg
)(1 Xg
