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

您所在的位置：网站首页 › 矩阵Amn乘c=b有解的充分必要条件 › KKT条件和二阶条件和凸度优化(六)

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

2023-12-21 11:14| 来源: 网络整理| 查看: 265

KKT要点和备注 KKT条件是一般约束优化问题的一阶必要条件（FONC）。KKT条件统一了所有以前研究过的FONC。满足KKT条件的IA（可行）点称为KKT点，无论它是否满足CQ。KKT点是局部最优解的候选点——就像平稳点一样。拉格朗日乘子（对偶变量） λ i = 0 ， i ∈ I ( x ) λ_i=0，i\in I(x) λi=0，i∈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 ) f(x), g_i(x) f(x),gi(x)和 h j ( x ) h_j(x) hj(x)是两次连续可导的。

拉格朗日函数中关于 x x x的黑森式为： ∇ x x L ( x , λ , μ ) = ∇ 2 f ( x ) + ∑ i = 0 n λ i ∇ 2 g i ( x ) + ∑ j = 0 p μ j ∇ 2 h j ( 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) ∇xxL(x,λ,μ)=∇2f(x)+i=0∑nλi∇2gi(x)+j=0∑pμj∇2hj(x)

临界锥体

我们定义了所谓的临界锥体： C ( x ) = { d ∈ R n : ∇ f ( x ) T d = 0 , ∇ g i ( x ) T d ≤ 0 , ∀ i ∈ A ( x ) , ∇ h j ( x ) T d = 0 , ∀ j } C(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\} C(x)={d∈Rn:∇f(x)Td=0,∇gi(x)Td≤0,∀i∈A(x),∇hj(x)Td=0,∀j}

二阶必要条件

二阶必要条件的形式如下： **定理：**约束问题的SONC设 x ∗ x^* x∗是一个局部极小化和正则（regular，LICQ）。然后，KKT条件保持不变，即，有唯一的乘数 λ ∈ R m 和µ ∈ R p λ \in R^m和µ \in R^p λ∈Rm和µ∈Rp，使： ∇ f ( x ∗ ) + ∇ g i ( x ∗ ) λ + ∇ h j ( x ∗ ) μ = 0 , λ ≥ 0 , λ i g i ( x ∗ ) = 0 , g i ( x ∗ ) ≤ , h j ( 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 ∇f(x∗)+∇gi(x∗)λ+∇hj(x∗)μ=0,λ≥0,λigi(x∗)=0,gi(x∗)≤,hj(x∗)=0

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

二阶充分条件

二阶充分条件的形式如下：定理：约束问题的SOSC设 x ∗ x^* x∗是一个带有乘子λ和µ的KKT点，即，我们有 ∇ f ( x ∗ ) + ∇ g i ( x ∗ ) λ + ∇ h j ( x ∗ ) μ = 0 , λ ≥ 0 , λ i g i ( x ∗ ) = 0 , g i ( x ∗ ) ≤ , h j ( 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 ∇f(x∗)+∇gi(x∗)λ+∇hj(x∗)μ=0,λ≥0,λigi(x∗)=0,gi(x∗)≤,hj(x∗)=0

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

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

总结：最佳条件最优条件：总结和复习无约束约束FONC: x ∗ x^* x∗ 局部最小点 (+ CQ) ∇ f ( x ∗ ) = 0 \nabla f(x^*) = 0 ∇f(x∗)=0KKT 条件SONC: x ∗ x^* x∗ 局部最小点 (+ CQ) ∇ f ( x ∗ ) = 0 ∇ 2 f ( x ∗ ) 半正定 \nabla f(x^*) = 0 \\ \nabla^2f(x^*) 半正定 ∇f(x∗)=0∇2f(x∗)半正定KKT 条件 \quad ∇ x x 2 L ( x , λ , μ ) \nabla^2_{xx}L(x, \lambda, \mu) ∇xx2L(x,λ,μ)在 C ( x ) C(x) C(x)上半正定SOSC: ∇ f ( x ∗ ) = 0 ∇ 2 f ( x ∗ ) 正定 , x ∗ ∈ R \ { 0 } \nabla f(x^*) = 0 \\ \nabla^2f(x^*) 正定, x^*\in R\backslash\{0\} ∇f(x∗)=0∇2f(x∗)正定,x∗∈R\{0}KKT 条件 \quad ∇ x x 2 L ( x , λ , μ ) \nabla^2_{xx}L(x, \lambda, \mu) ∇xx2L(x,λ,μ)在 C ( x ) \ { 0 } C(x)\backslash\{0\} C(x)\{0}上正定非线性优化的最优性条件： FONC，SONC，SOSC为无约束问题。FONC，SONC，SOSC，用于约束问题。优势：一般问题的条件。缺点：一般都不能保证全局最优性。凸优化

凸优化是一类特殊但重要的非线性优化。凸优化的主要思想：平稳性（FONC）足以进行全局最优性，将是接下来的研究。

内容来自cuhksz mat3007的ppt Professor Li Xiao，翻译为中文，修改了小部分，加入了一些笔者自己的理解。

【本文地址】

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

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

今日新闻

推荐新闻