学习要点 
1. 理解一般优化问题的有关概念． 
2. 理解凸优化问题的概念，掌握其性质． 
3. 理解对偶函数的概念, 会求常见优化问题的对偶函数． 
4. 理解优化问题的强对偶性及弱对偶性，掌握相关定理． 
5. 掌握一些常用的最优性条件． 
6. 理解并能应用几种不同形式的 Karush-Kuhn-Tucker 定理． 
3.1 优 化 问 题 
优化问题的一般形式为
min f(x) (3.1) 
s.t. gi(x) . 0, i = 1, 2, 
 
 
 , m, (3.2) 
hj(x) = 0, j = 1, 2, 
 
 
 , l. (3.3) 
其中, f : Dom(f)( Rn) ! R 称为目标函数 (objective function), 每个 gi 和 hi 都是定 
义在 Rn 中某个子集上的实值函数. 式 (3.2) 和式 (3.3) 是约束 (constraint), 前者为不等 
式约束, 后者为等式约束. 称 
D := Dom(f)\ m\i=1 
Dom(gi)!\  l \j=1 
Dom(hj)! (3.4) 
为优化问题 (3.1)(3.3) 的定义域, 它是目标函数和所有约束函数的定义域的交集. 称 
SF := fx 2 D : gi(x) . 0, hj(x) = 0, i = 1, 2, 
 
 
 , m, j = 1, 2, 
 
 
 , lg (3.5) 
为优化问题 (3.1)(3.3) 的可行集 (feasible set) 或约束集 (constraint set). 
称 
p. := infff(x) : x 2 SF g (3.6)
为优化问题 (3.1)(3.3) 的最优值 (optimal value), 如果 SF = ., 则约定 p. = 1. 如 
果存在 x. 2 SF 使得 f(x.) = p., 则称 x. 是优化问题 (3.1)(3.3) 的最优点 (optimal 
point) 或最优解 (optimal solution). 最优点可能不是唯一的, 把所有最优点所组成的集 
合称为最优集 (optimal set). 
如果优化问题 (3.1)(3.3) 的可行集非空, 则称它是可行的 (feasible); 如果它的最优 
集非空, 则称它是可解的 (solvable), 此时它的最优值是可达到的 (attainable). 
对于 ε > 0, 如果可行点 x 2 SF 满足 f(x) < p.+ε, 则称 x 是优化问题 (3.1)(3.3) 的ε- 
次优点 (ε-suboptimal point), 所有 ε-次优点所组成的集合称为ε-次优集 (ε-suboptimal 
set).
对于可行点 x0 2 SF , 如果存在 δ > 0 使得 
f(x0) = inf ff(x) : x 2 SF \ B(x0, δ)g , (3.7) 
则称 x0 是优化问题 (3.1)(3.3) 的局部最优点 (locally optimal point). 
在优化问题 (3.1)(3.3) 中, 对于可行点 x, 如果 gi(x) = 0, 则称不等式约束 gi(x) . 0 
是积极的 (active), 否则称它是非积极的 (inactive). 等式约束总是积极的. 
注意: 某个约束条件是积极的还是非积极的依赖于可行点 x, 对于不同的可行点 x, 结 
论可能不一样. 
如果删除某个约束条件不会改变可行集, 则称该约束条件是冗余的 (redundant). 
我们说两个优化问题是等价的 (equivalent), 即从其中一个问题的解可以导出另一个 
问题的解. 
例如优化问题
max..f(x), s.t. gi(x) . 0, i = 1, 2, 
 
 
 ,m (3.8) 
与优化问题 
min f(x), s.t. gi(x) . 0, i = 1, 2, 
 
 
 ,m (3.9) 
是等价的. 
又如, 优化问题 
min 
x∈Rn kAx .. bk2 (3.10) 
与优化问题 
min 
x∈Rn kAx .. bk22
(3.11) 
也是等价的. 
再如, 优化问题 
min 
x∈Rn 
ef(x), s.t. Ax . b (3.12) 
81
与优化问题 
min 
x∈Rn 
f(x), s.t. Ax . b (3.13) 
是等价的. 
3.2 凸优化问题 
3.2.1 凸优化问题的概念 
凸优化问题 (convex optimization problem) 的一般形式为 
min f(x) (3.14) 
s.t. gi(x) . 0, i = 1, 2, 
 
 
 , m, (3.15) 
aTj
x = bj , j = 1, 2, 
 
 
 , l. (3.16) 
其中, f, gi, i = 1, 2, 
 
 
 ,m 是凸函数. 凸优化问题的可行集显然是凸集, 凸优化问题的特点 
可概括为可行集是凸集, 目标函数是凸函数. 
如果 f 是凹函数, 则优化问题 
max f(x) (3.17) 
s.t. gi(x) . 0, i = 1, 2, 
 
 
 , m, (3.18) 
aTj
x = bj , j = 1, 2, 
 
 
 , l (3.19) 
与凸优化问题 
min..f(x) (3.20) 
s.t. gi(x) . 0, i = 1, 2, 
 
 
 , m, (3.21) 
aTj
x = bj , j = 1, 2, 
 
 
 , l (3.22) 
