二次规划问题

解决最优化问题 :

 

稍微对它做一下改动,如下:

    

这是一个约束优化问题,更进一步说是一个二次规划问题,复习一下约束优化问题:

定义1:约束非线性问题是,

其中都是定义在上的实值连续函数,且至少有一个是非线性的(反之为线性约束优化问题),m是一个正整数,叫做目标函数,叫做约束函数,如果目标函数是二次函数则叫做二次规划问题,由同时满足所有约束方程的点组成的集合叫做可行域,这些点叫可行点。

定义2:Farkas引理,对于给定的n维向量与b,对于任意满足  的向量P,必有的充要条件是:b在向量所形成的凸锥内,即成立:  

怎么理解“某个向量在若干其它向量形成的凸锥内”这个描述呢?可以看下图,

利用平行四边形法则,可以看到向量b处于由形成的凸多边形内,发挥一下想象力,在空间中这不就像是一个凸的锥状体嘛。

定义3:对于约束问题,如果有一个可行点,存在且满足

 这里都是有效约束。

叫做K-T点。

K-T点的几何意义可以从下图看出:

显然x1是K-T点而x2则不是。在一般非线性规划中,K-T条件是最优解的必要条件但不是它的充分条件,此时K-T点不一定是最优点,但对于凸规划问题,K-T条件是最优解的充要条件;顺便说下,凸规划是个好同志,它的局部最优解就是全局最优解,所以它的K-T点就是全局最优点。

定理1:设是约束问题的局部极小点,点处的线性化可行方向的集合等于其序列可行化方向的集合,则必存在 使得:

 这里都是有效约束。

点处的线性化可行方向的集合等于其序列可行化方向的集合”这个条件怎么满足呢?只要所有有效约束都是线性函数即可,此时必是一个K-T点。

定理2:一阶最优性条件:对于可行点,如果目标函数和所有有效约束在处可微,且任意、非零的,在处的序列可行化方向向量d满足:,则为严格局部极小点。这意味着,当向某一点处的任意方向移动都将导致目标函数值上升,那么这个点不就是一个局部极小点嘛。

定理3:二阶最优性条件:设为K-T点,是相应的拉格朗日乘子,如果,其中d为非零的、处的线性化零约束方向,则为严格的局部极小点。

推论1:设为K-T点,是相应的拉格朗日乘子,如果对一切满足的非零向量d都有,则为严格的局部极小点。

对于前面的约束非线性规划问题,如果是二次函数且所有约束是线性函数的时候就变成了二次规划问题,这一写成以下形式:

定理4:如果是二次规划问题的可行点,则是局部极小点的充要条件是:当且仅当存在拉格朗日乘子,使得:

   

成立,(即是K-T点)且对于一切满足

(其中E为等式的有效约束,I()为不等式的有效约束)

的向量d都有:

定理5:设H为半正定矩阵(所有特征值大于等于0),则二次规划问题的全局极小点当且仅当它是一个局部极小点或者K-T点。

当H为半正定矩阵,目标函数为凸函数时,该二次规划被叫做凸二次规划,它的任何K-T点都是极小点。回想我们开篇要解决的那个问题,目标函数显然是一个凸函数,所以它是一个凸二次规划问题,所以一定存在全局极小点(真好!)。

到此,我们就可以开始解决开篇的那个问题:

  

已经确定它是一个凸二次规划问题了,那么可以利用其拉格朗日函数:

通过对求偏导数后得到:

带入原始拉格朗日函数,转化为对偶问题:

这样就把带不等式约束的优化问题通过其对偶形式转化为只带等式约束的优化问题,即下面的最优化问题W:????

求得后就得到了,它使得几何间隔取最大值,从而得到最优分类超平面。

K-T点要满足的条件还有一个是:,这个式子说明了什么问题呢?

1、显然,函数间隔不等于1的那些输入点的拉格朗日系数必为0(这些点是非积极因素),而函数间隔恰好为1的输入点的拉格朗日系数则不为0(这些点是积极因素),这说明确定最终分类超平面的就是这些函数间隔为1的边界点,所以这些输入点就是支持向量(Support Vector)。从这里也能看出支持向量机的抗干扰能力比较强,对非积极因素的扰动对于最优化解没有影响;

2、,其中i为支持向量,因为:

,我们的目标函数

