接凸优化整理(二)

约束优化

约束优化问题

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

记可行集为

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)的局部最优解，则