Day 6
梯度方法
    梯度方法的定义：求取实值函数在Rn上的极小点的方法，在搜索过程中用到了函数的梯度，故称为梯度方法。
    *函数水平集概念复习：参照Day3博文[最优化导论(Machine Learning)集合约束和无约束优化问题的基础数学原理及公式]中函数f: Rn -> R的水平集合指的是能够满足f(x) = c的所有x组成的集合，c为常数，因此，对于点x0 ∈ R，若f(x0)=c 则可称该点是水平为c的水平集合中的元素
    *若函数f在x0处的梯度为▽f(x0)=Df(x)T {此处函数的一阶导数Df为：Df=[∂f/∂x1, ∂f/∂x2, ......, ∂f/∂xn]}不为零向量，那么它与水平集f(x)=c中任意一条经过x0处的光滑曲线的切向量正交(垂直)
    因此，一个实值可微函数在某点处函数值增加最快的方向正交于经过该点的函数水平集(即，在梯度方向上，自变量的细微变动，所导致的目标函数值的增加幅度最大，超过其他的任意方向)
    *函数f在点x处，在其可行方向d上的增长率标记为：<▽f(x), d>, ||d||=1
因为||d||=1，由柯西-施瓦茨不等式{柯西施瓦茨不等式：||<=||x||*||y||}
==><▽f(x), d> = ||▽f(x)|| ||1|| = ||▽f(x)||
若令d=▽f(x)/||▽f(x)||    
则有：[=xTy]
<▽f(x), ▽f(x)/||▽f(x)||> = ||▽f(x)||
        因此，梯度方向▽f(x)就是函数f在x处增加最快的方向
       反之，梯度负方向-▽f(x)就是函数f在x处见效最快的方向
       故梯度负方向搜索可以得出函数的极小点
    *令x(0)作为初始搜索点，并沿着负梯度方向构造一个新点x(0)-å▽f(x(0))可由泰勒定理得出：
f(x(0) - å▽f(x(0))) = f(x(0)) - å||▽f(x(0))||^2+O(å)
所以，如果▽f(x(0)) != 0，那么当å > 0足够小时，有
f(x(0) - å▽f(x(0))) < f(x(0))
成立 即，从搜索目标函数极小点的角度来看，x(0) - å▽f(x(0))相对于x(0)有所下降的改善和趋势
最速下降法(最快下降法)    *根据上述理念，设定一个搜索点x(k)，由此点出发，根据向量-åk▽f(x(k))指定的方向和幅度移动，构造一个新的点x(k+1)，其中åk为一个正实数，称之为步长，由此得到其迭代公式：x(k+1) = x(k) -åk▽f(x(k))这称之为梯度下降法的迭代公式，在搜索过程中，梯度不断变化，当接近极小点时，梯度趋近为0 {▽f(x) = 0 相当于一阶导数斜率为0}    最速下降法是梯度下降法的具现，在每次迭代中选择合适的步长åk，使得目标函数值能够得到最大程度地减小 åk实际上为函数øk(å) = f(x(k) - å▽f(x(k)))的极小点 即，åk = arg min(å>=0) f(x(k) - å▽f(x(k)))    *最速下降法按照如下方法运行，在每步迭代中，从迭代点x(k)出发，沿着负梯度方向 -▽f(x(k))开展一维搜索，直到找到步长的最优值，确定新的迭代点x(k+1)，最速下降法的相邻搜索方向是正交的
[此处为最快下降法迭代点序列特征,各迭代下降方向均正交]
[个人对最快下降法的理解]：类似于跟我们下山一样，在我们下山时，往往不会直接选择下山时坡最陡的地方直接下山(容易滑倒出现危险) 但是此处为下山时速度下降最快的方向，我们选择一个坡度最大，下山方向最快(垂直于某等高线曲线的切线方向)的坡来快速下降
以下系列图表示最速下降法的演示 
Designed By JINZEWEI(MacBook Grapher)
水平集和梯度概念类似于我们大美中国的梯田样式哟！
*截止到此处，各位应该存在疑惑，为什么每一次等高线的下降(或者反向来看为上升)两次相邻的搜索均为正交(垂直)的呢？
此处给出
[命题]：利用最速下降法搜索函数f: R2 -> R的极小点，迭代过程产生的序列为{x(k)}k=0~∞那么x(k+1)-x(k)与x(k+2)-x(k+1)正交垂直于所有的k>=0 均成立
[证明]：由迭代公式可知 ====>
åkåk+1<▽f(x(k)), ▽f(x(k+1))>
所以只需要证明<▽f(x(k)), ▽f(x(k+1))> = 0即可
因为åk为一个非负实数，是函数øk(å)=f(x(k)-å▽f(x(k)))的极小点
因此利用局部极小点的一阶必要条件和链式法则可得
[局部极小点位于约束聚合内的一阶必要条件]：▽f(x*)=0
则有：ø'k(åk)=0 ▽f(x*)=ø'k(å)
==>∂øk/∂å(åk) = ▽f(x(k) - åk▽f(x(k)))T(-▽f(x(k)))
==>-<▽f(x(k+1) ), ▽f(x(k))>
[命题]：利用最速下降法搜索函数f: Rn -> R的极小点，迭代过程产生的序列为{x(k)}k=0~∞，若▽f(x)(k) != 0那么f(x(k+1)) < f(x(k))
[证明]：已知x(k+1)=x(k)-åk▽f(x(k))
其中，åk >= 0是函数 øk(å)=f(x(k)-å▽f(x(k)))的极小点，å>=0，对于所有的å>=0都有øk(åk) <= øk(å)
利用链式法则---->
ø'k(o) = ∂øk/∂å(o) = -(▽f(x(k)-åk▽f(x(k))))T(▽f(x(k))) = -||▽f(x(k))||^2 < 0
因为▽f(x(k))!=0，因此，ø'k(o) < 0，这说明存在一个a>0，对于所有的å属于(0, å]都有øk(o) > øk(å)成立
所以有    f(x(k+1)) = øk(åk) <= øk(a) 
*上述命题说明了梯度下降的特性：只要▽f(x(k))!=0，就有f(x(k+1))
    但是在实际应用中，数值计算的方法很难恰好得到梯度为0的结果，因此▽f(x(k+1))=0并不适合直接作为停止规则