等价, 因此我们也称 (3.17)(3.19) 是凸优化问题. 
在优化问题 (3.14)(3.16) 中, 如果 f 是拟凸函数, 则称之为拟凸优化问题 (quasiconvex 
problem), 凸优化问题显然也是拟凸优化问题. 
3.2.2 凸优化问题的性质 
命题 3.1 拟凸优化问题的 ε-次优集一定是凸集, 特别地, 其最优集一定是凸集. 
证明 拟凸优化问题的 ε-次优集可表示为 
Xε = fx 2 Rn : f(x) . p. + εg \ SF , (3.23) 
其中, p. 是该优化问题的最优值, SF 是可行集. 由于 f 是拟凸函数, 因此下水平集 fx 2 
Rn : f(x) . p. + εg 是凸集, 又因为 SF 也是凸集, 因此 Xε 是凸集. 
82
对于凸优化问题 (3.14)(3.16), 根据定理 2.9, 有下列结论. 
定理 3.1 凸优化问题 (3.14)(3.16) 的局部最优点一定是全局最优点; 如果 f 是严 
格凸的, 则凸优化问题的最优点 (如果存在) 是唯一的. 
接下来讨论凸优化问题 (3.14)(3.16) 的最优性条件. 假设 f 是可微的凸函数, 设 SF 
是该优化问题的可行集, 根据定理 2.2, 对任意 x, y 2 SF 皆有 
f(y) . f(x) + (y .. x)Trf(x). (3.24) 
如果在 x 点满足 
(y .. x)Trf(x) . 0, 8 y 2 SF , (3.25) 
则有 
f(x) . f(y) .. (y .. x)Trf(x) . f(y), 8 y 2 SF , (3.26) 
因此 x 是最优点. 
反之, 如果 x 2 SF 是最优点, 则有 
f(x) . f((1 .. t)x + ty), 8 y 2 SF , 0 . t . 1. (3.27) 
令 φ(t) = f((1 .. t)x + ty), 0 . t . 1, 则 φ 是可微的, 且 φ(t) . φ(0), 8 0 . t . 1, 因此有 
φ′(0) = lim 
t→0+ 
φ(t) .. φ(0) 
t . 0, (3.28) 
由此立刻得到 
(y .. x)Trf(x) = φ′(0) . 0. (3.29) 
综上所述, 我们证明了如下定理. 
定理 3.2 设 f 是可微的凸函数, SF 是凸优化问题 (3.14)(3.16) 的可行集. 则 
x 2 SF 是最优点当且仅当条件 (3.25) 成立. 
推论 3.1 设 C  Rn 是开凸集, f 是定义在 C 上的可微凸函数, 考虑优化问题 
min 
x∈C 
f(x), (3.30) 
x 2 C 是它的最优点的充分必要条件是 rf(x) = 0. 
证明 先证必要性. 设 x 2 C 是最优点, 由于 C 是开集, 因此存在 r > 0 使得 
B(x, r)  C, 于是 
f(x + tu) . f(x), 8 u 2 Rn, kuk2 = 1, .. r . t . r. (3.31) 
令 φ(t) = f(x + tu),..r . t . r, 则 φ 是可微的, 且 φ 在 t = 0 处取得最小值, 因此有 
φ′(0) = 0, 由此得到
uTrf(x) = φ′(0) = 0, 8 u 2 Rn, kuk2 = 1, (3.32) 
83
因此必有 rf(x) = 0, 否则取 u = rf(x)/krf(x)k2, 则有 kuk2 = 1 且 uTrf(x) = 
krf(x)k2 6= 0, 矛盾. 
再证充分性. 由于 f 是 C 上的凸函数, 根据定理 2.9得 
f(y) . f(x) + (y .. x)Trf(x), 8 y 2 C, (3.33) 
如果 rf(x) = 0, 则有 f(x) . f(y), 8 y 2 C, 因此 x 是最优点. 
例 3.1 设 
f(x) = 
1
2
xTPx + qTx + r, x 2 Rn, (3.34) 
其中 P  0. 考察优化问题 
min 
x∈Rn 
f(x), (3.35) 
由于 r2f(x) = P, 8 x 2 Rn, 因此 f 是凸函数. 根据推论 3.1, x 2 Rn 是最优点当且仅当 
rf(x) = 0, 即 Px = ..q. 当 P  0 时, 方程 Px = ..q 有唯一解, 此时优化问题有唯一最优 
点; 当 P 是奇异矩阵且 q 2 R(P) 时, 其中 R(P) 表示 P 的像空间 (image space), 方程 
Px = ..q 有无穷多个解, 此时优化问题有无穷多个最优点; 当 P 是奇异矩阵且 q /2 R(P) 
时, 方程 Px = ..q 无解, 此时优化问题没有最优点. 
接下来考虑只带有等式约束的凸优化问题 
min f(x), s.t. Ax = b, (3.36) 
其中, A = (aij)m×n, b 2 Rm. 该优化问题的可行集是方程 Ax = b 的解集, 是一个仿射集. 
根据定理 3.2, 可行点 x 是最优点当且仅当 
(y .. x)Trf(x) . 0, 8 y 2 fy 2 Rn : Ay = bg, (3.37) 
由于仿射集 fy 2 Rn : Ay = bg 中的元素都可表示为 
y = x + v, v 2 N(A), (3.38) 
其中, N(A) 表示 A 的零空间 (null space), 因此式 (3.37) 等价于 
vTrf(x) . 0, 8 v 2 N(A), (3.39) 
由于 N(A) 是一个线性空间, 因此上述条件等价于 
vTrf(x) = 0, 8 v 2 N(A), (3.40) 
即 rf(x) 2 N(A)⊥. 注意到 N(A)⊥ = R(AT), 因此式 (3.40) 又等价于存在 ν 2 Rm 使得 
rf(x) + ATν = 0, (3.41) 
它与可行性条件 Ax = b 一起构成了 Lagrange 乘数法的最优性条件. 
综上所述, 我们证明了如下定理. 
84
定理 3.3 x 2 Rn 是凸优化问题 (3.36) 的最优点的充分必要条件是存在 ν 2 Rm, 使 
得它满足下列 Lagrange 乘数法最优性条件: 
Ax = b, rf(x) + ATν = 0. (3.42) 
再来考虑下列凸优化问题: 
min f(x), s.t. x  0, (3.43) 
其中, f 是凸函数. 此时最优性条件为 
x  0, (y .. x)Trf(x) . 0, 8 y  0. (3.44) 
从以上条件不难推出 rf(x)  0, 否则 (y .. x)Trf(x) 作为 y 的函数在非负象限上无下界, 
违背了条件 (y .. x)Trf(x) . 0. 由第二个条件得到 
yTrf(x) . xTrf(x), 8 y  0, (3.45) 
取 y = 0 便得到 xTrf(x) . 0, 又因为 x  0,rf(x)  0, 因此 xTrf(x) . 0, 从而只能是 
xTrf(x) = 0. 再注意到 
xTrf(x) = 
n Xi=1 
xi(rf(x))i, (3.46) 
其中, (rf(x))i 表示梯度向量 rf(x) 的第 i 个分量. 上式中每一项都是非负的, 因此 
xTrf(x) = 0 当且仅当 
xi(rf(x))i = 0, i = 1, 2, 
 
 
 , n. (3.47) 
