优化方法学习笔记_学习笔记的整理方法
优化方法学习笔记由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“学习笔记的整理方法”。
对偶理论：
原始问题和对偶问题的标准形式如下： 设原始问题为： min z=cx s.t.Ax = 0 则对偶问题为： max w=yb s.t.yA >= c y>=0 式中max表示求极大值，min表示求极小值，s.t.表示“约束条件为”；z为原始问题的目标函数，w为对偶问题的目标函数；x为原始问题的决策变量列向量（n×1），y为对偶问题的决策变量行向量(1×m)；A为原始问题的系数矩阵(m×n)，b为原始问题的右端常数列向量（m×1），c为原始问题的目标函数系数行向量（1×n）。在原始问题与对偶问题之间存在着一系列深刻的关系，现已得到严格数学证明的有如下一些定理。KKT条件介绍：
一般情况下，最优化问题会碰到一下三种情况：（1）无约束条件
这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于极值点。将结果带回原函数进行验证即可。（2）等式约束条件
设目标函数为f(x)，约束条件为hk(x)，形如
0的点可能是
s.t.表示subject to，“受限于”的意思，l表示有l个约束条件。
则解决方法是消元法或者拉格朗日法。消元法比较简单不在赘述，拉格朗日法这里在提一下，因为后面提到的KKT条件是对拉格朗日乘子法的一种泛化。
定义拉格朗日函数F(x)，其中λk是各个约束条件的待定系数。
然后解变量的偏导方程：
......,如果有l个约束条件，就应该有l+1个方程。求出的方程组的解就可能是最优化值（高等数学中提到的极值），将结果带回原方程验证就可得到解。
至于为什么这么做可以求解最优化？维基百科上给出了一个比较好的直观解释。
举个二维最优化的例子：
min f(x,y)
s.t.g(x,y)= c
这里画出z=f(x,y)的等高线（函数的等高线定义：二元函数z = f（x,y）在空间表示的是一张曲面，这个曲面与平面z = c的交线在xoy面上的投影曲线f(x,y)=c称为函数z=f(x,y)的一条登高线。）：
绿线标出的是约束的点的轨迹。蓝线是的等高线。箭头表示斜率，和等高线的法线平行。从梯度的方向上来看，显然有。绿色的线是约束，也就是说，只要正好落在这条绿线上的点才可能是满足要求的点。如果没有这条约束，的最小值应该会落在最小那圈等高线内部的某一点上。而现在加上了约束，最小值点应该在哪里呢？显然应该是在的等高线正好和约束线相切的位置，因为如果只是相交意味着肯定还存在其它的等高线在该条等高线的内部或者外部，使得新的等高线与目标函数的交点的值更大或者更小，只有到等高线与目标函数的曲线相切的时候，可能取得最优值。如果我们对约束也求梯度，则其梯度如图中绿色箭头所示。很容易看出来，要想让目标函数的等高线和约束相切，则他们切点的梯度一定在一条直线上。即：∇f(x,y)=λ（∇g(x,y)-C)，其中λ可以是任何非0实数。
一旦求出λ的值，将其套入下式，易求在无约束极值和极值所对应的点。
这就是拉格朗日函数的由来。（3）不等式约束条件
设目标函数f(x)，不等式约束为g(x)，有的教程还会添加上等式约束条件h(x)。此时的约束优化问题描述如下：
则我们定义不等式约束下的拉格朗日函数L，则L表达式为：
其中f(x)是原目标函数，hj(x)是第j个等式约束条件，λ不等式约束，uk是对应的约束系数。0
j是对应的约束系数，gk是
此时若要求解上述优化问题，必须满足下述条件（也是我们的求解条件）：
这些求解条件就是KKT条件。(1)是对拉格朗日函数取极值时候带来的一个必要条件，(2)是拉格朗日系数约束（同等式情况），(3)是不等式约束情况，(4)是互补松弛条件，(5)、(6)是原约束条件。
对于一般的任意问题而言，KKT条件是使一组解成为最优解的必要条件，当原问题是凸问题的时候，KKT条件也是充分条件。
关于条件(3)，后面一篇博客中给出的解释是：我们构造L(x,λ等于0就必须使得系数u>=0，这也就是条件(3)。,u)函数，是希望L(x,λ,u)
关于条件(4),直观的解释可以这么看:要求得推导而来。
为方便表示，举个简单的例子： 现有如下不等式约束优化问题：
L(x,λ,u)的最小值一定是三个公式项中取得最小值，此时第三项最小就是等于0值的时候。稍微正式一点的解释，是由松弛变量
此时引入松弛变量可以将不等式约束变成等式约束。设a1和b1为两个松弛变量，则上述的不等式约束可写为：
则该问题的拉格朗日函数为：
根据拉格朗日乘子法，求解方程组：
则同样 u2b1=0，来分析g2(x)起作用和不起作用约束。于是推出条件：
KKT条件介绍完毕。
拉格朗日对偶理论：
1.原始问题
假设f(x),ci(x),hj(x)f(x),ci(x),hj(x)是定义在RnRn上的连续可微函数，考虑约束最优化问题：
minx∈Rns.t.f(x)ci(x)≤0,i=1,2,…,khj(x)=0,j=1,2,…,kminx∈Rnf(x)s.t.ci(x)≤0,i=1,2,…,k
hj(x)=0,j=1,2,…,k
称为约束最优化问题的原始问题。现在如果不考虑约束条件，原始问题就是：
minx∈Rnf(x)minx∈Rnf(x)因为假设其连续可微，利用高中的知识，对
f(x)f(x)求导数，然后令导数为0，就可解出最优解很简单.但是问题来了，这里有约束条件，必须想办法把约束条件去掉才行，拉格朗日函数派上用场了。
引进广义拉格朗日函数（generalized Lagrange function）: L(x,α,β)=f(x)+∑i=0kαici(x)+∑j=1lβjhj(x)L(x,α,β)=f(x)+∑i=0kαici(x)+∑j=1lβjhj(x)不要怕这个式子，也不要被拉格朗日的名字给唬住了，让我们慢慢剖析！这里，x=(x(1),x(2),…,x(n))∈Rn,αi,βjx=(x(1),x(2),…,x(n))∈Rn,αi,βj是拉格朗日乘子（其实就是上面函数中的参数而已），特别要求αi≥0αi≥0。
现在，如果把L(x,α,β)L(x,α,β)看作是关于αi,βjαi,βj的函数，要求其最大值，即
maxα,β:αi≥0L(x,α,β)maxα,β:αi≥0L(x,α,β)再次注意L(x,α,β)L(x,α,β)是一个关于αi,βjαi,βj的函数，优化就是确定αi,βjαi,βj的值使得L(x,α,β)L(x,α,β)取得最大值（此过程中把xx看做常量），确定了αi,βjαi,βj的值，就可以得到
L(x,α,β)L(x,α,β)的最大值，因为αi,βjαi,βj已经确定，显然最大值maxα,β:αi≥0L(x,α,β)maxα,β:αi≥0L(x,α,β)就是只和xx有关的函数，定义这个函数为：
θP(x)=maxα,β:αi≥0L(x,α,β)θP(x)=maxα,β:αi≥0L(x,α,β)其中
L(x,α,β)=f(x)+∑i=0kαici(x)+∑j=1lβjhj(x)L(x,α,β)=f(x)+∑i=0kαici(x)+∑j=1lβjhj(x)
下面通过xx是否满足约束条件两方面来分析这个函数: θP(x)=maxα,β:αi≥0[f(x)+∑i=0kαici(x)+∑j=1lβjhj(x)]=+∞θP(x)=maxα,β:αi≥0[f(x)+∑i=0kαic
i(x)+∑j=1lβjhj(x)]=+∞
注意中间的最大化式子就是确定令
αi,βjαi,βj之后的结果，若ci(x)>0ci(x)>0，则αi→+∞αi→+∞，如果hj(x)≠0hj(x)≠0，很 易取值使得βjhj(x)→+∞βjhj(x)考虑xx满足原始的约束，则：
θP(x)=maxα,β:αi≥0[f(x)]=f(x)θP(x)=maxα,β:αi≥0[f(x)]=f(x)→+∞
，注意中间的最大化是确定的αi,βjαi,βj过程，将的最大值就是其本身。
f(x)f(x)看成一个常量，常量
通过上面两条分析可以得出：
θP(x)={f(x),+∞,x满足原始问题约束其他θP(x)={f(x),x满足原始问题约束+∞,其他 那么在满足约束条件下：
minxθP(x)=minxmaxα,β:αi≥0L(x,α,β)=minxf(x)minxθP(x)=minxmaxα,β:αi≥0L(x,α,β)=mi
nxf(x)即minxθP(x)minxθP(x)与原始优化问题等价,所以minxθP(x)minxθP(x)常用代表原始问题，下标 P 表示原始问题，定义原始问题的最优值：
p∗=minxθP(x)p∗=minxθP(x)
原始问题讨论就到这里，做一个总结：通过拉格朗日的办法重新定义一个无约束问题这个无约束问题等价于原来的约束优化问题，从而将约束问题无约束化！
2.对偶问题
定义关于α,βα,β的函数：
θD(α,β)=minxL(x,α,β)θD(α,β)=minxL(x,α,β)
注意等式右边是关于xx的函数的最小化，确定xx以后，最小值就只与有关，所以是一个关于α,βα,β的函数.考虑极大化θD(α,β)=minxL(x,α,β)θD(α,β)=minxL(x,α,β)，即
α,βα,βmaxα,β:αi≥0θD(α,β)=maxα,β:αi≥0minxL(x,α,β)maxα,β:αi≥0θD(α,β)=maxα,β:αi≥0minxL(x,α,β)这就是原始问题的对偶问题，再把原始问题写出来：
minxθP(x)=minxmaxα,β:αi≥0L(x,α,β)minxθP(x)=minxmaxα,β:αi≥0L(x,α,β)
形式上可以看出很对称，只不过原始问题是先固定L(x,α,β)L(x,α,β)中的xx，优化出参数α,βα,β，再优化最优xx，而对偶问题是先固定α,βα,β，优化出最优xx，然后再确定参数α,βα,β。定义对偶问题的最优值：
d∗=maxα,β:αi≥0θD(α,β)d∗=maxα,β:αi≥0θD(α,β)
3.原始问题与对偶问题的关系
定理：若原始问题与对偶问题都有最优值，则
d∗=maxα,β:αi≥0minxL(x,α,β)≤minxmaxα,β:αi≥0L(x,α,β)=p∗d∗=maxα,β:αi≥0minxL(x,α,β)≤
minxmaxα,β:αi≥0L(x,α,β)=p∗
证明：对任意的和，有
θD(α,β)=minxL(x,α,β)≤L(x,α,β)≤maxα,β:αi≥0L(x,α,β)=θP(x)θD(α,β)=minxL(x,α,β)≤L(x,α,β)≤maxα,β:αi≥0L(x,α,β)=θP(x)
即
θD(α,β)≤θP(x)θD(α,β)≤θP(x)
由于原始问题与对偶问题都有最优值，所以
maxα,β:αi≥0θD(α,β)≤minxθP(x)maxα,β:αi≥0θD(α,β)≤minxθP(x)
即
d∗=maxα,β:αi≥0minxL(x,α,β)≤minxmaxα,β:αi≥0L(x,α,β)=p∗d∗=maxα,β:αi≥0minxL(x,α,β)≤
minxmaxα,β:αi≥0L(x,α,β)=p∗
也就是说原始问题的最优值不小于对偶问题的最优值，但是我们要通过对偶问题来求解原始问题，就必须使得原始问题的最优值与对偶问题的最优值相等，于是可以得出下面的推论：
推论：设x∗x∗和α∗,β∗α∗,β∗分别是原始问题和对偶问题的可行解，如果d∗=p∗d∗=p∗，那么x∗x∗和α∗,β∗α∗,β∗都是原始问题和对偶问题的最优解。所以，当原始问题和对偶问题的最优值相等：d∗=p∗d∗=p∗时，可以用求解对偶问题来求解原始问题（当然是对偶问题求解比直接求解原始问题简单的情况下），但是到底满足什么样的条件才能使得d∗=p∗d∗=p∗呢，这就是下面要阐述的KKT 条件。
4.KKT 条件
定理：对于原始问题和对偶问题，假设函数f(x)f(x)和ci(x)ci(x)是凸函数，hi(x)hi(x)是仿射函数（即由一阶多项式构成的函数，f(x)=Ax + b, A是矩阵，x，b是向量）；并且假设不等式约束ci(x)ci(x)是严格可行的，即存在xx，对所有ii有ci(x)
∇xL(x∗,α∗,β∗)=0∇αL(x∗,α∗,β∗)=0∇βL(x∗,α∗,β∗)=0α∗ici(x)=0,i=1,2,…,k(KKT对偶互补条件)ci(x)≤0,i=1,2,…,kα∗i≥0,i=1,2,…,khj(x∗)=0,j=1,2,…,l∇xL(x∗,α∗,β∗)=0∇αL(x∗,α∗,β∗)=0∇βL(x∗,α∗,β∗)=0αi∗ci(x)=0,i=1,2,…,k(KKT对偶互补条件)ci(x)≤0,i=1,2,…,kαi∗≥0,i=
1,2,…,khj(x∗)=0,j=1,2,…,l
关于KKT 条件的理解：前面三个条件是由解析函数的知识，对于各个变量的偏导数为0（这就解释了为什么假设三个函数连续可微，如果不连续可微的话，这里的偏导数存不存在就不能保证），后面四个条件就是原始问题的约束条件以及拉格朗日乘子需要满足的约束。
特别注意当α∗i>0αi∗>0时，由KKT对偶互补条件可知：ci(x∗)=0ci(x∗)=0，这个知识点会在 SVM 的推导中用到.1.总结
一句话，把原始的约束问题通过拉格朗日函数转化为无约束问题，如果原始问题求解棘手，在满足KKT的条件下用求解对偶问题来代替求解原始问题，使得问题求解更加容易。
凸集定义：
凸集的极值点和极值方向：
最优化方法的基本结构：