如下给出可以作为停止规则的几种度量方法
(1)利用梯度范数||▽f(x(k))||小于某个阈值时，度量停止
(2)利用计算相邻两个迭代点之间对应的目标函数值之差的绝对值|f(x(k+1))-f(x(k))|小于某阈值ß时停止|f(x(k+1))-f(x(k))| 
(3)利用计算相邻两个迭代点之差的范数小于某阈值ß时停止 ||x(k+1)-x(k)||
(4)利用计算上述停止规则的相对值作为停止规则|f(x(k+1))-f(x(k))|/|f(x(k))|
*将最速下降法应用到二次型函数中，观察其运行情况，目标函数为
f(x) = 1/2xTQx - bTx
其中，Q ∈ Rn*m为对称正定矩阵, b ∈ Rn, x ∈ Rn函数f有唯一极小值，可通过令梯度为0求得，由于D(xTQx)=xT(Q + QT)=2xTQ，D(bTx) = bT故有▽f(x)=Qx-b，Q为对称矩阵是一个不失一般性的假设
后续推论请参考个人笔记：
[二次型的定义,一般来说将二次函数转化为二次型进行矩阵运算即可带入上述迭代公式求取梯度计算]
Final Example 圆，椭圆和课后8.1例题的最速下降法求解函数极小点
1.目标函数为圆的情况 f(x1,x2)=x1^2 + x2^2从任意初始点x(0) ∈ R2出发都可以通过每次迭代求得极小点x*=0 ∈ R2 [梯度最终收敛至=0处即(0,0)点位置]
[此处为便于视觉效果各个水平集梯度有所变更但原理不变]
2.如果目标函数为f(x1,x2)=1/5*x1^2 + x2^2的情况 各水平集均为椭圆的情况最速下降法将原函数转化为二次型后，依次计算梯度。最终最速下降法的迭代路径则不断的在类似视为狭窄山谷谷底方向内来回往复，形成锯齿状迭代状态，迭代效率略低
8.1利用最速下降法求解函数f(x1,x2)=x1+1/2x2 + 1/2x1^2 + x2^2 + 3的极小点，初始点为x(0)=0，开展两次迭代并利用解析方法求出该函数的极小点
[详细解答步骤参考下图手写部分]
写在最后          
用一个简单生动的陕西人通俗易懂的例子来深化一下今天的最速下降法概念：
        假如我们身处秦岭72峪的任何一个峪口最高处，要去最低的峪口山谷处找陕西人口口相传的神兽"鸹貔"。但是我们被蒙着眼睛看不到整个峪口的全貌并且不知道自己在哪里，不论走到哪都只知道自己当前所处位置的高度。那么该如何用最快速度找到神兽"鸹貔"呢？要找到"鸹貔"，我们需要走向最低的位置，看不到全貌的我们如何走到最低位置？最简单的策略就是走一步看一步。走一步要解决两个问题：方向和步长，方向决定向哪走，步长决定走多远。如何决定下一步方向呢？最简单的策略就是在当前所处的位置上去感受哪个方向是“最陡”的，最陡向下的方向就是我们下一步要走的方向。决定了方向后该如何选择“步长”？因为我们不知道峪口的全貌，整个秦岭又有很多山峰和山谷，走的步子太大会很冒险，可能错过最低的低谷；走的步子太小又浪费时间，因此我们要根据经验来选择一个适中的步长走下一步。就这样走一步决定一步，一步一步走到最低的低谷，我们就可以找到神兽"鸹貔"，可以简称这个策略就是我们今天介绍的“最速下降法”
参考文献：An Introduction to Optimization (Fourth Edition)
end
AI技术交流 + 兴趣讨论：

	

	

Day 9
初探优化中的拉格朗日问题
关于本节所引用的具体定义请参考之前博文：
最优化导论(Machine Learning)集合约束和无约束优化问题的基础数学原理及公式
最优化导论(Machine Learning)机器学习中所用的基础数学公式总结
感冒好了，鼻炎又犯了唉......    再难受也不拖更......
有约束非线性优化问题之仅含等式约束的优化问题
形如minimize f(x)
            subject to(s.t)    hi(x) = 0, i=1~m
                                        gi(x) <= 0, j=1~p
的该类有约束非线性优化问题的求解方法，其中，x ∈ Rn, f:Rn -> R, hi:Rn -> R, gi: Rn -> R, m < n 利用向量进行表示，可写为如下所示的标准型
            minimize f(x)
            subject to(s.t) h(x) = 0
                                     g(x) <= 0