这个条件称为互补性 (complementarity). 
综上所述, 我们证明了下列结果. 
定理 3.4 x 2 Rn 是凸优化问题 (3.43) 的最优点的充分必要条件是 
x  0, rf(x)  0, xi(rf(x))i = 0, i = 1, 2, 
 
 
 , n. (3.48) 
3.3 Lagrange 对偶函数 
3.3.1 Lagrange 对偶函数的定义 
现在回到一般的优化问题 (3.1)(3.3), 假设该问题的定义域 D 非空, 并设 p. 是该问 
题的最优值. 
定义 L : D  Rm  Rl ! R 为 
L(x, λ, ν) := f(x) + 
m Xi=1 
λigi(x) + 
l Xj=1 
νjhj(x), (3.49) 
称之为优化问题 (3.1)(3.3) 的 Lagrange 函数, 其中, λ 和 ν 称为 Lagrange 乘数 (Lagrange 
multiplier) 或对偶变量 (dual variable). 
85
定义 3.1 设 L(x, λ, ν) 是优化问题 (3.1)(3.3) 的 Lagrange 函数, 由式 (3.49) 定义, 
令 
LD(λ, ν) := inf 
x∈D 
L(x, λ, ν), λ 2 Rm, ν 2 Rl, (3.50) 
称之为优化问题 (3.1)(3.3) 的 Lagrange 对偶函数 (Lagrange dual function) 或简称 
之为对偶函数 (dual function). 
对于给定的 x 2 D, L(x, λ, ν) 是 λ 和 ν 的线性函数, 因此对偶函数 LD 是一族线性函 
数的逐点下确界, 从而是凸函数, 无论原优化问题是不是凸优化问题. 
例 3.2 考虑优化问题
min xTx, s.t. Ax = b, (3.51) 
其中, A 是 l  n 的实矩阵, l . n. 此优化问题的 Lagrange 函数为 
L(x, ν) = xTx + 
l Xj=1 
νj(xTaj .. bj) = xTx + νT(Ax .. b), (3.52) 
其中, aj 表示 A 的第 j 个行向量, bj 表示 b 的第 j 个分量. 为了找到对偶函数, 需要固定 
ν 找 L(x, ν) 的最小值. 注意到 r2
xL = 2I  0, 因此 L(
, ν) 是一个严格凸函数, 它取最小 
值的充分必要条件是 rxL(x, ν) = 0, 即 
2x + ATν = 0, (3.53) 
由此解得最小值点为 x = ..(ATν)/2, 因此有 
LD(ν) = inf 
x∈Rn 
L(x, ν) = 
1
4
νTAATν + νT(..
1
2
AATν .. b) = ..
1
4
νTAATν .. νTb, (3.54) 
这就是优化问题 (3.51) 的 Lagrange 对偶函数. 
例 3.3 考察线性规划问题 
min cTx, s.t. Ax = b, x  0. (3.55) 
其中, c 2 Rn, b 2 Rl, A 是 l  n 的实矩阵, l . n. 首先将不等式约束等价变形为 ..x  0, 
不难写出此优化问题的 Lagrange 函数为 
L(x, λ, ν)=cTx .. λTx + νT(Ax .. b) 
=(c .. λ + ATν)Tx .. νTb, x, λ 2 Rn, ν 2 Rl. (3.56) 
不难看出, 只有当 c .. λ + ATν = 0 时 L(x, λ, ν) 有下界 ..νTb, 因此对偶函数为 
LD(λ, ν) = inf 
x∈Rn 
L(x, λ, ν) = ( ..νTb, c .. λ + ATν = 0 
..1, 其他 
. (3.57) 
86
3.3.2 最优值的下界估计 
利用 Lagrange 对偶函数可以给出原优化问题的最优值 p. 的下界估计. 事实上, 有如 
下结果. 
定理 3.5 设 LD(λ, ν) 是优化问题 (3.1)(3.3) 的 Lagrange 对偶函数, p. 是该问题 
的最优值, 则有 
LD(λ, ν) . p., 8 λ  0, ν 2 Rl. (3.58) 
证明 设 D 和 SF 是优化问题 (3.1)(3.3) 的定义域和可行集, L(x, λ, ν) 是此优化问 
题的 Lagrange 函数, 则对任意 x 2 SF 皆有 
gi(x) . 0, i = 1, 2, 
 
 
 , m, hj(x) = 0, j = 1, 2, 
 
 
 , l, (3.59) 
于是当 λ  0 时, 有 
L(x, λ, ν) = f(x) + 
m Xi=1 
λigi(x) + 
l Xj=1 
νjhj(x) . f(x), (3.60) 
从而得到 
LD(λ, ν) = inf 
z∈D 
L(z, λ, ν) . L(x, λ, ν) . f(x), (3.61) 
由于上式对于任意 x 2 SF 皆成立, 因此有 
LD(λ, ν) . inf 
x∈SF 
f(x) = p.. (3.62) 
在例 3.2中, 我们已经求出了优化问题 (3.51) 的对偶函数 
LD(ν) = ..
1
4
νTAATν .. νTb, (3.63) 
设 p. 是该优化问题的最优值, 根据定理 3.5得 
LD(ν) . p., 8 ν 2 Rl, (3.64) 
因此有 
p. . sup 
ν∈Rl 
LD(ν), (3.65) 
如果 A 是行满秩的, 则 AAT 可逆, LD(ν) 取最大值的充分必要条件为 
rLD(ν) = ..
1
2
AATν .. b = 0, (3.66) 
87
由此推出最大值点为 ν = ..2(AAT).1b, 将其代入 LD 的表达式得到 LD 的最大值为 
bT(AAT).1b, 因此有 
p. . sup 
ν∈Rp 
LD(ν) = bT(AAT).1b. (3.67) 
在例 3.3中, 我们求出了线性规划问题 (3.55) 的对偶函数 
LD(λ, ν) = ( ..νTb, λ + ATν = c 
..1, 其他 
, (3.68) 
因此该问题的最优值 p. 满足 
p. . sup 
λ.0,ν∈Rp 
LD(λ, ν) = sup ..νTb : λ + ATν = c, λ  0	. (3.69) 
3.3.3 Lagrange 对偶函数与共轭函数的关系 
Lagrange 对偶与第 2 章讲的共轭函数有密切联系, 本小节给出一些例子. 先回忆一下 
共轭函数的定义为 
f.(y) = sup 
x∈Dom(f)
(yTx .. f(x)). (3.70) 
例 3.4 考察优化问题 
min f(x), s.t. Ax  b, Cx = d, (3.71) 
其 Lagrange 函数为
L(x, λ, ν) = f(x) + λT(Ax .. b) + νT(Cx .. d), (3.72) 
因此其对偶函数为 
LD(λ, ν)= inf 
x∈Dom(f)
L(x, λ, ν) = inf 
x∈Dom(f) f(x) + (CTν + ATλ)Tx .. λTb .. νTd	 
=..λTb .. νTd .. sup 
x∈Dom(f) ..(CTν + ATλ)Tx .. f(x)	 
=..λTb .. νTd .. f. ....CTν .. ATλ
. (3.73) 
例 3.5 考察优化问题 
min kxk, s.t. Ax = b. (3.74) 
其中, k 
 k 是 Rn 上的一个一般的范数, 其 Lagrange 函数为 
L(x, ν) = kxk + νT(Ax .. b), (3.75) 
88
因此其对偶函数为
LD(ν)= inf 
x∈Rn 
L(x, ν) = ..νTb .. sup 
x∈Rn ....(ATν)Tx .. kxk
 
=..νTb .. f.(..ATν), (3.76) 
其中, f. 是函数 f(x) = kxk 的共轭函数. 利用例 2.20的结论得到 
LD(ν) = ( ..νTb, kATνk. . 1 
..1, 其他 
. (3.77) 
例 3.6 考察熵最大化问题 
min f(x) = 
n Xi=1 
xi ln xi, s.t. Ax  b, 
n Xi=1 
xi = 1. (3.78) 
其中, ..f(x) 代表概率分布 PfX = ig = xi, i = 1, 2, 
 
 
 , n 的熵. 我们先来计算 f 的共轭 
函数. 
f.(y)=sup 
x.0  yTx .. 
n Xi=1 
xi ln xi!= sup 
x.0   n Xi=1
(xiyi .. xi ln xi)! 
= 
n Xi=1 
sup 
xi>0
(xiyi .. xi ln xi) 
= 
n Xi=1 
eyi.1. (3.79) 
现在利用例 3.4的结论得到 
LD(λ, ν)=..ν .. λTb .. f.(..ν1n×1 .. ATλ) 
=..ν .. λTb .. 
n Xi=1 
e.ν.aTi
λ.1 
=..ν .. λTb .. e.ν.1 
n Xi=1 
e.aTi
λ, (3.80) 
其中, 1n×1 表示元素全是 1 的 n  1 矩阵, ai 表示 A 的第 i 个列向量. 
例 3.7 考察优化问题 
min f(X) = ln..detX.1
, s.t. aTi
Xai . 1, i = 1, 2, 
 
 
 , m, (3.81) 
其中, 矩阵 X 在 Sn y++ 中取值. 注意到 detX.1 与椭球 aTXa . 1 的体积呈比例, 因 
此这个问题的本质是要找一个中心在坐标原点的椭球 aTXa . 1 以覆盖住给定点 ai, i = 
1, 2, 
 
 
 ,m, 并使其具有最小体积. 约束条件 aTi
Xai . 1 是线性的, 可以等价地写成 
tr((aiaTi
)X) . 1, i = 1, 2, 
 
 
 , m. (3.82) 
89
利用例 2.18的结论得到 
f.(Y ) = sup 
X∈Sny
++ 
gY (X) = ( ..n + ln det(..Y .1), Y  0 
1, Y  0 
, (3.83) 
再利用例 3.4的结论得到 
LD(λ)=..λT1m×1 .. f.  .. 
m Xi=1 
λiaiaTi 
! 
=8>
<>
: 
.. 
m Xi=1 
λi + n + ln det  m Xi=1 
λiaiaTi 
!!, 
m Xi=1 
λiaiaTi 
 0 
..1, 其他 
. (3.84) 
3.4 Lagrange 对偶问题 
3.4.1 对偶问题的概念及例子 
回到一般的优化问题 (3.1)(3.3), 设它的最优值为 p., Lagrange 对偶函数为 LD(λ, ν). 
根据定理 3.5得 
LD(λ, ν) . p., 8 λ  0, ν 2 Rl, (3.85) 
即任意满足 λ  0 的有序对 (λ, ν) 都给出了 p. 的一个下界 LD(λ, ν). 现在想要找一个最 
优的下界, 就需要求解优化问题 
maxLD(λ, ν), s.t. λ  0, (3.86) 
我们称式 (3.86) 为优化问题 (3.1)(3.3) 的 Lagrange 对偶问题 (Lagrange dual problem), 
或简称之为对偶问题 (dual problem). 如果 (λ, ν) 满足 λ  0 且 LD(λ, ν) > ..1, 
则称之为对偶可行点 (dual feasible point). 所有对偶可行点的集合称为对偶可行集 
(dual feasible set). 称对偶问题 (3.86) 的最优点 (λ., ν.) 为对偶最优点 (dual optimal 
point). 
须指出的是, 无论原问题是否为凸优化问题, 其对偶问题一定是凸优化问题. 
例 3.8 考察例 3.3中的线性规划问题 (3.55), 我们已经求出了其对偶函数为 
LD(λ, ν) = ( ..νTb, c .. λ + ATν = 0 
..1, 其他 
, (3.87) 
因此其对偶问题是 
maxLD(λ, ν) = ( ..νTb, c .. λ + ATν = 0 
..1, 其他 
. (3.88) 
90
s.t. λ  0, (3.89) 
注意目标函数中隐含了约束条件 c .. λ + ATν = 0, 因此上述问题等价于 
max..νTb, s.t. λ  0, c .. λ + ATν = 0. (3.90) 
利用等式约束条件消掉 λ 后得到等价问题 
max..νTb, s.t. ATν + c  0. (3.91) 
上述问题也被称作线性规划问题 (3.55) 的对偶问题. 
设 p. 是原问题 (3.1)(3.3) 的最优值, d. 是对偶问题 (3.86) 的最优值, 则有 
d. . p.. (3.92) 
这个性质称为弱对偶性 (weak duality). 我们称 p. .. d. 为最优对偶间隙 (optimal 
duality gap). 
例 3.9 我们来考虑一个集合划分的问题. 设 E = fvi : i = 1, 2, 
 
 
 , ng, 我们需要将 
其中的元素分成两类, 如果 vi 被分到第一类, 则给其赋予标签 xi = 1, 如果 vi 被分到 
第二类, 则给其赋予标签 xi = ..1, 因此将 E 中的元素分类就相当于给出一个标签向量 
x = (x1, x2, 
 
 
 , xn)T, 它的每一个分量 xi 取 1 或 ..1. 现在来考虑分类代价函数, 如果 xi 
与 xj 被划分在同一类, 则分类代价为 2wij , 否则分类代价为 ..2wij , 则总的分类代价为 
f(x) = 
n Xi=1 
n Xj=1 
xixjwij = xTWx, (3.93) 
其中, W = (wij)n×n 是一个 n 阶实对称矩阵. 集合划分问题就是要找一个代价最小的划 
分, 即 
min f(x) = xTWx, s.t. x2i
= 1, i = 1, 2, 
 
 
 , n. (3.94) 
这是一个非凸的优化问题, 下面找其对偶问题, 其 Lagrange 函数为 
L(x, ν) = xTWx + 
n Xi=1 
νi(x2i 
.. 1) = xT (W + Dν) x .. 
n Xi=1 
νi, (3.95) 
其中, Dν 表示以 ν1, ν2, 
 
 
 , νn 为对角元素的对角矩阵. 因此对偶函数为 
LD(ν) = inf 
x∈Rn 
L(x, ν) =8>
<>
: 
.. 
n Xi=1 
νi, W + Dν  0 
..1, 其他 
, (3.96) 
因此对偶问题为 
max 
ν∈Rn 
LD(ν) =8>
<>
: 
.. 
n Xi=1 
νi, W + Dν  0 
..1, 其他 
. (3.97) 
91
由于目标函数中隐含了约束条件 W + Dν  0, 因此上述问题又等价于 
max.. 
n Xi=1 
νi, s.t. W + Dν  0. (3.98) 
这是一个凸优化问题, 有非常有效的算法可以求解这类问题. 
3.4.2 强对偶性 
弱对偶性表明优化问题的最优值 p. 与对偶最优值 d. 满足 d. . p.. 那么等式是否成 
立呢? 对于一般的优化问题, 并不能保证 d. = p.. 例如优化问题 
min f(x) = e.x1 , s.t. 
x21 
x2 
. 0, (3.99) 
其中, x = (x1, x2)T 在 D := f(x1, x2)T : x2 > 0g 中取值. 这个问题的可行集是 SF = 
f(0, x2)T : x2 > 0g, 因此最优值为 p. = 1, 其对偶函数为 
LD(λ) = inf 
x∈D e.x1 + λ
x21 
x2= ( 0, λ . 0 
..1, λ < 0. 
(3.100) 
因此对偶问题为 
max 
λ.0 
LD(λ), (3.101) 
对偶最优值为 d. = 0, 从而有 d. < p.. 
如果一个优化问题的最优值 p. 和对偶最优值 d. 相等, 即 p. = d., 则称它满足强对偶 
性 (strong duality). 
接下来研究保证强对偶性的条件. 
对于 Rn 的子集 E, 其仿射包为 aff(E), 如果 E 的仿射维数小于 n, 则 aff(E) 是一个维 
数小于 n 的仿射集. 对于 x 2 E, 如果存在开球 B(x, r) := fz 2 Rn : kz .. xk2 < rg 使得 
B(x, r) \ aff(E)  E, (3.102) 
则称 x 是 E 的相对内点 (relative interior point). 称 E 的所有相对内点所构成的集合 
为 E 的相对内部 (relative interior), 记为 relint(E). 
回到凸优化问题 (3.14)(3.16), 设其定义域为 D, 如果存在 x 2 relint(D) 使得 
gi(x) < 0, i = 1, 2, 
 
 
 , m, aTj
x .. bj = 0, j = 1, 2, 
 
 
 , l, (3.103) 
则称该优化问题满足 Slater 条件 (Slater’s condition), 称这样的点 x 为严格可行点 
(strictly feasible point). 
92
如果 gi, i = 1, 2, 
 
 
 ,m 中含有仿射函数, 不妨设前 k(k . m) 个是仿射函数, 则可以将 
Slater 条件减弱, 定义弱 Salter 条件 (weak Slater’s condition) 为存在 x 2 relint(D) 
使得 
gi(x) . 0, i = 1, 2, 
 
 
 , k, gi(x) < 0, i = k + 1, k + 2, 
 
 
 , m, 
aTj
x .. bj = 0, j = 1, 2, 
 
 
 , l. (3.104) 
定理 3.6 对于凸优化问题 (3.14)(3.16), 如果它满足 Slater 条件, 则它满足强对偶 
性, 而且对偶最优值是可达到的. 如果不等式约束函数中有仿射函数, 则只需满足弱 Slater 
条件, 上述结论就成立. 
证明 我们只证 D 的仿射维数等于 n 的情形, 此时 relint(D) = D.. 先证明定理的第 
一部分. 首先, 我们可以假设 a1, a2, 
 
 
 , al 线性无关, 否则可以去掉一些冗余的等式约束直 
至剩余向量线性无关, 这样做不会改变问题的可行集, 最优值 p. 和对偶最优值 d. 都不会 
改变. 为了表示简洁, 令 
g = (g1, g2, 
 
 
 , gm)T, hj(x) = aTj
x .. bj , h = (h1, h2, 
 
 
 , hl)T. (3.105) 
采用这些记号可将凸优化问题 (3.14)(3.16) 表示为 
min f(x), s.t. g(x)  0, h(x) = 0. (3.106) 
原问题的 Lagrange 函数为
L(x, λ, ν) = f(x) + λTg(x) + νTh(x). (3.107) 
现在定义 Rm  Rl  R 的子集 
A := f(u, v, t) : 9 x 2 D, g(x)  u, h(x) = v, f(x) . tg , (3.108) 
如果原问题是可行的, 则 A 非空. 这是因为如果 x0 是原问题的可行点, 则对任意满足 s . 
f(x0) 的实数 s 皆有 (0, 0, s) 2 A. 此外, A 还是凸集. 这是因为对任意 (u, v, t), (.u, .v, .t) 2 A, 
存在 x, .x 2 D 使得 
g(x)  u, g(.x)  .u, h(x) = v, h(.x) = .v, f(x) . t, f(.x) . .t, (3.109) 
由于 g 的每个分量是凸函数, h 的每个分量是仿射函数, f 是凸函数, 因此对任意 0 < θ < 1 
皆有 
g((1 .. θ)x + θ.x)  (1 .. θ)g(x) + θg(.x)  (1 .. θ)u + θ.u, (3.110) 
h((1 .. θ)x + θ.x) = (1 .. θ)h(x) + θh(.x) = (1 .. θ)v + θ.v, (3.111) 
f((1 .. θ)x + θ.x) . (1 .. θ)f(x) + θf(.x) . (1 .. θ)t + θ.t, (3.112) 
由于 D 是凸集, 因此 (1 .. θ)x + θ.x 2 D, 由此得出 
(1 .. θ)(u, v, t) + θ(.u, .v, .t) 2 A, (3.113) 
93
这就证明了 A 是凸集. 
再定义 
B := f(0, 0, s) 2 Rm  Rl  R : s < p.g, (3.114) 
则 B 显然也是凸集, 且 A \ B = .. 这是因为如果 (0, 0, s) 2 A, 则存在 x0 2 D 使得 
g(x0)  0, h(x0) = 0, f(x0) . s, (3.115) 
因此 
s . f(x0) . inf 
x∈SF 
f(x) = p., (3.116) 
其中, SF 是原优化问题的可行集, 因此 (0, 0, s) /2 B. 
如果原凸优化问题满足 Slater 条件, 则原问题至少有一个可行点, 因此 p. < 1, 如果 
p. = ..1, 则根据弱对偶性, d. = ..1, 定理结论成立. 如果 p. > ..1, 则 A 和 B 都是非 
空凸集, 根据凸集分离定理, 存在 (.λ, .ν, μ) 6= 0 使得 
.λ
Tu + .νTv + μt . α, 8 (u, v, t) 2 A, (3.117) 
μs . α, 8 (0, 0, s) 2 B, (3.118) 
由式 (3.117) 得 .λ 
 0, μ . 0, 否则 .λ
Tu + .νTv + μt 在 A 上无下界. 再由式 (3.118) 得 
μs . α, 8 s < p., 由此推出 μp. . α. 综合以上推论得 
.λ
Tu + .νTv + μt . α, .λ 
 0, μ . 0, μp. . α, 8 (u, v, t) 2 A. (3.119) 
对任意 x 2 D 皆有 (g(x), h(x), f(x)) 2 A, 因此有 
.λ
Tg(x) + .νTh(x) + μf(x) . α . μp.. (3.120) 
如果 μ > 0, 则由式 (3.120) 得到 
1
μ
.λ
Tg(x) + 
1
μ 
.νTh(x) + f(x) . p., 8 x 2 D, (3.121) 
即 
L x, 
.λ 
μ
, 
.ν
μ!. p., 8 x 2 D, (3.122) 
因此有 
LD  .λ 
μ
, 
.ν
μ!= inf 
x∈D 
L x, 
.λ 
μ
, 
.ν
μ!. p., (3.123) 
94
由此得到 d. = sup 
λ.0,ν∈Rl 
LD(λ, ν) . p., 结合弱对偶性立刻得到 d. = p., 这就证明了强对偶 
性, 而且证明了对偶最优值是可达到的. 
接下来证明 μ 不可能为零. 如果 μ = 0, 则由式 (3.120) 得到 
.λ
Tg(x) + .νTh(x) . 0, 8 x 2 D. (3.124) 
根据 Slater 条件, 存在 .x 2 D. 使得 g(.x)  0, h(.x) = 0, 将其代入式 (3.124) 得 
.λ
Tg(.x) . 0, (3.125) 
由于 .λ 
 0, 因此必有 .λ
= 0, 于是由式 (3.124) 得 
.νTh(x) . 0, 8 x 2 D. (3.126) 
既然 (.λ, .ν, μ) 6= 0, 必有 .ν 6= 0. 由于 .x 2 D., 因此存在 δ > 0, 使得当 y 2 B(0, δ) 时恒有 
.x + y 2 D, 于是有 
.νTATy = .νTh(.x + y) . 0, 8 kyk2 < δ, (3.127) 
其中, A = (a1, a2, 
 
 
 , al), h(x) = ATx .. b, b = (b1, b2, 
 
 
 , bl)T. 由此得到 
A.ν = 0, 
即 
l Xj=1 
.νjaj = 0, (3.128) 
由于已经假设 a1, a2, 
 
 
 , al 线性无关, 因此必有 .ν = 0, 矛盾. 
接下来证明定理的第二部分. 如果原问题含有仿射不等式约束, 例如 
aT0
x .. b0 . 0, (3.129) 
则加入松弛变量 y 使其转换为等式约束, 原问题等价于 
min φ(x, y) = f(x), (3.130) 
s.t. g(x)  0, aT0
x + y .. b0 = 0, aTj
x .. bj = 0, j = 1, 2, 
 
 
 , l, (3.131) 
此时问题的定义域为 
D′ = f(x, y) : x 2 D, y 2 Rg. (3.132) 
如果原问题满足弱 Slater 条件, 则加松弛变量后的问题满足 Slater 条件, 根据已经证明的 
前部分结论, 存在 .λ 
 0, .ν 2 Rp 及 .ν0 2 R 使得 
L′D(.λ, .ν, .ν0) = inf 
(x,y)∈D′ 
L′(x, y, .λ, .ν, .ν0) 
95
:= inf 
(x,y)∈D′ 
f(x) + .λ
Tg(x) + .νTh(x) + .ν0(aT0
x + y .. b0) = p.. (3.133) 
如果 p. = ..1, 则定理结论显然成立. 如果 p. 是有限实数, 则必有 .ν0 = 0(否则 .ν0(aT0
x + 
y .. b0) 无下界), 此时原问题的 Lagrange 函数满足 
L(x, .λ, .ν, .ν0) = f(x) + .λ
Tg(x) + .νTh(x) + .ν0(aT0
x .. b0), (3.134) 
因此有 
LD(.λ, .ν, .ν0)= inf 
x∈D 
L(x, .λ, .ν, .ν0) = inf 
(x,0)∈D′ 
L′(x, 0, .λ, .ν, .ν0) 
. inf 
(x,y)∈D′ 
L′(x, y, .λ, .ν, .ν0) = p., (3.135) 
由此推出 d. . p., 强对偶性得证. 
例 3.10 考虑仿射约束凸优化问题 
min f(x), s.t. Cx . d, Ax = b, (3.136) 
其中, f : Rn ! R 是凸函数, C 是 m n 的实矩阵, A 是 l  n 的实矩阵. 只要该问题是可 
行的, 就一定满足弱 Slater 条件, 根据定理 3.6, 它满足强对偶性, 而且存在 .λ 2 Rm, .ν 2 Rp 
使得 LD(.λ, .ν) = d. = p.. 
作为特例, 线性规划问题 
min αTx, s.t. cTi
x . di, i = 1, 2, 
 
 
 , m, aTj
x = bj , j = 1, 2, 
 
 
 , l (3.137) 
只要是可行的, 就满足强对偶性, 而且对偶最优值是可以取到的. 
例 3.11 回到例 3.6的熵最大化问题 (3.78), 我们已经求出其对偶函数 
LD(λ, ν) = ..ν .. λTb .. e.ν.1 
n Xi=1 
e.aTi
λ, (3.138) 
因此对偶问题为 
maxLD(λ, ν) = ..ν .. λTb .. e.ν.1 
n Xi=1 
e.aTi
λ, s.t. λ  0. (3.139) 
这个问题还可以简化, 对于给定的 λ  0, 先将 LD(λ, ν) 对 ν 取最大值, 得 
sup 
ν∈R 
LD(λ, ν) = ..ln  n Xi=1 
e.aTi
λ!.. λTb, (3.140) 
因此对偶问题 (3.139) 等价于 
max..ln  n Xi=1 
e.aTi
λ!.. λTb, s.t. λ  0, (3.141) 
96
这是一个带有非负约束的几何规划问题, 而且是凸优化问题. 由于原问题的约束条件都是 
仿射约束, 根据定理 3.6, 只要存在 x  0 满足 Ax  b 及 
n Pi=1 
xi = 1, 它就满足强对偶性, 而 
且对偶最优值 d. = p. 是可取到的. 
例 3.12 回到例 3.7介绍的最小体积椭圆覆盖问题 (3.81), 我们已经求出其对偶函数 
LD(λ) =8>
<>
: 
.. 
m Xi=1 
λi + n + ln det  m Xi=1 
λiaiaTi 
!!, 
m Xi=1 
λiaiaTi 
 0 
..1, 其他 
, (3.142) 
因此对偶问题为 
max.. 
m Xi=1 
λi + n + ln det  m Xi=1 
λiaiaTi 
!!, s.t. λ  0. (3.143) 
原问题的不等式约束 aTi
Xai . 1 对变量 X 是仿射约束, 因此只要满足弱 Slater 条件, 原问 
题就具有强对偶性. 弱 Slater 条件相当于存在 X 2 S++ 使得 
aTi
Xai . 1, i = 1, 2, 
 
 
 , m, (3.144) 
即原问题是可行的. 
3.5 最优性条件 
3.5.1 无约束优化问题的最优性条件 
本小节我们考虑无约束优化问题 
min 
x∈D 
f(x), (3.145) 
其中, D 是 Rn 中的开集, f 是一阶连续可微的, 这里并不假设 f 是凸函数. 如果 x. 2 D 是 
局部最优点, 则对任意 v 2 Rn, 当实数 t 的绝对值足够小时必有 
f(x.) . f(x. + tv). (3.146) 
记 φ(t) := f(x. + tv), 则 φ 在 t = 0 处取得局部极小值, 因此有 
φ′(0) = vTrf(x.) = 0, (3.147) 
由 v 的任意性推出 rf(x.) = 0. 于是我们得到了下列必要条件. 
定理 3.7 设 D 是 Rn 中的开集, f 是一阶连续可微的, 则 x. 是无约束优化问题 
(3.145) 的局部极小点的必要条件是 rf(x.) = 0. 
须指出的是, 上述条件是必要的, 但不是充分的. 如果 f 是二阶连续可微的, 则有下列 
充分条件. 
97
定理 3.8 设 D 是 Rn 中的开集, f 是二阶连续可微的, 则 x. 是无约束优化问题 
(3.145) 的严格局部极小点的充分条件是 
rf(x.) = 0, r2f(x.)  0. (3.148) 
证明 由于 f 二阶连续可微, 因此 r2f(x) 是连续依赖于 x 的, 因此存在 δ > 0, 使得 
当 x 2 B(x., δ) 时恒有 r2f(x)  0. 对任意 x 2 B(x., δ) n fx.g, 由 Taylor 公式得 
f(x)=f(x.) + (x .. x.)Trf(x.) + 
1
2
(x .. x.)Tr2f(x. + θ(x .. x.))(x .. x.) 
=f(x.) + 
1
2
(x .. x.)Tr2f(x. + θ(x .. x.))(x .. x.), (3.149) 
其中, 0 < θ < 1. 由于 x. + θ(x .. x.) 2 B(x., δ), 因此 r2f(x. + θ(x .. x.))  0, 从而有 
(x .. x.)Tr2f(x. + θ(x .. x.))(x .. x.) > 0, (3.150) 
由此得到 f(x) > f(x.), 8 x 2 B(x., δ) n fx.g, 这就证明了 x. 是 f 的严格局部极小点. 
3.5.2 只含等式约束的优化问题的最优条件 
先考虑只含有一个等式约束的优化问题 
min f(x), s.t. h1(x) = 0, (3.151) 
我们假设问题的定义域是 Rn 中的开集, 目标函数 f 和约束函数 h1 都是一阶连续可微的. 
设 x. 是问题 (3.151) 的局部极小点, v 是与 rh1(x.) 正交的向量, 则有 
f(x. + tv) = f(x.) + tvTrf(x.) + o(t), (3.152) 
h1(x. + tv) = h1(x.) + tvTrh1(x.) + o(t) = h1(x.) + o(t), (3.153) 
如果忽略高阶无穷小量 o(t), 则有 
f(x. + tv)  f(x.) + tvTrf(x.), (3.154) 
h1(x. + tv)  h1(x.) = 0, (3.155) 
由于 x. 是问题 (3.151) 的局部极小点, 因此必有 vTrf(x.) = 0. 换言之, 每一个与 rh1(x.) 
正交的向量都必须与 rf(x.) 正交, 因此 rf(x.) 与 rh1(x.) 共线, 或者说存在 ν 2 R 使得 
rf(x.) = νrh1(x.). (3.156) 
再来看有多个等式约束的优化问题 
min f(x), s.t. hj(x) = 0, j = 1, 2, 
 
 
 , l. (3.157) 
设 x. 是问题 (3.157) 的局部极小点, 记 W = Spanfrhj(x.) : j = 1, 2, 
 
 
 , lg, 即由约束函 
数的梯度张成的线性空间, 设 v 2 W⊥, 则有 
vTrhj(x.) = 0, j = 1, 2, 
 
 
 , l. (3.158) 
98
于是对于绝对值足够小的 t 有 
f(x. + tv) = f(x.) + tvTrf(x.) + o(t), (3.159) 
hj(x. + tv) = hj(x.) + tvTrhj(x.) + o(t) = hj(x.) + o(t), j = 1, 2, 
 
 
 , l. (3.160) 
如果忽略高阶无穷小量 o(t), 则有 
f(x. + tv)  f(x.) + tvTrf(x.), (3.161) 
hj(x. + tv)  hj(x.) = 0, j = 1, 2, 
 
 
 , l. (3.162) 
由于 x. 是问题 (3.157) 的局部极小点, 因此必有 vTrf(x.) = 0. 换言之, rf(x.) 与 W⊥ 
中每一个向量都正交, 因此 rf(x.) 2 W, 从而存在实数 ν1, ν2, 
 
 
 , νl 使得 
rf(x.) = 
l Xj=1 
νjrhj(x.). (3.163) 
归纳以上分析的结果, 得到下列定理. 
定理 3.9 设优化问题 (3.157) 的定义域 D 是 Rn 的开子集, 目标函数 f 和等式约 
束函数 hj , j = 1, 2, 
 
 
 , l 都是连续可微的, 且 l < n. 设 W 是由约束函数的梯度向量 
rhj(x.), j = 1, 2, 
 
 
 , l 张成的向量空间. 则 x. 是该优化问题的局部极小点的必要条件是 
rf(x.) 2 W, 即存在 ν = (ν1, ν2, 
 
 
 , νl)T 2 Rl 使得式 (3.163) 成立. 
前面的分析非常粗略, 不能充当定理的证明. 下面给出定理的严格证明. 
证明 首先可以假设约束函数在点 x. 的梯度向量 
rh1(x.),rh2(x.), 
 
 
 ,rhl(x.), (3.164) 
线性无关, 否则可以去掉 (在该点的) 冗余约束, 使得剩余的梯度向量线性无关. 
接下来用反证法证明定理结论成立. 如果 rf(x.) /2 W, 设 PW(rf(x.)) 是 rf(x.) 在 
W 上的正交投影, 则 v = rf(x.)..PW(rf(x.)) 是与 W 正交的非零向量, 且 vTrf(x.) > 
0. 令 u = v/kvk2 并将其将扩充为 W⊥ 的规范正交基 
fu, u(1), u(2), 
 
 
 , u(n.l.1)g, (3.165) 
考虑关于 x 的方程组
8>
><>>:
hj(x) = 0, j = 1, 2, 
 
 
 , l 
(u(k))T(x .. x.) = 0, k = 1, 2, 
 
 
 , n .. l .. 1, 
uT(x .. x.) = t 
(3.166) 
(3.167) 
(3.168) 
其中, t 是一个可变参数. 下面用反函数定理 (附录 D 中的定理 D.1) 证明方程组 (3.166) 
(3.168) 在局部范围内有解 x = x(t), 而且它是 t 的连续可微函数. 记 
8>
><>
>:
.j(x) = hj(x), j = 1, 2, 
 
 
 , l 
.l+k(x) = (u(k))T(x .. x.), k = 1, 2, 
 
 
 , n .. l .. 1, 
.n(x) = uT(x .. x.), . = (.1, .2, 
 
 
 , .n)T 
(3.169) 
(3.170) 
(3.171) 
99