您当前的位置: 首页 > 

B417科研笔记

暂无认证

  • 3浏览

    0关注

    154博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

【凸优化】关于 KKT 条件 及其最优性

B417科研笔记 发布时间:2021-04-19 19:42:39 ,浏览量:3

拉格朗日对偶

对于一个标准形式的优化问题, 我们可以写为:

minimize ⁡ f 0 ( x )  subject to  f i ( x ) ⩽ 0 , i = 1 , ⋯   , m h i ( x ) = 0 , i = 1 , ⋯   , p , \begin{array}{ll} \operatorname{minimize} & f_{0}(x) \\ \text { subject to } & f_{i}(x) \leqslant 0, \quad i=1, \cdots, m \\ & h_{i}(x)=0, \quad i=1, \cdots, p, \end{array} minimize subject to ​f0​(x)fi​(x)⩽0,i=1,⋯,mhi​(x)=0,i=1,⋯,p,​

我们定义其 拉格朗日函数 为:

L ( x , λ , ν ) = f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ i = 1 p ν i h i ( x ) (1) L(x, \lambda, \nu)=f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x) \tag{1} L(x,λ,ν)=f0​(x)+i=1∑m​λi​fi​(x)+i=1∑p​νi​hi​(x)(1)

L ( x , λ , ν ) L(x, \lambda, \nu) L(x,λ,ν) 被称为 Lagrange 函数, 就是在原目标函数上加上了 约束条件的 加权和。 λ i \lambda_i λi​ 代表 f i ( x ) ≤ 0 f_i(x)\le 0 fi​(x)≤0这一约束的拉格朗日乘子。 类似的, v i v_i vi​就是 h i ( x ) = 0 h_i(x)=0 hi​(x)=0的拉格朗日乘子。

进一步地, 在(1)中对 x x x取最小, 即: g ( λ , ν ) = inf ⁡ x ∈ D L ( x , λ , ν ) = inf ⁡ x ∈ D ( f 0 ( x ) + ∑ i = 1 m λ i f i ( x ) + ∑ i = 1 p ν i h i ( x ) ) g(\lambda, \nu)=\inf _{x \in \mathcal{D}} L(x, \lambda, \nu)=\inf _{x \in \mathcal{D}}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i} f_{i}(x)+\sum_{i=1}^{p} \nu_{i} h_{i}(x)\right) g(λ,ν)=x∈Dinf​L(x,λ,ν)=x∈Dinf​(f0​(x)+i=1∑m​λi​fi​(x)+i=1∑p​νi​hi​(x)) inf ⁡ \inf inf代表下界。 函数 g g g 被称为 拉格朗日对偶函数。

注意到 g ( λ , ν ) g(\lambda, \nu) g(λ,ν)可被视作 一簇关于 λ \lambda λ 和 ν \nu ν 的 仿射函数 (不同的 x x x对应具体不同的仿射函数) 的 逐点下确界。 因此, g ( λ , ν ) g(\lambda, \nu) g(λ,ν) 必定是一个凹函数(详细证明略)。

拉格朗日函数的核心意义在于, 给出了最优解的一个下界:

当 λ ⪰ 0 \lambda \succeq 0 λ⪰0 时, 将有: g ( λ , ν ) ⩽ p ⋆ . g(\lambda, \nu) \leqslant p^{\star} . g(λ,ν)⩽p⋆. 这是因为, 对于任意一个原问题的可行点 x ~ \tilde{\boldsymbol{x}} x~, 必有: ∑ i = 1 m λ i f i ( x ~ ) + ∑ i = 1 p ν i h i ( x ~ ) ⩽ 0 \sum_{i=1}^{m} \lambda_{i} f_{i}(\tilde{x})+\sum_{i=1}^{p} \nu_{i} h_{i}(\tilde{x}) \leqslant 0 i=1∑m​λi​fi​(x~)+i=1∑p​νi​hi​(x~)⩽0 那么: L ( x ~ , λ , ν ) = f 0 ( x ~ ) + ∑ i = 1 m λ i f i ( x ~ ) + ∑ i = 1 p ν i h i ( x ~ ) ⩽ f 0 ( x ~ ) L(\tilde{x}, \lambda, \nu)=f_{0}(\tilde{x})+\sum_{i=1}^{m} \lambda_{i} f_{i}(\tilde{x})+\sum_{i=1}^{p} \nu_{i} h_{i}(\tilde{x}) \leqslant f_{0}(\tilde{x}) L(x~,λ,ν)=f0​(x~)+i=1∑m​λi​fi​(x~)+i=1∑p​νi​hi​(x~)⩽f0​(x~) 而根据 g g g的定义, 他是 L L L函数关于 x x x求得的最小值, 因此必定有: g ( λ , ν ) = inf ⁡ x ∈ D L ( x , λ , ν ) ⩽ L ( x ~ , λ , ν ) ⩽ f 0 ( x ~ ) g(\lambda, \nu)=\inf _{x \in \mathcal{D}} L(x, \lambda, \nu) \leqslant L(\tilde{x}, \lambda, \nu) \leqslant f_{0}(\tilde{x}) g(λ,ν)=x∈Dinf​L(x,λ,ν)⩽L(x~,λ,ν)⩽f0​(x~) 也就是说, 对于任意可行点 x ~ \tilde{\boldsymbol{x}} x~都成立, 那么最优点显然也是可行点之一, 因此就有 g ( λ , ν ) ⩽ p ⋆ . g(\lambda, \nu) \leqslant p^{\star} . g(λ,ν)⩽p⋆.

