拉格朗日&KKT条件极值求解

2023-09-02 04:44| 来源: 网络整理| 查看: 265

拉格朗日乘数法(等式约束条件极值) 基础用法

设,若 x , y x,y x,y满足 x + 3 y = 5 x y x+3y=5xy x+3y=5xy,求 3 x + 4 y 3x+4y 3x+4y的最小值:

构建拉格朗日函数:

L ( x , y , λ ) = 3 x + 4 y + λ ( x + 3 y − 5 x y ) L(x,y,\lambda)=3x+4y+\lambda(x+3y-5xy) L(x,y,λ)=3x+4y+λ(x+3y−5xy) 分别对 L ( x , y , λ ) L(x,y,\lambda) L(x,y,λ)中的 x , y , λ x,y,\lambda x,y,λ求导,并令偏导数等于0,用于求出拉格朗日函数的驻点. 注意:驻点不一定就是极值点则得到一下方程组 { L x ′ = 3 + λ ( 1 − 5 y ) = 0 ( 1 ) L y ′ = 4 + λ ( 3 − 5 x ) = 0 ( 2 ) L λ ′ = x + 3 y + 5 x y = 0 ( 3 ) \begin{cases} L'_x=3 + \lambda(1-5y)=0 &&& (1)\\ L'_y=4 + \lambda(3-5x)=0 &&& (2)\\ L'_\lambda=x+3y+5xy=0 &&& (3)\\ \end{cases} ⎩⎪⎨⎪⎧Lx′=3+λ(1−5y)=0Ly′=4+λ(3−5x)=0Lλ′=x+3y+5xy=0(1)(2)(3) 由上式 ( 1 ) ( 2 ) (1)(2) (1)(2)消去 λ \lambda λ,可求得: 3 x − 1 = 4 y ( 4 ) 3x-1=4y \kern{2em} (4) 3x−1=4y(4) 将 ( 4 ) (4) (4)式带入到 ( 3 ) (3) (3)中求得: { x = 1 y = 1 2 或 { x = 1 5 y = − 1 10 \begin{cases} x=1\\ \kern{2em}\\ y=\dfrac{1}{2} \end{cases} \kern{2em} 或 \kern{2em} \begin{cases} x=\dfrac{1}{5}\\ \kern{2em}\\ y=-\dfrac{1}{10}\\ \end{cases} ⎩⎪⎪⎨⎪⎪⎧x=1y=21或⎩⎪⎪⎪⎨⎪⎪⎪⎧x=51y=−101 分别将两组解(也是拉格朗日函数的驻点)带入到 3 x + 4 y 3x+4y 3x+4y中,分别得到: 3 ∗ 1 + 4 ∗ 1 2 = 5 或 3 ∗ 1 5 + 4 ∗ ( − 1 10 ) = 1 5 3*1 + 4 * \dfrac{1}{2}=5\\ 或\\ 3*\dfrac{1}{5} + 4*(-\dfrac{1}{10})=\dfrac{1}{5} 3∗1+4∗21=5或3∗51+4∗(−101)=51 所以最小值为: 1 5 \dfrac{1}{5} 51

多条件情况例如:在满足条件 g ( x , y ) = 0 ψ ( x , y ) = 0 g(x,y)=0 \kern{1em} \psi(x,y)=0 g(x,y)=0ψ(x,y)=0的条件下,求 f ( x , y ) f(x,y) f(x,y)的极值,可以构建拉格朗日函数: L ( x , y , λ , η ) = f ( x , y ) + λ g ( x , y ) + η ψ ( x , y ) L(x,y,\lambda,\eta)=f(x,y)+\lambda{g(x,y)}+\eta{\psi(x,y)} L(x,y,λ,η)=f(x,y)+λg(x,y)+ηψ(x,y) 在分别求 x , y , λ , η x,y,\lambda,\eta x,y,λ,η的偏导数,并令其等于0,最终求解方程组,得到 f ( x , y ) f(x,y) f(x,y)的驻点,再带入原方程得到极值

拉格朗日乘数法通用公式定义等式约束优化一般形式,其中 h k ( x 1 , x 2 , x 3 . . . , x n ) h_k(x_1,x_2,x_3...,x_n) hk(x1,x2,x3...,xn)是一个集合,标示不同的约束条件,也就是上述 L ( x , y , λ , η ) = f ( x , y ) + λ g ( x , y ) + η ψ ( x , y ) L(x,y,\lambda,\eta)=f(x,y)+\lambda{g(x,y)}+\eta{\psi(x,y)} L(x,y,λ,η)=f(x,y)+λg(x,y)+ηψ(x,y)中的函数 g ( x , y ) g(x,y) g(x,y)和 ψ ( x , y ) \psi(x,y) ψ(x,y): m i n f ( x 1 , x 2 , x 3 . . . , x n ) s . t . h k ( x 1 , x 2 , x 3 . . . , x n ) = 0 k ∈ ( 1 , 2 , 3 , . . . , l ) minf(x_1,x_2,x_3...,x_n)\\ s.t.h_k(x_1,x_2,x_3...,x_n)=0 \kern{2em} k\isin(1,2,3,...,l) minf(x1,x2,x3...,xn)s.t.hk(x1,x2,x3...,xn)=0k∈(1,2,3,...,l) 构造拉格朗日函数,其中 λ k \lambda_k λk标示不同条件的乘子,也就式上述 L ( x , y , λ , η ) = f ( x , y ) + λ g ( x , y ) + η ψ ( x , y ) L(x,y,\lambda,\eta)=f(x,y)+\lambda{g(x,y)}+\eta{\psi(x,y)} L(x,y,λ,η)=f(x,y)+λg(x,y)+ηψ(x,y)中的 λ \lambda λ和 η \eta η: L ( x 1 , x 2 , x 3 . . . , x n , λ 0 , λ 1 , λ 2 , . . . , λ k ) = f ( x 1 , x 2 , x 3 . . . , x n ) + λ k ∑ k = 0 l h k ( x 1 , x 2 , x 3 . . . , x n ) L(x_1,x_2,x_3...,x_n,\lambda_0,\lambda_1,\lambda_2,...,\lambda_k) = f(x_1,x_2,x_3...,x_n) + \lambda_k\sum_{k=0}^lh_k(x_1,x_2,x_3...,x_n) L(x1,x2,x3...,xn,λ0,λ1,λ2,...,λk)=f(x1,x2,x3...,xn)+λkk=0∑lhk(x1,x2,x3...,xn) 将 x 1 , x 2 , x 3 . . . , x n x_1,x_2,x_3...,x_n x1,x2,x3...,xn用 x i i ∈ ( 1 , 2 , 3 , . . . , n ) x_i \kern{1em} i\isin(1,2,3,...,n) xii∈(1,2,3,...,n), λ 1 , λ 2 , . . . , λ k \lambda_1,\lambda_2,...,\lambda_k λ1,λ2,...,λk用 λ k k ∈ ( 0 , 1 , 2 , . . . , l ) \lambda_k \kern{1em} k\isin(0,1,2,...,l) λkk∈(0,1,2,...,l)标示,上式可以写为: L ( x i , λ k ) = f ( x i ) + λ k ∑ k = 0 l h k ( x i ) i ∈ ( 1 , 2 , 3 , . . . , n ) k ∈ ( 0 , 1 , 2 , . . . , l ) L(x_i,\lambda_k)=f(x_i)+\lambda_k\sum_{k=0}^lh_k(x_i) \kern{2em} i\isin(1,2,3,...,n) \kern{1em} k\isin(0,1,2,...,l) L(xi,λk)=f(xi)+λkk=0∑lhk(xi)i∈(1,2,3,...,n)k∈(0,1,2,...,l) 建立方程组: { Δ L Δ x i = 0 i ∈ ( 1 , 2 , 3 , . . . , n ) Δ L Δ λ k = 0 k ∈ ( 1 , 2 , 3 , . . . , l ) \begin{cases} \dfrac{\varDelta L}{\varDelta x_i}=0 \kern{2em} i\isin(1,2,3,...,n)\\ \\ \dfrac{\varDelta L}{\varDelta \lambda_k}=0 \kern{2em} k\isin(1,2,3,...,l) \end{cases} ⎩⎪⎪⎪⎨⎪⎪⎪⎧ΔxiΔL=0i∈(1,2,3,...,n)ΔλkΔL=0k∈(1,2,3,...,l) 根据上诉方程组,求出驻点,并带入到原函数 f ( x ) f(x) f(x)当中验证,并最终得到极值点.

KKT(不等式约束条件极值)

不等式条件极值求解的思路是将不等式约束转换为等式约束,如有一下求解问题: m i n f ( x i ) i ∈ ( 0 , 1 , 2 , . . . , n ) s . t . g k ( x i ) ≤ 0 i ∈ ( 0 , 1 , 2 , . . . , n ) k ∈ ( 0 , 1 , 2 , . . . , l ) minf(x_i) \kern{1em} i\isin(0,1,2,...,n)\\ s.t.g_k(x_i)\le0 \kern{1em} i\isin(0,1,2,...,n) \kern{1em} k\isin(0,1,2,...,l) minf(xi)i∈(0,1,2,...,n)s.t.gk(xi)≤0i∈(0,1,2,...,n)k∈(0,1,2,...,l) 将上式的不等式约束添加一个松弛变量,让不等式变成等式,由于 g k ( x i ) ≤ 0 g_k(x_i)\le0 gk(xi)≤0,需要在不等式左边加上一个非负数,因此松弛变量为 a k 2 a_k^2 ak2,这样就不需要在引入新的约束 a k ≥ 0 a_k \ge0 ak≥0: h k ( x i , a k ) = g k ( x i ) + a k 2 = 0 h_k(x_i,a_k) = g_k(x_i)+a_k^2=0 hk(xi,ak)=gk(xi)+ak2=0 则,转换后,原来的不等式约束可以写成: m i n f ( x i ) i ∈ ( 0 , 1 , 2 , . . . , n ) s . t . h k ( x i , a k ) = g k ( x i ) + a k 2 = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) k ∈ ( 0 , 1 , 2 , . . . , l ) minf(x_i) \kern{1em} i\isin(0,1,2,...,n)\\ s.t.h_k(x_i,a_k)=g_k(x_i)+a_k^2=0 \kern{1em} i\isin(0,1,2,...,n) \kern{1em} k\isin(0,1,2,...,l) minf(xi)i∈(0,1,2,...,n)s.t.hk(xi,ak)=gk(xi)+ak2=0i∈(0,1,2,...,n)k∈(0,1,2,...,l) 根据等式约束条件极值的求法,可以写出拉格朗日函数为: L ( x i , λ k , a k ) = f ( x i ) + λ k ∑ k = 0 l [ g k ( x i ) + a k 2 ] L(x_i,\lambda_k,a_k)=f(x_i)+\lambda_k\sum_{k=0}^l[g_k(x_i)+a_k^2] L(xi,λk,ak)=f(xi)+λkk=0∑l[gk(xi)+ak2] 建立方程组: { Δ L Δ x i = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) Δ L Δ λ k = 0 k ∈ ( 0 , 1 , 2 , . . . , l ) Δ L Δ a k = 0 k ∈ ( 0 , 1 , 2 , . . . , l ) \begin{cases} \dfrac{\varDelta L}{\varDelta x_i}=0 \kern{1em} i\isin(0,1,2,...,n)\\ \\ \dfrac{\varDelta L}{\varDelta\lambda_k}=0 \kern{1em} k\isin(0,1,2,...,l)\\ \\ \dfrac{\varDelta L}{\varDelta a_k}=0 \kern{1em} k\isin(0,1,2,...,l) \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧ΔxiΔL=0i∈(0,1,2,...,n)ΔλkΔL=0k∈(0,1,2,...,l)ΔakΔL=0k∈(0,1,2,...,l) 根据上述方程组最终求解得到极值点

等式约束&条件约束极值

条件极值问题可写为: m i n f ( x i ) i ∈ ( 0 , 1 , 2 , . . . , n ) s . t . h k ( x i ) = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) k ∈ ( 1 , 2 , 3 , . . . , l ) s . t . g m ( x i ) ≤ 0 i ∈ ( 0 , 1 , 2 , . . . , n ) m ∈ ( 0 , 1 , 2 , . . . , z ) minf(x_i) \kern{1em} i\isin(0,1,2,...,n)\\ s.t.h_k(x_i)=0 \kern{2em} \kern{1em} i\isin(0,1,2,...,n) \kern{1em} k\isin(1,2,3,...,l)\\ s.t.g_m(x_i)\le0 \kern{1em} i\isin(0,1,2,...,n) \kern{1em} m\isin(0,1,2,...,z) minf(xi)i∈(0,1,2,...,n)s.t.hk(xi)=0i∈(0,1,2,...,n)k∈(1,2,3,...,l)s.t.gm(xi)≤0i∈(0,1,2,...,n)m∈(0,1,2,...,z) 可转换为: m i n f ( x i ) i ∈ ( 0 , 1 , 2 , . . . , n ) s . t . h k ( x i ) = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) k ∈ ( 1 , 2 , 3 , . . . , l ) s . t . ψ ( x i , a m ) = g m ( x i ) + a m 2 = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) m ∈ ( 0 , 1 , 2 , . . . , z ) minf(x_i) \kern{1em} i\isin(0,1,2,...,n)\\ s.t.h_k(x_i)=0 \kern{2em} \kern{1em} i\isin(0,1,2,...,n) \kern{1em} k\isin(1,2,3,...,l)\\ s.t.\psi(x_i,a_m)=g_m(x_i)+a_m^2 = 0 \kern{1em} i\isin(0,1,2,...,n) \kern{1em} m\isin(0,1,2,...,z) minf(xi)i∈(0,1,2,...,n)s.t.hk(xi)=0i∈(0,1,2,...,n)k∈(1,2,3,...,l)s.t.ψ(xi,am)=gm(xi)+am2=0i∈(0,1,2,...,n)m∈(0,1,2,...,z) 拉格朗日函数: L ( x i , λ k , η m , a m ) = f ( x i ) + λ k ∑ k − 0 l h k ( x i ) + η m ∑ m = 0 z [ g m ( x i ) + a m 2 ] i ∈ ( 0 , 1 , 2 , . . . , n ) k ∈ ( 1 , 2 , 3 , . . . , l ) m ∈ ( 0 , 1 , 2 , . . . , z ) L(x_i,\lambda_k,\eta_m,a_m)=f(x_i)+\lambda_k\sum_{k-0}^lh_k(x_i)+\eta_m\sum_{m=0}^z[g_m(x_i)+a_m^2]\\ \kern{1em} i\isin(0,1,2,...,n) \kern{1em} k\isin(1,2,3,...,l) \kern{1em} m\isin(0,1,2,...,z) L(xi,λk,ηm,am)=f(xi)+λkk−0∑lhk(xi)+ηmm=0∑z[gm(xi)+am2]i∈(0,1,2,...,n)k∈(1,2,3,...,l)m∈(0,1,2,...,z) 建立方程组: { Δ L Δ x i = 0 i ∈ ( 0 , 1 , 2 , . . . , n ) Δ L Δ λ k = 0 k ∈ ( 0 , 1 , 2 , . . . , l ) Δ L Δ η m = 0 m ∈ ( 0 , 1 , 2 , . . . , z ) Δ L Δ a m = 0 m ∈ ( 0 , 1 , 2 , . . . , z ) \begin{cases} \dfrac{\varDelta L}{\varDelta x_i}=0 \kern{1em} i\isin(0,1,2,...,n)\\ \\ \dfrac{\varDelta L}{\varDelta \lambda_k}=0 \kern{1em} k\isin(0,1,2,...,l)\\ \\ \dfrac{\varDelta L}{\varDelta \eta_m}=0 \kern{1em} m\isin(0,1,2,...,z)\\ \\ \dfrac{\varDelta L}{\varDelta a_m}=0 \kern{1em} m\isin(0,1,2,...,z)\\ \end{cases} ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧ΔxiΔL=0i∈(0,1,2,...,n)ΔλkΔL=0k∈(0,1,2,...,l)ΔηmΔL=0m∈(0,1,2,...,z)ΔamΔL=0m∈(0,1,2,...,z) 求解方程组,得到极值点

【本文地址】

公司简介

联系我们