精华内容
下载资源
问答
  • 拉格朗日乘子法和对偶问题
    千次阅读
    2017-12-20 17:25:40

    拉格朗日乘子法与对偶问题

    1、原始问题

    假设 f(x),gi(x),hj(x) 是定义在 Rn 上的连续可微函数,考虑约束最优化问题:

    minf(x)

    s.t.gi(x)0i=1,2,n

    s.t.hj(x)=0i=1,2,m

    称为约束最优化问题的原始问题。

    引入广义拉格朗日函数:

    L(x,λ,β)=f(x)+ni=1λigi(x)+mj=1βjhj(x)

    要求 λi0 , λi,βj 是拉格朗日乘子。

    原问题就变成了:

    minxL(x,λ,β)

    2、原问题分析

    在上面的问题中,求解最优值对应的 x , 还需要知道λi,βj

    现在,把 L(x,λ,β) 看作是关于 λ,β 的函数,要求其最大值,即

    maxλ0,βL(x,λ,β)

    在此优化过程中将 x 看作常量,确定了λi,βj 后,就得到 L 函数的最大值,最后只需要求关于x的有关函数最优解就行。为什么拉格朗日函数能这样求解后等价于原问题呢?令θp(x)=maxλ0,βL(x,λ,β), 因为对于 maxλ0,βL(x,λ,β) 这个问题,当 x 违反了原始问题的约束,那么gi(x)0hj(x)0,那么 λi,βj 很容易取值使 maxλ0,βL(x,λ,β) 这个问题就趋于无穷大,所以考虑 x 满足原始的约束,要使得 L(x,λ,β)取最大则 λigi(x)=0 hi(x)=0 , 那么 θp(x)=maxλ0,βL(x,λ,β)=f(x) .

    x 满足约束下,minxθp(x)=minxf(x), minxθp(x) 可以代表原始问题,定义 x ,P分别为 minxθp(x) 问题的最优解、最优值。

    3、对偶问题

    如果这个拉格朗日函数能很容易求解?直接求导就能得到最优解,但是这个问题不容易求解时,就需要找到拉格朗日函数的对偶问题就行求解。为什么这样可行?接下来进行解释:

    对偶问题形式:

    θd(λ,β)=minxL(x,λ,β) , 注意这里的角标变化(和上面的进行对比),然后

    maxλ,βθd(λ,β)=maxλ,βminxL(x,λ,β)

    这就是原始问题的对偶问题,再和原问题 minxθp(x)=minxmaxλ0,βL(x,λ,β) 进行对比。

    这里就可以发现原始问题和对偶问题只不过是先优化 x , 还是λ,β的问题。

    定义 (λ,β) ,D分别为对偶问题 maxλ,βθd(λ,β) 的最优解、最优值。

    4、原始问题和对偶问题的关系:

    θd(λ,β)=minxL(x,λ,β)L(x,λ,β)maxλ0,βL(x,λ,β)=θp(x)

    那么D≤P。也就是说原始问题的最优值不小于对偶问题的最优值。

    5、强对偶性

    强对偶性,就是说D=P,也就是说原始问题的最优值等于对偶问题的最优值。利用强对偶性,可以通过求解对偶问题的最优解从而知道原始问题的最优解,一般认为凸规划(不是所有)具有强对偶性。

    6、强对偶性存在的KKT条件

    那么对应第1点当中的原始问题,具有强对偶性,即 D=P=L(x,λ,β)

    那么 x,(λ,β) 分别是原始问题和对偶问题的最优解的充要条件 x,λ,β 满足KKT条件:

    Lx(x,λ,β)=0 (1)

    Lλ(x,λ,β)=0 (2)

    Lβ(x,λ,β)=0 (3)

    λigi(x)=0 (4)

    λi0 (5)

    gi(x)0 (6)

    hj(x)=0 (7)

    以上7个条件一起合为KKT条件,其中第4个条件是KKT对偶互补的条件。前3个条件可以总写为 f(x)+ni=0λigi(x)+mj=0βjhj(x)=0

    这样一看KKT条件不就是KT条件嘛(所以先看懂了KT条件的推导,这里理解起来就很简单了),注意只有凸规划才能说KKT是充要条件,其他的只能是必要条件,因为其他规划的极值点也满足KT条件。

    更多相关内容
  • 拉格朗日乘子法 和对偶问题

    千次阅读 2018-04-18 22:59:04
    拉格朗日乘数就是求条件极值转化为非条件极值嗯哼哼 首先看下条件极值为一个等式的情况将条件转化为带入z 就变成简单的一元函数求极值了嗯哼多变量也同样如此现在看看不等式约束嗯哼哼重要的数学思想来了 像...

    拉格朗日乘数法就是求条件极值转化为非条件极值

    嗯哼哼  首先看下条件极值为一个等式的情况


    将条件转化为


    带入z 

    就变成简单的一元函数求极值了


    嗯哼

    多变量也同样如此


    现在看看不等式约束

    嗯哼哼

    重要的数学思想来了 

    像条件极值转化为非条件极值

    我们能不能将不等式约束转化为等式约束 然后就依样画葫芦了

    嗯哼哼 引入松弛变量 

    what 什么是松弛变量

    比如X1<= 4 

    定义松弛变量 X2 = 4 - X1 故约束X1<= 4 

    X1 + X2 = 4且 X2 >= 0 完全等价

    故原来的约束 X1 - 4<= 0

    变成 X1 + X2 - 4 = 0

    然后就和等式条件的拉格朗日乘子法一样

    因为 X2要求大于零 又是一个新的不等式约束 故我们可以把变量写成 一个数的平方

    栗子如下


    引入松弛变量


    然后对其求偏导


    第五个是一个重要的条件

    来说下 

    什么是KKT条件

    就是说满足一定条件后不等式约束下的 拉格朗日乘子法 

    就可以完成对偶的变换

    嗯哼哼  先来看看 不等式约束


    其中 是不等式约束 

    再来看不等式约束要满足什么条件 可以发生转换  为什么

    当其满足以下条件是 就是所谓的KKT条件








    故在满足的条件下 

    可转化为其对偶问题



    再说说 为什么受约束条件的求极值能能通过拉格朗日乘子式

    嗯哼哼 拉格朗日这大牛YY了一个惩罚因子  使L()只能走在约束区内


    通过改变使得其中 X暂看作常量,记作



    一旦X 违反约束条件

     



    其惩罚因子都会 


    使得




    对偶问题


    就是看作常量 ,改变X的值使得函数最小



    证明


    而加上上述的KKT条件就是  强对偶问题了





    展开全文
  • 拉格朗日乘子法和对偶问题

    千次阅读 2017-06-27 15:54:51
    拉格朗日乘子法和对偶问题

    拉格朗日乘子法和对偶问题

    优化问题中,拉格朗日乘子法在理论分析中非常重要。今天学习了一般情形的拉格朗日乘子法,并且理解了它的严谨的理论基础。


    等式形式的约束

    这里写图片描述


    不等式形式的约束

    这里写图片描述


    一般约束的拉格朗日乘子法

    一般情形如下:
       m i n   f ( x ) min\ f(x) min f(x)
       s . t . s.t. s.t.
       h i ( x ) = 0 h_i(x)=0 hi(x)=0
       g j ( x ) = 0 g_j(x)=0 gj(x)=0
      
      对应的拉格朗日乘子如下:
       L ( x , λ , μ ) = f ( x ) + λ T h ( x ) + μ T g ( x ) L(x,\lambda,\mu)=f(x)+\lambda^Th(x)+\mu ^Tg(x) L(x,λ,μ)=f(x)+λTh(x)+μTg(x)
      
      对应的KKL条件:
       g ( x ) ≤ 0 g(x)\le 0 g(x)0
       μ ≥ 0 \mu \ge 0 μ0
       μ T g ( x ) = 0 \mu^Tg(x) = 0 μTg(x)=0

    对偶问题

    这里写图片描述

    也就是说,原问题对偶问题为:
       m a x L ( x , λ , μ ) maxL(x,\lambda,\mu) maxL(x,λ,μ)
       s . t . s.t. s.t. KKT

    理解对偶问题,注意与它的特例—线性规划的对偶问题比较理解。
      事实上,线性规划的优化,也可以由拉格朗日乘子法推出。

    展开全文
  • 拉格朗日乘子法和对偶问题详解

    千次阅读 2018-08-12 11:01:44
    拉格朗日乘子法和对偶问题详解 第十二次写博客,本人数学基础不是太好,如果有幸能得到读者指正,感激不尽,希望能借此机会向大家学习。这一篇主要是为了下面要讲的SVMSVR做理论储备,这部分涉及到的数学...

    拉格朗日乘子法和对偶问题详解

    第十二次写博客,本人数学基础不是太好,如果有幸能得到读者指正,感激不尽,希望能借此机会向大家学习。这一篇主要是为了下面要讲的SVM和SVR做理论储备,这部分涉及到的数学知识稍难理解,文章内容是结合网上的解释,以自己的理解写出来的。本文脉络清晰,非常适合读者为学习支持向量机打下一定基础。


    首先回顾一下梯度(Gradient)的相关知识,这部分是整篇文章的基础,从不同的角度介绍了不同空间下的梯度定义,然后对拉格朗日乘子法(Lagrange Multipliers)进行介绍和原理证明,之后介绍一些最优化中的凸优化问题,最后对对偶问题进行推导和证明。

    梯度(Gradient)

      首先介绍一下几个定义:
      导数,在自变量变化趋于无穷小的时候,函数值的变化与自变量变化的比值代表了导数,几何中的意义为该点的切线。物理中的意义为该时刻的(瞬时)变化率 。
      偏导数,沿着某一个自变量方向的导数。
      方向导数,是空间中一个点沿各个(自变量)方向的导数。
      梯度的本意是一个向量(矢量),表示某一函数在空间某一点处的方向导数沿着该方向将会取得最大值,即函数在该点处沿着该方向(该点梯度的方向)变化最快,变化率最大(为该点梯度的模)。具体的介绍可见如何直观形象的理解方向导数与梯度以及它们之间的关系?(知乎),梯度的计算方法可见梯度(百度百科),下面分别对二维和三维情况进行讨论:
    (1) 曲线(二维)上某点的切向量、法向量和梯度之间的关系
      1) 假设二维空间上存在一条曲线 l l l,当采用普通形式进行表示时,即 y = f ( x ) y=f\left(x\right) y=f(x)或者 F ( x , y ) F\left(x,y\right) F(x,y),那么曲线上某点 ( x , y ) \left(x,y\right) (x,y)
       a.切向量为 [ d x d x , d y d x ] T [\frac{dx}{dx},\frac{dy}{dx}]^T [dxdx,dxdy]T [ d x d x , d f ( x ) d x ] T [\frac{dx}{dx},\frac{df\left(x\right)}{dx}]^T [dxdx,dxdf(x)]T
       b.法向量为 [ ∂ F ( x , y ) ∂ x , ∂ F ( x , y ) ∂ y ] T [\frac{\partial{F\left(x,y\right)}}{\partial{x}},\frac{\partial{F\left(x,y\right)}}{\partial{y}}]^T [xF(x,y),yF(x,y)]T
       c.梯度同样为 [ ∂ F ( x , y ) ∂ x , ∂ F ( x , y ) ∂ y ] T [\frac{\partial{F\left(x,y\right)}}{\partial{x}},\frac{\partial{F\left(x,y\right)}}{\partial{y}}]^T [xF(x,y),yF(x,y)]T
      2) 假设二维空间XOY上存在一条曲线 l l l,当采用参数形式进行表示时,即 f ( n ) = { n 2 , if  n  is even 3 n + 1 , if  n  is odd f(n)=\begin{cases}\frac{n}{2},&amp;\text{if $n$ is even}\\[2ex]3n+1,&amp;\text{if $n$ is odd}\\[2ex]\end{cases} f(n)=2n,3n+1,if n is evenif n is odd或者转化为不带参数 t t t F ( x , y ) F\left(x,y\right) F(x,y),那么曲线上某点 ( x , y ) \left(x,y\right) (x,y)
       a.切向量为 [ d x ( t ) d x ( t ) , d y ( t ) d t ⋅ 1 d x ( t ) d t ] T [\frac{dx\left(t\right)}{dx\left(t\right)},\frac{dy\left(t\right)}{dt}\cdot\frac{1}{\frac{dx\left(t\right)}{dt}}]^T [dx(t)dx(t),dtdy(t)dtdx(t)1]T
       b.法向量为 [ ∂ F ( x , y ) ∂ x , ∂ F ( x , y ) ∂ y ] T [\frac{\partial{F\left(x,y\right)}}{\partial{x}},\frac{\partial{F\left(x,y\right)}}{\partial{y}}]^T [xF(x,y),yF(x,y)]T
       c.梯度同样为 [ ∂ F ( x , y ) ∂ x , ∂ F ( x , y ) ∂ y ] T [\frac{\partial{F\left(x,y\right)}}{\partial{x}},\frac{\partial{F\left(x,y\right)}}{\partial{y}}]^T [xF(x,y),yF(x,y)]T
      以曲线 y = sin ⁡ x y=\sin{x} y=sinx ( 0 , 0 ) \left(0,0\right) (0,0)处为例,从下图中可以看出,原函数 y = sin ⁡ x y=\sin{x} y=sinx,切向量 y = x y=x y=x,法向量(梯度) y = − x y=-x y=x三者之间的关系。

      从上面的讨论中我们可以看出在二维情况下,某点的法向量与梯度是相同的,均与该点的切向量垂直。
      (2) 曲面(三维)上某点的切平面、法向量和梯度之间的关系
        假设三维空间中存在一个曲面 z = f ( x , y ) z=f\left(x,y\right) z=f(x,y),梯度的意义是“沿着哪一个方向,值上升的最快 z z z”,这时对于梯度的讨论要依赖于二维空间XOY中的等高线。以三维抛物面 z = x 2 4 + y 2 4 z=\frac{x^2}{4}+\frac{y^2}{4} z=4x2+4y2为例,如下图所示

    这时要讨论梯度,首先要将三维曲面映射为二维空间XOY上的等高线图,如下图(等高线和梯度)所示

    从这张图中我们可以看出,梯度的方向是由低等高线指向高等高线的。对于这个例子的讨论,适用于所有三维情况下的梯度分析。
      1) 梯度
        通过上面对梯度的讨论,可知三维曲面 z = ( x , y ) z=\left(x,y\right) z=(x,y)的梯度可以表示为 z z z对参数 x x x y y y的偏导数,即 [ ∂ z ∂ x , ∂ z ∂ y ] T [\frac{\partial{z}}{\partial{x}},\frac{\partial{z}}{\partial{y}}]^T [xz,yz]T [ ∂ f ( x , y ) ∂ x , ∂ f ( x , y ) ∂ y ] T [\frac{\partial{f\left(x,y\right)}}{\partial{x}},\frac{\partial{f\left(x,y\right)}}{\partial{y}}]^T [xf(x,y),yf(x,y)]T
      2) 法向量
        这里要尤其注意与二维情况的不同,要求三维曲面 z = f ( x , y ) z=f\left(x,y\right) z=f(x,y)上某点的法向量,首先原三维曲面的方程可以转化为 F ( x , y , z ) = 0 F\left(x,y,z\right)=0 F(x,y,z)=0,然后令 u = F ( x , y , z ) u=F\left(x,y,z\right) u=F(x,y,z),最后法向量可以表示为 u u u对参数 x x x y y y z z z的偏导数,即 [ ∂ u ∂ x , ∂ u ∂ y , ∂ u ∂ z ] T [\frac{\partial{u}}{\partial{x}},\frac{\partial{u}}{\partial{y}},\frac{\partial{u}}{\partial{z}}]^T [xu,yu,zu]T [ ∂ F ( x , y , z ) ∂ x , ∂ F ( x , y , z ) ∂ y , ∂ F ( x , y , z ) ∂ z ] T [\frac{\partial{F\left(x,y,z\right)}}{\partial{x}},\frac{\partial{F\left(x,y,z\right)}}{\partial{y}},\frac{\partial{F\left(x,y,z\right)}}{\partial{z}}]^T [xF(x,y,z),yF(x,y,z),zF(x,y,z)]T,这里法向量与梯度是完全不相同的。
      3) 切平面
        三维空间 z = f ( x , y ) z=f\left(x,y\right) z=f(x,y)上某点的切平面是由该点指向各个方向的切向量构成的,与该点的法向量垂直,计算方法见切平面方程怎么求。这里就引出了梯度的第二个定义,即切平面上使上升得最快的方向向量到二维空间XOY的投影,如下图所示
    测标签值,则指数损失函数可以表示为,

    拉格朗日乘子法(Lagrange Multipliers)

      拉格朗日乘子法是一种寻找多元函数在一组约束下的极值的方法,通过引入拉格朗日乘子,可以将 d d d个变量的多元函数和 k k k个约束条件的最优化问题转化为具有 d + k d+k d+k个变量的无约束优化问题来进行求解。下面分别对不同情况进行讨论:
    (1) 约束条件为等式约束
      假设优化问题的优化变量 x = [ x , y ] \mathbf{x}=[x,y] x=[x,y],目标优化函数为 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x),等式约束为 h ( x ) = 0 h\left(\mathbf{x}\right)=0 h(x)=0 d = 3 d=3 d=3 k = 1 k=1 k=1,例如

    从几何角度上看,这个问题的目的是,求出 h ( x , y ) = 0 h\left(x,y\right)=0 h(x,y)=0确定的曲线上的某一点 x ∗ \mathbf{x}^* x,使得 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x)最小。
      以 f ( x , y ) = x 2 + y 2 f\left(x,y\right)=x^2+y^2 f(x,y)=x2+y2 h ( x , y ) = y − x 2 − 2 = 0 h\left(x,y\right)=y-x^2-2=0 h(x,y)=yx22=0为例,通过下图可以很明显的看出目标函数、约束曲线和最优点这三者之间的关系,图中黑色箭头为约束曲线在最优点上的梯度方向,蓝色箭头为目标函数在最优点上的梯度方向,这两个梯度是相互平行的。

    那么下面两条结论成立:
     ① 由二维空间下梯度与法向量的关系可知,曲线 h ( x , y ) = 0 h\left(x,y\right)=0 h(x,y)=0上每点的梯度均为该点的法向量,即正交于该约束曲线;
     ② 由三维空间下梯度的定义可知,目标函数在最优点 x ∗ \mathbf{x}^* x上的梯度与约束曲线 h ( x , y ) = 0 h\left(x,y\right)=0 h(x,y)=0正交,如果不满足正交条件,那么肯定存在半径( z \sqrt{z} z )更小的圆(等高线)可以与约束曲线正交;
      由此可知,在最优点 x ∗ \mathbf{x}^* x,梯度 ▽ h ( x ∗ ) \triangledown{h\left(\mathbf{x}^*\right)} h(x) ▽ f ( x ∗ ) \triangledown{f\left(\mathbf{x}^*\right)} f(x)的方向相同或相反,即存在 λ ≠ 0 \lambda\neq0 λ̸=0使得

    其中, λ \lambda λ被称为拉格朗日乘子,定义拉格朗日函数

    将上式对 x \mathbf{x} x求偏导 ∂ L ( x , λ ) ∂ x \frac{\partial{L\left(\mathbf{x},\lambda\right)}}{\partial{\mathbf{x}}} xL(x,λ)并置零即得式(1),将上式对 λ \lambda λ求偏导 ∂ L ( x , λ ) ∂ λ \frac{\partial{L\left(\mathbf{x},\lambda\right)}}{\partial{\lambda}} λL(x,λ)并置零即得等式约束 h ( x ) = 0 h\left(\mathbf{x}\right)=0 h(x)=0,因此,原等式约束优化问题可以转化为对拉格朗日函数的无约束优化问题。
      推论:
      上述讨论可以进行如下推广,假设优化问题的目标优化函数为 f ( x ) f\left(\mathbf{x}\right) f(x),等式约束为 h i ( x ) = 0 h_i\left(\mathbf{x}\right)=0 hi(x)=0,例如

    在这种情况下,拉格朗日函数可以定义为

    (2) 约束条件为不等式约束
      假设优化问题的优化变量 x = [ x , y ] \mathbf{x}=[x,y] x=[x,y],目标优化函数为 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x),不等式约束为 g ( x ) ⩽ 0 g\left(x\right)\leqslant0 g(x)0 d = 3 d=3 d=3 k = 1 k=1 k=1,例如

    从几何角度上看,这个问题的目的是,求出由 g ( x ) ⩽ 0 g\left(x\right)\leqslant0 g(x)0这条曲线所围成的曲面上的某一点 x ∗ \mathbf{x}^* x,使得 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x)最小。
      这个问题可以看做是,在 g ( x ) &lt; 0 g\left(x\right)&lt;0 g(x)<0 g ( x ) = 0 g\left(x\right)=0 g(x)=0这两种情况下分别求得各自的最优点,再进行比较,其中,第一种情况就是等式约束下的优化问题,这里的讨论与上一部分相同,而当满足第二种情况时,不等式约束 g ( x ) ⩽ 0 g\left(x\right)\leqslant0 g(x)0不起作用,最优点 x ∗ \mathbf{x}^* x可直接通过对目标函数求梯度并置零得到(由 z = x 2 4 + y 2 4 z=\frac{x^2}{4}+\frac{y^2}{4} z=4x2+4y2的梯度示意图可知,目标函数 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x)上梯度为零的点就是最低点即最优点 x ∗ \mathbf{x}^* x,假设不考虑局部最低点的情况),这等价于将拉格朗日函数中的参数 λ \lambda λ置零,求其梯度并置零。综合以上两种情况,可以得到以下结论

    上式被称为KKT条件,即在满足KKT条件的情况下,可以将不等式约束的优化问题转化为拉格朗日函数的无约束优化问题,并定义拉格朗日函数为

      推论:
      上述讨论可以进行如下推广,假设优化问题的目标优化函数为 f ( x ) f\left(\mathbf{x}\right) f(x),不等式约束为 g i ( x ) g_i\left(x\right) gi(x),例如

    在这种情况下,拉格朗日函数可以定义为

    可以证明,不等式约束下的拉格朗日乘子法要满足KKT条件,即

    (3) 包含以上两种情况
      假设优化问题的目标优化函数为 z = f ( x ) z=f\left(\mathbf{x}\right) z=f(x),等式约束为 h i ( x ) = 0 h_i\left(x\right)=0 hi(x)=0,不等式约束为 g i ( x ) ⩽ 0 g_i\left(x\right)\leqslant0 gi(x)0,例如

    在这种情况下,拉格朗日函数可以定义为

    可以证明,这种情况下的拉格朗日乘子法要满足KKT条件,即

    凸集(Convex Set)

      在凸几何中,凸集(convex set)是在凸组合下闭合的仿射空间的子集。更具体地说,在欧氏空间中,凸集是对于集合内的每一对点,连接该对点的直线段上的每个点也在该集合内。例如,立方体是凸集,但是任何中空的或具有凹痕的例如月牙形都不是凸集。特别的凸集是实数R上(或复数C上)的向量空间中,如果集合S中任两点的连线上的点都在S内,则称集合S为凸集。以下图为例

    凸函数(Convex Function)

      首先要明确一点,中国大陆数学界某些机构关于函数凹凸性定义和国外的定义是相反的,Convex Function在某些中国大陆的数学书中指凹函数,Concave Function指凸函数,但在这里使用国外的定义。
      假设向量空间 X X X是是向量空间中的一个凸集(见上),且存在从该向量空间到实数空间的映射 f : X → R f:X\rightarrow{R} f:XR,那么,凸函数(Convex Function)的定义为

    严格凸函数(Strictly Convex Function)的定义为

    有关凸函数的其他性质和重要不等式见Convex function(维基百科)

    仿射变换

      “仿射变换”就是:“线性变换”+“平移”。见如何通俗地讲解「仿射变换」这个概念?(知乎)中“马同学”的解释。

    仿射函数(Affine Function)

      从n维实空间 R n \mathbb{R}^n Rn到m维实空间 R m \mathbb{R}^m Rm的映射 f : x ↦ A x + b f:\mathbf{x}\mapsto{\mathbf{Ax}+\mathbf{b}} f:xAx+b,称为仿射变换(Affine Transform)或仿射映射(Affine Map),其中 x \mathbf{x} x是一个n维向量, A \mathbf{A} A是一个mxn矩阵, b \mathbf{b} b是一个m维向量。当 m = 1 m=1 m=1时,称上述仿射变换为仿射函数(Affine Function)。通俗地讲,仿射函数就是最高次数为1的多项式函数,而常数项为零的仿射函数称为线性函数。

    凸优化(Convex Optimization)

      凸优化问题的标准形式满足以下三个条件:
      1) 目标函数 f ( x ) f\left(\mathbf{x}\right) f(x)为凸函数,其中 x \mathbf{x} x为优化变量;
      2) 不等式约束 g i ( x ) ⩽ 0 g_i\left(\mathbf{x}\right)\leqslant0 gi(x)0中,函数 g i ( x ) g_i\left(\mathbf{x}\right) gi(x)为凸函数;
      3) 等式约束 h i ( x ) = 0 h_i\left(\mathbf{x}\right)=0 hi(x)=0中,函数 h i ( x ) h_i\left(\mathbf{x}\right) hi(x)为仿射函数。
      需要注意的是,对于凸优化问题,局部最优解就是全局最优解。具体解释见Convex optimization(维基百科)

    对偶问题(Dual Problem)

      一个优化问题可以从两个角度考虑,即“主问题”(Primal Problem)和“对偶问题”(Dual Problem)。对主问题

    基于其拉格朗日函数

    其拉格朗日“对偶函数”(Dual Function) Γ : R m × R n ↦ R \Gamma:\mathbb{R}^m\times{\mathbb{R}^n}\mapsto{\mathbb{R}} Γ:Rm×RnR定义为

      若 x ~ ∈ D \tilde{x}\in{D} x~D为主问题可行域中(满足约束)的点,则对任意 λ ≠ 0 \lambda\neq0 λ̸=0 μ ⩾ 0 \mu\geqslant0 μ0都有

    进而有

      若主问题的最优值为 p ∗ p^* p,则对任意 λ ≠ 0 \lambda\neq0 λ̸=0 μ ⩾ 0 \mu\geqslant0 μ0都有

    即对偶函数给出了主问题最优值的下界,这个下界取决于参数 λ ≠ 0 \lambda\neq0 λ̸=0 μ ⩾ 0 \mu\geqslant0 μ0的值。那么,主问题的对偶问题可以表示为

    且无论主问题的凸性如何,其对偶问题始终是凸优化问题。
      当主问题不满足凸优化问题的条件(见上)时,对偶问题的最优值 d ∗ d^* d满足 d ∗ ⩽ p ∗ d^*\leqslant{p^*} dp,这称为“弱对偶性”(Weak Duality)成立;当主问题满足凸优化问题的条件(见上)时,对偶问题的最优值 d ∗ d^* d满足 d ∗ = p ∗ d^*={p^*} d=p,这称为“强对偶性”(Strong Duality)成立,当强对偶性成立时,对偶问题的最优解就是主问题的最优解。

    展开全文
  • 实验目录一、拉格朗日乘子法和KKT的介绍二、手工数学推导三、拉格朗日乘子法的有约束情况四、手工数学推导,考虑有约束情况的比较五、参考文献 一、拉格朗日乘子法和KKT的介绍 拉格朗日乘子法 拉格朗日乘子λ代表...
  • 通过对变量和拉格朗日乘子进行多次迭代,求出最优值,例子很简单,可以套用,很容易看会,有问题的欢迎留言,共同探讨。
  • (三)拉格朗日乘子法——对偶问题

    千次阅读 2018-09-03 23:06:46
    给出不等式约束优化问题 minx&nbsp;f(x)s.t.&nbsp;&nbsp;&nbsp;hi(x)=0,&nbsp;i=1,2,...,m&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&...
  • 本文通过一系列的例子来说明拉格朗日乘子的运算以及原理,通俗易懂。 1、拉格朗日乘数(乘子)原理 定义: In mathematical optimization, the method of Lagrange multipliers is a strategy for finding the ...
  • 用次梯度方法求解拉格朗日对偶问题的例子。。。。。。
  • 拉格朗日乘子法详解

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

    千次阅读 2019-05-09 01:09:06
    约束优化问题中,常常利用拉格朗日对偶性将原始问题转换为对偶问题,通过解对对偶问题而得到原始问题。该方法应用在许多统计学习方法中,例如最大熵模型支持向量机。 1、原始问题 假设f(x),ci(x),hj(x)f(x), c_{...
  • 这是手工推导的SVM的推导过程,其中对拉格朗日乘子对偶问题做了详细的推导
  • 拉格朗日乘子法要解决的式带有约束的最优化问题,约束条件分为等式约束不等式约束。 等式约束可以直接应用拉格朗日乘子法去求取最优值;含不等式约束的优化问题可以转化为在满足KKT条件下应用拉格朗日乘子法求解。...
  • 本文承接上一篇约束优化方法之拉格朗日乘子法与KKT条件,将详解一些拉格朗日对偶的内容。都是一些在优化理论中比较简单的问题或者一些特例,复杂的没见过,但是简单的刚接触都感觉如洪水猛兽一般,所以当真是...
  • SVM支持向量机-拉格朗日乘子对偶问题(1)

    万次阅读 多人点赞 2018-04-09 17:06:43
    对于支持向量机,我们首先要关注的几个点就是间隔,超平面,支持向量,再深入的话就是对偶问题拉格朗日对偶问题,凸优化,KKT条件,我们先从基本的间隔,超平面,支持向量说起。 1.SVM基础模型 给定训练集...
  • 这一节主要针对拉格朗日乘子法以及其KKT条件还有强对偶、弱对偶问题进行总结推导,希望在这一块有疑问的同学可以一起交流学习。萌新第一次写博客,很多地方表述不足希望大家指出。 1.SVM回顾 支持向量机(SVM)是...
  • 转载 目录 动机 ...在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier) KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如
  • 拉格朗日乘子法 本段内容参考了拉格朗日(Lagrange)乘子法超简说明。 先从物理意义上介绍拉格朗日乘子法。 原问题 我们要解决带有等式约束的最优化问题。为方便书写,以二维函数为例: maxf(x,y),s.t.g(x,y)=0 ...
  • 拉格朗日乘子法 & KKT条件

    千次阅读 2019-08-08 10:18:17
    目录 1. 拉格朗日乘子法用于最优化的原因 2. 最优化问题三种情况 2.1 无约束条件 2.2 等式约束条件:拉格朗日乘子法 2.3 不等式约束条件:KKT ... 在求解最优化问题中,拉格朗日乘子法(Lagrange...
  • 在求取有约束条件的优化问题时,拉格朗日乘子法(Lagrange Multiplier)KKT条件是非常重要的两个求取方法,对于等式约束的优化问题,可以应用拉格朗日乘子法去求取最优值;如果含有不等式约束,可以应用KKT条件去求...
  • 乘子法本文先简要介绍三个乘子法,它们的收敛条件依次减弱(不做具体...Lagrange Multiplier(拉格朗日乘子法)Augmented Lagrangian Multiplier(增广拉格朗日乘子法,ALM)Alternating Direction Method of Multipliers...
  • 一直对拉格朗日乘子法不是理解的不是很透彻,今天决定要push一下自己,彻底的理解拉格朗日乘子法,希望对大家有所帮助。...1.3.1 为什么拉格朗日乘子法可以将带约束的优化问题转换成无约束的优化问题? ...
  • 拉格朗日乘子法对偶、KTT 一般情况下,最优化问题分为三类 一、 无约束条件下的最优化问题 这种最优化问题比较简单,直接求导为0就可以得到。 二、 等式约束下的最优化问题 即除了目标函数之外,还有一些约束条件...
  • 拉格朗日乘子法求解最优化问题

    万次阅读 多人点赞 2019-04-02 17:38:03
    最近在看机器学习有关SVM的内容,在SVM模型中,我们要求得一个划分超平面,使得相同类别的样本处于同...至此引入我们这篇文章讲述的主要内容:“使用拉格朗日乘子法求解最优化问题”,下面我们先从最简单的最优化...
  • 真正理解拉格朗日乘子法和KKT条件

    万次阅读 多人点赞 2018-05-29 11:08:13
     这篇博文中直观上讲解了拉格朗日乘子法和 KKT 条件,对偶问题等内容。 首先从无约束的优化问题讲起,一般就是要使一个表达式取到最小值: minf(x)minf(x) min f(x)  如果问题是 maxf(x)maxf(x)maxf(x) 也可以...
  • 文章目录前言Lagrangian:Equality Constraint例子Multiple...一般情况下,最优化问题分为三类 一、 无约束条件下的最优化问题 这种最优化问题比较简单,直接求导为0就可以得到。 二、 等式约束下的最优化问题 即除了...
  • ⚪目标函数为求解分类间隔d的最大值,所以目标函数及约束条件为: 求解满足上式的wb是我们的目标,因为目标函数有二次项,所以以上问题可看作一个凸二次规划问题,可以通过拉格朗日乘子法求解,转换后函数如下: ...
  • 在求解最优化问题中,拉格朗日乘子法(Lagrange Multiplier)KKT(Karush Kuhn Tucker)条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法,在有不等约束时使用KKT条件。  我们这里提到的最优化问题...
  • 在约束最优化问题中,常常利用拉格朗日...对于等式约束的优化问题,可以应用拉格朗日乘子法(Lagrange Multiplier)去求取最优值;如果含有不等式约束,可以应用KKT(Karush-Kuhn-Tucker)条件去求取。当然,这两个...

空空如也

空空如也

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

拉格朗日乘子法和对偶问题