KKT条件

首先, 我们先直接给出 KKT 条件, 为:

f i ( x ⋆ ) ⩽ 0 , i = 1 , ⋯   , m h i ( x ⋆ ) = 0 , i = 1 , ⋯   , p λ i ⋆ ⩾ 0 , i = 1 , ⋯   , m λ i ⋆ f i ( x ⋆ ) = 0 , i = 1 , ⋯   , m ∇ f 0 ( x ⋆ ) + ∑ i = 1 m λ i ⋆ ∇ f i ( x ⋆ ) + ∑ i = 1 p ν i ⋆ ∇ h i ( x ⋆ ) = 0 , \begin{aligned} &f_{i}\left(x^{\star}\right) \leqslant 0, i =1, \cdots, m \\ &h_{i}\left(x^{\star}\right) =0, i =1, \cdots, p \\ &\lambda_{i}^{\star} \geqslant 0, i=1, \cdots, m \\ &\lambda_{i}^{\star} f_{i}\left(x^{\star}\right) =0, i=1, \cdots, m \\ &\nabla f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} \nabla f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} \nabla h_{i}\left(x^{\star}\right) =0, \end{aligned} ​fi​(x⋆)⩽0,i=1,⋯,mhi​(x⋆)=0,i=1,⋯,pλi⋆​⩾0,i=1,⋯,mλi⋆​fi​(x⋆)=0,i=1,⋯,m∇f0​(x⋆)+i=1∑m​λi⋆​∇fi​(x⋆)+i=1∑p​νi⋆​∇hi​(x⋆)=0,​ 满足上述条件的点 x ⋆ x^{\star} x⋆就是KKT条件给出的解。

接下来, 我们分析 KKT 条件的意义。 即, 这个 x ⋆ x^{\star} x⋆ 到底是什么?

首先, 假设原问题就是一个凸问题。 也就是说, f 0 ( x ) f_0(x) f0​(x)是一个凸函数。 此时, x ⋆ x^{\star} x⋆就是原问题的最优解。

我们接下来进行相应的证明。

假设 x ~ , λ ~ , ν ~ \tilde{x}, \tilde{\lambda}, \tilde{\nu} x~,λ~,ν~ 是满足KKT条件的点。

由于 f 0 ( x ) f_0(x) f0​(x) 是 凸函数, 而 λ ⪰ 0 \lambda \succeq 0 λ⪰0, 因此 L ( x , λ ~ , ν ~ ) L(x, \tilde{\lambda}, \tilde{\nu}) L(x,λ~,ν~) 是 x x x的凸函数。 因为 f i ( x ) f_i(x) fi​(x)是凸函数(因为假设原问题是凸问题), 而凸函数加凸函数仍是一个凸函数。

因此, 最后一个条件即梯度为0代表了 x ~ \tilde{x} x~ 为 L L L的最小点。 因此,有: g ( λ ~ , ν ~ ) = L ( x ~ , λ ~ , ν ~ ) = f 0 ( x ~ ) + ∑ i = 1 m λ ~ i f i ( x ~ ) + ∑ i = 1 p ν ~ i h i ( x ~ ) = f 0 ( x ~ ) \begin{aligned} g(\tilde{\lambda}, \tilde{\nu}) &=L(\tilde{x}, \tilde{\lambda}, \tilde{\nu}) \\ &=f_{0}(\tilde{x})+\sum_{i=1}^{m} \tilde{\lambda}_{i} f_{i}(\tilde{x})+\sum_{i=1}^{p} \tilde{\nu}_{i} h_{i}(\tilde{x}) \\ &=f_{0}(\tilde{x}) \end{aligned} g(λ~,ν~)​=L(x~,λ~,ν~)=f0​(x~)+i=1∑m​λ~i​fi​(x~)+i=1∑p​ν~i​hi​(x~)=f0​(x~)​ 第一个等式来自于 g g g的定义: L L L关于 x x x的下界。 最后一个等式成立是因为KKT条件中的 λ i ⋆ f i ( x ⋆ ) = 0 , i = 1 , ⋯   , m \lambda_{i}^{\star} f_{i}\left(x^{\star}\right) =0, i=1, \cdots, m λi⋆​fi​(x⋆)=0,i=1,⋯,m

