凸优化整理(三)

接凸优化整理(二)

约束优化

约束优化问题

考虑如下一般形式约束优化问题：

记可行集为

1. 假设问题(P)中的函数f(x)，(g_i)(x)，(h_i)(x)均为连续可微函数；
2. 注意几类非光滑函数的转化(有不可微点)；

比如f(x)=max {x,(x^2)}，它的图形如下红色的部分

它有两个点是不可微的，一个是(0,0)，一个是(1,1)。如果我们要求目标函数的最小值min f(x)，可以转化为

min t

s.t.  f(x)≤t

进而转化为

min t

s.t.   x≤t

(x^2)≤t

这样就都满足了处处可微的条件进行求解。

例：约束优化最优解的特征

min f(x)            x∈(R^n)

s.t.  (g_1)(x)≤0

(g_2)(x)≤0

(g_3)(x)≤0

在上图中，S是由 (g_1)(x)≤0， (g_2)(x)≤0， (g_3)(x)≤0组成的可行集，虚线是f(x)的等值线，左侧方向是其负梯度方向。现已知(x^*)是局部最优解，由 (g_1)(x)和(g_2)(x)共同作用而成， (g_3)(x)未参与，且(g_3)((x^*))<0。由上图可知

-∇f((x^*))=(λ_1)∇(g_1)((x^*))+(λ_2)∇(g_2)((x^*))                    (λ_1)≥0，(λ_2)≥0

变形有

∇f((x^*))+(λ_1)∇(g_1)((x^*))+(λ_2)∇(g_2)((x^*))=0

为了让 (g_3)((x^*))参与其中，我们可以写为

∇f((x^*))+(λ_1)∇(g_1)((x^*))+(λ_2)∇(g_2)((x^*))+(λ_3)∇ (g_3)((x^*))=0

(λ_1)≥0，(λ_2)≥0，(λ_3)≥0

(λ_1)(g_1)((x^*))=0，(λ_2)(g_2)((x^*))=0，(λ_3)(g_3)((x^*))=0

最优解的一阶必要条件(Karush-Kuhn-Tucher,KKT条件)

假设(x^*)是问题(P)的局部最优解，且(x^*)处某个"适当的条件"(constraint qualification)成立，则存在λ∈(R^m)，μ∈(R^l)使得

以上条件也称为Karush-Kuhn-Tucher(KKT)条件。这里的(λ_i),(μ_i)被称为拉格朗日乘子。

怎么证明KKT必要条件？

1. 对于(x^*)∈S，若点列{(x_k)}⊂S满足所有(x_k)≠(x^*)，

则称之为可行点列；

1. 基本思路：若 (x^*)∈S是局部最优解，则沿着任意可行点列目标函数不会下降(即当k充分大时有

);

1. 考虑(x^*)处的集合

均为f(x)是(x^*)处的下降方向；

1. 考虑(x^*)处的集合

该集合称为(x^*)处的切锥！

1. 若(x^*)是问题(P)的局部最优解，则