其中, h: Rn -> Rm, g: Rn -> Rp, 可按照与线性规划类似的方法，定义非线性有约束优化问题的可行点和可行集合
[定义]:满足所有约束条件的点称为可行点，所有可行点组成的集合{x∈Rn: h(x)=0, g(x)<=0}称为可行集 之前提到过，可不失一般性只考虑极小化目标函数的情况，这是因为，极大化问题可以轻易转化为极小化问题
maximize f(x) = minimize -f(x)
问题描述，讨论形如 minimize f(x) subject to(s.t) h(x)=0 一类的优化问题，其中x∈Rn, f:Rn -> R, h:Rn -> Rm, h=[h1, ......, hm]T, m<=n 假定函数h连续可微，即h∈C1。引入如下定理
[定理]: 对于满足约束h1(x*)=0, ......, hm(x*)=0的点x*。如果梯度向量▽h1(x*), ......, ▽hm(x*)是线性无关的，则称点x*为该约束的一个正则点
[即，满足所有约束函数情况下的x*点(h?(x*)=0时) 各个约束函数的梯度 即一阶导数向量[▽h1(x*), ......, ▽hm(x*)]T不可用有限个的其他向量的线性组合所表示出来就是(线性无关)，该点x*唯一，只能表示它自身，所以x*为在该约束上的正则点]
令Dh(x*)为向量h=[h1, h2, ......, hm]T在x*处的雅可比矩阵:
Dh(x*) = [Dh1(x*), Dh2(x*), ......, Dhm(x*)] = [▽h1(x*)T, ▽h2(x*)T, ......, ▽hm(x*)]T
则,当且仅当 rank Dh(x*) = m(即,雅可比矩阵满秩)时,x*是正则点
线性约束的集合h1(x)=0, ......, hm(x)=0, hi:Rn -> R定义的是一个曲面，S={x∈Rn: h1(x)=0, ......, hm(x)=0}如果S上的所有点都是正则点，那么曲面S的维数为n-m
原书典型例题:(优化问题的图解法求解，实际就是在二维坐标系内划分满足约束函数条件的阴影范围)
例题2：令n=3, m=2, 如果S中的所有点都是正则点，那么S是一个一维对象(即R3空间中的一条曲线)
例如，h1(x)=x1, h2(x)=x2-x3^2 则有▽h1(x)=[1,0,0]T, ▽h2(x)=[0,1,-2x3]T可以看出向量▽h1(x), ▽h2(x)在R空间是线性无关的，所以有：
dimS = dim{x: h1(x)=0, h2(x)=0} = n-m = 1
三维建模图像如下所示[可见dimS = 1曲线S是一维的]
[Design by JINZEWEI Used MacbookPro Grapher App]
切线空间和法线空间
[定义]:曲面S上的曲线C，是由t∈(a,b)连续参数化的一组点构成的集合，{x(t)∈S: t∈(a,b)}也就是说，x:(a,b) --> S是连续函数
由曲线的定义可知，曲线上的所有点都满足曲面方程，如果曲线C通过一个点x*，那么必然存在t*∈(a,b)，使得x(t*)=x*
直观上看，可把曲线C={x(t): t∈(a,b)}当作某个点在曲面S上运动时经过点x的路径，x(t)表示在点t时刻的位置
(下图曲线上的点都在曲面上且满足曲面方程)
[Design by JINZEWEI Used MacbookPro Grapher App]
[定义]:如果对于所有的t∈(a,b), 下式都存在的话，那么曲线C={x(t): t∈(a,b)}是可微的
如果对于所有t∈(a,b), 下式都存在的话，那么曲线C={x(t): t∈(a,b)}是二次可微的
[注意：x.(t)和x..(t)均值n维向量，可以把x.(t)和x..(t)分别视为运动路径为C的某个点x(t)在t时刻的速度与加速度，向量x.(t)指向x(t)的瞬时运动方向，因此向量x.(t*)在x*处与曲线C相切]
有了这些准备知识，接下来我们引入切线空间的概念，考虑集合S={x∈Rn: h(x)=0} h∈C1, S就是Rn空间中的一个曲面
[切线空间定义]:曲面S={x∈Rn: h(x)=0}中点x*处的切线空间为集合T(x*)={y:Dh(x*)y=0}
可以看出，切线空间T(x*)是矩阵Dh(x*)的零空间：
T(x*)=N(Dh(x*))
Dh(x*) = [▽h1(x*)T, ......, ▽hm(x*)T]
因此，切线空间也是Rn的子空间
假设x*是正则点，那么切线空间的维数为n-m, m是等式约束hi(x*)=0的数量，切线空间经过原点，但是为了方便起见，切线空间经常描述为一个经过点x*的平面，为此，定义点x*处的切平面为：
TP(x*) = T(x*) + x* = {x+x*: x∈T(x*)}
直观上，曲面中某店出的切线空间，应该是该点出所有切向量的集合，对于曲面中经过某点的曲线，其导数是曲线的切向量，自然也是该曲面的切向量，当x*是正则点时，这一直觉是准确无误的
[曲面S在x*点处的切平面(R3上的切线空间和切平面)]
[R2上的切线空间和切平面]
[Design by JINZEWEI Used MacbookPro Grapher App]
[法线空间定义]:曲面S={x∈Rn: h(x)=0}中点x*处的法线空间N(x*)定义为N(x*)={x法线空间定义Rn: x=Dh(x*)Tz, z∈Rm} 法线空间还可以表示为N(x*)=R(Dh(x*)T) 也就是说，法线空间实际上是矩阵Dh(x*)T的值域，注意，法线空间N(x*)是由向量[▽h1(x*)T, ......, ▽hm(x*)T]张成的子空间
即：
N(x*) = span[▽h1(x*), ......, ▽hm(x*)] =
{x∈Rn :x=z1▽h1(x*), ......, zm▽hm(x*), z1~zm∈Rn}
法线空间包含零向量，当x*是正则点时，法线空间N(x*)的维数为m，按照与切线空间相同的处理方式，把法线空间N(x*)描绘成经过点x*(而不是经过点Rn的原点)的平面更为方便
为此，定义x*处的法平面为：NP(x*)=N(x*)+x*={x+x*∈Rn: x∈N(x*)}
[R3中的法线和法平面如下图所示]
Hint:切线空间与法线空间相互为正交补(由上图可以看出NP空间和TP空间相互垂直)
拉格朗日条件
    拉格朗日定理，即有约束极值问题的一阶必要条件，首先考虑只包含两个决策变量和一个等式约束的优化问题，令h:R2 -> R为约束函数，已知函数定义域中点x处的梯度▽h(x)为与通过该点的h(x)水平集正交，选择点x*=[x1*, x2*]T使得h(x*)=0，且▽h(x*)!=0经过点x*的水平集为集合{x: h(x)=0}可利用曲线{x(t)}在x*邻域内对水平集进行参数化，x(t)为一个连续可微的向量函数x:R -> R2