(注意这里为常数,且有约束条件

于是通过这样的对偶转化,我们得到了实现几何间隔为的最大间隔超平面。

通过上面的推导也可以看出将二次规划转化为其对偶问题可以简化约束条件,让我们记住最优化问题W吧,这是一个很牛逼的转化,这个式子还有个特点,就是“数据仅出现在内积中”。

前面的讨论都是说输入样本是线性可分的时候怎么找到最大间隔超平面来划分两类数据,那么如果输入样本是线性不可分的,那可怎么办呀,前面的那些讨论不就成徒劳的了么?学习SVM后才知道它牛的地方,如果我们可以通过某种函数映射将输入样本映射到另外一个高维空间并使其线性可分的话,前面的讨论结果不就都可以用到了么,还记得“数据仅出现在内积中”吧,假设这个映射关系是:,这时候的内积就变成了,如果有方法能够将内积直接算出,就将把输入样本“从低维空间向高维空间映射”和“求映射后的内积”这两步合并成了一步,这样直接计算的方法就是核函数方法,下篇学习核函数吧,SVM的理论部分还是很数学的啊!

时间: 11-02

二次规划问题的相关文章

用二次规划法解带约束的线性回归

对于解带约束(线性约束)的线性回归通常的办法是,将约束直接表示在线性回归中,也就是减少一个变量(即回归到线性约束本身的自由变量数目).然而今天由于要解一个问题发现了另一种思路的解法,是比变换变量更为通用的办法,就是用二次规划法解带约束的线性回归. 二次规划法有如下一般形式: 各个部分为: 特别地如果约束条件为等号,则可以用拉格朗日乘子法直接求解.如果Q是不定矩阵,甚至有一个特征值是负数的,问题就是NP难问题.. 解决一个带约束的线性回归问题,形如: 需要求解最小化: 这个式子展开来写成矩阵形式就

凸集,凸函数,凸优化问题,线性规划,二次规划,二次约束二次规划,半正定规划

没有系统学过数学优化,但是机器学习中又常用到这些工具和技巧,机器学习中最常见的优化当属凸优化了,这些可以参考Ng的教学资料:http://cs229.stanford.edu/section/cs229-cvxopt.pdf,从中我们可以大致了解到一些凸优化的概念,比如凸集,凸函数,凸优化问题,线性规划,二次规划,二次约束二次规划,半正定规划等,从而对凸优化问题有个初步的认识.以下是几个重要相关概念的笔记. 凸集的定义为: 其几何意义表示为:如果集合C中任意2个元素连线上的点也在集合C中,则C为

关于SVM数学细节逻辑的个人理解(三) :SMO算法理解

第三部分:SMO算法的个人理解 接下来的这部分我觉得是最难理解的?而且计算也是最难得,就是SMO算法. SMO算法就是帮助我们求解: s.t.   这个优化问题的. 虽然这个优化问题只剩下了α这一个变量,但是别忘了α是一个向量,有m个αi等着我们去优化,所以还是很麻烦,所以大神提出了SMO算法来解决这个优化问题. 关于SMO最好的资料还是论文<Sequential Minimal Optimization A Fast Algorithm for Training Support Vector

R与数据分析旧笔记(十二)分类 (支持向量机)

支持向量机(SVM) 支持向量机(SVM) 问题的提出:最优分离平面(决策边界) 优化目标 决策边界边缘距离最远 数学模型 问题转化为凸优化 拉格朗日乘子法--未知数太多 KKT变换和对偶公式 问题的解决和神经网络化 对偶公式是二次规划问题,有现成的数值方法可以求解 大部分的拉格朗日乘子为0,不为0的对应于"支持向量"(恰好在边界上的样本点) 只要支持向量不变,修改其他样本点的值,不影响结果,当支持变量发生改变时,结果一般就会变化 求解出拉格朗日乘子后,可以推出w和b,判别函数可以写成

Convex optimization 凸优化

zh.wikipedia.org/wiki/凸優化 以下问题都是凸优化问题,或可以通过改变变量而转化为凸优化问题:[5] 最小二乘 线性规划 线性约束的二次规划 半正定规划 Convex function Convex minimization is a subfield of optimization that studies the problem of minimizing convex functions over convex sets. The convexity makes opt

SVM学习笔记-线性支撑向量机

最大间隔超平面 线性分类器回顾 当数据是线性可分的时候,PLA算法可以帮助我们找到能够正确划分数据的超平面hyperplane,如图所示的那条线. 哪一条线是最好的? 对于PLA算法来说,最终得到哪一条线是不一定的,取决于算法scan数据的过程. 从VC bound的角度来说,上述三条线的复杂度是一样的  Eout(w)≤Ein0+Ω(H)dvc=d+1 直观来看,最右边的线是比较好的hyperplane. 为什么最右边的分隔面最好? 对于测量误差的容忍度是最好的.例如对于每

关于凸优化的一些简单概念

http://www.cnblogs.com/tornadomeet/p/3300132.html 没有系统学过数学优化,但是机器学习中又常用到这些工具和技巧,机器学习中最常见的优化当属凸优化了,这些可以参考Ng的教学资料:http://cs229.stanford.edu/section/cs229-cvxopt.pdf,从中我们可以大致了解到一些凸优化的概念,比如凸集,凸函数,凸优化问题,线性规划,二次规划,二次约束二次规划,半正定规划等,从而对凸优化问题有个初步的认识.以下是几个重要相关概

统计学习笔记之支持向量机

支持向量机(SVM)是一种二分类模型,跟之前介绍的感知机有联系但也有区别.简单来讲,感知机仅仅是找到了一个平面分离正负类的点,意味着它是没有任何约束性质的,可以有无穷多个解,但是(线性可分)支持向量机和感知机的区别在于,支持向量机有一个约束条件,即利用间隔最大化求最优分离超平面,这时,支持向量机的解就是唯一存在的. 首先来看线性可分的支持向量机,对于给定的数据集,需要学习得到的分离超平面为: 以及对应的分类决策函数: 一般而言,一个点距离分离超平面的远近可以表示分类预测的确信程度.如果超平面确定

初译 Support Vector Machines:A Simple Tutorial(二)

(二)Maximum margin hyperplane for linearly separable classes (线性可分的数据的最大间隔分类器) 接上文,假设SVM分类器是由两种线性可分的数据集训练而成,其决定函数(decision function)为:                                     (2.1) 其中为定义该超平面的公式,该超平面对于训练集拥有最大的margin,并且相对于两种训练集的距离相等(见下图) 在本节中,我们会讨论一种一个关于超平面