2018-12-01 20:54:47 weixin_37352167 阅读数 1011

  • 凸集

    如果从一个点集中任取不同的两个点 x1 和 x2 ,它们之间的线段(包括端点)上的点都属于这个点集,则称这个点集为凸集。

    比如下图中左边的是凸集,而右边不是。
    凸集

    数学定义:

    给定集合 Cx1,x2C0<θ<1C,x_1,x_2 ∈ C;0<θ<1

    如果有:θx+(1θ)yCθx+(1-θ)y∈C

    则称 CC 为凸集,θx1+(1θ)x2θx_1+(1-θ)x_2 为点 x1,x2x_1,x_2 的凸组合。

  • 凸函数

    设一函数 f:RnRf:\mathbb{R}^n→\mathbb{R},记其定义域为 D(f)D(f),如果 D(f)D(f) 是凸集,且在其中任取两个点x1,x2x_1,x_2,满足以下性质:

    f(θx1+(1θx2))θf(x1)+(1θ)f(x2)f(θx_1+(1−θx_2))≤θf(x_1)+(1−θ)f(x_2)

    那么就称 ff 为凸函数。

    几何上看:
    凸函数

    注意:这里所说的凸函数对应于考研数学中的凹函数(实际上加一个 “-” 就可以)。

  • 凸优化

    凸优化的结果一定是全局最优解。

    1. 水平子集

      假定 f(x)f(x) 是一个凸函数, 给定一个实数 αRα∈R,我们把集合 {xD(f)f(x)αx∈D(f)|f(x)≤α} 叫做αα 水平子集。

      αα 水平子集是所有满足 f(x)αf(x)≤α 的点构成的集合,且水平子集也是凸集。

      水平子集告诉我们,给凸函数添加一个上限,定义域内剩下的点构成的点集仍然是一个凸集。

    2. 仿射函数

      把形如: h(x)=Ax+bh(x)=Ax+b 的函数叫做仿射函数。

      其中,AmnA_{m*n},向量 bRmb∈Rm。直观上理解,仿射函数将一个n维空间的向量通过线性变换 AA 映射到 m 维空间,并在其基础上加上向量 bb,进行了平移。

      {xD(h)h(x)=0x∈D(h)|h(x)=0} 也是凸集。

    3. 优化

      优化,是求近似解的过程。例如:

      {x1+x2=02x1+x2=13x2+2x2=1\begin{cases} x_1 + x_2 = 0\\ 2x_1 + x_2 = 1 →此方程组无解\\ 3x_2 + 2x_2 = 1\\ \end{cases}

      但是我们可以得到一个使相差最小的解,即:

      minx1,x2(x1+x20)2+(2x1+x21)2+(3x2+2x21)2min_{x_1,x_2} (x_1 + x_2 - 0)^2 + (2x_1 + x_2 - 1)^2 + (3x_2 + 2x_2 - 1)^2

      求得和能使最小的解,即可达到三个方程同时近似。

      为了能得到近似解,我们可以使用上一篇文章介绍的:求正规方程的最小二乘解。

      而我们也可以使用约束优化方法。

    4. 约束优化

      例:
      minminf(x)=(x12)2+x2f(x) = (x_1-2)^2 + x_2
      s.ts.tc1(x)=x12x2+60,c_1(x) = x_1 - 2x_2 + 6 \geqslant 0,
         c2(x)=x1+30c_2(x)=x_1 + 3 \geqslant 0

      此时的优化,相当于在由 3 个函数 f(x)c1(x)c2(x)f(x),c_1(x),c_2(x) 共同围城的可行域中,求 f(x)f(x) 的最小值(而且一定是在 f(x)f(x) 与某一或某几个约束函数的边界上取到,即约束被激活)。

  • 拉格朗日对偶性

    根据拉格朗日对偶性,即将原始问题转化成对偶问题,从而更容易地进行函数优化。

    1. 原始问题

      假设 f(x),ci(x),hj(x)f(x),c_i(x),h_j(x)是定义在 Rn\mathbb{R}^n 上的连续可微函数,考虑约束优化问题:

      minxmin_xf(x)f(x)
      s.ts.t     ci(x)0i=1,2,,kc_i(x)\leqslant{0},i=1,2,…,k
              hj(x)=0j=1,2,,lh_j(x)=0,j=1,2,…,l

      为要求解地原始问题。

    2. 原始问题的拉格朗日函数

      L(x,α,β)==f(x)+i=1kαici(x)+j=1lβihj(x)L(x,α,β)==f(x) + \sum_{i=1}^{k}α_ic_i(x) +\sum_{j=1}^{l}β_ih_j(x)

      目标 为:最大化 L(x,α,β)L(x,α,β) ,因为在满足约束的条件下 L(x,α,β)L(x,α,β) 最大化时, L(x,α,β)L(x,α,β) 才等价于原函数 f(x)f(x)(下面将证明)。

      考虑:

      Θp(x)=α,β;αi0MaxL(x,α,β)Θ_p(x)=\mathop{}_{α,β;α_i\geqslant{0}}^{Max}L(x,α,β)

      Θp(x)Θ_p(x) 此时一定是凹函数(对应于考研数学中的凸函数)。


      倘若某 xx 违反原始问题地约束条件时:

      ① 违反约束条件,即某个 ci(x)>0c_i(x)>0
      · 欲使 L(x,α,β)L(x,α,β) 值最大,可令对应的乘子 αi+α_i → +\infty ,则此时 Θp(x)+Θ_p(x) → +\infty

      ② 违反约束条件,即某个 hj(x)0h_j(x)\neq0
      · 欲使 L(x,α,β)L(x,α,β) 值最大,可令某 βihj(x)+β_ih_j(x) → +\infty,其余的 αi,βjα_i,β_j 都取 00,则此时 Θp(x)+Θ_p(x) → +\infty


      \bigstar 以上,即:

      Θp(x)=Θ_p(x)= {f(x)x+x\begin{cases} f(x),x满足约束条件\\ +\infty,x不满足约束条件\\ \end{cases}

      xx 满足约束条件,为使 L(x,α,β)L(x,α,β) 取最大值,

      应:i=1kαici(x)=0j=1lβihj(x)=0\sum_{i=1}^{k}α_ic_i(x)=0,\sum_{j=1}^{l}β_ih_j(x)=0

      此时,Θp(x)α,β;αi0MaxL(x,α,β)f(x)Θ_p(x) \leftrightharpoons \mathop{}_{α,β;α_i\geqslant{0}}^{Max} L(x,α,β) \leftrightharpoons f(x)


      优化问题下,目标为:xMinΘp(x)\mathop{}_{x}^{Min} Θ_p(x)

      根据等价关系可得:xMinΘp(x)xMinα,β;αi0MaxL(x,α,β)xMinf(x)\mathop{}_{x}^{Min} Θ_p(x) \leftrightharpoons \mathop{}_{x}^{Min} \mathop{}_{α,β;α_i\geqslant{0}}^{Max} L(x,α,β) \leftrightharpoons \mathop{}_{x}^{Min} f(x)

      定义原始问题的最优值为 p=xMinΘp(x)p^*=\mathop{}_{x}^{Min}Θ_p(x)

    3. 原始问题的对偶问题

      定义: ΘD(α,β)=xMinL(x,α,β)Θ_D(α,β)=\mathop{}_{x}^{Min}L(x,α,β)

      考虑极大化:α,β;αi0MaxΘD(α,β)=α,β;αi0MaxxMinL(x,α,β)\mathop{}_{α,β;α_i\geqslant{0}}^{Max}Θ_D(α,β)= \mathop{}_{α,β;α_i\geqslant{0}}^{Max} \mathop{}_{x}^{Min}L(x,α,β)

      定义对偶问题的最优值为 d=α,β;αi0MaxΘD(α,β)d^*=\mathop{}_{α,β;α_i\geqslant{0}}^{Max}Θ_D(α,β)

      ΘD(α,β)Θ_D(α,β) 此时一定为凸函数(对应于考研数学中的凹函数)。

    4. 原始问题与对偶问题的关系

      d=α,β;αi0MaxxMinL(x,α,β)xMinα,β;αi0MaxL(x,α,β)=pd^*=\mathop{}_{α,β;α_i\geqslant{0}}^{Max}\mathop{}_{x}^{Min}L(x,α,β) \leqslant \mathop{}_{x}^{Min} \mathop{}_{α,β;α_i\geqslant{0}}^{Max} L(x,α,β)=p^*
      原始问题与对偶问题

      设 {x,α,β{x^*,α^*,β^*}} 为原始问题与对偶问题的可行解,并且 d=pd^* = p^*

      则 {x,α,β{x^*,α^*,β^*}} 就是原始问题与对偶问题两个问题的最优解。

      (最大值集合中的最小值 \geqslant 最小值集合中的最大值)

    5. KKT 条件

      KKK (Karush Kuhn Tucker) 条件:

      {xL(x,α,β)=0αL(x,α,β)=0βL(x,α,β)=0αici(x)=0,i=1,2,,kci(x)0,i=1,2,kαi0,i=1,2khj(x)=0,j=1,2,l\begin{cases} \nabla_x L(x^*,α^*,β^*)=0\\ \nabla_α L(x^*,α^*,β^*)=0\\ \nabla_β L(x^*,α^*,β^*)=0\\ α_i^*c_i(x^*)=0,i=1,2,…,k\\ c_i(x^*)\leqslant0,i=1,2…,k\\ α_i^*\geqslant0,i=1,2…k\\ h_j(x^*)=0,j=1,2…,l \end{cases}

      其中,αici(x)=0,i=1,2,,kα_i^*c_i(x^*)=0,i=1,2,…,k 为 KKT 条件的对偶互补条件:
      {α>0ci(x)=0ci(x)<0α=0\begin{cases} 若α^*>0,则 c_i(x^*)=0\\ 若c_i(x^*)<0,则α^*=0 \end{cases}

      x,α,βx^*,α^*,β^* 是原始问题与对偶问题的解 x,α,β\leftrightharpoons x^*,α^*,β^* 满足 KKT 条件。

2015-11-24 03:03:42 mijian1207mijian 阅读数 2523

KKT条件(几何的解释)

对于凸优化,KKT条件的点就是其极值点(可行下降方向)。

  • x是非线性规划的局部最小点,目标函数f(x)x可微,约束方程(g(x))在x处可微,连续;则X*点不存在可行下降方向(因为已经是局部最小点了)

  • 若极小值点在内部,则无约束问题,直接拉格朗日乘子法

  • 若极小值在边界上,(gi(x)=0)
  • 互补松弛条件
    f(x)γ1g1(x)γ2g2(x)=0
    γi0γigi(x)=0
    满足其他约束

  • 一阶得到是局部极值点 ,还需要通过二阶判断是否是鞍点


强对偶条件( 鞍点解释)->对偶函数取下确界,则对偶函数一定是凹函数

  • 原函数不好求,转换为求解对偶函数,则对偶函数下确界求得,则比为凹函数(负号为凸函数)
  • 上确界求得,比为凸函数
  • 满足KKT条件后,对偶函数和原函数最优值相等
  • 求解对偶函数,及求解凸函数
  • 对偶和原函数相等(对偶间隔=0)需要满足的式子也是KKT,同时最优点是鞍点,也就是KKT方程的解

这里写图片描述

这里写图片描述


对偶问题:若要对偶函数的最大值即为原问题的最小值问题(对偶间隙是0),解凸优化问题等价于解KKT方程;

  • f0(x)=g(λ,ν)>
    =infx(f0(x)+i=1mλifi(x)+i=1pvihi(x)
    infx(f0(x)+i=1mλifi(x)+i=1pvihi(x)
    f0(x)

上式等号成立需要:

fi(x)0,i=1,...,m
hi(x)=0,i=1,...,m
λi0,i=1,...,m
λifi(x)=0,i=1,...,m
f0(x)+i=1mλifi(x)+i=1pvihi(x)=0

2017-03-14 22:53:48 evillist 阅读数 596

概念:

min.:f(x)
s.t.:gi(x)≤0,i=1,2,…,p,
hj(x)=0,k=1,2,…,q,
x∈Ω⊂Rn
KTT条件是指在满足一些有规则的条件下, 一个非线性规划(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=1pμi∇gi(x∗)+∑j=1qλ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没有符号的限制, 其符号要视等式限制条件的写法而定.
2017-08-23 18:16:30 u014675538 阅读数 5654

1.引言

本篇博客主要总结了拉格朗日乘子和KTT条件在机器学习中求解最优值的原理,博主尽量举点小例子帮助大家一起共同学习。

2.拉格朗日和KKT作用

我们在求解问题时,经常会遇到一些在约束条件下求解函数的。
在有等式约束条件下,我们选用拉格朗日乘子;
在有不等式约束条件下,选用KKT方法求解最优解。
因此我们可以将KKT条件看成是拉格朗日乘子的泛化。

3.求解最优问题的集中形式

通常我们需要求解的最优化问题有如下几类:

  • 无约束条件下求最优值
    minf(x,y)
  • 在等式条件下求解最优值
    minf(x,y)
    s.t...g(x,y)=c
  • 在不等式条件下求解最优值
    minf(x,y)
    s.tg(x)<=0,h(x)<=0

4.求解不同最优问题方法

4.1无约束条件下的最优值求解

无约束条件下的函数f(x,y)求解最大或者最小值,一般求该函数对各个参数的偏导数,令偏导数为0,求解得到的x0,y0即为在该条件下可以使函数f(x,y)最优。

αf(x,y)/αx=0

αf(x,y)/αy=0

这样求解的首先需要保证函数f(x,y)为凸函数。

4.2 等式条件下的最优值求解(拉格朗日乘子)

假设我们需要求解的函数为f(x,y)的最优值,同时需要满足条件 g(x,y)=c,因此问题就转化为,在 g(x,y)=c条件下,求解函数f(x,y)的最优值。函数f(x,y)=d在x,y平面上面具有一些等高线,如下图所示
这里写图片描述
g(x,y)=c是一条红色的曲线,那么我们在什么样的情况下可以求出他的最优值呢,我们发现函数g(x,y)=c会与f(x,y)=d相交,那么交点是不是最优值呢,我们以前知识学过,两个函数的交点说明,是两个函数共同的可行解。那最优点怎样求取呢,我们可以更改d的大小,我们得到一系列的等高线。红色曲线与函数f(x,y)=d的交点就是最优解。
而拉格朗日乘子就是解决这样问题的,通过引入一个λ约束条件g(x,y)=c组合得到一个新的函数,这个新函数与目标函数f(x,y),得到最终需要优化函数。

L(x,y,λ)=f(x,y)+λ[g(x,y)c]

接下来就是求解函数L(x,y,λ)对各个参数的偏导数,并令各个偏导数为0,联立可以求出三个参数x,y,λ,代入原式,可以求解最优解。
αL(x,y,λ)/αx=0

αL(x,y,λ)/αy=0

αL(x,y,λ)/αλ=0

接下来举一个小例子
f(x,y)=x2y,g(x,y)=x2+y21
则可以得到

L(x,y,λ)=f(x,y)+λg(x,y)=x2y+λ(x2+y21)

对各个参数求解偏导数得到
2xy+2λx=0
x2+2λy=0
x2+y21=0

4.3不等式条件下求解最优解(KKT条件)

对KTT条件的讲解主要采用作者(xianlingmao),对作者表示感谢
对于含有不等式约束的优化问题,如何求取最优值呢?常用的方法是KKT条件,同样地,把所有的不等式约束、等式约束和目标函数全部写为一个式子L(a,b,x)=f(x)+ag(x)+bh(x),KKT条件是说最优值必须满足以下条件:

  • L(a, b, x)对x求导为零;
  • h(x) =0;
  • a*g(x) = 0;

求取这三个等式之后就能得到候选最优值。其中第三个式子非常有趣,因为g(x)<=0,如果要满足这个等式,必须a=0或者g(x)=0.
KTT满足的强对偶条件可以这样理解,我们要求minf(x), L(a,b,x)=f(x)+ag(x)+bh(x)a>=0,我们可以把f(x)写为:maxa,bL(a,b,x),为什么呢?因为h(x)=0,g(x)<=0,现在是取L(a,b,x)的最大值,a*g(x)是<=0,所以L(a,b,x)只有在a*g(x) = 0的情况下才能取得最大值,否则,就不满足约束条件,因此max_{a,b} L(a,b,x)在满足约束条件的情况下就是f(x),因此我们的目标函数可以写为 min_x max_{a,b} L(a,b,x)。如果用对偶表达式: max_{a,b} min_x L(a,b,x),由于我们的优化是满足强对偶的(强对偶就是说对偶式子的最优值是等于原问题的最优值的),所以在取得最优值x0的条件下,它满足 f(x0) = max_{a,b} min_x L(a,b,x) = min_x max_{a,b} L(a,b,x) =f(x0),我们来看看中间两个式子发生了什么事情:
f(x0) = max_{a,b} min_x L(a,b,x) = max_{a,b} min_x f(x) + a*g(x) + b*h(x) = max_{a,b} f(x0)+a*g(x0)+b*h(x0) = f(x0)

可以看到上述加黑的地方本质上是说 min_x f(x) + a*g(x) + b*h(x) 在x0取得了最小值,用fermat定理,即是说对于函数 f(x) + a*g(x) + b*h(x),求取导数要等于零,即

f(x)的梯度+a*g(x)的梯度+ b*h(x)的梯度 = 0

这就是kkt条件中第一个条件:L(a, b, x)对x求导为零。

而之前说明过,a*g(x) = 0,这时kkt条件的第3个条件,当然已知的条件h(x)=0必须被满足,所有上述说明,满足强对偶条件的优化问题的最优值都必须满足KKT条件,即上述说明的三个条件。可以把KKT条件视为是拉格朗日乘子法的泛化。

2016-04-08 23:01:06 zhb_bupt 阅读数 4594

前言

  本文旨在详细介绍KKT条件的推导和计算方法。
  拉格朗日算子常用语等式约束最优化的求解中,是KKT条件的特殊形式。KKT条件用于含有不等式约束的条件下的优化问题,例如SVM算法。要深入理解SVM算法必需深入理解KKT条件,本文尝试使用简单易懂的方法向读者介绍KKT条件的推导和使用方法。博主尽量使用图形来阐述KKT条件的深层内涵,数学功底较弱的读者可直接跳过推导过程看结论和例子。

拉格朗日乘子法

  考虑如下约束条件下的:
  

minxf(x)s.t.hi(x)=0i=1,2,k

  其中:
  
xRn

  本博客以二元函数为例介绍拉格朗日乘子法的推导过程。
  考虑如下优化问题:f(x,y)满足约束h(x,y)=0
  如果在(x0,y0)处取得极值,那么有:
  
h(x0,y0)=0

  约束条件确定一个连续且具有连续导数的函数:
  
y=φ(x)

  这时,原问题为:
  
f(x,φ(x))

  上式在(x0,y0)处取得极值,由一元可导函数取得极值的必要条件知道:
  
fx(x0,y0)+fy(x0,y0)dydxx=x0=0

  由隐函数求导公式有:
  
dydxx=x0=hx(x0,y0)hy(x0,y0)

  所以有:
  
fx(x0,y0)fy(x0,y0)hx(x0,y0)hy(x0,y0)=0

  引入λ,有:
  
fx(x0,y0)hx(x0,y0)=fy(x0,y0)hy(x0,y0)=λ

  这样,上述必要条件就变为:
  
fx(x0,y0)+λhx(x0,y0)=0fy(x0,y0)+λhy(x0,y0)=0h(x0,y0)=0

  若引入辅助函数:
  
L(x,y)=f(x,y)+λh(x,y)

  这不难看出,上述极值条件为:
  
Lx(x,y)=0Ly(x,y)=0Lλ(x,y)=0

  推广到多元情况为:
  
L(x1,,xn)=f(x1,,xn)+ikαihi(x1,,xn)

  L(x1,,xn)的极值点即原问题的极值点。
  即满足以下条件的点即原问题的最优解:
Lxi(x1,,xn)=0 i=1,,nLαj(x1,,xn)=0j=1,,k

  以下以几何形式阐述这一原理:
这里写图片描述
  图中的用等高线表示f(x,y)。由于原优化问题是凸优化问题,当h(x,y)=0 和等高线相交时意味着在两个交点之间存在更优的点。只有当等高线和h(x,y)=0 相切时才是满足约束条件的最优点。即在交点处满足:
  
f(x,y)=λh(x,y)h(x,y)=0

  以下以一例子说明拉格朗日乘子法的计算步骤。

未完待续。。。
/**********************
* 本文来自博客 “zhb_bupt“
* 转载请标明出处:http://blog.csdn.net/zhb_bupt
* 博客迁往: http://deepminer.ailifenet.com
********************************/

没有更多推荐了,返回首页