接下来就可以证明，▽h(x*)和x*(t*)正交，由于h在曲线{x(t): t∈(a,b)}上是常数，即对任意的t∈(a,b)有h(x(t))=0 因此，对于任意的t∈(a,b)有∂/∂th(x(t))=0
利用链式法则，可得出∂/∂th(x(t)) = ▽h(x)Tx(t) = 0
因此，▽h(x*)与x*(t*)正交
如果，x*是f: R -> R2在集合{x: h(x)=0}上的极小点，可以证明▽f(x*)与x*(t*)正交，构造关于t的复合函数:ø(t) = f(x(t)) 该函数在t=t*时取得极小值，根据无约束极值问题的一阶必要条件可知∂ø/∂t(t*)=0
利用链式法则可得:
    0 = ∂/∂tø(t*) = ▽f(x(t*))Tx(t*) = ▽f(x*)Tx(t*)
因此，▽f(x*)与x*(x*)正交，由于x*(t*)与曲线{x(t)}在点x*处相切，因此▽f(x*)与曲线{x(t)}在点x*处正交
*之前证明过，▽h(x*)也和x*(t*)正交，因此向量▽h(x*)与▽f(x*)平行，也就是说，▽f(x*)等于▽h(x*)与一个标量的乘积
[梯度▽f(x*)与曲线{x(t)}在点x*处正交,x*是函数f在曲线上的极小点]
[n=2, m=1时的拉格朗日定理]:假设点x*是函数f:R2 -> R的一个极小点，约束条件是h(x)=0, h:R2 -> R, 那么，▽f(x*)与▽h(x*)平行，即如果▽h(x*)!=0，则存在标量λ*,使得：
▽f(x*)+λ*▽h(x*)=0
λ*为拉格朗日乘子，需要指出的是，该定理对极大化问题maximize也同样成立
[n=2, m=1情况下的拉格朗日定理]
*拉格朗日定理是局部极小点的一阶必要条件，即拉格朗日条件，其中包含两个方程
▽f(x*)+λ*▽h(x*)=0
                    h(x*)=0
