精华内容
下载资源
问答
  • 机器学习中的数学——拉格朗日乘子法(一):等式约束的拉格朗日乘子法
    万次阅读
    2021-08-15 21:21:44

    分类目录:《机器学习中的数学》总目录
    相关文章:
    ·拉格朗日乘子法(一):等式约束的拉格朗日乘子法
    ·拉格朗日乘子法(二):不等式约束与KKT条件


    拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子,可将有 d d d个变量与 k k k个约束条件的最优化问题转化为具有 d + k d+k d+k个变量的无约束优化问题求解。即对于:
    min ⁡ f ( x ) s.t. g i ( x ) = 0 , i = 1 , 2 , ⋯   , k \begin{aligned} \min&\quad f(x)\\ \text{s.t.}&\quad g_i(x)=0\qquad ,i=1,2,\cdots,k \end{aligned} mins.t.f(x)gi(x)=0,i=1,2,,k我们定义拉格朗日函数:
    L ( x , λ ) = f ( x ) + λ i g i ( x ) L(x,\lambda)=f(x)+\lambda_ig_i(x) L(x,λ)=f(x)+λigi(x)
    我们即可将原优化问题转化为:
    ∇ X L ( x , λ ) = ∇ f + λ i ∇ g k = 0 ∇ λ L ( x , λ ) = g ( x ) = 0 \begin{aligned} \nabla_X L(x,\lambda)&=\nabla f+\lambda_i \nabla g_k=0\\ \nabla_\lambda L(x,\lambda)&=g(x)=0 \end{aligned} XL(x,λ)λL(x,λ)=f+λigk=0=g(x)=0

    先考虑一个等式约束的优化问题。假定 x x x d d d维向量,欲寻找 x x x的某个取值 x ∗ x^* x,使目标函数 f ( x ) f(x) f(x)最小且同时满足 g ( x ) = 0 g(x)=0 g(x)=0的约束。从几何角度看,该问题的目标是在由方程 g ( x ) = 0 g(x)=0 g(x)=0确定的 d − 1 d-1 d1维曲面上寻找能使目标函数 f ( x ) f(x) f(x)最小化的点。此时可以得到如下结论:

    • 对于约束曲面上的任意点 x x x,该点的梯度 ∇ g ( x ) \nabla g(x) g(x)正交于约束曲面
    • 在最优点 x ∗ x^* x,目标函数在该点的梯度 ∇ f ( x ∗ ) \nabla f(x^*) f(x)正交于约束曲面

    由此可知,在最优点 x ∗ x^* x,如下图所示,梯度 ∇ g ( x ) \nabla g(x) g(x) ∇ f ( x ∗ ) \nabla f(x^*) f(x)的方向必相同或相反,即存在 λ ≠ 0 \lambda\neq0 λ=0使得:
    ∇ f ( x ∗ ) + λ ∇ g ( x ∗ ) = 0 \nabla f(x^*) + \lambda\nabla g(x^*) =0 f(x)+λg(x)=0
    λ \lambda λ称为拉格朗日乘子,我们定义拉格朗日函
    L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda)=f(x)+\lambda g(x) L(x,λ)=f(x)+λg(x)
    不难发现,将其对 x x x的偏导数 ∇ x L ( x , λ ) \nabla_x L(x,\lambda) xL(x,λ)置零即得上式。同时,将其对入的偏导数 ∇ λ L ( x , λ ) \nabla_\lambda L(x,\lambda) λL(x,λ)置零即得约束条件 g ( x ) = 0 g(x)=0 g(x)=0

    等式约束
    于是,原约束优化问题可转化为对拉格朗日函数 L ( x , λ ) L(x,\lambda) L(x,λ)的无约束优化问题。

    现在我们以一个常见的例子来考虑拉格朗日乘子法。假设 x x x为2维向量,且:
    g ( x ) = x 1 2 x 2 − 3 = 0 g(x)=x_1^2x_2-3=0 g(x)=x12x23=0
    现在我们想求其上的点与原点的最短距离,即:
    min ⁡ f ( x ) = x 1 2 + x 2 2 \min f(x)=x_1^2+x_2^2 minf(x)=x12+x22
    此时,圆( f ( x ) f(x) f(x))和曲线( g ( x ) g(x) g(x))相切,也就是在该点切线相同:

    示例图

    此时 f f f梯度:
    ∇ f x 1 = 2 x 1 ∇ f x 2 = 2 x 2 \nabla f_{x_1}=2x_1 \\ \nabla f_{x_2}=2x_2 fx1=2x1fx2=2x2
    此时 g g g梯度:
    ∇ g x 1 = 2 x 1 x 2 ∇ g x 2 = x 1 2 \begin{aligned} &\nabla g_{x_1}=2x_1x_2\\ &\nabla g_{x_2}=x_1^2 \end{aligned} gx1=2x1x2gx2=x12

    梯度向量平行,我们可以写为:
    ∇ f = λ ∇ g \nabla f=\lambda \nabla g f=λg

    所以我们可得:
    ∇ f = λ ∇ g g ( x ) = x 1 2 x 2 − 3 = 0 \begin{aligned} \nabla f&=\lambda \nabla g\\ g(x)&=x_1^2x_2-3=0 \end{aligned} fg(x)=λg=x12x23=0
    我们构造拉格朗日函数:
    L ( x , λ ) = f ( x ) + λ g ( x ) L(x,\lambda)=f(x)+\lambda g(x) L(x,λ)=f(x)+λg(x)
    并利用拉格朗日乘子法即可得到与上式相同的等式:
    ∇ X L ( x , λ ) = ∇ f + λ ∇ g = 0 ∇ λ L ( x , λ ) = g ( x ) = x 1 2 x 2 − 3 = 0 \begin{aligned} \nabla_X L(x,\lambda)&=\nabla f+\lambda \nabla g=0\\ \nabla_\lambda L(x,\lambda)&=g(x)=x_1^2x_2-3=0 \end{aligned} XL(x,λ)λL(x,λ)=f+λg=0=g(x)=x12x23=0

    更多相关内容
  • 拉格朗日乘子法最优值求解,求解函数的最小值,极小值求解,求解速度快。效率高
  • 拉格朗日乘子法2.python –拉格朗日乘子法3.python sympy包 –拉格朗日乘子法 1.拉格朗日乘子法 题目如下:等式约束下的拉格朗日乘子法求解过程 2.python –拉格朗日乘子法 题目如上: from scipy.optimize import ...
  • 单纯形: #导入包 from scipy import optimize import numpy as np #确定c,A,b,Aeq,beq c = np.array([115,90]) A = np.array([[10,20],[4,16],[15,10]]) b = np.array([200,128,220]) #Aeq = np.array([[1,-1,1]...
  • 实验目录一、拉格朗日乘子法和KKT的介绍二、手工数学推导三、拉格朗日乘子法的有约束情况四、手工数学推导,考虑有约束情况的比较五、参考文献 一、拉格朗日乘子法和KKT的介绍 拉格朗日乘子法 拉格朗日乘子λ代表...
  • 拉格朗日乘子法-fmincon,拉格朗日乘子法原理,matlab源码.zip
  • 增广拉格朗日乘子法ALM算法是机器学习中十分常用且有效的一种优化算法,经常用于低秩和稀疏问题的优化求解中,这个包是增广拉格朗日乘子法的matlab代码
  • 拉格朗日乘子法最优值求解,求解函数的最小值,极小值求解,求解速度快。效率高
  • 这篇文章详细介绍了拉格朗日乘子法的原理及其相关知识。
  • 拉格朗日乘子法 约束优化问题的标准形式为 min f ( x, x Rn s.t g (x ) 0,i 1,2, m i h (x ) 0, j 1,2,l j 其中 f , g , h : Rn R i j 约束优化算法的基本思想是 通过引入效用函数的方法将约束优化问题转换为无约束...
  • 增广拉格朗日乘子法

    2014-09-18 10:39:20
    这是一个描述增广拉格朗日乘子法原理及Java算法的文档,很值得大家学习!
  • 拉格朗日乘子法详解

    2021-07-27 14:09:06
    一、拉格朗日乘子法简介 拉格朗日乘子法的应用十分广泛,它是SVM的理论基础,是凸优化的重要研究部分。它用于求解约束条件下的极值问题,过程简单巧妙,也是各类考试的常考题型。然而,拉格朗日乘子法的原理我却...

    一、拉格朗日乘子法简介

    拉格朗日乘子法的应用十分广泛,它是SVM的理论基础,是凸优化的重要研究部分。它用于求解约束条件下的极值问题,过程简单巧妙,也是各类考试的常考题型。然而,拉格朗日乘子法的原理我却一直模模糊糊,每次看的时候才知道,一段时间不看就又忘了,所以特地写这篇博客来供自己时刻学习。

    先从一个简单的例子开始:

    假如我们需要求一个函数的最小值,即约束条件为。我们用拉格朗日乘子法来求解:

     首先用描述约束条件,即

    而后引入拉格朗日乘子λ,并构造一个新的函数:

    因为,于是,因此当取得极小值时有:

          (1)

    于是得到: =>

    即当==1时,取得最小值,最小值为2。这就是拉格朗日乘子法求解过程。

    拉格朗日乘子法非常巧妙,但其中的原理却难以琢磨,从几何角度观察,我们可以更加直观地理解拉格朗日乘子法的原理以及这个乘子λ的几何含义。

    首先我们观察约束条件,在平面上是一条直线如下图中的蓝色直线所示。

     再看,令这表示的某一条等高线,随着r的改变我们得到了多条等高线,在上图中以绿色圆圈表示。

    在图中,如果某一条等高线与直线相交,则表示在的约束条件下,可以取到r的值。为了求得的最小值,在保证绿色圆圈与蓝色直线有交点的前提下,逐渐将r缩小,直到绿色等高线圆小到与蓝色直线相切,此时r0最小,我们认为获得了最小值

    下面我们来计算,在图中我们看到等高线圆与约束直线相切。此时在切点处,等高线圆与约束直线具有相同的切线方向与法线方向。

    又因为等高线f的切线方向与在该点的梯度方向相互正交,于是的法线方向即是的梯度方向,而该梯度方向为

    同理直线的法线方向也就是的梯度方向

    在切点处GfGg的方向相同,即相切。那么f ( x ) g ( x ) 在这一点的梯度一定是成比例的(具体理解起来就是法向量一定成比例)。

    因此我们引入乘子λ,并且有

      =>    2

    上式与式(1)相同。这个方程组总共包含n + 1个方程(梯度是一个向量,梯度等于0必须每一维都为0),恰好可以解出所有的λ ​    

    到此我们也已经获得了与拉格朗日乘子法相一致的结论。于是我们从几何角度解释了拉格朗日乘子引入的过程,也验证了拉格朗日乘子法的结论。

    二、拉格朗日乘子法求解带等式约束的最优化问题

    拉格朗日求得的并不一定是最优解,只有在凸优化的情况下,才能保证得到的是最优解,所以我们说拉格朗日乘子法得到的为可行解,其实就是局部极小值。

    1、构造拉格朗日函数

    之所以这样构造的原理我们可以继续看上面式(2,我们把式子的右边移到左边,并把常数移进微分算子,得到:

    把这个式子重新解释一下,这个就是函数无约束条件下极值点的充分条件。

    2、构造完之后就可以分别对参数求偏导,并令其等于0,就能解出无约束极值和极值所对应的点。

    三、引入KKT条件求带不等式约束条件的最优化问题

    所谓的KKT条件,是指对一类符合条件的所有拉格朗日乘子法问题进行公式化求解的过程。在机器学习中,我们解决的问题一般最后都化为目标函数最优化问题,即转化为在给定约束条件下最大或最小化目标函数。

    约束条件会有一般包括以下三类:

    1)仅含等式约束

    2)仅含不等式约束

    3)等式和不等式约束混合型

    当然还有一类没有任何约束条件的最优化问题。仅含等式约束的目标函数不再赘述。

    对于不等式约束g(x)<=0,和等式约束h(x)=0不一样,h(x)=0可以在平面上画出一条等高线,而g(x)<=0是一个区域,很多个等高线堆叠而成的一块区域,我们把这块区域称为可行域。

    不等式约束分两种情况来讨论,第一种是原有函数的(不考虑可行域限制时的)极值点落在可行域内(不包含边界),第二种是原有函数的(不考虑可行域限制时的)极值点落在可行域外(包含边界)。

    下面举两个例子来解释这两种情况,然后总结两种情况给出转换求解。

    (一)带不等式约束条件的最优化

    在有不等式g(x)<=0的约束下,可行解 x 只能在 g(x)<0 或者 g(x)=0 的区域里取得:

    当可行解 x 落在 g(x)<0 的区域内,此时直接极小化 f(x) 即可;

    当可行解 x 落在 g(x)=0 即边界上,此时等价于等式约束优化问题.

    case1:当约束区域包含目标函数原有的的可行解时,此时加上约束可行解仍落在约束区域内部,对应 g(x)<0 的情况,这时约束条件不起作用;

    现在我们假设问题是:,其中

     我们很容易知道f(x)的最小值在(00),等高线如下图:

    接下来我们画上g(x1,x2)限制的可行域(以(00)为圆心,半径为1的圆型区域,包括边界):

    很明显这个约束并不起作用,函数f(x1,x2)的极值点不变,这种情况约束不起作用,考虑极小值点x*,这个时候,g(x*) < 0f(x*)的梯度等于0

    case2:当约束区域不包含目标函数原有的可行解时,此时加上约束后可行解落在边界 g(x)=0 上。下面我们考虑另外一个不等式约束下的问题:,其中

    我们可以看一下这个问题的等高线情况:

    以上两种情况就是说,要么可行解落在约束边界上即得 g(x)=0,要么可行解落在约束区域内部,此时约束不起作用,令 λ=0 消去约束即可,所以无论哪种情况都会得到λ(也就是KKT条件的其中之一)。

    还有一个问题是 λ 的取值,在等式约束优化中,约束函数与目标函数的梯度只要满足平行即可,而在不等式约束中则不然,若 λ≠0,这便说明 可行解 x 是落在约束区域的边界上的,这时可行解应尽量靠近无约束时的解,所以在约束边界上,目标函数的负梯度方向应该远离约束区域朝向无约束时的解,此时正好可得约束函数的梯度方向与目标函数的负梯度方向应相同:

    上式需要满足的要求是拉格朗日乘子 λ>0

    (二)满足KKT条件

    可见对于不等式约束,只要满足一定的条件,依然可以使用拉格朗日乘子法解决,这里的条件便是 KKT 条件。

    对于如下:

    我们定义的拉格朗日函数:

    这时,KKT条件如下:

    满足 KKT 条件后极小化 Lagrangian 即可得到在不等式约束条件下的可行解。 KKT 条件看起来很多,其实很好理解:

    1) 拉格朗日取得可行解的必要条件;

    2) 这就是以上分析的一个比较有意思的约束,称作松弛互补条件;

    34) 初始的约束条件;

    5) 不等式约束的 Lagrange Multiplier 需满足的条件

    (三)原最优化问题转对偶问题

    每个线性规划问题都有一个与之对应的对偶问题,对偶问题有非常良好的性质,以下列举几个:

    1)对偶问题的对偶是原问题;

    2)无论原始问题是否是凸的,对偶问题都是凸优化问题;

    3)对偶问题可以给出原始问题一个下界;

    4)当满足一定条件时,原始问题与对偶问题的解是完全等价的;

    任何满足强对偶性的优化问题,只要其目标函数与约束函数可微,任一对原始问题与对偶问题的解都是满足 KKT 条件的。即满足强对偶性的优化问题中,若x*为原始问题的最优解,α* ,β* 为对偶问题的最优解,则可得 x*,α*,β* 满足 KKT 条件。

    当原始问题是凸优化问题,且存在x*,α*,β*满足 KKT 条件,那么它们分别是原始问题和对偶问题的极值点并且强对偶性成立。

    当满足KKT条件时, f(x)是等价的。

    因此我们的目标函数可以写为:

    如果用对偶表达式: 由于我们的优化是满足强对偶的(满足KKT条件),强对偶就是说对偶式子的最优值是等于原问题的最优值的,所以在取得最优值 x 的条件下,它满足:

    我们来看看中间两个式子发生了什么事情:

    可以看到上式本质上是说 x 取得了最小值,对于函数 f(x)+ag(x)+bh(x),求取导数要等于零,即

    这就是KKT条件中第一个条件:

    所有上述说明,满足强对偶条件的优化问题的最优值都必须满足KKT条件,也就是说当满足KKT条件时原始问题与其对偶问题具有相同的最优解。

    参考网址:

    https://www.cnblogs.com/jason-wyf/p/6727524.html

    https://blog.csdn.net/Laurel1115/article/details/88238944

    https://blog.csdn.net/weixin_44273380/article/details/109016774

    展开全文
  • 图解拉格朗日乘子法

    2018-03-24 14:44:56
    在数学中的最优化问题中,拉格朗日乘数法方法可以将一个有n个变量与k个约束条件的最优化问题转换为一个解有n + k个变量的方程组的解的问题...本文以可视化的形式讲解拉格朗日乘子法,注意,虽然是英语,但是都很简单哦
  • 拉格朗日乘子法

    2020-07-27 11:22:48
    在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。 这里提到的最优化问题通常是指...

    搬运工
    在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)和KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。

    这里提到的最优化问题通常是指对于给定的某一函数,求其在指定作用域上的全局最小值(因为最小值与最大值可以很容易转化,即最大值问题可以转化成最小值问题)。提到KKT条件一般会附带的提一下拉格朗日乘子。对学过高等数学的人来说比较拉格朗日乘子应该会有些印象。二者均是求解最优化问题的方法,不同之处在于应用的情形不同。

    拉格朗日乘数法(Lagrange multiplier)有很直观的几何意义。举个2维的例子来说明:假设有自变量x和y,给定约束条件g(x,y)=c,要求f(x,y)在约束g下的极值。我们可以画出f的等高线图,如下图。此时,约束g=c由于只有一个自由度,因此也是图中的一条曲线(红色曲线所示)。显然地,当约束曲线g=c与某一条等高线f=d1相切时,函数f取得极值。两曲线相切等价于两曲线在切点处拥有共线的法向量。因此可得函数f(x,y)与g(x,y)在切点处的梯度(gradient)成正比。于是我们便可以列出方程组求解切点的坐标(x,y),进而得到函数f的极值。
    1 与原点的最短距离假如有方程:图像是这个样子滴:

    现在我们想求其上的点与原点的最短距离:

    这里介绍一种解题思路。首先,与原点距离为 的点全部在半径为 的圆上:

    那么,我们逐渐扩大圆的半径:

    显然,第一次与 相交的点就是距离原点最近的点:

    此时,圆和曲线相切,也就是在该点切线相同:

    至此,我们分析出了:2 等高线为了继续解题,需要引入等高线。这些同心圆:

    可以看作函数 的等高线:

    根据梯度的性质(关于梯度可以查看如何通俗地理解梯度?),梯度向量:是等高线的法线:
    另外一个函数 的等高线为:
    之前的曲线 就是其中值为3的等高线:

    因此,梯度向量:也垂直于等高线 :

    梯度向量是等高线的法线,更准确地表述是:3 拉格朗日乘子法3.1 求解根据之前的两个分析:综合可知,在相切点,圆的梯度向量和曲线的梯度向量平行:

    也就是梯度向量平行,用数学符号表示为:还必须引入 这个条件,否则这么多等高线,不知道指的是哪一根:

    因此联立方程:求一下试试:这就是拉格朗日乘子法。3.2 定义要求函数 在 约束下的极值这种问题可以表示为: 意思是subject to,服从于,约束于的意思。可以列出方程组进行求解:用这个定义来翻译下刚才的例子,要求:令:求:联立方程进行求解:3.3 变形这个定义还有种变形也比较常见,要求:定义:求解下面方程组即可得到答案:把等式左边的偏导算出来就和上面的定义是一样的了。3.4 多个约束条件如果增加一个约束条件呢?比如说:求:从图上看约束条件是这样的:

    很显然所求的距离是这样的:

    那这三者的法线又有什么关系呢? 的法线是 和 的法线的线性组合:

    假设:那么线性组合就表示为:联立方程:即可求解。往更高纬度走的话,多约束条件的情况下,问题变为了 围成的曲线 和 相切,直观上看 必然在 张成的空间中:

    这点的严格性这里就不证明了。文章最新版本在(有可能会有后续更新):如何理解拉格朗日乘子法?编辑于 2018-07-31予人玫瑰,手有余香赞赏8 人已赞赏​已赞同 1505​​64 条评论​分享​收藏​喜欢​收起​lemonvisual state estimation256 人赞同了该回答为什么出现拉格朗日乘子法?最短路径问题从几何意义中获得灵感:从数学公式中获得灵感推广到高维空间------------------------------------------------------一个最短路径问题

    假设你在M点,需要先到河边(上图右侧曲线 )再回到C点,如何规划路线最短?假设: 河流曲线满足方程 g(x,y) = 0 (例如 如果它是一个圆: )用P表示河边上的任意P(x,y)点,用d(M,P)表示M,P之间距离,那么问题可以描述为: , 约束于 如何求解问题? 1. 从几何意义中获得灵感:首先,f§是一个标量(只有大小没有方向),那么在上图的二维空间中必然存在了一个标量场f§,即对于每一个点P都对应着一个f§值,它代表经过该点的路径总和是多少。如果我们画出它的等值线(场线),就会发现它呈椭圆向外辐射:

    显然,f§的等值线与河边曲线的交点P即为我们想求的点。那么问题来了: 这样的点满足何种性质? (如果没有性质也就无法列出关系式进行求解,但是这么特殊的点极有可能存在良好某种特性)最直观的性质: 等值线(椭圆)在P点的法向量n与河边曲线的法向量m平行:

    而在多元微积分中,一个函数h在某一点P的梯度是点P所在等值线(二维)或等值面(三维)的法向量,即,所以对于函数 f , g : (注意 梯度是一个向量,准备在另一个问题中对梯度的概念做详细阐述)即由相交点的性质我们得到了2个关系式(因为是二维平面,对于三维则可以得到三个关系式,以此类推),再加上我们的约束条件:一共3个关系式,由线性代数中知识可知 3个关系式,3个未知量()极有可能有唯一解,当然也不排除会出现多个解甚至无穷多解 (例如 下图 河边是一条直线,且M,C就在河边时)。(关于这个知识点稍后在其它答案中给出解释)。

    2. 从数学公式中获得灵感仍人是问题: 我们知道在多元微积分中如果想求一个函数的极值一般的做法是把 ,如何把这个公式和我们的约束条件 统一在一起呢?答案是: 引入 并且定义一个新的函数: ,令: 与我们要求解的优化问题是 等价的: 因为: 与约束条件等价,而且此时 即拉格朗日函数与我们的目标函数 取相同值。 用拉格朗日函数把目标函数和约束条件统一在了一起。 实际上这种方法与上面的几何方法是完全等价的:
    3. 3. 推广到高维空间以上我们一直在讨论 二维的情形,下面让我们看看这个问题的高维情况: 以几何观点为例:假设约束条件变成 ,其中 h是紫色椭球面, g是平面。它们相交于黑色的环,且在相交线上(黑色环)各自的方向向量() 与相交线垂直。对于我们的目标函数 ,下图中红色椭球是它的等值面。它与黑色环的交点 ,此处的向量
    4. 更高维度同理。
    主要内容转载自知乎如何理解拉格朗日乘子法? - 马同学的回答 - 知乎
    https://www.zhihu.com/question/38586401/answer/457058079

    其他参考:
    https://www.cnblogs.com/mo-wang/p/4775548.html
    用于个人学习记录,侵删

    展开全文
  • 约束优化与拉格朗日乘子法, 来自优化大牛Dimitri P Bertsekas
  • 使用拉格朗日乘子法对目标进行分离,将视频的每一帧图像分离为前景图像和背景图像
  • 数值计算之 拉格朗日乘子法初探前言等式约束优化等式约束的几何解释不等式约束优化多约束优化KKT条件 前言 LM算法的置信域方法中,通过在优化函数后添加一个优化量约束来提升迭代过程中的稳定性。 拉格朗日乘子法(La...

    前言

    LM算法的置信域方法中,通过在优化函数后添加一个优化量约束来提升迭代过程中的稳定性。

    拉格朗日乘子法(Lagrange Multiplier Method)是非线性优化中的常用方法,置信域约束实际上就是拉格朗日乘子法的应用。

    本篇将学习记录拉格朗日乘子法的原理和使用。

    注意:之所以是初探,是因为我还没有总结过凸优化的基础内容,现在不会深入研究拉格朗日乘子法需要满足的限定条件。

    等式约束优化

    对于优化函数 f : R n → R f:{\bf R}^n \to {\bf R} f:RnR,求 f f f在某个可行域 x ∈ R n {\bf x}\in {\bf R^n} xRn下的极值点。如果可行域通过等式 g ( x ) = 0 g{\bf (x)}=0 g(x)=0表达,则记为:
    min ⁡ x f ( x ) s . t . g ( x ) = 0 \min_{\bf x} f({\bf x}) \\ s.t. \quad g({\bf x})=0 xminf(x)s.t.g(x)=0
    假设 f ( x ) , g ( x ) f({\bf x}),g({\bf x}) f(x),g(x)都连续可导,则定义拉格朗日函数,获得极值条件:
    L ( x , λ ) = f ( x ) + λ g ( x ) min ⁡ x , λ L ( x , λ ) = min ⁡ x , λ ( f ( x ) + λ g ( x ) ) → { ∇ x L ( x , λ ) = ∇ x f ( x ) + λ ∇ x g ( x ) = 0 ∇ λ L ( x , λ ) = g ( x ) = 0 L({\bf x,\lambda})=f({\bf x})+\lambda g({\bf x}) \\ \quad \\ \min_{\bf x,\lambda} L({\bf x},\lambda)=\min_{\bf x,\lambda} (f({\bf x})+\lambda g({\bf x})) \\ \quad \\ \to \begin{cases} \nabla_{\bf x} L({\bf x}, \lambda)=\nabla_{\bf x} f({\bf x})+\lambda\nabla_{\bf x}g({\bf x})=0 \\ \nabla_{\lambda} L({\bf x}, \lambda)= g({\bf x})=0 \\ \end{cases} L(x,λ)=f(x)+λg(x)x,λminL(x,λ)=x,λmin(f(x)+λg(x)){xL(x,λ)=xf(x)+λxg(x)=0λL(x,λ)=g(x)=0
    于是,等式约束优化就变成了无约束优化问题。

    不过,拉格朗日函数的构造有一些突兀,这里给出一个几何解释。

    等式约束的几何解释

    下图是求极大值的例子,蓝色虚线表示优化函数 f ( x , y ) f(x,y) f(x,y) f ( x , y ) = d 1 , d 2 , … f(x,y)=d_1,d_2,\dots f(x,y)=d1,d2,表示该函数的一个个等高线, d 1 > d 2 > d 3 d_1>d_2>d_3 d1>d2>d3,蓝色小箭头表示该处的梯度;红色线表示约束方程 g ( x , y ) = c g(x,y)=c g(x,y)=c,红色小箭头表示该处的梯度。需要注意,该图像是从三维空间投影到xy平面上的结果。
    在这里插入图片描述
    等式约束条件下, x , y x,y x,y的值只能在红线上取。优化函数的极值必然会在蓝线与红线相切的切点获得,这是因为:蓝色梯度是优化函数增长最快的方向,如果极值点是切点附近的点,那么向切点运动,函数值仍然会增加,这就不符合极大值点的定义了。求极小值的情况也同理。

    给出切点处是极小值点的数学形式,即:
    ∇ x , y f ( x , y ) = − λ ∇ x , y g ( x , y ) g ( x , y ) = 0 \nabla_{x,y} f(x,y)=-\lambda \nabla_{x,y} g(x,y) \\ g(x,y) = 0 x,yf(x,y)=λx,yg(x,y)g(x,y)=0
    第一个式子表示两个函数 f , g f,g f,g处的梯度平行(说 f , g f,g f,g相切并不严谨,因为图示只是在xy平面上的函数投影),第二个式子表示约束条件决定的可行域。

    不等式约束优化

    优化函数不变,约束条件变成了不等式 g ( x ) ≤ 0 g({\bf x})\le 0 g(x)0,则可行域从曲线变成了一个曲面,如下图所示,灰色部分代表可行域。
    在这里插入图片描述
    此时需要考虑两种情况。

    第一种情况如图左,如果极值点落在可行域边界内,即 g ( x ) < 0 g({\bf x})<0 g(x)<0,则约束条件并没有影响优化函数本来的极值点位置 x ∗ \bf x^* x,也就是说拉格朗日函数 L ( x , λ ) L({\bf x},\lambda) L(x,λ) f ( x ) f(\bf x) f(x)的极值是等价的, λ = 0 \lambda=0 λ=0,得到极值条件:
    ∇ x L ( x , λ ) = 0 λ = 0 g ( x ) < 0 \nabla_{\bf x} L({\bf x},\lambda)=0 \\ \lambda = 0 \\ g({\bf x}) < 0 xL(x,λ)=0λ=0g(x)<0

    第二种情况如图右,如果极值点落在可行域边界上,即 g ( x ) = 0 g(\bf x)=0 g(x)=0,则与等式约束优化的极值条件相同:
    ∇ x L ( x , λ ) = 0 λ ≥ 0 g ( x ) = 0 \nabla_{\bf x} L({\bf x},\lambda)=0 \\ \lambda \ge 0\\ g({\bf x})=0 xL(x,λ)=0λ0g(x)=0
    其中, λ ≥ 0 \lambda \ge 0 λ0是因为,在求极小值时,等式约束条件是 ∇ x f ( x ) = − λ ∇ g x ( x ) \nabla_{\bf x} f({\bf x})=-\lambda \nabla g_{\bf x}({\bf x}) xf(x)=λgx(x),其中 ∇ x f ( x ) \nabla_{\bf x} f({\bf x}) xf(x)指向可行域内(如果指向可行域外,那么在可行域内移动时,优化函数值还会继续下降,不符合极小值定义), ∇ x g ( x ) \nabla_{\bf x} g({\bf x}) xg(x)指向可行域外(梯度方向指向 g ( x ) > 0 g({\bf x})>0 g(x)>0)。这就限定了 λ ≥ 0 \lambda \ge 0 λ0 λ = 0 \lambda=0 λ=0意味着可行域边界通过了 ∇ x f ( x ) = 0 \nabla_{{\bf x}}f({\bf x})=0 xf(x)=0的位置。

    将两种情况综合考虑,获得不等式约束优化的KKT(Karush-Kuhn-Tucker)条件:
    ∇ x L ( x , λ ) = ∇ x f ( x ) + λ ∇ x g ( x ) = 0 g ( x ) ≤ 0 λ ≥ 0 λ g ( x ) = 0 \nabla_{\bf x} L({\bf x}, \lambda) = \nabla_{\bf x}f({\bf x})+\lambda \nabla_{\bf x}g({\bf x}) = {\bf 0} \\ g({\bf x}) \le 0 \\ \lambda \ge 0 \\ \lambda g({\bf x}) = 0 xL(x,λ)=xf(x)+λxg(x)=0g(x)0λ0λg(x)=0

    多约束优化

    上面的等式与不等式约束可以共同推广到多个约束的优化情况:
    L ( x , λ ) = f ( x ) + ∑ i = 1 m λ i g i ( x ) + ∑ j = 1 n μ j h j ( x ) s . t . g i ( x ) ≤ 0 , h j ( x ) = 0 L({\bf x},\lambda)=f({\bf x})+\sum_{i=1}^m \lambda_i g_i({\bf x}) + \sum_{j=1}^n \mu_j h_j({\bf x}) \\ \quad \\ s.t. \quad g_i{(\bf x)} \le 0,\quad h_j({\bf x}) = 0 \\ L(x,λ)=f(x)+i=1mλigi(x)+j=1nμjhj(x)s.t.gi(x)0,hj(x)=0

    其KKT条件为:
    ∇ x L ( x , λ ) = ∇ x f ( x ) + ∑ i = 1 m λ i ∇ g i ( x ) + ∑ j = 1 n μ j ∇ h j ( x ) = 0 g i ( x ) ≤ 0 h j ( x ) = 0 λ i ≥ 0 λ i g i ( x ) = 0 \nabla_{\bf x} L({\bf x}, \lambda) = \nabla_{\bf x} f({\bf x})+\sum_{i=1}^m \lambda_i \nabla g_i({\bf x}) + \sum_{j=1}^n \mu_j \nabla h_j({\bf x}) = 0 \\ \quad \\ \quad g_i{(\bf x)} \le 0 \\ \quad h_j({\bf x}) = 0 \\ \lambda_i \ge 0 \\ \lambda_i g_i({\bf x}) = 0 xL(x,λ)=xf(x)+i=1mλigi(x)+j=1nμjhj(x)=0gi(x)0hj(x)=0λi0λigi(x)=0

    KKT条件

    上面给出的KKT条件,实际上是约束优化问题有解时满足的必要条件。也就是说,非极值也可能满足KKT条件。因此,只有满足某些正则条件时,KKT条件才能正确使用,比如最常用的线性无关条件LICQ:

    对于极值点落在边界上的不等式约束条件在极值点处的梯度与等式约束在极值点处的梯度线性无关时。

    由于这一部分涉及很多凸优化内容,因此等我学习到凸优化时,再来深入探究KKT条件。

    代码示例

    这里给出一个基于python sympy的等式约束拉格朗日乘子法示例。由于sympy不能单独完成不等式约束,需要添加其它模块,以后会补充不等式约束代码。

    import numpy as np
    import math
    import scipy
    import sympy
    
    
    def solve_lagarange(F, G=0, H=0):
        x, y, l, u = sympy.symbols('x, y, l, u')
        L = F + l * G + u * H
        px, py, pl, pu = sympy.derive_by_array(L, [x, y, l, u])
        res = sympy.solve([px, py, pl, pu], x, y, l, u)
        print(res)
    
    
    def eq_limit_solve():
        a, b = sympy.symbols('x, y')
        optim_function = non_linear_func_2(a, b)
        eq_limit_function = limite_func_1(a, b)
        solve_lagarange(optim_function, 0, eq_limit_function)
    
    
    def non_linear_func(x, y):
        fxy = 0.5 * (x ** 2 + y ** 2)
        return fxy
    
    
    def non_linear_func_2(x, y):
        fxy = x*x + 2*y*y + 2*x*y + 3*x - y - 2
        return fxy
    
    
    def non_linear_func_3(x, y):
        fxy = 0.5 * (x ** 2 - y ** 2)
        return fxy
    
    
    def non_linear_func_4(x, y):
        fxy = x**4 + 2*y**4 + 3*x**2*y**2 + 4*x*y**2 + x*y + x + 2*y + 0.5
        return fxy
    
    
    def limite_func_1(x, y):
        fxy = 2 * x + y - 5
        return fxy
    
    
    def limite_func_2(x, y):
        fxy = x**2 + y**2 - 9
        return fxy
    
    
    if __name__ == '__main__':
        a, b = sympy.symbols('x, y')
        eq_limit_solve()
    
    展开全文
  • 2、拉格朗日乘子法 求解支持向量的时候需要用到拉格朗日乘子法,此处先简单介绍一下拉格朗日乘子法的概念及作用。 拉格朗日乘子法的基本原理是通过引入拉格朗日乘子(λ)将原来的约束优化问题转化为无约束的方程组...
  • 字符矫正是光学字符识别(OCR)系统预处理过程中的重要步骤,针对传统的增广拉格朗日乘子法(ALM)求解字符矫正问题时收敛性和计算速度的不足,本文研究了并行分离的增广拉格朗日乘子法,综合考虑字符矫正模型的建立过程,...
  • 在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier)和KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求...
  • 1. 拉格朗日乘子法 这个问题我们之前涉及到过,在机器学习实战(基于scikit-learn和TensorFlow)学习心得(23)--逻辑回归 Logistic Regression的时候我们把带约束条件的方程通过拉格朗日乘子法合并为了一个方程. ...
  • 现在接着《拉格朗日乘子法(一):等式约束的拉格朗日乘子法》的思路考虑不等式约束g(x)≤0g(x)\leq0g(x)≤0,如下图所示,此时最优点x∗x^*x∗或在g(x)<0g(x)<0g(x)<0的区域中,或在边界g(x)=0g(x)=0g(x)=...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,742
精华内容 3,496
关键字:

拉格朗日乘子法

友情链接: 21_ganesh_sci.rar