KKT条件和二阶条件和凸度优化(六)

无约束约束FONC:x∗x^*x∗局部最小点 (+ CQ)∇fx∗0∇fx∗0KKT 条件SONC:x∗x^*x∗局部最小点 (+ CQ)∇fx∗0∇2fx∗半正定\nabla f(x^*) = 0 \\ \nabla^2f(x^*) 半正定∇fx∗0∇2fx∗半正定KKT 条件\quad∇xx2Lxλμ∇xx2Lxλμ在CxC(x)Cx上半正定∇fx∗0∇2fx∗。

红豆怪怪

2615人浏览 · 2023-04-11 15:55:18

红豆怪怪 · 2023-04-11 15:55:18 发布

KKT要点和备注

KKT条件是一般约束优化问题的一阶必要条件（FONC）。
KKT条件统一了所有以前研究过的FONC。
满足KKT条件的IA（可行）点称为KKT点，无论它是否满足CQ。
KKT点是局部最优解的候选点——就像平稳点一样。
拉格朗日乘子（对偶变量） $λi=0，i∈I(x)λ_i=0，i\in I(x)$ （为什么？complementarity)
如果一个局部极小化器x满足LICQ，那么拉格朗日乘子是由KKT条件求解的（对偶变量）λ，µ必须是唯一的（为什么？线性独立）。

应用KKT条件的策略

在研究了一些例子之后，我们可以总结出一些策略：
一般策略：

检查了LICQ（如果需要的话）。
推导出KKT的条件。
通过互补条件（将乘数或约束设为0）来讨论一些简单的情况来找到所有KKT点。

附加信息：

检查f是否是强制的或者 $Ω\Omega$ 是有界的，那么这个问题有全局解（如果CQ成立，则必须是KKT点）。
如果LICQ成立，那么λ和µ总是唯一的。
如果CQ成立，那么全局优化器必须是一个KKT点。如果将来有一个唯一的KKT点，那么这个点必须是全局最小化点。

受约束问题的二阶最优性条件

KKT条件是必要的一阶最优性条件（FONC）。KKT点是局部最小化点的潜在候选点。

问：
我有可能像在无约束的情况下那样使用二阶条件吗？
回答：是的！
我们假设 $f(x), g_i(x)$ 和 $h_j(x)$ 是两次连续可导的。

拉格朗日函数中关于 $x$ 的黑森式为：
$∇xxL(x,λ,μ)=∇2f(x)+∑i=0nλi∇2gi(x)+∑j=0pμj∇2hj(x)\nabla_{xx}L(x, \lambda, \mu) = \nabla^2 f(x) + \sum_{i=0}^n \lambda_i \nabla^2 g_i(x) + \sum_{j = 0}^p \mu_j \nabla^2 h_j(x)$

临界锥体

我们定义了所谓的临界锥体：
$\{d \in R^n : \nabla f(x)^T d = 0, \nabla g_i(x)^T d \leq 0, \forall i \in A(x) ,\nabla h_j(x)^Td = 0, \forall j\}$

二阶必要条件

二阶必要条件的形式如下：
**定理：**约束问题的SONC设 $x^*$ 是一个局部极小化和正则（regular，LICQ）。然后，KKT条件保持不变，即，有唯一的乘数 $\in R^m和µ \in R^p$ ，使：
$∇f(x∗)+∇gi(x∗)λ+∇hj(x∗)μ=0,λ≥0,λigi(x∗)=0,gi(x∗)≤,hj(x∗)=0\nabla f(x^*) + \nabla g_i(x^*) \lambda + \nabla h_j(x^*) \mu = 0,\\ \lambda \geq 0, \lambda_i g_i(x^*) = 0, g_i(x^*) \leq, h_j(x^*) = 0$

同时，我们有：
$dT∇xx2L(x,λ,μ)d≥0,∀d∈C(x)d^T\nabla_{xx}^2L(x, \lambda, \mu)d \geq 0, \forall d \in C(x)$

二阶充分条件

二阶充分条件的形式如下：
定理：
约束问题的SOSC设 $x^*$ 是一个带有乘子λ和µ的KKT点，即，我们有
$∇f(x∗)+∇gi(x∗)λ+∇hj(x∗)μ=0,λ≥0,λigi(x∗)=0,gi(x∗)≤,hj(x∗)=0\nabla f(x^*) + \nabla g_i(x^*) \lambda + \nabla h_j(x^*) \mu = 0,\\ \lambda \geq 0, \lambda_i g_i(x^*) = 0, g_i(x^*) \leq, h_j(x^*) = 0$

并假设该条件
$dT∇xx2L(x,λ,μ)d>0,∀d∈C(x)\{0}d^T\nabla_{xx}^2L(x, \lambda, \mu)d > 0, \forall d \in C(x)\backslash\{0\}$

被满足。那么， $x^*$ 是一个严格的局部最小化点。

总结：最佳条件

最优条件：总结和复习

	无约束	约束
FONC: $x^*$ 局部最小点 (+ CQ)	$∇f(x∗)=0\nabla f(x^*) = 0$	KKT 条件
SONC: $x^*$ 局部最小点 (+ CQ)	$∇f(x∗)=0∇2f(x∗)半正定\nabla f(x^) = 0 \\ \nabla^2f(x^) 半正定$	KKT 条件 $\quad$ $∇xx2L(x,λ,μ)\nabla^2_{xx}L(x, \lambda, \mu)$ 在 $C (x)$ 上半正定
SOSC:	$∇f(x∗)=0∇2f(x∗)正定,x∗∈R\{0}\nabla f(x^) = 0 \\ \nabla^2f(x^) 正定, x^*\in R\backslash\{0\}$	KKT 条件 $\quad$ $∇xx2L(x,λ,μ)\nabla^2_{xx}L(x, \lambda, \mu)$ 在 $C(x)\{0}C(x)\backslash\{0\}$ 上正定