注意⚠️：拉格朗日条件时必要条件而不是充分条件
下图给出一些满足拉格朗日条件的点，其中有些点并不是极值点
接下来将特殊情况下的拉格朗日定理推广到一般情况，即f:Rn -> R，h:Rn -> Rm，m <= n
[拉格朗日定理]: x*是f:Rn -> R的局部极小点(或为极大点),约束条件为h(x)=0, h:Rn -> Rm, m <= n如果x*是正则点，那么存在λ*∈Rm，使得
Df(x*) + λ*TDh(x*) = 0T
拉格朗日定理表明，如果x*是极小点，那么目标函数f在该点处的梯度可以表示为关于约束函数在该点处梯度的线性组合
上述定理中的向量λ*称为拉格朗日乘子向量，其组成元素称为拉格朗日乘子
[拉格朗日定理证明]:找出一个λ*∈Rm，使得▽f(x*) = -λ*Dh(x*)即可，也就是说，证明▽f(x*) ∈ R(Dh(x*)T)=N(x*)即可，此处N(x*)是之前定理中所提及的零空间：(切线空间定义内)
根据引理：T(x*)=N(x*)且T(x*)T可知，只要证明▽f(x*) ∈ T(x*)T即可，令y ∈ T(x*)根据之前定理可知，存在可微曲线{x(t): t ∈ (a,b)}使得对于任意的t∈(a,b)有h(x(t))=0和存在t*∈(a,b)满足x(t*)=x*, x*(t*)=y
之后考虑复合函数，ø(t)=f(x(t))易得知t*是该函数的局部极小点，根据无约束局部极小点的一阶必要条件得∂ø/∂t(t*) = 0
之后利用链式法则，有
∂ø/∂t(t*) = ∂f(x(t))/∂t = Df(x*)x*(t*) = Df(x*)y = ▽f(x*)Ty = 0
故，对于任意的y∈T(x*)，有▽f(x*)Ty = 0
因为 y∈T(x*)，所以有▽f(x*) ∈ T(x*) 证毕
*从拉格朗日定理的证明过程可以看出，拉格朗日条件的紧凑形式为▽f(x*)∈N(x*)若不满足该条件，那么x*不是极值点，注意⚠️：正则性是拉格朗日定理的必须假设条件
下图为不满足拉格朗日条件的图像
[Design by JINZEWEI Used MacbookPro Grapher App]
[例题]：考虑约束集合为椭圆f(x)=x1^2 + x2^2的优化问题，试求目标函数
{[x1,x2]T：h(x)=x1^2+2x2^2-1=0}的极值点
目标函数和约束条件函数的梯度分别为:▽f(x) = [2x1, 2x2]T, ▽h(x)=[2x1, 4x2]T
带入拉格朗日条件得出：Dxl(x,λ) = Dx[f(x) + λh(x)] = [2x1+2λx1, 2x2+4λx2]
Dλl(x,λ) = h(x) = x1^2 + 2x2^2 - 1
令Dxl(x,λ) = 0T 和Dλl(x,λ) = 0可以得出如下方程组：
2x1 + 2λx1 = 0 (1)
2x2 + 4λx2 = 0 (2)
x1^2 + 2x2^2 = 1(3)
方程组包含3个未知数，可证明得到，所有可行点都是正则点
根据方程(1)可以得出：x1=0 or λ=-1
当x1=0时，根据方程2和3可得λ=-1/2, x2=±1/(2^1/2)
当λ=-1时，根据方程2和3可得x1=±1 and x2=0
由此求出所有满足拉格朗日极值条件的点:
x(1)=[0, 1/(2^1/2)]T    x(2)=[0, -1/(2^1/2)]T
x(3)=[1, 0]T    x(4)=[-1, 0]T
f(x(1)) = f(x(2)) = 1/2    f(x(3)) = f(x(4)) = 1
因此极小点为x(1), x(2)    极大点为x(3), x(4)
下图为利用图解法求解例题中的极值点表示
[Design by JINZEWEI Used MacbookPro Grapher App]
引伸：为方便描述，引入拉格朗日函数l:Rn*Rm -> R
可利用拉格朗日函数表示局部极小点x*的拉格朗日条件，即，存在一个λ*，满足Dl(x*,λ*) = 0T
拉格朗日函数定义为：l(x, λ) = f(x) + λTh(x)
上述中的求导运算D指的是求解关于变量[xT,λT]的导数
注意⚠️：换句话说，拉格朗日定理给出的必要条件，等价于将拉格朗日方程视为无约束优化问题的目标函数对应的一阶必要条件
令Dxl表示l关于x的导数，Dλl表示l关于λ的导数，对拉格朗日函数求导有：
Dl(x,λ) = [Dxl(x,λ), Dλl(x,λ)] = 0T
此处经手推公式细分:
Dxl(x,λ) = Df(x) + λTDh(x)
Dλl(x,λ) = h(x)T
因此，关于局部极小点x*的拉格朗日条件可以表示为存在λ*，满足
Dxl(x*,λ*) = Df(x*) + λTDh(x*) = 0T    (1)
Dλl(x*,λ*) = h(x*)T = 0T    (2)
即Dl(x*,λ*)=0T 证明拉格朗日条件写为Dl(x*,λ*)=0T时完全可以成立的
通过求解(1)&(2)可以找出所有可能成立的极值点，求解出的这一方程组包括n+m个方程和n+m个未知数
但是需要注意的是，拉格朗日条件是必要而非充分条件，故满足上述方程的点x*不一定是绝对的极值点(与之前图20.12中所展示的一样，存在满足条件，但非极值点的点位)
二阶条件
    由于拉格朗日条件只是必要条件，因此它们只是等式的约束条件下目标函数极值点的候选对象，为判断这些候选点是极大,极小点或者两者皆不是的非满足极值点，下述引申出更强的条件范围更强的二阶充分条件和二阶必要条件
已知f:Rn -> R和h:Rn -> Rm是二次连续可微函数，即f,h ∈ C2,拉格朗日函数为l(x,λ) = f(x) + λTh(x) = f(x) + λ1h1(x) + ,......, λmhm(x)
记L(x,λ)是l(x,λ)关于x的黑塞矩阵:
L(x,λ) = F(x) + λ1H1(x) + ...... + λmHm(x)
其中H(x)为f在x处的黑塞矩阵，Hk(x)是hk，k=1~m在x处的黑塞矩阵
记[λH(x)] =  λ1H1(x) + ...... + λmHm(x) 这样拉格朗日函数写为
L(x, λ) = F(x) + [λH(x)]
[拉格朗日函数的二阶必要条件定理]：设x*是f:Rn -> R在约束条件h(x)=0，h:Rn -> Rm，m <= n，f,h ∈ C2下的局部极小点 如果x*是正则点，那么存在λ* ∈ Rm使得：
1.Df(x*) + λ*TDh(x*) = 0T
2.对于所有的y ∈ T(x*)，都有yTL(x*,λ*)y >= 0
注意⚠️：L(x,λ)在二阶必要条件定理中的作用，与无约束极小化问题中目标函数f的黑塞矩阵F(x)所起到的作用类似，但是需要注意的是L(x*,λ*)>=0仅仅在T(x*)上成立，而不是在整个Rn上成立
[拉格朗日函数的二阶充分条件定理]：函数f,h ∈ C2 如果存在点x* ∈ Rn 和λ* ∈ Rm使得：
1.Df(x*) + λ*TDh(x*) = 0T
2.对于所有的y ∈ T(x*)，y!=0，都有yTL(x*,λ*)y > 0
那么可以说，x*是f在约束条件h(x) = 0下的严格局部极小点
注意⚠️：二阶充分条件定理表明，如果x*满足拉格朗日条件，且L(x*,λ*)在T(x*)上正定，那么x*就是严格意义上的严格局部极小点
参考文献：An Introduction to Optimization (Fourth Edition)
end
AI技术交流 + 兴趣讨论：

	

证明方法

$A\Rightarrow B$就是组合命题“（非A）或B”，经常读作“A当且仅当Ｂ”，“如果Ａ，则Ｂ”、“Ａ是Ｂ的充分条件”或者“Ｂ是Ａ的必要条件”。可以将两个命题组合成等价命题的形式$A\Leftarrow \Rightarrow B$ 读作“A成立，当且仅当B成立”或者“A等价于B”或者“A对于B是充分必要的”



