等式约束和不等式约束下的KKT条件求法

xiaoxiao2021-02-28  20

一、写在前面

本篇内容主要写非线性规划等式约束和不等式约束下的KKT条件,主要通过举例说明。

二、等式约束下的KKT条件

1、 题目描述

考虑等式约束的最小二乘问题 m i n i m i z e x T x s u b j e c t   t o A x = b minimize \quad x^Tx \\ subject \ to \quad Ax=b minimizexTxsubject toAx=b 其中, A ∈ R m ∗ n , r a n k ( A ) = m A \in \mathbb{R}^{m*n},rank(A)=m ARmn,rank(A)=m。给出KKT条件,推导原问题最优解 x ∗ x^* x 以及对偶问题最优解 v ∗ v^* v 的表达式。

2、Lagrarian函数

L ( x , v ) = x T x + v T ( A x − b ) = x T x + v T A x − v T b \begin{array}{lcl} L(x,v) &=& x^Tx+v^T(Ax-b) \\ &=& x^Tx+v^TAx-v^Tb \end{array} L(x,v)==xTx+vT(Axb)xTx+vTAxvTb

3、KKT条件

其对应的KKT条件如下: ∂ L ( x ∗ , v ∗ ) ∂ ( x ∗ ) = 0 / / 导 数 为 0 ( v ∗ ) T ≠ 0 / / L a g r a n g e 乘 子 不 为 0 A x ∗ = b / / 等 式 约 束 条 件 \begin{array}{lcl} \frac{\partial L(x^*,v^*)}{\partial (x^*)} = 0 \quad \quad //导数为0\\ (v^*)^T \neq 0 \quad \quad //Lagrange乘子不为0 \\ Ax^* = b \quad \quad //等式约束条件 \end{array} (x)L(x,v)=0//0(v)T̸=0//Lagrange0Ax=b//

二、不等式约束下的KKT条件

1、 题目描述

考虑不等式约束下的线性规划问题 m a x i m i z e f ( x ) = ( x − 3 ) 2 s u b j e c t   t o 1 ≤ x ≤ 5 maximize \quad f(x)=(x-3)^2 \\ subject \ to \quad 1≤x≤5 maximizef(x)=(x3)2subject to1x5

2、Lagrarian函数

原条件等价于: m i n   f ( x ) = − ( x − 3 ) 2 g 1 ( x ) = 1 − x ≤ 0 g 2 ( x ) = x − 5 ≤ 0 \begin{array}{lcl} min \ f(x)=-(x-3)^2\\ g_1(x)=1-x ≤0 \\ g_2(x)=x-5 ≤0 \end{array} min f(x)=(x3)2g1(x)=1x0g2(x)=x50 其对应的Lagrarian函数为: L ( x , λ 1 , λ 2 ) = f ( x ) + λ 1 g 1 ( x ) + λ 2 g 2 ( x ) = − ( x − 3 ) 2 + λ 1 ( 1 − x ) + λ 2 ( x − 5 ) \begin{array}{lcl} L(x,λ_1,λ_2) &=& f(x)+λ_1g_1(x)+λ_2g_2(x) \\ &=&-(x-3)^2+λ_1(1-x)+λ_2(x-5) \end{array} L(x,λ1,λ2)==f(x)+λ1g1(x)+λ2g2(x)(x3)2+λ1(1x)+λ2(x5)

3、KKT条件

其对应的KKT条件如下: ∂ L ( x ∗ , v ∗ ) ∂ ( x ∗ ) = − 2 ( x ∗ − 3 ) − λ 1 ∗ + λ 2 ∗ = 0 / / 导 数 为 0 λ 1 ∗ g 1 ( x ∗ ) = λ 1 ∗ ( 1 − x ∗ ) = 0 / / 不 等 式 约 束 条 件 λ 2 ∗ g 2 ( x ∗ ) = λ 2 ∗ ( x ∗ − 5 ) = 0 / / 不 等 式 约 束 条 件 g 1 ( x ∗ ) ≤ 0 / / 不 等 式 约 束 条 件 g 2 ( x ∗ ) ≤ 0 / / 不 等 式 约 束 条 件 λ 1 ∗ ≥ 0 / / L a g r a n g e 乘 子 大 于 0 λ 2 ∗ ≥ 0 / / L a g r a n g e 乘 子 大 于 0 \begin{array}{lcl} \frac{\partial L(x^*,v^*)}{\partial (x^*)} = -2(x^*-3)-λ_1^*+λ_2^* = 0 \quad \quad //导数为0\\ λ_1^*g_1(x^*) =λ_1^*(1-x^*)=0 \quad \quad //不等式约束条件\\ λ_2^*g_2(x^*) =λ_2^*(x^*-5)=0 \quad \quad //不等式约束条件\\ g_1(x^*) ≤ 0 \quad \quad //不等式约束条件\\ g_2(x^*) ≤ 0 \quad \quad //不等式约束条件\\ λ_1^*≥0 \quad \quad //Lagrange乘子大于0\\ λ_2^*≥0\quad \quad //Lagrange乘子大于0\\ \end{array} (x)L(x,v)=2(x3)λ1+λ2=0//0λ1g1(x)=λ1(1x)=0//λ2g2(x)=λ2(x5)=0//g1(x)0//g2(x)0//λ10//Lagrange0λ20//Lagrange0

二、等式约束和不等式约束结合的KKT条件

1、 题目描述

考虑不等式约束下的线性规划问题 m i n i m i z e f ( x ) g ( x ) = 0 h ( x ) ≤ 0 minimize f(x) \\ g(x)=0 \\ h(x)≤0 minimizef(x)g(x)=0h(x)0

2、Lagrarian函数

其对应的Lagrarian函数为: L ( x , λ , μ ) = f ( x ) + λ g ( x ) + μ h ( x ) \begin{array}{lcl} L(x,λ,μ) & = f(x)+λg(x)+μh(x) \end{array} L(x,λ,μ)=f(x)+λg(x)+μh(x)

3、KKT条件

其对应的KKT条件如下: ∂ L ( x ∗ , v ∗ ) ∂ ( x ∗ ) = 0 / / 导 数 为 0 λ ∗ ≠ 0 / / 等 式 L a g r a n g e 乘 子 不 为 0 g ( x ∗ ) = 0 / / 等 式 约 束 条 件 μ ∗ h ( x ∗ ) = 0 / / 不 等 式 约 束 条 件 h ( x ∗ ) ≤ 0 / / 不 等 式 约 束 条 件 μ ∗ ≥ 0 / / 不 等 式 L a g r a n g e 乘 子 大 于 0 \begin{array}{lcl} \frac{\partial L(x^*,v^*)}{\partial (x^*)} = 0 \quad \quad //导数为0\\ λ^* \neq 0 \quad \quad //等式Lagrange乘子不为0 \\ g(x^*) =0 \quad \quad //等式约束条件 \\ μ^*h(x^*) =0 \quad \quad //不等式约束条件\\ h(x^*) ≤ 0 \quad \quad //不等式约束条件 \\ μ^*≥0 \quad \quad //不等式Lagrange乘子大于0\\ \end{array} (x)L(x,v)=0//0λ̸=0//Lagrange0g(x)=0//μh(x)=0//h(x)0//μ0//Lagrange0

转载请注明原文地址: https://www.6miu.com/read-1750063.html

最新回复(0)