QxRed

发信人: qxred (天下第二菜), 信区: AI
标  题: 对偶和KKT条件的简单推导
发信站: 日月光华 (2006年11月04日10:57:59 星期六), 站内信件

以下内容来自Convex Optimization 第5章，p215-p242

设想我们优化如下的目标函数：
minimize    f_0(x)
s.t.        f_i(x)<=0,  i=1,2,...,m
            h_i(x)=0,   i=1,2,...,p

我们把这个目标函数称为原函数
构造该函数的对偶函数如下：

maximize
g(r,v)=inf_x \{f_0(x)+\sum_{i=1}^m r_i*f_i(x)+\sum_{i=1}^p v_i*h_i(x)\}
s.t.    r_i>=0  i=1,2,...,m

假设x'是原函数的一个可行点（满足原函数的约束），r',v'是对偶函数的一个可行点
因为r'_i>=0,f_i(x')<=0,所以\sum_{i=1}^m r'_i*f_i(x')<=0,同理
\sum_{i=1}^p v'_i*h_i(x')=0
因此，我们有，对于任意的满足原函数约束的x和满足对偶函数约束的r,v

g(r,v)<=\{f_0(x)+\sum_{i=1}^m r_i*f_i(x)+\sum_{i=1}^p v_i*h_i(x)\}
      <=f_0(x)

记x^* 为原函数的一个最优点，最优值为p^*
r^*,v^*为对偶函数的一个最优点，最优值为d^*
我们有
    p^*>=d^*（weak duality）

如果x^*,r^*,v^*能够使得p^*=d^*成立，
则称strong duality成立，即
f_0(x^*)=g(r^*,v^*)

现在假设strong duality能够成立，并且假设x^*是原函数的最优解,r^*,v^*为对偶函数
的一个最优点，那么
f_0(x^*)=g(r^*,v^*)
    =inf_x \{f_0(x)+\sum_{i=1}^m r^*_i*f_i(x)+\sum_{i=1}^p v^*_i*h_i(x)\}
    <=f_0(x^*)+\sum_{i=1}^m r^*_i*f_i(x^*)+\sum_{i=1}^p v^*_i*h_i(x^*)
    <=f_0(x^*)
第一个等式是strong duality，第二行等式是对偶函数的定义，第三行不等式是inf的定
义，第四行不等式是因为r^*_i>=0,f_i(x^*)<=0,h_i(x^*)=0

因此，我们有\sum_{i=1}^m r^*_i*f_i(x^*)=0,
因为对每个i, r^*_i*f_i(x^*)<=0，
所以有
r^*_i*f_i(x^*)=0（Complementary slackness）

因为x^*是使得g(r^*,v^*)最小的点，（注意上面的第三行等式成立）
所以g(r^*,v^*)关于x的导数在x^*处为0
f_0'(x^*)+\sum_{i=1}^m r^*_i*f_i'(x^*)+\sum_{i=1}^p v^*_i*h_i'(x^*)=0

综上所述我们得到了f_0(x^*)=g(r^*,v^*)的条件：
f_i(x^*)<=0     i=1,2,...,m
h_i(x^*)=0      i=1,2,...,p
r^*_i>=0        i=1,2,...,m
r^*_i*f_i(x^*)=0    i=1,2,...,m
f_0'(x^*)+\sum_{i=1}^m r^*_i*f_i'(x^*)+\sum_{i=1}^p v^*_i*h_i'(x^*)=0
这就是KKT条件
--
from this day forward let no human make war upon any other human,
- let no terran agency conspire against this new beginning.
- and let no man consort with alien powers...
- and to all the enemies of humanity seek not to bar our way,
- for we shall win through, no matter the cost.
※ 来源:·日月光华 bbs.fudan.edu.cn·[FROM: 10.11.3.132]