向量与矩阵


  

  
如果方程 $$\alpha_1 a_1+\alpha_2 a_2+·····+\alpha_k a_k=0$$  

  中所有的系数$\alpha_i(i=1,···,k)$都等于0，那么称向量集${\alpha_1,\alpha_2,·····，\alpha_k}$是先行无关的。
  
如果向量集不是线性无关的，那么称其线性相关。
  
如果集合中只包括一个向量0，由于对于任意$\alpha \neq 0$,都有$\alpha 0 =0$,因此，该集合是线性相关的，实际上，所有包含0向量的集合都是线性相关的。
  
如果集合中只包括单个非零向量$\alpha \neq 0$,只有$\alpha=0$s时，才有$a \alpha = 0$成立，因此，该集合是线性相关的。
  
给定向量$\alpha$,如果存在标量$a_1,a_2,·····，a_k$,使得 $$\alpha=a_1 \alpha_1 +a_2 \alpha_2+·····+a_k \alpha_k$$  

  那么称向量$\alpha$为$\alpha_1,\alpha_2,······，\alpha_k$的线性组合。
  
命题2.1向量集${\alpha_1,\alpha_2,······，\alpha_k }$是线性相关的，当且仅当集合中有一个向量可以表示为其他向量的线性组合。
  
令$\nu$表示为$R^n$的一个子集，如果$\nu$在向量的加法和运算以及标量乘积运算下是封闭的，那么成为$\nu$是$R^n$的子空间。
  
假定${\alpha_1,\alpha_2,······，\alpha_k }$是$R^n$中的任意向量，它们所有的线性组合的集合称为${\alpha_1,\alpha_2,······，\alpha_k }$张成的子空间，记为 

   $$span[\alpha_1,\alpha_2,······，\alpha_k ]={\sum_{i=1}^{k}a_i \alpha_i:\alpha_1,\alpha_2,······，\alpha_k \subset R^n}$$  

  对于向量$\alpha$，子空间$span[\alpha]$是由向量$a \alpha$组成，$\alpha$为任意的实数。同样$\alpha$可表示为${\alpha_1,\alpha_2,······，\alpha_k }$的线性组合，则有 $$span[\alpha_1,\alpha_2,······，\alpha_k ,\alpha]=span[\alpha_1,\alpha_2,······，\alpha_k ]$$ ,因此，任意向量集合都能够张成一个子空间。
  
基：给定子空间$V$,如果存在线性无关的向量集合${\alpha_1,\alpha_2,······，\alpha_k } \subset V$使得$V=span[\alpha_1,\alpha_2,······，\alpha_k ,\alpha]$,那么称$\{\alpha_1,\alpha_2,······，\alpha_k \}$是子空间$V$的一组基。子空间$V$中的所有基都包含相同数量的向量，这一数量称为$V$的维数，记为$dimV$.
  
命题2.2  如果$\{\alpha_1,\alpha_2,······，\alpha_k \}$是$V$的一组基，那么$V$中的任意向量$\alpha$可以唯一地表示为 

   $$\alpha=a_1 \alpha_1 +a_2 \alpha_2+·····+a_k \alpha_k$$  

  其中，$a_i \subset R$,$i=1,2,······，k$.
  
矩阵的秩  矩阵A中线性无关列的最大数目成为A的秩，记为$rank A$.可以看出$rank A$正是$span[\alpha_1,\alpha_2,······，\alpha_k ,\alpha]$的维数。
  
命题2.3 以下运算，矩阵A的秩保持不变： 

  1、矩阵A的某个（些）列乘以非零标量 

  2、矩阵内部交换次序 

  3、在矩阵中加入一列，该列是其他列的线性组合。
  
定理2.1方程组$Ax=b$有解，当且仅当 $$rankA=rank[A,b]$$  

  一个非奇异（可逆）的矩阵是一个行列式非零的方阵。假定A是$n \times n$的方阵,A 是非奇异的，当且仅当存在$n \times n$方阵B，使得 $$AB=BA=I_n$$  其中$I_n$是单位矩阵
  
定理2.2 考虑方程$Ax=b$，其中$A \subset R^{m\times n}$且$rank A = m$.可以通过n-m个未知数富裕任意值求解其他未知数来获取$Ax=b$的解。
  
对于$x,y \subset R^n$,定义欧式内积 

   $$<x,y>=\sum_{i=1}^{n}x_iy_i=x^Ty$$  

  内积是一个实值函数$<·，·> R^n \times R^n \rightarrow R$,具有如下性质： 

  1、非负性：$<x,x> \geq0$ 当且仅当$x=0$时，$<x,x> =0$ 

  2、对称性：$<x,y>=<y,x>$  

  3、可加性：$<x+y,z>=<x,z>+<y,z>$  

  4、齐次性：对于任意的$r\subset R$,总有$<rx,y>=r<y,x>$ 
  
特征值与特征向量 

  
  
  
  
设A,B两个n阶矩阵，如果存在n 阶可逆矩阵C使得$C^TAC=B$,则称A与B合同，若$P^{-1}AP=B$则称A与B相似。如果C是正交矩阵$C^T=C^{-1}$,则B与A既相似又合同。



反身性：对于任意方阵A，都对自身合同
对称性
传递性 

 

 

	

Day 8
拟牛顿法总结
前几日因西安连日阴雨，略感冒，延迟至今天更新拟牛顿法   
          
