因此函数在 x* 处的导数必须为零，即，
m
p
f0 (x*) i*fi (x*) vi*hi (x* ) 0
i 1
i 1
因此，我们有
fi (x*) 0 i 1,..., m
hi (x*) 0, i 1,..., p
i* 0, i 1,..., m (5.49)
f
(x)v

1 (1T z)2
(
n i 1
zi )(
n i 1
vi2 zi )
(
n i 1
vi zi )2


0.
上述不等式可以应用 Cauchy-Schwarz 不等式 (aT a)(bTb) (aTb)2 得到，此
时向量 a 和 b 的分量为 ai vi zi , bi zi 。
时其无界。
总之，

f
*
(
y)



n
yi log yi
i 1

如果 y 0且1T y 1 其他情况
换言之，指数和函数的对数函数的共轭函数是概率单纯形内
的负熵函数。
2. 求半正定规划的拉格朗日对偶
minimize c x
subject to x1F1 ... xnFn G 0
共轭函数求解
n
f (x) log( exi )
为了得到指数和的对数函数
i1 的共轭函数，
首先考察 y 取何值时 yT x f (x) 的最大值可以得到。对 x 求导，令其
为零，我们得到如下条件
e xi yi n ,
exj
j 1
i 1,..., n.
当且仅当 y 0 以及1T y 1时上述方程有解。将 yi 的表达式代入
i* fi (x*) 0, i 1,..., m
m
p
f0 (x*) i*fi (x*) vi*hi (x*) 0
i 1
i1
我们称上式为 Karush-Kuhn-Tucker(KKT)条件。
总之，对于目标函数和约束函数可微的任意优化问题，如果强对
偶性成立，那么任何一对原问题最优解和对偶问题的最优解必须满足
其对 x 是仿射的。对偶函数可以描述为
g(Z ) inf L(x ,Z )
tr(GZ )
tr(F i
Z
)

c i

0,i
1,...,n
x

其他情况
所以对偶问题可以写成
max imize tr(GZ )
subject to tr(FiZ ) ci 0, i 1,..., n
指数和的对数函数的 Hessian 矩阵为 2 f (x) 1 ((1T z)diag(z) zzT ), (1T z)2
其中 z (ex1 ,..., exn ) 。为了说明 2 f (x) 0 ，我们证明对任意 v ，有
vT 2 f (x)v 0 ，即
vT2
其中 g ( y) 由
1 g ( y)
m
exp y1

...

exp yi exp ym
i 1
给出。
利用复合公式我们有:
2 f (x) AT ( 1 diag(z) 1 zzT ) A,
1T z
(1T z)2
其中 zi exp(aiT x bi ), i 1,..., m 。
（5.93）
其中
F1,...Fn , G

Sk
。（此时，
f1 是仿射的，锥为半正定锥
S
k
。）、
对约束引入一个对偶变量或者乘子 Z S k ，因此 Largrange 函数为
L(x, Z ) cT x tr((x1F1 ... xn Fn G)Z )
x1(c1 tr(F1Z )) ... xn (cn tr(FnZ )) tr(GZ ),
f
的
Hessian
矩阵的简单公式。
通过求偏导数，或者利用 2h(x) g ' ( f (x))2 f (x) g '' ( f (x))f (x)f (x)T . 并
m
注意到 g 是 log 和 i1exp yi 的复合函数，可以得到
2g ( y) diag(g ( y)) g ( y)g ( y)T ,
KKT 条件（5.49）。
凸问题的 KKT 条件
当原问题是凸问题时，满足 KKT 条件的点也是原、对偶最优解。 换言之，如果函数 fi 是凸函数， hi 是仿射函数， x, , v 是任意满足 KKT 条件的点。
fi (x) 0, i 1,..., m
hi (x) 0, i 1,..., p
i 0, i 1,..., m
i fi (x) 0, i 1,..., m
m
p
f0 (x) ifi (x) vihi (x) 0,
i 1
i 1
那么 x 和 (, v) 分别是原问题和对偶问题的最优解，对偶间隙为零。
为了说明这一点，注意到前两个条件说明了 x 是原问题的可行解。
设函数 f0,... fm , h1,...hp 可微（因此定义域是开集），但是并不
假设这些函数是凸函数。
非凸问题的 KKT 条件
和前面一样，令 x* 和 (*, *) 分别是原问题和对偶问题的某对最优
解，对偶间隙为零。因为 L(x, *, v*) 关于 x 求极小在 x* 处取得最小值，
设 y 的某个分量是负的，比如说 yk 0 ，令 xk t, xi 0,i k, 令 t 趋向
于无穷， yT x f (x) 无上界。
如果 y 0 但是1T y 1 ，令 x t1 ，可得
yT x f (x) t1T y t log n.
若1T y 1，当 t 时上述表达式无界；当1T y 1时，若 t
Z 0
(在这里我们用到了
Sk
是自对偶的性质，即
(
S
k
)*

Sk
)
(非负象限中。锥 Rn 的对偶是它本身：
yT x 0,x 0 y 0. 我们称这种锥自对偶 ) 若半定规划（5.93）是严格可行的，即存在一点 x 满足下式
x1F1 ... xn Fn G 0
n
yT x f (x) 可以得到 f *( y) i1 yi log yi 。根据前面的约定， 0 log 0 等
于 0 ，因此只要满足 y 0 以及1T y 1，即使当 y 的某些分量为零时，
f * 的表达式仍然正确。
事实上 f * 的定义域即为 1T y 1， y 0 。为了说明这一点，假
因为 i 0 ， L(x, , v) 是 x 的凸函数;最后一个 KKT 条件说明在 x x 处， Lagrange 函数的导数为零。因此 L(x, , v) 关于 x 求极小在 x 处取得最小
值。我们得出结论
g (, v) L(x, , v)
m
p
f0 (x) i fi (x) vihi (x)
i 1
i 1
f0 (x)
最后一行成立是因为 hi (x) 0 以及 i fi (x) 0 。这说明原问题的解 x 和对偶问题的解 (, v) 之间的对偶间隙为零，因此分别是原、对偶最优 解。总之，对目标函数和约束函数可微的任意凸优化问题，任意满足 KKT 条件的点分别是原、对偶最优解，对偶间隙为零。
1. 证明函数为凸函数并求其共轭函数
凸函数证明
我们考虑函数 f : Rn R
m
f (x) log exp(aiT x bi ),
i 1
其 中 a1,..., am Rn , b1,..., bm R 。 利 用 f (x) g ( Ax b) ， 其 中
m
g ( y) log(i1exp yi ) ，我们可以得到
若某个凸优化问题具有可微的目标函数和约束函数，且满足 Slater 条件，那么 KKT 条件是最优性的充要条件：slater 条件意味着最 优对偶间隙为零且对偶最优解可以达到，因此 x 是原问题最优解，当 且仅当存在 (, v) ，二者满足 KKT 条件。
KKT 条件在优化领域有着重要的作用。在一些特殊的情形下，是 可以解析求解 KKT 条件的（也因此可以求解优化问题）。更一般地， 很多求解凸优化问题的方法可以认为或者理解为求解 KKT 条件的方 法。