注意到, 也就是说: g ( λ ~ , ν ~ ) = f 0 ( x ~ ) g(\tilde{\lambda}, \tilde{\nu}) =f_{0}(\tilde{x}) g(λ~,ν~)=f0​(x~), 而我们上面证明过: g ( λ , ν ) ⩽ p ⋆ . g(\lambda, \nu) \leqslant p^{\star} . g(λ,ν)⩽p⋆. 因此, f 0 ( x ~ ) ⩽ p ⋆ f_{0}(\tilde{x})\leqslant p^{\star} f0​(x~)⩽p⋆。 而 p ⋆ p^{\star} p⋆的定义就是 f 0 ( x ) f_0(x) f0​(x)的最小值。 因此 f 0 ( x ~ ) ≥ p ⋆ f_{0}(\tilde{x})\ge p^{\star} f0​(x~)≥p⋆。 所以, 有: f 0 ( x ~ ) = p ⋆ f_{0}(\tilde{x}) = p^{\star} f0​(x~)=p⋆。 即: x ~ \tilde{x} x~ 就是 f 0 ( x ) f_0(x) f0​(x)的最优解。

总结一下,结论就是: 当原问题是凸问题时, 满足KKT条件的解, 就是原问题的解。

但如果原问题不是凸问题的时候呢? 此时 g ( λ ~ , ν ~ ) = L ( x ~ , λ ~ , ν ~ ) g(\tilde{\lambda}, \tilde{\nu}) =L(\tilde{x}, \tilde{\lambda}, \tilde{\nu}) g(λ~,ν~)=L(x~,λ~,ν~)这一步就不一定成立了, 因为导数为0不代表就是最小值。 但是,如果我们已知强对偶性成立, 即 g ( λ ~ , ν ~ ) = p ⋆ g(\tilde{\lambda}, \tilde{\nu})=p^{\star} g(λ~,ν~)=p⋆时,有: f 0 ( x ⋆ ) = g ( λ ⋆ , ν ⋆ ) = inf ⁡ x ( f 0 ( x ) + ∑ i = 1 m λ i ⋆ f i ( x ) + ∑ i = 1 p ν i ⋆ h i ( x ) ) ⩽ f 0 ( x ⋆ ) + ∑ i = 1 m λ i ⋆ f i ( x ⋆ ) + ∑ i = 1 p ν i ⋆ h i ( x ⋆ ) ⩽ f 0 ( x ⋆ ) \begin{aligned} f_{0}\left(x^{\star}\right) &=g\left(\lambda^{\star}, \nu^{\star}\right) \\ &=\inf _{x}\left(f_{0}(x)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}(x)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}(x)\right) \\ & \leqslant f_{0}\left(x^{\star}\right)+\sum_{i=1}^{m} \lambda_{i}^{\star} f_{i}\left(x^{\star}\right)+\sum_{i=1}^{p} \nu_{i}^{\star} h_{i}\left(x^{\star}\right) \\ & \leqslant f_{0}\left(x^{\star}\right) \end{aligned} f0​(x⋆)​=g(λ⋆,ν⋆)=xinf​(f0​(x)+i=1∑m​λi⋆​fi​(x)+i=1∑p​νi⋆​hi​(x))⩽f0​(x⋆)+i=1∑m​λi⋆​fi​(x⋆)+i=1∑p​νi⋆​hi​(x⋆)⩽f0​(x⋆)​ 由此可见, 两个不等式必须要取等号。 因为 f 0 ( x ⋆ ) = f 0 ( x ⋆ ) f_{0}\left(x^{\star}\right) =f_{0}\left(x^{\star}\right) f0​(x⋆)=f0​(x⋆)。 第一个不等号要想成立, 那么必须满足KKT条件的最后一个条件:即对 x ⋆ x^{\star} x⋆的导数为0. 而第二个等号要想成立, 就必须满足KKT的最后第二个条件。

因此, 此时KKT条件时最优解的必要条件 (但不一定充分)。

关注
打赏
1649265742
查看更多评论
立即登录/注册

微信扫码登录

0.0428s