人工智能基础学习：拉格朗日乘子法实现非线性规划

拉格朗日乘子法原理介绍

对于二元函数，设目标函数为f($x_1,x_2$x1​,x2​)，极值存在的必要条件为：
等式约束为：$g(x_1,x_2)=0$g(x1​,x2​)=0
在无约束时，$\frac{\partial f^*}{\partial x_1}=\frac{\partial f^*}{\partial x_1}=0，即df=(\frac{\partial f^*}{\partial x_1})dx_1+(\frac{\partial f^*}{\partial x_2})dx_2=0$∂x1​∂f∗​=∂x1​∂f∗​=0，即df=(∂x1​∂f∗​)dx1​+(∂x2​∂f∗​)dx2​=0
在有等式约束时，除了以上关系式还要满足：
$dg=(\frac{\partial g^*}{\partial x_1})dx_1+(\frac{\partial g^*}{\partial x_2})dx_2=0$dg=(∂x1​∂g∗​)dx1​+(∂x2​∂g∗​)dx2​=0
由以上两个式子可以得出
$\frac {dx_2}{dx_1}=-(\frac{\partial f^*/\partial x_1}{\partial f^*/\partial x_2}) \frac {dx_2}{dx_1}=-(\frac{\partial g^*/\partial x_1}{\partial g^*/\partial x_2})$dx1​dx2​​=−(∂f∗/∂x2​∂f∗/∂x1​​)dx1​dx2​​=−(∂g∗/∂x2​∂g∗/∂x1​​)
即为$(\frac{\partial f^*}{\partial x_1})(\frac{\partial g^*}{\partial x_2})=(\frac{\partial f^*}{\partial x_2})(\frac{\partial g^*}{\partial x_1})$(∂x1​∂f∗​)(∂x2​∂g∗​)=(∂x2​∂f∗​)(∂x1​∂g∗​)
令这个式子等于一个可正可负的常数$\lambda$λ，这个数为拉格朗日乘子
$\lambda=(\frac{\partial f^*}{\partial x_1})(\frac{\partial g^*}{\partial x_2})=(\frac{\partial f^*}{\partial x_2})(\frac{\partial g^*}{\partial x_1})$λ=(∂x1​∂f∗​)(∂x2​∂g∗​)=(∂x2​∂f∗​)(∂x1​∂g∗​)
这些就可以得到一个方程组为
$\begin{cases} \frac{\partial f^*}{\partial x_1}-\lambda \frac{\partial g^*}{\partial x_1}=0 \\\\ g(x_1,x_2)=0 \\\\ \frac{\partial f^*}{\partial x_2}-\lambda \frac{\partial g^*}{\partial x_2}=0\\\\ \end{cases}$⎩⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎧​∂x1​∂f∗​−λ∂x1​∂g∗​=0g(x1​,x2​)=0∂x2​∂f∗​−λ∂x2​∂g∗​=0​
联立解方程组可得$x_1、x_2、\lambda$x1​、x2​、λ，就求得了极值点
这个方程组就相当于一个无约束的函数$L=f-\lambda g$L=f−λg的极值点，
此函数极值点存在的必要条件为$\frac{\partial L}{\partial x_2}=\frac{\partial L}{\partial x_2}=\frac{\partial L}{\partial \lambda}=0$∂x2​∂L​=∂x2​∂L​=∂λ∂L​=0
这个新定义的函数就为拉格朗日函数$L$L
$df=\lambda(\frac{\partial g^*}{\partial x_2})dx_1+\lambda(\frac{\partial g^*}{\partial x_2})dx_2=\lambda dg$df=λ(∂x2​∂g∗​)dx1​+λ(∂x2​∂g∗​)dx2​=λdg
这表明在极值点附近，L为目标函数f随约束条件g的微小变化而变化的比率
通过应用拉格朗日乘子，可以使求等式约束条件下函数f的极小点，成为求拉格朗日函数$L$L的驻点。这种引进待定乘子，将有等式约束的寻优问题转化为无约束的寻优问题的做法，称为拉格朗日乘子法。可用于求解有等式约束的非线性规划，还可以用于求解有不等式约束的非线性规划。
对于不等式约束，就要引入松弛变量使得不等式约束变为等式约束，然后进行求解。
例如不等式约束为：
$g(X)=ax_1+bx_2+c \leq 0$g(X)=ax1​+bx2​+c≤0
引入松弛变量后为：
$g(X)=ax_1+bx_2+c+x_3^2=0$g(X)=ax1​+bx2​+c+x32​=0，然后就可以用拉格朗日乘子法进行求解。

拉格朗日乘子法python代码

非线性规划为：min $f(x)=60-10x_1-4x_2+x_1^2+x_2^2-x_1x_2$f(x)=60−10x1​−4x2​+x12​+x22​−x1​x2​
等式约束为：$g(x)=x_1+x_2-8=0$g(x)=x1​+x2​−8=0
构造的拉格朗日等式为：$L=60-10x_1-4x_2+x_1^2+x_2^2-x_1x_2-\lambda(x_1+x_2-8)$L=60−10x1​−4x2​+x12​+x22​−x1​x2​−λ(x1​+x2​−8)
$\lambda$λ为乘子
对未知数求导$\frac{\partial L}{\partial x_1}、\frac{\partial L}{\partial x_2}、\frac{\partial L}{\partial \lambda}$∂x1​∂L​、∂x2​∂L​、∂λ∂L​
令得到的三个公式等于0，可以求出$x_1$x1​、$x_2$x2​、$\lambda$λ，从而将$x_1$x1​、$x_2$x2​带入f(X)中，就得到了极小值的最优解。

from sympy import * 
import numpy as np
#设置变量
x1 = symbols("x1")
x2 = symbols("x2")
a = symbols("a")
#构造拉格朗日等式
L = 60-10*x1-4*x2+x1*x1+x2*x2-x1*x2 - a * (x1+x2-8)
#求导，构造KKT条件
difyL_x1 = diff(L, x1)  #对变量x1求导
difyL_x2 = diff(L, x2)  #对变量x2求导
difyL_a = diff(L,a)  #对乘子a求导
#求解KKT等式
aa = solve([difyL_x1, difyL_x2, difyL_a], [x1, x2, a])
b=[]
#打印结果
for key in aa:
    b.append(aa[key])
    print(key,aa[key])
c=60-10*b[0]-4*b[1]+b[0]*b[0]+b[1]*b[1]-b[0]*b[1]
print("f(x)=",c)

结果为：

用KKT条件验证解的有效性

KKT条件：最优值必须满足
1、拉格朗日函数L对未知数求导$\frac{\partial L}{\partial x_1}、\frac{\partial L}{\partial x_2}、\frac{\partial L}{\partial \lambda}$∂x1​∂L​、∂x2​∂L​、∂λ∂L​为0，
2、拉格朗日乘子与约束函数相乘为0，$\lambda g(X)=0$λg(X)=0
3、约束函数$g(X)$g(X)为0
求取这三个条件所得到的等式就能得到候选最优值。
具体原理参考： 拉格朗日乘子法与KKT条件详解.
对于极值的优化是满足强对偶的（就是对偶式子的最优值是等于原式子的最优值的）
如有错误请指正！