附录一 库恩-塔克定理

首先，我们给出一个简化的约束最优化问题。

x是选择变量；F是目标函数，连续可微；c≥G（x）是约束条件，G也是连续可微的函数。那么，约束最优化问题为：

附录

上述问题很简单，因为它是静态无随机元素，同时也只有一个选择变量一个约束。后面会将其一般化。

从初级部分学到高级部分，我们遇到最优化问题，第一个想到的就是拉格朗日乘数。其数学基础就是拉格朗日定理，或者是库恩-塔克定理。

从我们熟悉的拉格朗日算式开始：

L（x，λ）=F（x）+λ［c-G（x）］

库恩-塔克定理 假设x^*使得F（x）在c≥G（x）的约束下最大化，F、G都是连续可微的，假设：

G′（x^*）≠0

那么，存在一个λ^*使得x^*和λ^*满足下列条件：

附录

附录

附录

附录

证明：考虑两种情形，一种是在x^*处约束为等式，另一种是在x^*处约束为不等式。

情形一，约束为不等式。如果c＞G（x），然后让λ^*=0。那么，上述式（2）至式（4）均成立。那么，此时就是要证明式（1）成立。因为λ^*=0，式（1）成立，当且仅当

附录

下面我们用反证法，来证明式（5）成立。假设F′（x^*）＜0。

那么，根据F、G连续可微，一定存在一个ε＞0，使得：

F′（x^*-ε）＞F′（x^*），且c＞G（x^*-ε）

这与定理中的条件，x^*使得F在约束下最大相矛盾。同理可证，当式（5）F′（x^*）＞0时也与此条件矛盾，因此，式（5）成立。

情形二，约束为等式。如果c=G（x），然后让λ^*=F′（x^*）/G′（x^*）。那么，式（1）、式（2）、式（4）成立，现在要证明式（3）成立。由于λ^*=F′（x^*）/G′（x^*），那么，也就是F′（x^*）/G′（x^*）≥0。

同理，利用反证法