拟牛顿法
    关于之前的牛顿法以及具体推导,请参考 Day 7最优化导论(Machine Learning)牛顿法特辑以及python代码实现
    传统的牛顿法是一种具有较高实用性的优化问题求解方法，若牛顿法收敛，则收敛阶数至少为2，但当目标函数为一般的非线性函数时，牛顿法不能保证从任意起始点x(0)收敛到函数的极小点
    [即，如果初始点x(0)不足够接近极小点，则牛顿法有可能不具有下降特性]
    牛顿法的基本思路是在每次迭代中，利用二次型函数来局部近似目标函数f并求解近似函数的极小点作为下一次迭代，迭代公式为：
    x(k+1) = x(k) - F(x(k))^-1*g(k)
    修正后的牛顿法迭代公式为：
        x(k+1) = x(k) - åkF(x(k))^-1*g(k)
        步长为åk = arg minå>=0 f(x(k) - åF(x(k))^-1*g(k))
    合理的确定步长，使得f(x(k+1)) < f(x(k))通过在方向-F(x(k))^-1*g(k)上进行一维搜索，即可确定åk
    其一维搜索过程实际上就是求一元实值函数øk(å)=f(x(k)-åF(x(k))^-1*g(k))的极小点
*拟牛顿法的思路
    因为牛顿法的缺陷是必须计算黑塞矩阵F(x(k))和求解方程F(x(k))d(k)=-g(k)[即：d(k)=-F(x(k)^-1*g(k)) ]为避免F(x(k))^-1这种矩阵求逆运算，可通过设计F(x(k))^-1的近似矩阵来代替它，这就是拟牛顿法的思路
    F(x(k))^-1的近似矩阵随着迭代的进行而不断更新，使其至少拥有F(x(k))^-1的部分性质，为分析近似矩阵所应该具有的关于F(x(k))^-1的性质，引入等式:
                    x(k+1)=x(k) - åHkg(k)
    
    Hk为n*m阶实数矩阵，å>0为搜索步长，在x(k)处对f进行一阶泰勒展开，并将x(k+1)带入后，可得：
                    f(x(k+1)) = f(x(k)) + g(k)T(x(k+1) - x(k)) + O(||x(k + 1) - x(k)||)
                                    = f(x(k)) - åg(k)THkg(k) + O(||Hkg(k)||å)
当å趋于0时，上式等号右侧的第二项主导第三项，因此，当å较小时，为保证函数f从x(k)到x(k+1)是下降的，必须有g(k)THkg(k) > 0
要保证上式成立，最简单的方法就是保证Hk为正定的
[命题]函数f一阶连续可微f∈C1, x(k)∈Rn, g(k)=▽f(x(k))!=0, Hk是n*n阶对称矩阵，若令x(k+1)=x(k)-åkHkg(k),其中åk=arg minå>=0f(x(k)-åHkg(k))，那么有åk>0, f(x(k+1))(k))
*在拟牛顿法中，构造黑塞矩阵逆矩阵的近似矩阵时，只需用到目标函数的函数值和梯度
*黑塞矩阵的近似
    令H0, H1, H2,......表示黑塞矩阵逆矩阵f(x(k))^-1的一系列近似矩阵，此类矩阵应该满足的条件拟牛顿法的基础
    首先假定目标函数f的黑塞矩阵F(x)是常数矩阵，与x的取值无关，即，目标函数时二次型函数，F(x)=Q，且Q=QT，则有，g(k+1)-g(k) = Q(x(k+1)-x(k))
令 ∆g(k)  g(k+1) - g(k), ∆x(k)  x(k+1) - x(k) 可得出 ∆g(k)  ∆Q*x(k)
记对称正定实矩阵H0作为近似矩阵的初始矩阵
在给定的k下，矩阵Q^-1应该满足:
                    Q^-1∆g(i) = ∆x(i), 0 <= i <= k  
因此，近似矩阵Hk+1应该满足:
                     HK+1∆g(i) = ∆x(i). 0<=i<=k
如果共展开n次迭代，则共产生n个迭代方向∆x(0), ∆x(1), ∆x(2), ......, ∆x(n-1)
由此可得，Hn应该满足的条件为:
                    Hn∆g(0) = ∆x(0)
                    Hn∆g(1) = ∆x(1)        .......以此类推
                    Hn∆g(n-1) = ∆x(n-1)
将其改写为，Hn[∆g(0), ∆g(1), ......, ∆g(n-1)] = [∆x(0), ∆x(1), ......, ∆x(n-1)]
矩阵Q能够满足Q[∆x(0), ∆x(1), ......, ∆x(n-1)] = [∆g(0), ∆g(1), ......, ∆g(n-1)]和Q^-1[∆g(0), ∆g(1), ......, ∆g(n-1)] = [∆x(0), ∆x(1), ......, ∆x(n-1)] 这说明，如果[∆g(0), ∆g(1), ......, ∆g(n-1)]非奇异，那么矩阵Q^-1能够在n次迭代后唯一确定，即：
    Q^-1 = Hn = [∆x(0), ∆x(1), ......, ∆x(n-1)] * [∆g(0), ∆g(1), ......, ∆g(n-1)]^-1
由此得，若Hn能够使的方程Hn∆g(i)=∆x(i), 0<=i<=n-1成立，那么利用，迭代公式x(k+1)=x(k)-åHkg(k), åk=arg minå>=0 f(x(k) - åHkg(k))求解n维二次型优化问题，可得x(n+1)=x(n) - ånHng(n)这与牛顿法迭代公式是一致的，说明一定能够在n+1次迭代中完成求解
    *以上给出了拟牛顿法的基本思路，拟牛顿法的迭代公式为：
        d(k) = -Hkg(k)
        åk = arg minå>=0 f(x(k) + åd(k))
        x(k+1) = x(k) + åkd(k)
