精华内容
下载资源
问答
  • 拉格朗日乘数的意义
    2021-04-08 01:29:05

    在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数极值的方法。这种方法将一个有n 个变量与k 个约束条件最优化问题转换为一个有n + k个变量的方程组的极值问题,其变量不受任何约束。本文介绍拉格朗日乘数法(Lagrange multiplier)。

    概述

    • 我们擅长解决的是无约束极值求解问题,这类问题仅需对所有变量求偏导,使得所有偏导数为0,即可找到所有极值点和鞍点。我们解决带约束条件的问题时便会尝试将其转化为无约束优化问题

    • 事实上如果我们可以通过g得到某个变量的表示,例如 x 1 = h ( x 2 , . . . , x n ) x_1 = h(x_2, ..., x_n) x1=h(x2,...,xn),将该式带入 y y y即可抓换为无约束优化(初高中就是这么做的,所谓消元法是也),但有的时候我们无法得到这样的表示,便需要借助拉格朗日乘数法来避免消元法的困境。

    作为一种优化算法,拉格朗日乘数法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有 n n n个变量和 k 个 k个 k约束条件的约束优化问题转化为含有 ( n + k ) (n+k) n+k个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

    思想

    • 考虑二元函数 f ( x , y ) f(x,y) f(x,y),在约束 g ( x , y ) = c g(x,y)=c g(x,y)=c下的极值
    • 首先我们可以绘制出 f ( x , y ) f(x,y) f(x,y)的一层层等高线,当等高线与 g ( x , y ) = c g(x,y)=c g(x,y)=c相切时即可能是该问题的极值点

    拉格朗日乘数法示意图(转自知乎)

    拉格朗日乘数法

    单个等式约束

    考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x_1, x_2,...,x_n) y=f(x1,x2,...,xn),在等式约束 g ( x 1 , x 2 , . . . , x n ) = 0 g(x_1, x_2,...,x_n)=0 g(x1,x2,...,xn)=0 下的极值点求解问题

    • 在极值点,必有 y y y g g g法向量平行
    • y y y的法向量为:

    [ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n ] [\frac{{\partial y}}{{\partial {x_1}}},\frac{{\partial y}}{{\partial {x_2}}},...,\frac{{\partial y}}{{\partial {x_n}}}] [x1y,x2y,...,xny]

    • g g g的法向量为:

    [ ∂ g ∂ x 1 , ∂ g ∂ x 2 , . . . , ∂ g ∂ x n ] [\frac{{\partial g}}{{\partial {x_1}}},\frac{{\partial g}}{{\partial {x_2}}},...,\frac{{\partial g}}{{\partial {x_n}}}] [x1g,x2g,...,xng]

    • 二者平行,则存在常数 λ \lambda λ使得:

    [ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n ] + λ [ ∂ g ∂ x 1 , ∂ g ∂ x 2 , . . . , ∂ g ∂ x n ] = 0 [\frac{{\partial y}}{{\partial {x_1}}},\frac{{\partial y}}{{\partial {x_2}}},...,\frac{{\partial y}}{{\partial {x_n}}}] + \lambda [\frac{{\partial g}}{{\partial {x_1}}},\frac{{\partial g}}{{\partial {x_2}}},...,\frac{{\partial g}}{{\partial {x_n}}}] = 0 [x1y,x2y,...,xny]+λ[x1g,x2g,...,xng]=0

    • 即:

    ∂ y ∂ x i + λ ∂ g ∂ x i = 0 , 1 ≤ i ≤ n \frac{{\partial y}}{{\partial {x_i}}} + \lambda \frac{{\partial g}}{{\partial {x_i}}} = 0,1 \le i \le n xiy+λxig=0,1in

    • 这样我们就得到了 n n n个等式方程,再加上 g ( x 1 , x 2 , . . . , x n ) = 0 g(x_1, x_2,...,x_n)=0 g(x1,x2,...,xn)=0一起构成 n + 1 n+1 n+1个方程的方程组,未知数为 [ x 1 , x 2 , . . . , x n , λ ] [x_1,x_2,...,x_n,\lambda] [x1,x2,...,xn,λ] n + 1 n+1 n+1个,方程组的解即为所有极值点和鞍点的集合,每组解中的 λ \lambda λ即为两个平行法向量的倍数,该值在等式约束轨迹穿过 y y y的极值点时为0。

    多个等式约束

    原理与单个等式约束情况类似

    考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x_1, x_2,...,x_n) y=f(x1,x2,...,xn),在 m m m个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m g_i(x_1, x_2,...,x_n)=0, 1 \le i \le m gi(x1,x2,...,xn)=0,1im) 下的极值点求解问题

    • n n n维空间由 m m m个条件约束,会确定一个 n − m n-m nm维的曲面,我们讨论 y y y在这个曲面上的极值问题
    • 这个曲面由 m m m n − 1 n-1 n1维曲面交织而成,存在 m m m个法向量,这 m m m个法向量构成了 n − m n-m nm维曲面的法空间
    • 在问题的极值点, y y y的法向量必然落在 n − m n-m nm维曲面的法空间之内,也就是说 y y y的法向量可以由 n − m n-m nm维曲面的 m m m个法向量的线性组合表示:

    [ ∂ y ∂ x 1 , ∂ y ∂ x 2 , . . . , ∂ y ∂ x n ] + ∑ i = 1 m λ i [ ∂ g i ∂ x 1 , ∂ g i ∂ x 2 , . . . , ∂ g i ∂ x n ] = 0 [\frac{{\partial y}}{{\partial {x_1}}},\frac{{\partial y}}{{\partial {x_2}}},...,\frac{{\partial y}}{{\partial {x_n}}}] + \sum\limits_{i = 1}^m {{\lambda _i}[\frac{{\partial {g_i}}}{{\partial {x_1}}},\frac{{\partial {g_i}}}{{\partial {x_2}}},...,\frac{{\partial {g_i}}}{{\partial {x_n}}}]} = 0 [x1y,x2y,...,xny]+i=1mλi[x1gi,x2gi,...,xngi]=0

    • 即:

    ∂ y ∂ x j + ∑ i = 1 m λ i ∂ g i ∂ x j = 0 , 1 ≤ j ≤ n \frac{{\partial y}}{{\partial {x_j}}} + \sum\limits_{i = 1}^m {{\lambda _i}\frac{{\partial {g_i}}}{{\partial {x_j}}}} = 0,1 \le j \le n xjy+i=1mλixjgi=0,1jn

    • 此时我们得到了 n n n个等式方程,再加上 m m m个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m g_i(x_1, x_2,...,x_n)=0, 1 \le i \le m gi(x1,x2,...,xn)=0,1im) 一起构成 n + m n+m n+m个方程的方程组,未知数为 [ x 1 , x 2 , . . . , x n , λ 1 , λ 2 , . . . , λ m ] [x_1,x_2,...,x_n,\lambda_1,\lambda_2,...,\lambda_m] [x1,x2,...,xn,λ1,λ2,...,λm] n + m n+m n+m个,方程组的解即为所有极值点和鞍点的集合,每组解中的 λ i \lambda_i λi的值即为 y y y的法向量在 n − m n-m nm维曲面的法空间中的线性组合系数。

    单个不等式约束

    不等式约束其实是等式约束的扩展,等式约束表示一组确定的等高线(面),不等式约束则表示等高线(面)的某一边区域

    考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x_1, x_2,...,x_n) y=f(x1,x2,...,xn),在不等式约束 g ( x 1 , x 2 , . . . , x n ) ≤ 0 g(x_1, x_2,...,x_n) \le 0 g(x1,x2,...,xn)0 下的极值点求解问题

    • 若该问题有解,那么有两种情况
    1. 解在 g ( x 1 , x 2 , . . . , x n ) = 0 g(x_1, x_2,...,x_n) = 0 g(x1,x2,...,xn)=0 曲面上
    2. 解在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x_1, x_2,...,x_n) < 0 g(x1,x2,...,xn)<0 范围内
    • 当解在 g ( x 1 , x 2 , . . . , x n ) = 0 g(x_1, x_2,...,x_n) = 0 g(x1,x2,...,xn)=0 曲面上时,说明该不等式对 y y y取最小值的区域进行了限制,最终解落在了 y y y和约束相切的位置,那么此时二者的法向量方向必然相反(否则 y y y会在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x_1, x_2,...,x_n) < 0 g(x1,x2,...,xn)<0 范围内找到更小的值),按照等式情况构建方程:

    ∂ y ∂ x i + λ ∂ g ∂ x i = 0 , 1 ≤ i ≤ n \frac{{\partial y}}{{\partial {x_i}}} + \lambda \frac{{\partial g}}{{\partial {x_i}}} = 0,1 \le i \le n xiy+λxig=0,1in

    • 便有结论: λ ≥ 0 \lambda \ge 0 λ0

    • 当解在 g ( x 1 , x 2 , . . . , x n ) < 0 g(x_1, x_2,...,x_n) < 0 g(x1,x2,...,xn)<0 范围内时,事实上这个不等式没有对 y y y的求解起到约束作用,此时相当于 λ = 0 \lambda = 0 λ=0

    • 而且两种情况下分别有 g ( x 1 , x 2 , . . . , x n ) = 0 g(x_1, x_2,...,x_n) = 0 g(x1,x2,...,xn)=0 λ = 0 \lambda = 0 λ=0,也就是二者必有一方为0

    • 因此对于单个不等式约束的拉格朗日乘数法,仅需增加限制条件: λ ≥ 0 \lambda \ge 0 λ0 λ g ( x 1 , x 2 , . . . , x n ) = 0 \lambda g(x_1, x_2,...,x_n) = 0 λg(x1,x2,...,xn)=0

    多个不等式约束

    考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x_1, x_2,...,x_n) y=f(x1,x2,...,xn),在 m m m个不等式约束( g i ( x 1 , x 2 , . . . , x n ) ≤ 0 , 1 ≤ i ≤ m g_i(x_1, x_2,...,x_n)\le0, 1 \le i \le m gi(x1,x2,...,xn)0,1im) 下的极值点求解问题

    • 本质上与单个不等式约束相同,只是数量变多了
    • 此情况下需要在等式拉格朗日乘数法基础上增加条件:

    λ i ≥ 0 , 1 ≤ i ≤ m λ i g i = 0 , 1 ≤ i ≤ m \begin{aligned} \lambda_i &\ge 0,1 \le i \le m\\ \lambda_ig_i &= 0,1 \le i \le m \end{aligned} λiλigi0,1im=0,1im

    算法描述

    • 基于上述原理,提出了拉格朗日乘数法:
    1. 考虑 n n n元函数 y = f ( x 1 , x 2 , . . . , x n ) y=f(x_1, x_2,...,x_n) y=f(x1,x2,...,xn),在 m 1 m_1 m1个等式约束( g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m 1 g_i(x_1, x_2,...,x_n)=0, 1 \le i \le m_1 gi(x1,x2,...,xn)=0,1im1) 、 m 2 m_2 m2个不等式约束( h j ( x 1 , x 2 , . . . , x n ) ≤ 0 , 1 ≤ j ≤ m 2 h_j(x_1, x_2,...,x_n)\le0, 1 \le j \le m_2 hj(x1,x2,...,xn)0,1jm2) 下的极值点求解问题

    2. 加入常数 λ , μ \lambda,\mu λ,μ构造方程:

    z = f ( x 1 , x 2 , . . . , x n ) + ∑ i = 1 m 1 λ i g i ( x 1 , x 2 , . . . , x n ) + ∑ j = 1 m 2 μ j h j ( x 1 , x 2 , . . . , x n ) z = f({x_1},{x_2},...,{x_n}) + \sum\limits_{i = 1}^{{m_1}} {{\lambda _i}{g_i}({x_1},{x_2},...,{x_n})} + \sum\limits_{j = 1}^{{m_2}} {{\mu _j}{h_j}({x_1},{x_2},...,{x_n})} z=f(x1,x2,...,xn)+i=1m1λigi(x1,x2,...,xn)+j=1m2μjhj(x1,x2,...,xn)

    1. 对所有变量求偏导,并令导数为0:

    ∂ z ∂ x i = 0 ∂ y ∂ x k + ∑ i = 1 m 1 λ i ∂ g ∂ x k + ∑ j = 1 m 1 μ j ∂ h ∂ x k = 0 \begin{aligned} \frac{{\partial z}}{{\partial {x_i}}} &= 0\\ \frac{{\partial y}}{{\partial {x_k}}} + \sum\limits_{i = 1}^{{m_1}} {{\lambda _i}\frac{{\partial g}}{{\partial {x_k}}}} + \sum\limits_{j = 1}^{{m_1}} {{\mu _j}\frac{{\partial h}}{{\partial {x_k}}}} {\rm{ }} &= 0 \end{aligned} xizxky+i=1m1λixkg+j=1m1μjxkh=0=0

    其中: 1 ≤ k ≤ n 1 \le k \le n 1kn

    1. 将上述 n n n个方程与 m 1 m_1 m1个等式约束方程 g i ( x 1 , x 2 , . . . , x n ) = 0 , 1 ≤ i ≤ m 1 g_i(x_1, x_2,...,x_n)=0, 1 \le i \le m_1 gi(x1,x2,...,xn)=0,1im1 联立
    2. 将上述 n + m 1 n+m_1 n+m1个方程与 μ j h j = 0 , 1 ≤ j ≤ m 2 \mu_j h_j=0, 1 \le j \le m_2 μjhj=0,1jm2联立,得到 n + m 1 + m 2 n+m_1+m_2 n+m1+m2个方程
    3. 加上限制条件 μ j ≥ 0 \mu_j \ge 0 μj0 h j ≤ 0 h_j \le 0 hj0 , 1 ≤ j ≤ m 2 , 1 \le j \le m_2 ,1jm2
    4. 在限制条件下解 n + m 1 + m 2 n+m_1+m_2 n+m1+m2元方程即可得到极值点与鞍点集合
    5. 从所有解中筛选出极值点

    KKT条件

    • 上述 n + m 1 + m 2 n+m_1+m_2 n+m1+m2元方程与限制条件即为KKT条件
    • KKT条件是拉格朗日函数取极值时的必要条件

    { ∇ f + ∑ i m 1 λ i ∇ g i + ∑ j m 2 μ j ∇ h j = 0 g i = 0 , h j ≤ 0 , μ j ≥ 0 , μ j h j = 0 \left\{\begin{array}{l} \nabla f+\sum_{i}^{m_1} \lambda_{i} \nabla g_{i}+\sum_{j}^{m_2} \mu_{j} \nabla h_{j}=0 \\ g_{i}=0, \\ h_{j} \leq 0, \\ \mu_{j} \geq 0, \\ \mu_{j} h_{j}=0\\ \end{array}\right. f+im1λigi+jm2μjhj=0gi=0,hj0,μj0,μjhj=0

    其中 i ∈ { 1 , 2 , ⋯   , m 1 } i \in \{ 1,2, \cdots, m_1\} i{1,2,,m1} j ∈ { 1 , 2 , ⋯   , m 2 } j \in \{ 1,2, \cdots, m_2\} j{1,2,,m2}

    • 总结一下所有条件的含义:
    内容含义
    ∇ f + ∑ i m 1 λ i ∇ g i + ∑ j m 2 μ j ∇ h j = 0 \nabla f+\sum_{i}^{m_1} \lambda_{i} \nabla g_{i}+\sum_{j}^{m_2} \mu_{j} \nabla h_{j}=0 f+im1λigi+jm2μjhj=0求解极值需要在各个自变量方向上导数为0
    g i = 0 g_{i}=0 gi=0等式约束
    h j ≤ 0 h_{j} \le 0 hj0不等式约束
    μ j ≥ 0 \mu_{j} \geq 0 μj0不等式约束时的两种情况:
    1. 不等式约束无效( μ j = 0 \mu_{j} = 0 μj=0)
    2. 不等式分界面法向量与原函数法向量方向相反( μ j > 0 \mu_{j} > 0 μj>0)
    μ j h j = 0 \mu_{j} h_{j}=0 μjhj=0不等式约束时的两种情况:
    1. 不等式约束无效,极值点在 h j < 0 h_{j} < 0 hj<0范围内 ( μ j = 0 \mu_{j} = 0 μj=0)
    2. 不等式约束有效,极值点在 h j = 0 h_{j} = 0 hj=0曲面上( h j = 0 h_{j} = 0 hj=0)

    参考资料

    • https://baike.baidu.com/item/%E6%8B%89%E6%A0%BC%E6%9C%97%E6%97%A5%E4%B9%98%E6%95%B0%E6%B3%95/8550443?fr=aladdin

    • https://www.zhihu.com/question/38586401

    • https://www.zhihu.com/question/359162625

    • https://www.zhihu.com/question/23311674/answer/468804362

    • https://blog.csdn.net/johnnyconstantine/article/details/46335763

    更多相关内容
  • 拉格朗日乘数法详解

    千次阅读 2021-09-22 10:42:25
    拉格朗日乘子法 写这篇文章的动机主要是最近正在学习机器学习的课程,学到逻辑回归的时候发现使用了拉格朗日乘子法,网上也很多文章讲拉格朗日乘子法的,因此这篇文章只是记录学习的过程,希望能较为全面地展示...

    拉格朗日乘子法

    写这篇文章的动机主要是最近正在学习机器学习的课程,学到逻辑回归的时候发现使用了拉格朗日乘子法,网上也很多文章讲拉格朗日乘子法的,因此这篇文章只是记录学习的过程,希望能较为全面地展示拉格朗日乘子法的各个方面。如果文章有错误请大家指出。也希望接下来能在学习过程中记录下机器学习中的一些知识点。

    基本思想

    拉格朗日乘子法想要解决的问题事实上是比较常出现的,也就是对于一个式子来说,大多数情况下我们是不可能无限制求其理想情况下的最优值的(这里的最优值可能是最大值也可能是最小值),总是存在一些约束生成了一部分可行解域,从机器学习上来说,我们的可行解域就被限制住了。但是很显然我们如果将这个视为约束条件下的最优化,直接求解起来事实上是有一定困难的,我们更希望求解的是无约束的优化问题。

    作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。

    在转化过程中,拉格朗日乘子法通过引入k个拉格朗日乘子,将n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。举个例子来说,会有如下转化:
    m i n x , y , z f ( x , y , z ) s . t .   g ( x , y , z ) = 0 min_{x,y,z} f(x,y,z)\\ s.t. \ g(x,y,z)=0 minx,y,zf(x,y,z)s.t. g(x,y,z)=0
    求解上述最优化等价于求如下无约束优化:
    m i n x , y , z , λ f ( x , y , z ) + λ g ( x , y , z ) min_{x,y,z,\lambda}f(x,y,z)+\lambda g(x,y,z) minx,y,z,λf(x,y,z)+λg(x,y,z)
    接下来对于约束条件只有等式以及约束条件中出现不等式约束的情况分别讨论。

    等式约束

    等式约束是拉格朗日乘子法中最简单的一种形式,为了方便画图辅助理解,假设我们有如下优化式子:
    m a x x , y f ( x , y ) s . t .   g ( x , y ) = c max_{x,y} f(x,y)\\ s.t. \ g(x,y)=c maxx,yf(x,y)s.t. g(x,y)=c
    我们最后会将其转化为无约束优化:
    m a x x , y , λ f ( x , y ) + λ ( g ( x , y ) − c ) (1) max_{x,y,\lambda}f(x,y)+\lambda (g(x,y)-c) \tag{1} maxx,y,λf(x,y)+λ(g(x,y)c)(1)
    这里的 λ \lambda λ​​是没有约束的,这是和不等式约束一个很大的区别,因此在这里进行解释为什么这样能够求出最优值点。这是在一个二维平面上的优化式子,因此可以做出如下图辅助理解:

    img

    需要注意的是上图中蓝色的虚线表示待优化原函数的等高线图,也就是说在一条蓝色虚线上的点 f ( x , y ) f(x,y) f(x,y)​都是相等的,而绿色的实线其实也可以理解为 g ( x , y ) g(x,y) g(x,y)​的等高线图,只不过由于约束,可行解只能落在这一条绿色的实线上。

    如果结合图像来理解,对于 f ( x , y ) f(x,y) f(x,y)来说,我们不妨假设其越往内的等高线表示其值越大,也就是说针对图中的值来说 d 2 > d 1 d_2>d_1 d2>d1​​,由于在某一点的梯度指向最快的上升方向,因此对图上的函数来说梯度方向都是向内的。而对于绿色的线来说由于没有前置条件,所以我们无法判断其梯度的具体方向,结合图来说,图中的绿色箭头表示约束条件函数的梯度方向,但是这个方向如果取反向事实上也是可以的。

    我们猜想最优值的点就在图中的切点位置,更具体一点也就是在这一点原函数 f ( x , y ) f(x,y) f(x,y)​的梯度方向和 g ( x , y ) g(x,y) g(x,y)​的梯度方向相同或相反。如果不是用严格的数学定理来证明,而是从几何意义来说, f ( x , y ) f(x,y) f(x,y)​​当然希望沿着梯度方向走的越多越好,而且使用朴素的思想来说,只要在梯度方向还能运动,就说明还没到达最优值点。

    而我们的可行域固定在了 g ( x , y ) = c g(x,y)=c g(x,y)=c​这一条线上,不妨假设我们在这条线上移动点来求得最优值,那么如果当前点处 g ( x , y ) = c g(x,y)=c g(x,y)=c​的梯度和与当前节点相交的 f ( x , y ) = d f(x,y)=d f(x,y)=d​的梯度方向并不平行,那么就表示如果继续移动这个点,总存在 f ( x , y ) = d f(x,y)=d f(x,y)=d​的梯度方向的一个分量使得 f ( x , y ) f(x,y) f(x,y)​​的值更大,也就不符合最优值点的定义,由此可见最优值点处约束函数与待优化函数的梯度必是平行的,转化为数学的语言来说也就是:
    ∇ f ( x , y ) + λ ∇ g ( x , y ) = 0 \nabla f(x,y)+\lambda\nabla g(x,y)=0 f(x,y)+λg(x,y)=0
    我们发现这不就是公式(1)的梯度为0的点吗?由此可见只要求出我们转化后的梯度为0的点其实就等价于求出了最优值点。

    那么看到这里可能会产生一个疑惑,上述例子中给出的是求 f ( x , y ) f(x,y) f(x,y)的最大值点,那么我们求出来的梯度为0的点会不会是最小值点呢?也就是说求的极值不符合要求呢?同样是从上图来看,如果在该约束下还能求出 f ( x , y ) f(x,y) f(x,y)的最小值,那么最小值点处也必是满足 ∇ f ( x , y ) + λ ∇ g ( x , y ) = 0 \nabla f(x,y)+\lambda\nabla g(x,y)=0 f(x,y)+λg(x,y)=0​​​,由此可见拉格朗日乘子法只是极值点的一个必要条件,但是保证不了求出的是不是我们要求的那一个极值点(也就是说不能保证我们目标是max,求出的会不会是min),因此求出的结果还需要自行根据实际情况判断。

    不等式约束、KKT条件

    在真实情况下约束条件大多是有不等式约束也有等式约束,因此这一小节主要介绍不等式约束条件下的拉格朗日乘子法以及这一部分很重要的一个KKT条件,这一条件在SVM的对偶问题转换中起到重要作用。

    这里我们先单独考虑只有不等式的约束条件,如果约束中还有考虑约束条件下的优化如下:
    m i n x , y f ( x , y ) s . t .   g ( x , y ) < 0 min_{x,y} f(x,y)\\ s.t. \ g(x,y)<0 minx,yf(x,y)s.t. g(x,y)<0
    先给出结论,这一优化问题转化为无约束优化如下:
    m i n x , y , λ f ( x , y ) + α g ( x , y )       s . t .     α > = 0 (2) min_{x,y,\lambda}f(x,y)+\alpha g(x,y) \tag{2}\\ \ \ \ \ \ s.t.\ \ \ \alpha>=0 minx,y,λf(x,y)+αg(x,y)     s.t.   α>=0(2)
    其中很重要的一点就是 α > = 0 \alpha>=0 α>=0这一约束,这和等式约束是很不一样的。接下来同样结合图来解释。

    对于不等式约束,我们可以给出两种情况,第一种情况就是不等式约束给出的可行解域中包含了f(x,y)的最值,那么这种情况对应的图示如下:

    在这种情况下也就是说不等式约束事实上是不起作用的,所以求解带不等式约束的最优化问题等价于求原优化问题,所以等价于求公式(2)中 α = 0 \alpha=0 α=0的情况。

    更需要关注的是可行解域不包含f(x,y)的最值的情况,可用如下图表示:

    我们不妨结合图来看,首先给出观点,我们要求的最小值点图中的切点位置,在这一点处g(x,y)的梯度和f(x,y)的梯度是反向的,而且这个反向是必须的,这一点和等式约束中的可以是相同方向不同。接下来从几何意义方面解释为什么必须是反向的。

    从图上的情况来看,由于我们要求最小值,当然希望等高线缩得越靠近最优值点越好,而且需要注意的是由于约束条件确定的可行解域(图中的绿色部分)不包含理想情况下的最优值点,因此我们的最值将会在可行解域的边界上取到。不妨假设我们沿着边界移动来寻找最优值点,那么解释和上面等式约束一样,可以比较容易得出在最优值点处一定是两个梯度平行的,接下来解释为什么两个梯度一定是反向的。

    结合图中来说,我们观察切点,如果这个点处两个梯度是相同方向的关系,也就是说图中的切点处的绿色箭头和蓝色箭头同向,那就是说在当前切点处沿着梯度的反方向(也就是当前的绿色箭头方向)运动一点得到的g(x,y)是比当前切点处小的,而当前切点处的g(x,y)=0,那不就是说我们可以继续往理想情况的最优值点靠近一点吗?那也就意味着当前点不是最优值点,和假设不符。

    从几何角度解释这一点我认为是更容易理解的,因此不给出详细的数学证明。最后给出一个KKT条件,这一条件是强对偶性的充要条件,后续博客中将会详细介绍强对偶性和KKT条件的关系,这里只给出KKT的形式:

    假设有一个优化问题如下:
    m i n x f ( x ) s . t .   g i ( x ) = 0      i = 1 , 2 , . . p h j ( x ) ≤ 0           j = 1 , 2 , . . . q min_{x}f(x) \\s.t.\ g_i(x)=0\ \ \ \ i=1,2,..p \\h_j(x)\le0\ \ \ \ \ \ \ \ \ j=1,2,...q minxf(x)s.t. gi(x)=0    i=1,2,..phj(x)0         j=1,2,...q
    则可以转化为拉格朗日函数如下:
    L ( x , λ , μ ) = f ( x ) + ∑ i = 1 q λ i g i ( x ) + ∑ j = 1 p α j h j ( x ) L(x,\lambda,\mu)=f(x)+\sum_{i=1}^{q}\lambda_ig_i(x)+\sum_{j=1}^{p}\alpha_jh_j(x) L(x,λ,μ)=f(x)+i=1qλigi(x)+j=1pαjhj(x)
    则KKT条件为:
    ∇ L = 0 g i ( x ) = 0 , i = 1 , 2 , . . p h j ( x ) ≤ 0 , j = 1 , 2.. q α j ≥ 0 α j h j ( x ) = 0 , j = 1 , 2 , . . p \nabla L=0\\ g_i(x)=0,i=1,2,..p\\ h_j(x)\le0,j=1,2..q\\ \alpha_j\ge0\\ \alpha_j h_j(x)=0,j=1,2,..p L=0gi(x)=0,i=1,2,..phj(x)0,j=1,2..qαj0αjhj(x)=0,j=1,2,..p

    展开全文
  • 拉格朗日乘子法几何意义

    千次阅读 2021-04-30 10:44:01
    为什么出现拉格朗日乘子法? 最短路径问题 从几何意义中获得灵感: 从数学公式中获得灵感 推广到高维空间 一个最短路径问题 假设你在M点,需要先到河边(上图右侧曲线 )再回到C点,如何规划路线最短? ...

    为什么出现拉格朗日乘子法?

    • 最短路径问题
    • 从几何意义中获得灵感:
    • 从数学公式中获得灵感
    • 推广到高维空间

    一个最短路径问题

    假设你在M点,需要先到河边(上图右侧曲线 )再回到C点,如何规划路线最短?

     

    假设:
    河流曲线满足方程 g(x,y) = 0 (例如 如果它是一个圆:f(x,y)=x^{2}+y^{2}-r^{2})

    用P表示河边上的任意P(x,y)点,
    用d(M,P)表示M,P之间距离,
    那么问题可以描述为:minf(P)=d(M,P)+d(P,C),约束g(P)=0;

    如何求解问题?

    1. 从几何意义中获得灵感:

    首先,f(P)是一个标量(只有大小没有方向),那么在上图的二维空间中必然存在了一个标量场f(P),即对于每一个点P都对应着一个f(P)值,它代表经过该点的路径总和是多少。
    如果我们画出它的等值线(场线),就会发现它呈椭圆向外辐射:


    显然,f(P)的等值线与河边曲线的交点P即为我们想求的点。

     

    那么问题来了: 这样的点满足何种性质? (如果没有性质也就无法列出关系式进行求解,但是这么特殊的点极有可能存在良好某种特性)

     

    最直观的性质: 等值线(椭圆)在P点的法向量n与河边曲线的法向量m平行:

    n=\lambda m

    而在多元微积分中,一个函数h在某一点P的梯度是点P所在等值线(二维)或等值面(三维)的法向量,即n=\Delta h(P),所以对于f,g

    n=\lambda m\Rightarrow \Delta f(P)=\lambda \Delta g(P)\Rightarrow \binom{fx}{fy}=\lambda \binom{gx}{gy}\Rightarrow fx=\lambda gx

    即:fy=\lambda gy

    即由相交点的性质我们得到了2个关系式(因为是二维平面,对于三维则可以得到三个关系式,以此类推),

    再加上我们的约束条件:g(P)=g(x,y)=0

    一共3个关系式,由线性代数中知识可知 3个关系式,3个未知量(x,y,\lambda)极有可能有唯一解,当然也不排除会出现多个解甚至无穷多解 (例如 下图 河边是一条直线,且M,C就在河边时)。

    2. 从数学公式中获得灵感

    仍人是问题:

    3. 推广到高维空间
    以上我们一直在讨论 二维的情形,下面让我们看看这个问题的高维情况: 以几何观点为例:

    假设约束条件变成

    学习总结:

    若函数 f(x,y,z) 的变量受约束 g(x,y,z)=0限制, 函数的极值可以用下面Lagrange乘子法求出.

     

     

    参考地址:https://www.zhihu.com/question/38586401

    http://www.slimy.com/~steuard/teaching/tutorials/Lagrange.html

     

    展开全文
  • 拉格朗日乘数法 —— 通俗理解

    万次阅读 多人点赞 2019-02-15 17:03:38
    拉格朗日乘数法(Lagrange Multiplier Method)在数学最优问题中,是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。记得以前大学高数、数模等课程多次提到过,在求解最有问题中很有用处,最近重温了...

      拉格朗日乘数法(Lagrange Multiplier Method)在数学最优问题中,是一种寻找变量受一个或多个条件所限制的多元函数极值的方法。记得以前大学高数、数模等课程多次提到过,在求解最有问题中很有用处,最近重温了下拉格朗日乘数法的思想:

      拉格朗日乘数法将一个有n个变量与k个约束条件最优化问题转换为一个有n + k个变量的方程组的极值问题,其变量不受任何约束。这种方法引入了一种新的标量未知数,即拉格朗日乘数:约束方程的梯度(gradient)的线性组合里每个向量的系数。此方法的证明牵涉到偏微分,全微分或链法,从而找到能让设出的隐函数的微分为零的未知数的值。

    1. 拉格朗日乘数法的基本思想

      作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题。拉格朗日乘子背后的数学意义是其为约束方程梯度线性组合中每个向量的系数。

           如何将一个含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束优化问题?拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导对应了n个方程,然后加上k个约束条件(对应k个拉格朗日乘子)一起构成包含了(n+k)变量的(n+k)个方程的方程组问题,这样就能根据求方程组的方法对其进行求解。

      解决的问题模型为约束优化问题:

      min/max a function f(x,y,z), where x,y,z are not independent and g(x,y,z)=0.

      即:min/max f(x,y,z)

        s.t. g(x,y,z)=0

     


    2. 拉格朗日乘数法的数学实例

      首先,我们先以麻省理工学院数学课程的一个实例来作为介绍拉格朗日乘数法的引子。

    【麻省理工学院数学课程实例】求双曲线xy=3上离原点最近的点。

      解:首先,我们根据问题的描述来提炼出问题对应的数学模型,即:

      min f(x,y)=x2+y2(两点之间的欧氏距离应该还要进行开方,这里进行了简化,去掉了开方)

      s.t. xy=3.

      根据上式我们可以知道这是一个典型的约束优化问题,其实我们在解这个问题时最简单的解法就是通过约束条件将其中的一个变量用另外一个变量进行替换,然后代入优化的函数就可以求出极值。我们在这里为了引出拉格朗日乘数法,所以我们采用拉格朗日乘数法的思想进行求解。

      我们将x2+y2=c的曲线族画出来,如下图所示,当曲线族中的圆与xy=3曲线进行相切时,切点到原点的距离最短。也就是说,当f(x,y)=c的等高线和双曲线g(x,y)相切时,我们可以得到上述优化问题的一个极值(注意:如果不进一步计算,在这里我们并不知道是极大值还是极小值)。

      现在原问题可以转化为求当f(x,y)和g(x,y)相切时,x,y的值是多少?

      如果两个曲线相切,那么它们的切线相同,即法向量是相互平行的,▽f//▽g.

      由▽f//▽g可以得到,▽f=λ*▽g。

      这时,我们将原有的约束优化问题转化为了一种对偶的无约束的优化问题,如下所示:

    原问题:

    对偶问题:

    min f(x,y)=x2+y2

    s.t.  xy=3

    由▽f=λ*▽g得:

      fx=λ*gx,

      fy=λ*gy,

      xy=3.

    约束优化问题

    无约束方程组问题

      通过求解右边的方程组我们可以获取原问题的解,即

      2x=λ*y,2y=λ*x,xy=3

      通过求解以上方程组可得:λ=2或者是-2;当λ=2时,(x,y)=(\sqrt{3},\sqrt{3})或者(-\sqrt{3}, -\sqrt{3}),而当λ=-2时,无解。所以原问题的解为(x,y)=(\sqrt{3}, \sqrt{3})或者(-\sqrt{3}, -\sqrt{3})。

      通过举上述这个简单的例子就是为了体会拉格朗日乘数法的思想,即通过引入拉格朗日乘子(λ)将原来的约束优化问题转化为无约束的方程组问题。

     


    3. 拉格朗日乘数法的基本形态

       求函数在满足下的条件极值,可以转化为函数的无条件极值问题。

      我们可以画图来辅助思考:

      绿线标出的是约束g(x,y)=c的点的轨迹。蓝线是f(x,y)的等高线。箭头表示斜率,和等高线的法线平行。

      从图上可以直观地看到在最优解处,f和g的斜率平行。

    \nabla[f(x,y)+\lambda (g(x,y)-c)]=0, \lambda \neq 0

      一旦求出λ的值,将其套入下式,易求在无约束极值和极值所对应的点。

    F(x,y)=f(x,y)+\lambda (g(x,y)-c)

      新方程F(x,y)在达到极值时与f(x,y)相等,因为F(x,y)达到极值时g(x,y)−c总等于零。

      上述式子取得极小值时其导数为0,即\nabla f(x)+\nabla\sum \lambda_{i} g_{i}(x)=0,也就是说f(x)和g(x)的梯度共线。

    题目1:

      给定椭球

         

      求这个椭球的内接长方体的最大体积。这个问题实际上就是条件极值问题,即在条件   

        

      下,求的最大值。

      当然这个问题实际可以先根据条件消去z,然后带入转化为无条件极值问题来处理。但是有时候这样做很困难,甚至是做不到的,这时候就需要用拉格朗日乘数法了。通过拉格朗日乘数法将问题转化为

         

      对求偏导得到

         

      联立前面三个方程得到,带入第四个方程解之

          

      带入解得最大体积为

          

      拉格朗日乘数法对一般多元函数在多个附加条件下的条件极值问题也适用。

    题目2:

      题目:求离散分布的最大熵。

      分析:因为离散分布的熵表示如下

         

         而约束条件为

         

         要求函数 f 的最大值,根据拉格朗日乘数法,设

         

         对所有的pk求偏导数,得到

         

         计算出这 n 个等式的微分,得到

         

         这说明所有的pk都相等,最终解得:

         

         因此,使用均匀分布可得到最大熵的值。

     


    4. 拉格朗日乘数法与KKT条件

      我们上述讨论的问题均为等式约束优化问题,但等式约束并不足以描述人们面临的问题,不等式约束比等式约束更为常见,大部分实际问题的约束都是不超过多少时间,不超过多少人力,不超过多少成本等等。所以有几个科学家拓展了拉格朗日乘数法,增加了KKT条件之后便可以用拉格朗日乘数法来求解不等式约束的优化问题了。

      首先,我们先介绍一下什么是KKT条件。

      KKT条件是指在满足一些有规则的条件下, 一个非线性规划(Nonlinear Programming)问题能有最优化解法的一个必要和充分条件. 这是一个广义化拉格朗日乘数的成果. 一般地, 一个最优化数学模型的列标准形式参考开头的式子, 所谓 Karush-Kuhn-Tucker 最优化条件,就是指上式的最优点x∗必须满足下面的条件:

      1). 约束条件满足gi(x∗)≤0,i=1,2,…,p, 以及,hj(x∗)=0,j=1,2,…,q

      2). ∇f(x∗)+∑i=1μi∇gi(x∗)+∑j=1λj∇hj(x∗)=0, 其中∇为梯度算子;

      3). λj≠0且不等式约束条件满足μi≥0,μigi(x∗)=0,i=1,2,…,p。

      KKT条件第一项是说最优点x∗必须满足所有等式及不等式限制条件, 也就是说最优点必须是一个可行解, 这一点自然是毋庸置疑的. 第二项表明在最优点x∗, ∇f必须是∇gi和∇hj的线性組合, μi和λj都叫作拉格朗日乘子. 所不同的是不等式限制条件有方向性, 所以每一个μi都必须大于或等于零, 而等式限制条件没有方向性,所以λj没有符号的限制, 其符号要视等式限制条件的写法而定.

      为了更容易理解,我们先举一个例子来说明一下KKT条件的由来。

      let L(x,μ)=f(x)+∑k=1μkgk(x),其中μk≥0,gk(x)≤0

      ∵μk≥0 gk(x)≤0  =>  μg(x)≤0

      ∴maxμL(x,μ)=f(x)                    (2)

      ∴minxf(x)=minxmaxμL(x,μ)     (3)

      maxμminxL(x,μ)=maxμ[minxf(x)+minxμg(x)]=maxμminxf(x)+maxμminxμg(x)=minxf(x)+maxμminxμg(x)

      又∵μk≥0, gk(x)≤0

      

      ∴maxμminxμg(x)=0, 此时μ=0 or g(x)=0.

      ∴maxμminxL(x,μ)=minxf(x)+maxμminxμg(x)=minxf(x)      (4)

      此时μ=0 or g(x)=0.

      联合(3),(4)我们得到minxmaxμL(x,μ)=maxμminxL(x,μ), 亦即

       

      minxmaxμL(x,μ)=maxμminxL(x,μ)=minxf(x)

      我们把maxμminxL(x,μ)称为原问题minxmaxμL(x,μ)的对偶问题,上式表明当满足一定条件时原问题、对偶的解、以及minxf(x)是相同的,且在最优解x∗处μ=0 or g(x∗)=0。把x∗代入(2)得maxμL(x∗,μ)=f(x∗),由(4)得maxμminxL(x,μ)=f(x∗),所以L(x∗,μ)=minxL(x,μ),这说明x∗也是L(x,μ)的极值点,即

      

      最后总结一下:

      

      KKT条件是拉格朗日乘子法的泛化,如果我们把等式约束和不等式约束一并纳入进来则表现为:

      

      注:x,λ,μ都是向量。

      

      表明f(x)在极值点x∗处的梯度是各个hi(x∗)和gk(x∗)梯度的线性组合。


    PS:本文转自Poll的笔记[Math & Algorithm] 拉格朗日乘数法,并更正原文几点小错误,算是对拉格朗日乘数法比较通俗的解释

    展开全文
  • 拉格朗日乘数法基础

    万次阅读 2019-02-19 10:17:33
    背景 线性可分 SVM 的目标函数...本文将摘录高等数学下册中拉格朗日乘数法的数学知识,08年学的高等数学下册,十多年了早还给老师了,只是还保留着当年的书本,这次春节回家把两本高数书带来了,当作AI学习的参考资...
  • 最优化方法:拉格朗日乘数

    千次阅读 2020-12-24 06:50:20
    解决约束优化问题——拉格朗日乘数法拉格朗日乘数法(Lagrange Multiplier Method)应用广泛,可以学习麻省理工学院的在线数学课程。拉格朗日乘数法的基本思想作为一种优化算法,拉格朗日乘子法主要用于解决约束优化...
  • 我们研究了包括f(T)引力在内的远距平行理论的Lagrange乘数公式,其中连接没有先验设置为零,并将其与纯框架理论进行了比较。 从动力学方程具有相同的内容的意义上来说,我们明确表明这两个公式是等效的。 一个结果...
  • 拉格朗日乘数法整理

    2020-07-24 20:22:54
    拉格朗日乘数法 一种不直接依赖消元法而求解条件极值问题的有效方法 二元函数入手 我们从 f,φf, \varphif,φ皆为二元函数这一简单情况人手. 欲求函数 z=f(x,y) z=f(x, y) z=f(x,y) 的极值,其中(x,y)( x,y)(x,y)受...
  • 拉格朗日乘数法及KKT条件-通俗理解

    千次阅读 2020-12-07 16:10:26
    1.拉格朗日乘数法的基本思想 在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的...
  • 拉格朗日乘数法(Lagrange Multiplier Method)基本思想 作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有...
  • L ( x , y , λ ) L(x,y,\lambda) L(x,y,λ)称为拉格朗日函数, λ \lambda λ称为拉格朗日乘数。 例 求 z = f ( x , y ) = 8 x 2 − 2 y z=f(x,y)=8x^2-2y z=f(x,y)=8x2−2y在 x 2 + y 2 = 1 x^2+y^2=1 x2+y2=1...
  • 条件极值问题、拉格朗日乘数

    千次阅读 2020-12-24 12:33:54
    最近有一道网红题长这样: 求 这看上去不是很像高中题,倒像是联赛的送分题,或者是拉格朗日乘数法的练习题。在这里,我就给出一个有拉乘味道的解法:取等条件看了文章的标题,就能够知道上面 的系数是怎么来的了。...
  • [Math & Algorithm] 拉格朗日乘数

    千次阅读 2019-05-27 19:57:54
    阅读目录 1. 拉格朗日乘数法的基本思想 ... 拉格朗日乘数法(Lagrange Multiplier Method)之前听数学老师授课的时候就是一知半解,现在越发感觉拉格朗日乘数法应用的广泛性,所以特意抽时间学...
  • 回到上面的题目,通过拉格朗日乘数法将问题转化为: F(x,y,z,λ)=f(x,y,z)+λφ(x,y,z)=8xyz+λ(x2a2+y2b2+z2c2−1)F(x,y,z,\lambda)=f(x,y,z)+\lambda\varphi (x,y,z)=8xyz+\lambda(\frac{x^2}{a^2}+\frac{y^2}{b^...
  • 最优化方法:拉格朗日乘数法 2016年08月18日 14:34:38-柚子皮-阅读数 31809更多 分类专栏:机器学习MachineLearningMath 版权声明:本文为博主原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上...
  • 约束规划——拉格朗日乘数

    千次阅读 2020-04-15 20:12:49
    拉格朗日乘数拉格朗日乘数法的基本思想 拉格朗日乘数法(Lagrange Multiplier Method)是一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束...
  • 机器学习之拉格朗日乘数

    千次阅读 2016-11-19 18:39:08
    在数学最优问题中,拉格朗日乘数法(以数学家约瑟夫·路易斯·拉格朗日命名)是一种寻找变量受一个或多个条件所限制的多元函数的极值的方法。这种方法将一个有n 个变量与k 个约束条件的最优化问题转换为一个有n + k...
  • 拉格朗日乘数法(Lagrange Multiplier Method)基本思想 作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的...拉格朗日乘数法从数学意义入手,通过引入拉格朗日乘子建立极值条件,对n个变量分别求偏导
  • 作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个...拉格朗日乘数法从数学意义入手,通过引入拉格
  • 非线性优化-拉格朗日乘数法(8)

    千次阅读 2018-09-22 19:21:04
    1. 拉格朗日乘数法的基本思想  作为一种优化算法,拉格朗日乘子法主要用于解决约束优化问题,它的基本思想就是通过引入拉格朗日乘子来将含有n个变量和k个约束条件的约束优化问题转化为含有(n+k)个变量的无约束...
  • - 有约束最优化问题:拉格朗日乘数法。 一、梯度下降法 1、算法简介   梯度下降法是最早最简单,也是最为常用的最优化方法。梯度下降法实现简单,当目标函数是凸函数时,梯度下降法的解是全局解。一般情况下,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,059
精华内容 423
关键字:

拉格朗日乘数的意义