大家好,欢迎来到IT知识分享网。
KKT条件
全部笔记的汇总贴:最优化学习目录
KKT条件(最优解的一阶必要条件)
∇ f ( x ∗ ) + ∑ i = 1 m λ i ∇ g i ( x ∗ ) + ∑ i = 1 l μ i ∇ h i ( x ∗ ) = 0 \nabla f\left(x^{*}\right)+\sum_{i=1}^{m} \lambda_{i} \nabla g_{i}\left(x^{*}\right)+\sum_{i=1}^{l} \mu_{i} \nabla h_{i}\left(x^{*}\right)=0 ∇f(x∗)+i=1∑mλi∇gi(x∗)+i=1∑lμi∇hi(x∗)=0 λ i ⩾ 0 , i = 1 , … m \lambda_{i} \geqslant 0, \quad i=1, \ldots m λi⩾0,i=1,…m g i ( x ∗ ) ⩽ 0 , i = 1 , ⋯ m g_{i}\left(x^{*}\right) \leqslant 0, i=1, \cdots m gi(x∗)⩽0,i=1,⋯m h i ( x ∗ ) = 0 , i = 1 , ⋯ l h_{i}\left(x^{*}\right)=0, i=1, \cdots l hi(x∗)=0,i=1,⋯l λ i g i ( x ∗ ) = 0 , i = 1 , … m \lambda_{i} g_{i}\left(x^{*}\right)=0, i=1, \ldots m λigi(x∗)=0,i=1,…m
Complementary Slackness 互补松弛条件
这里要引入一个Complementary Slackness 互补松弛条件
λ i g i ( x ∗ ) = 0 , i = 1 , … m \lambda_{i} g_{i}\left(x^{*}\right)=0, i=1, \ldots m λigi(x∗)=0,i=1,…m { λ i > 0 ⇒ g i ( x ⋆ ) = 0 g i ( x ∗ ) < 0 = > λ i = 0 \left\{\begin{array}{l}\lambda_{i}>0 \Rightarrow g_{i}\left(x^{\star}\right)=0 \\ g_{i}\left(x^{*}\right)<0=>\lambda_{i}=0\end{array}\right. {
λi>0⇒gi(x⋆)=0gi(x∗)<0=>λi=0
切锥与约束规范
为了证明KKT,这里引入几个定义
最优解的必要条件
若 x ∗ x^{*} x∗是问题P的局部最优解
D ( x ∗ ) ∩ T ( x ∗ ) = ϕ D\left(x^{*}\right) \cap T\left(x^{*}\right)=\phi D(x∗)∩T(x∗)=ϕ D ( x ∗ ) = { d ∣ ∇ f ( x ∗ ) ⊤ d < 0 } \left.D\left(x^{*}\right)= \{ d \mid \nabla f\left(x^{*}\right)^{\top} d<0\right \} D(x∗)={
d∣∇f(x∗)⊤d<0} T ( x ∗ ) = { α d ∣ α > 0 , d = lim k → ∞ x k − x ∗ ∣ x k − x ∗ ∣ } T\left(x^{*}\right)=\left.\{ \alpha d\right|\alpha>0, d=\lim _{k \rightarrow \infty} \frac{x_{k}-x^{*}}{\left|x_{k}-x^{*}\right| } \} T(x∗)={
αd∣α>0,d=k→∞lim∣xk−x∗∣xk−x∗}
线性可行方向集
线性无关约束规范(LICQ)
引用Farkas 引理证明KKT条件
免责声明:本站所有文章内容,图片,视频等均是来源于用户投稿和互联网及文摘转载整编而成,不代表本站观点,不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益,请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权,请联系删除,如若转载,请注明出处:https://yundeesoft.com/11590.html