其中，矩阵H0, H1, H2, ......为对称矩阵，目标函数为二次型函数时，他们必须满足Hk+1∆g(i)=∆x(i), 0<=i<=k
其中， ∆x(i) = x(i+1) - x(i) = åid(i), ∆g(i) = g(i+1) - g(i) = Q∆x(i)
[定理]：将拟牛顿法应用至二次型问题中，黑塞矩阵为Q = QT = F(x(k))，对于0<=k
        Hk+1∆g(i) = ∆x(i)    0<=i<=k
其中，HK+1=Hk+1T，如果åi != 0, 0<= i <=k，那么d(0), d(1), ......, d(k+1)是Q共轭的
[证明]：采用数学归纳法证明，先证明k=0时，d(0)和d(1)是Q共轭的，由于å0!=0根据拟牛顿法的迭代公式，x(k+1)=x(k)+åkd(k)可得，d(0)=∆x(0)/å0，因此参照公式d(k)=-g(k)Hk有---->
d(1)TQd(0) = -g(1)TH1Qd(0)        [d(0)=∆x(0)/å0]
                   = -g(1)TH1*Q∆x(0)/å0        [矩阵H0~Hn满足Hk+1∆g(i)=∆x(i)]
                   = -g(1)T*H1∆x(0)/å0            [∆g(i)=Q∆x(i)]
                   = -g(1)T*H1∆g(0)/å0
                   = -g(1)T*∆x(0)/å0
                   = -g(i)Td(0)
由于å0>0是函数ø(å)=f(x(0)+åd(0))的极小点，因此，g(1)Td(0)=0，固有d(1)TQd(0)=0共轭证毕
*依上述定理，对于n维二次型问题，拟牛顿法最多经过n步迭代即可解出最优解[注意：从矩阵Hk必须满足的方程来看，矩阵Hk并不唯一确定，因此关于计算矩阵Hk自由不可控，故引申出秩1修正公式在矩阵Hk+1上通过在矩阵Hk上增加一个修正项得出]
*秩1修正公式(单秩对称算法)
    在秩1修正公式中，修正项为åkz(k)z(k)T, åk∈R, z(k)∈Rn, 是一个对称矩阵，近似矩阵更新方程为:
        Hk+1 = Hk + åkz(k)z(k)T
此处注意，rank z(k)z(k)T = rank([z1(k), ......, zn(k)]T[z1(k), ......, zn(k)]) = 1
对称矩阵z(k)z(k)T的秩为1，故称为秩1修正算法(单秩对称算法)
向量积z(k)z(k)T陈伟外积，明显的，若Hk对称，则Hk+1也是对称的
*之后问题可以重新规划为，给定Hk，∆g(k)，∆x(k)之后，确定åk和z(k)使得近似矩阵能够满足之前[黑塞矩阵逆矩阵中给出的近似]条件，即：Hk+1∆g(i)=∆x(i), i=1, ......, k 首先考虑满足条件Hk+1∆g(k)=∆x(k)即：给定Hk, ∆g(k), ∆x(k)前提下，确定适合的åk和z(k)
保证满足：Hk+1∆g(k)=(Hk + åkz(k)z(k)T)∆g(k)=∆x(k)
所以有，z(k) = ∆x(k)=Hk∆g(k) / åk(z(k)T∆g(k))
由此可得，åkz(k)z(k)T = (∆x(k)-Hk∆g(k))(∆x(k)-Hk∆g(k))T / åk(z(k)T∆g(k))^2
得到近似矩阵的中间更新方程为：
    Hk+1 = Hk + (∆x(k)-Hk∆g(k))(∆x(k)-Hk∆g(k))T / åk(z(k)T∆g(k))^2
接下来，将上述等式右侧整理为只与Hk，∆g(k)，∆x(k)有关，为此，在∆x(k)-Hk∆g(k)=(åkz(k)T∆g(k))z(k)两端同时乘以∆g(k)T，可得：
∆g(k)T∆x(k) - ∆g(k)THk∆g(k) = ∆g(k)Tåkz(k)z(k)T∆g(k)
由于åk为标量，∆g(k)Tz(k)=z(k)∆g(k)=åk(z(k)T∆g(k))^2
将其反带入中间的更新方程中，得到最终的更新方程为：
    Hk+1 = Hk + (∆x(k) - Hk∆g(k))*(∆x(k) - Hk∆g(k)) / ∆g(k)T(∆x(k) - Hk∆g(k))
*秩1修正算法步骤：
    1. 令k=0,选择初始点x(0)，任选一个对称正定矩阵H0
    2. 若g(k)=0(∆f(x)) 停止迭代，否则d(k)=-Hkg(k)
    3. 计算：    åk = arg minå>=0 f(x(k) + åd(k))
                       x(k+1) = x(k) + åkd(k)
    4.计算：    ∆x(k) = åkd(k) = åk(-Hkg(k))
                      ∆g(k) = g(k+1) - g(k)
                      Hk+1 = Hk + (∆x(k) - Hk∆g(k))*(∆x(k) - Hk∆g(k)) / ∆g(k)T(∆x(k) - Hk∆g(k))
    5.令 k=k+1，返回第二步
*秩1修正算法是基于方程：Hk+1∆g(k) = ∆x(k) 推导得出
但是希望满足的条件为：Hk+1∆g(i)= ∆x(i),    i = 0, ......, k
*秩1修正算法的缺点：首先该算法产生的矩阵Hk+1并不一定是正定的，这将导致d(k+1)可能不是下降方向，即使对于二次型问题，这种情况仍有可能发生，其次，如果∆g(x)T(∆x(k) - Hk∆g(k))接近于0，在计算Hk+1时可能会有困难
参考文献：An Introduction to Optimization (Fourth Edition)
end
AI技术交流 + 兴趣讨论：