(本科）第03章-数学回顾.pdf

(c) 2020，陈强，机器学习及 R 应用，高等教育出版社 1 第第 3 章章 数学回顾数学回顾 3.1 微积分 3.1.1 导数导数 对于一元函数( )yf x，记其一阶导数(first derivative)为dydx或( )fx，其定义为 00()( )( )limlimxxdyyf xxf xfxdxxx (3.1) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 2 几何上，(一阶)导数就是函数( )yf x在x处的切线斜率，参见图 3.1。 图 3.1 导数的示意图 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 3 一阶导数( )fx仍然是x的函数，故可定义( )fx的导数，即二阶导数(second derivative)： 22( )( )dydd ydxfxfxdxdx (3.2) 直观上，二阶导数表示切线斜率(一阶导数)的变化速度，即曲线( )f x的弯曲程度，也称“曲率”(curvature)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 4 3.1.2 偏导数偏导数 对于多元函数12( )( ,)nyff x xxx，其中列向量12()nx xx x，可定义y对于1x的偏导数(partial derivative)为 112111121201( ,)(,)( ,)limnnnxf x xxyxxf xx xxf x xxx (3.3) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 5 将多元函数( )f x的所有偏导数写成一个列向量，即为梯度向量(gradient vector)： 1( )( )( )( )nfxfffxxxxxx (3.4) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 6 由于偏导数1( )yxx依然是12( ,)nx xx的函数，故可进一步求其自身的二阶偏导数， 21211yxyxx (3.5) 以及混合偏导数，比如： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 7 21122yxyx xx (3.6) 在一般情况下 （要求二阶偏导数为连续函数） ， 混合偏导数与求导顺序无关，即 221221yyx xx x (3.7) 将多元函数( )f x的所有二阶偏导数排成一个矩阵，即为黑塞矩阵(Hessian Matrix)： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 8 2222222112221( )( )( )( )( )nnnffffyyxx xyyxxx xxxxxH xxx xx (3.8) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 9 其中，( )f xxx表示对梯度(列)向量的每个分量分别求偏导，并排成一行(故分母为x)。 由于混合偏导数与求导顺序无关，故黑塞矩阵为对称矩阵。 梯度向量与黑塞矩阵在最优化中起着重要作用。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 10 有 时 我 们 需 要 同 时 考 虑 多 个 响 应 变 量 ， 比 如11( ),( )mmyfyfxx，故存在m个函数关系。 可将其写为从向量x到向量y的“向量值函数”(vector-valued function)： ( )yf x (3.9) 其中，1()myyy。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 11 将所有( ) (1,)iiyfimx的梯度向量写为行向量，然后叠放在一起，即可得到雅各比矩阵(Jacobian Matrix)： 1111( )( )nmmnyyxxyyxxf xJ xx (3.10) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 12 3.1.3 方向导数方向导数 偏导数给出了当x沿着某坐标轴(比如1x)变动时，函数( )yfx变化的速率。 有时我们想知道当x沿着任意方向变化时， 函数( )f x的变化率。 任意给定*x， 考虑( )f x在*x处， 沿着任意方向1()nvvv的方向导数(directional derivative)，其中将v的长度标准化为 1，即2211nvvv。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 13 沿着方向v，经过*x的直线方程为 *txxv (3.11) 其中，随着参数tR变化，可得到整条直线。函数( )f x沿着此直线方向的取值可写为 *11( )()(,)nng tftf xtvxtvxv (3.12) 使用链式法则(chain rule)，可得函数( )g t在0t 处的导数，即方向导数： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 14 *1101*1()()()( )()() ()nntnnfffg tvvxxvfffxxvxxxvxxxv (3.13) 方向导数*()f xv是各偏导数*()(1, )jfjnxx的线性组合，而组合的权重为方向v沿着各坐标轴的分量1()nvv。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 15 命题 3.1 梯度向量( )fx为函数( )f x增长最快的方向， 而负梯度方向( )fx为该函数下降最快的方向。 证明：在n维空间n中，记梯度向量*()fx与方向v的夹角为，则根据线性代数知识，此夹角的余弦为 *()cos()ffxvxv (3.14) 由于1v，故沿方向v的方向导数可写为 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 16 *()()() cosfff xxvxv (3.15) 由于1cos1 ，故当cos1(即v的方向与*()fx相同)，方向导数*()()ff xxv(梯度向量的长度)达到最大值。 因此，梯度向量*()fx为在*x处，函数( )f x增加最快的方向，称为“梯度上升”(gradient ascent)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 17 反之，当cos1 (即v的方向与*()fx相反)，方向导数*()()ff xxv(梯度向量长度的负数)达到最小值。 因此，负梯度向量*()fx为在*x处，函数( )f x下降最快的方向，称为“梯度下降”(gradient descent)。 函数( )f x上升最快与下降最快的方向正好相反。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 18 在几何上，应如何想象梯度向量？这可通过函数( )f x的“水平集”(level set)来考察。 任意给定*x，函数( )f x相应的水平集可定义为 *:( )()Cffxxx (3.16) 水平集也称为“等值集”(contour set)；比如，地形图的“等高线”或气压图的“等压线” ，参见图 3.2。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 19 图 3.2 梯度向量与水平集(等值集)正交 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 20 命题3.2 梯度向量*()fx与水平集*:( )()Cffxxx正交。 证明：给定水平集*:( )()Cffxxx。假定 *11( )( ),( )nntxx txx tx (3.17) 为在水平集C上， 经过*x的一条任意曲线。 当0t时，*( ) t xx；而当t变化时，即得到n空间的一条曲线。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 21 根据微积分知识，在*x处，曲线( )tx的切线方向为 1(0)(0)(0)ndxddxdtdtdtx (3.18) 将此曲线方程的表达式(3.17)代入水平集的方程(3.16)，则有 *11( ( )( ),( )()nnftf xx txx tfxx (3.19) 在0t处，将此方程两边对t求导可得： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 22 *11(0)()(0)()0nndxfdxfxdtxdtxx (3.20) 上式可写为 *(0)()0dfdtxx (3.21) 其中，1(0)(0)(0)ndxddxdtdtdtx为曲线( ) tx在*x处的切线方向，而梯度向量*()fx与此切线方向正交(垂直)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 23 由于( )tx为水平集C上的任意曲线， 而它们在*x处的切线方向均与梯度向量*()fx垂直，故在水平集C这一曲面上，通过点*x的一切曲线在点*x处的切线都在同一个平面上， 即水平集C在点*x的切平面。 因此，故梯度向量*()fx与水平集C正交。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 24 3.1.4 向量微分向量微分 在进行最优化时，常需对向量求微分(vector differentiation)。 (1) 线性函数的向量微分规则 对于线性函数y x，其向量微分为()xx。 将此线性函数展开写： 1 122nnyxxxx (3.22) 其中，参数向量12()n 。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 25 由于iiyx，故其梯度向量为 11()()()nnxxxxxx (3.23) 此向量微分的规则类似于对一次函数求导。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 26 (2) 二次型的向量微分规则 对于二次(型)函数y xAx， 其向量微分为()xAxAA xx。特别地，如果A为对称矩阵，则2xAxAxx。 将此二次(型)函数展开写： 11nnijijijya x xxAx (3.24) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 27 其中，二次型的矩阵1111nnnnaaaaA。 考虑对第k个变量kx求偏导。 由于在双重求和式11nnijijija x x中，只有1nkjkjja x x(当ikxx)与1nikikia x x(当jkxx)才包含kx，故 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 28 111111()()nnkjjikijikkknknknnya xa xxxxaaaaxx (3.25) 上式适用于所有1,kn，故共有n个方程。 将这n个方程叠放可得 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 29 11111111111()nnnnnnnnnnnyxyxaaxaaxaaxaaxxAxxAxA xAA x (3.26) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 30 其中，A为矩阵A的转置。 如果A为对称矩阵，则AA，上式可简化为 2xAxAxx (3.27) 对二次型的向量微分类似于对二次函数求导。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 31 (3) 复合函数的向量微分规则 对于复合函数( )yfx z，其向量微分为yfxzzx。 将此复合函数(composite function)展开写： 111( )( ,),( ,)KnKyff x zzx zzx z (3.28) 其中，1( ,)nxxx，而1( ,)Kzzz。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 32 考虑对kz求偏导数。根据微积分的链式法则(chain rule)，此复合函数的偏导数可写为 1111nnkknkkknfxxxyfxfxzxzxzzzfx (3.29) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 33 上式对1,kK 均成立， 将这些方程叠放， 可得梯度向量： 111111nnKnKKxyxfzzzxyfyxfxzxzzxzzx (3.30) 其中，xz为( )x z的雅各比矩阵xz之转置。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 34 上式似乎与一元复合函数的微分规则不同，但如果将上式两边同时转置则有 yf xzxz (3.31) 这意味着，如果将梯度向量定义为行向量，则复合函数的向量微分规则在形式上与一元复合函数相同。 在较早的文献中，为了保持这种形式上的一致，一般将梯度向量定义为偏导数的行向量。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 35 3.2 最优化 3.2.1 一元最优化 机器学习的主要方法为最优化(optimization)， 尤其是最小化问题(minimization)。有时也涉及最大化问题(maximization)，比如最大似然估计(Maximum Likelihood Estimation，简记 MLE)。 最大化问题可等价地写为最小化问题，只要将目标函数加上负号即可： max( )min( )xxf xf x (3.32) 因此，我们主要讨论最小化问题。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 36 考虑以下无约束(unconstrained)的一元最小化问题(参见图3.3)， min( )xf x (3.33) 图 3.3 最小化的示意图 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 37 从图 3.3 可知，函数( )f x在其“山谷”底部*x处达到局部最小值。 在山底*x处，( )f x的切线恰好为水平线，故切线斜率为 0。故一元最小化问题的必要条件为 *()0fx (3.34) 由于此最小化的必要条件涉及一阶导数，故称为一阶条件(first order condition)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 38 直观上， 如果*()0fx，则在*x处增加x可使函数值( )f x进一步下降， 故*()f x不是最小值； 反之， 如果*()0fx，则在*x处减少x可使函数值( )f x进一步下降，故*()f x也不是最小值。因此，在最小值处，必然有*()0fx。 根据同样的逻辑，最大化问题的一阶条件与最小化问题相同，都要求在最优值*x处的切线斜率为 0，即*()0fx，参见图3.4。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 39 图 3.4 最大化的示意图 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 40 最小化问题与最大化问题的区别在于最优化的二阶条件(second order condition)， 即最小化要求*()0fx(函数( )f x在*x处为凸函数)，而最大化要求二阶导数*()0fx(函数( )f x在*x处为凹函数)。 对于最优化的一阶条件与二阶条件，下面给出较为严格的证明。假设( )f x在*x处达到局部最小值，则对于在*x附近任意小的扰动x，都有 *()()f xf xx (3.35) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 41 假设函数( )f x二阶连续可导(twice continuously differentiable)，可将上式右边在*x处进行二阶“泰勒展开”(Taylor expansion)： *21()()()()()2f xxf xfxxfxxx (3.36) 其中，01。将此式代入(3.35)可得“基本不等式”(fundamental inequality)： *21()()()02fxxfxxx (3.37) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 42 上式对任意小的x都成立。 如果0 x ， 在上式两边同除以x， 并求右极限(0 x )可得 *01lim()()()()02xfxfxxxfx (3.38) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 43 反之，如果0 x ，在上式两边同除以x，并求左极限(0 x )可得 *01lim()()()()02xfxfxxxfx (3.39) 综合不等式(3.38)与(3.39)可知，最小化问题的必要条件为*()0fx。将此一阶条件代入基本不等式(3.37)可得： *2()()0fxxx (3.40) 在上式中，由于2()0 x，故 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 44 *()0fxx (3.41) 由于此式对于任意小的x都成立，而二阶导数( )fx假设为连续函数，故最小化的二阶条件要求： *()0fx (3.42) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 45 根据同样的逻辑， “严格局部最小值” (strict local minimum)的充分条件包括：一阶条件*()0fx，二阶条件*()0fx。 如果此一阶条件与二阶条件均成立， 则基本不等式(3.37)取严格大于号()，故*x为严格局部最小值。 同理可证，最大化的二阶条件要求*()0fx。 “严格局部最大值”(strict local maximum)的充分条件包括：一阶条件*()0fx，二阶条件*()0fx。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 46 3.2.2 多元最优化多元最优化 更一般地，考虑以下无约束的多元最小化问题， 12min( )(,)nff x xxxx (3.43) 其中，12()nx xx x。 此最小化问题的一阶条件要求， 在最优值*x处， 梯度向量等于0： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 47 *1*()()()()nfxfffxxxx0 xx (3.44) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 48 假设函数( )f x在*12()nx xx x达到最小值，则一元函数1*2( ,)nf x xx在*11xx达到最小值。故根据一元最小化的一阶条件可得，*1211,()()0nx xxffxxx。由此可知，在最优值*x处，所有的偏导数均等于 0： 12*()()()0nfffxxxxxx (3.45) 多元最大化的一阶条件与此相同。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 49 假设( )fx在*x达到局部最小值，则对于在*x附近任意小的扰动x，都有 *()()ffhxxx (3.46) 其中，0h 为任意小的正数，12()nxxx x为n维空间n的一个方向， 而jx为对jx任意小的扰动，1,jn。 假设函数( )fx二阶连续可导，可将上式右边在*x处进行二阶泰勒展开： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 50 *2*22()1()()()()2fhffhfhh xx(xxxxxxxxx 二次型 (3.47) 其中，01，而二次型2*2()()()fhxxxxx的矩阵为黑塞矩阵22( )fxx在*()hxx处的取值。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 51 将上式代入(3.46)可得基本不等式： *2*22)1()()()02ffhhh (xxxxxxxx (3.48) 在上式中，代入一阶条件*()f x0 x，并消去212h可得 2*2()()()0fhxxxxx (3.49) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 52 根据半正定矩阵的定义(参见下文)，上式要求黑塞矩阵2*2()fhxxx半正定(positive semidefinite)。 由于x为任意的扰动，且假设二阶导函数连续，故最小化的二阶条件要求： 2*2()()()0fxxxx (3.50) 故在最小值*x处，黑塞矩阵2*2()fxx半正定。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 53 几何上， 这要求在*x处， 函数( )fx为凸函数(convex function)。 反之，对于最大化问题，其二阶条件则要求黑塞矩阵2*2()fxx半负定(negative semidefinite)，即函数( )fx在*x处为凹函数(concave function)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 54 3.2.3 约束极值问题：等式约束约束极值问题：等式约束 有时我们还会遇到如下“约束极值”(constrained optimization)问题，比如 1212,12min( ,). .( ,)x xf x xs t g x xb (3.51) 其中， “. .s t”表示“subject to” ，即“可行解” (feasible solutions)受到非线性等式“12( ,)g x xb”的约束。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 55 求解方法之一为“消元法”(elimination)，即根据约束条件，将2x写为1x的函数，然后代入目标函数，将其变为无约束的一元极值问题。 在一定条件下，上述约束条件定义了一个隐函数(implicit function)21()xh x。 对约束条件“12( ,)g x xb”进行全微分可得： 12120ggdgdxdxxx (3.52) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 56 由此可得隐函数21()xh x的导数： 21112dhdxgxdxdxgx (3.53) 将隐函数21()xh x代入目标函数， 可将此二元约束极值问题，转化为一元无约束极值问题： 1111min()( , ()xF xf x h x (3.54) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 57 根据无约束极值的一阶条件可得： 11121()0dF xff dhdxxx dx (3.55) 将表达式(3.53)代入上式可得： 121121( )0dF xffxgdxxgxx (3.56) 另一方面，下式显然也成立： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 58 22220ffxgxgxx (3.57) 定义22fxgx，则方程(3.56)与(3.57)意味着，约束极值问题的一阶条件为 0(1,2)jjfgjxx (3.58) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 59 可通过定义如下“拉格朗日函数”(Lagrangian)来得到上述一阶条件： 12121212,min( , )( ,)( ,)x xL x xf x xbg x x (3.59) 其中，为“拉格朗日乘子”(Lagrange multiplier)，也是优化的变量。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 60 上式可视为针对12( , )x x的无约束优化问题，其一阶条件为 *()()0(1,2)jjjLfgjxxxxx (3.60) *12(,)0Lbg x x (3.61) 其中，方程(3.61)正是原来的约束条件“12( ,)g x xb” 。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 61 方程(3.60)意味着，在最优解*x处，目标函数( )fx的梯度向量与约束条件( )gx的梯度向量平行(二者可能方向相同或相反)， 二者仅相差一个倍数*： *11*22()()()()fgxxfgxxxxxx (3.62) 由于梯度向量与水平集(等值线)正交，故在最优解*x处， (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 62 目标函数( )fx的等值线正好与函数( )gx的等值线 “( )gbx”相切，参见图 3.5。 图 3.5 约束极值问题的一阶条件图示 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 63 拉格朗日乘子有何意义？显然，最优解*12(,)x x为参数b的函数，可写为 *1111( ),( ),( )xx bxx bb (3.63) 将上式代入拉格朗日函数(3.59)可得： 1212( )( ( ),( )( )( ( ),( )L bf x b x bb bg x b x b (3.64) 把上式对b求导数可得： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 64 *12121212120 ()*112211220 ()=0 ()*( )( )( ,) +1L bfxfxgxgxb bg x xbxbxbxbxbfxgxfxgxxbxbxbxb 约束条件一阶条件一阶条件 (3.65) 由于在最优解处，12( )( ),( )L bf x b x b，因此 *11( )( ( ),( )L bf x b x bbb (3.66) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 65 故最优拉格朗日乘子*( )b，等于放松约束条件b对目标函数最优值12( ),( )f x b x b的边际作用(marginal effect)。 如果将约束条件“12( ,)g x xb”视为资源约束(可用资源总量为b)， 则在经济学上可将*( )b解释为资源的 “影子价格”(shadow prices)，反映此资源的重要性或价值。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 66 更一般地，考虑受到m个非线性等式约束的n元最小化问题： 111min( )( ,). .( ),( )nmmff xxs t gbgbxxxx (3.67) 此时，由于有m个约束条件，故须在拉格朗日函数中引入m个拉格朗日乘子1()m： 1,1min( ,)( )( )mmkkkkLfbgx xxx (3.68) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 67 相应的一阶条件为 11( ,)( )( )mmkkkLgfxxx0 xxx (3.69) 1( ,)( )0(1,)mkkkLbgkmxx (3.70) 其中，等式(3.69)包含n方程(因为x为n维向量)，而等式(3.70)包括原来的m个约束条件。 更简洁地，可以定义 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 68 111( ),( )( )mmmbgbgxbg xx (3.71) 则拉格朗日函数可写为 ,min( , )( )( )Lfx x x bg x (3.72) 使用向量微分的规则，一阶条件可写为 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 69 ( , )( )( )Lfx xg x0 xxx (3.73) ( , )( )Lx bg x0 (3.74) 其中，方程(3.73)的( )g xx为( )g x的雅各比矩阵，并使用了复合函数的向量微分规则(将( ) g x视为复合函数)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 70 最优解*(,)x 包含()nm个变量， 须同时满足等式(3.73)与(3.74)，共()nm个方程。 在几何上， 一阶条件(3.73)意味着， 目标函数的梯度向量( )f xx为各约束条件梯度向量( )kgxx的线性组合，而组合权重即为相应的拉格朗日乘子k(反映每个约束条件的重要性)： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 71 111( )( )( )( )mmkkkmggfgxxxxxxxx (3.75) 拉格朗日乘子向量依然可解释为资源约束的影子价格。 例如，拉格朗日乘子1可解释为放松约束条件“11( )gbx”对目标函数最优值的边际作用，以此类推。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 72 二阶条件则要求，在最小值*x处，目标函数( )fx的黑塞矩阵2*2()fxx在约束集:( ) xg xb中半正定。 如果不限制在约束集:( ) xg xb内， 则黑塞矩阵也可以是“不定的” (indefinite)。例如，考虑以下目标函数： 2212( )yfxxx (3.76) 显然，此函数( )fx是不定的，其几何形状为鞍形(saddle)，参见图 3.6。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 73 图 3.6 函数2212yxx的鞍形图像 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 74 从图 3.6 可见，由于函数2212yxx是不定的，故并无最大值或最小值。 但如果加上约束条件“20 x ” ，则函数222121yxxx，故在约束集122( ,):0 x xx (即1x轴)中正定， 并在 “10 x ”处达到最小值。 反之，如果加上约束条件“10 x ” ，则函数222122yxxx ， 故在约束集121( ,):0 x xx (即2x轴)中负定，并在“20 x ”处达到最大值。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 75 对于函数2212yxx， 原点(0, 0)为其 “鞍点” (saddle point)。在此鞍点(0, 0)处，沿着1x的方向，函数2212yxx达到最小值；而沿着2x的方向，则函数2212yxx达到最大值。 在一定条件下，可以证明，约束极值问题(3.67)的最优解*(,)x ，正是拉格朗日函数( , )Lx 的鞍点。具体来说，在鞍点*(,)x 处，沿着x的方向，拉格朗日函数( , )Lx 在*x处达到最大值；而沿着的方向，则拉格朗日函数( , )Lx 在*处达到最小值。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 76 3.2.4 约束极值问题：非负约束约束极值问题：非负约束 在有些优化问题中，要求优化变量x只能取非负值。此时，最小化问题可写为 1min( )( ,). .nff xxs txxx0 (3.77) 对目标函数在最优解*x处进行二阶泰勒展开，依然可得到同样的基本不等式： (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 77 *2*22)1()()()02ffhhh (xxxxxxxx (3.78) 如果*x为“内点解”(interior solution)，即*x0，则上式对于任意方向的x都成立，故一阶条件依然要求梯度向量为0，即*()f x0 x。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 78 如果最优解*x的某个分量*jx发生于“边界”(boundary)，即*0jx ，则为了满足约束条件“x0” ，必有0jx(增量必须为正)。假设其他分量的变动均为 0，即0 ()ixij，则上式可写为 *2*222)1()()02jjjjffhhxhxxx(xxx (3.79) 其中，(0000)jx x。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 79 上式两边同除以0jx，并让0jx可得 *)0(0)jjfxx(x如果 (3.80) 总之 ，对于内点解*0jx ，一阶条件为*)0jfx(x；而对于边界解*0jx ，则一阶条件为*)0jfx(x，参见图 3.7。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 80 图 3.7 非负约束极值问题的一阶条件 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 81 综上所述，要么*)0jfx(x(内点解)，要么*0jx (边界解)，故二者的乘积必然为 0： *)0(1, )jjfxjnx(x (3.81) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 82 上式称为 “互补松弛条件” (complementary slackness conditions)，它意味着，如果*0jx (不等式“*0jx ”取严格大于号，即所谓 “松弛” )， 则不等式*)0jfx(x就必须取等号， 即*)0jfx(x，故此不等式是“紧的”(tight 或 binding)。 反之，如果*)0jfx(x(不等式取严格大于号，处于“松弛”状态)，则不等式*0jx 就必须是紧的，即*0jx 。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 83 由于方程(3.81)对于1,jn均成立，加总这n个方程可得： *1)0njjjffxx(x(xxx (3.82) 由于*)0jfx(x且*0jx ，故求和式(3.82)意味着，每一项*)jjfxx(x均为 0，即方程(3.81)对所有1,jn都成立。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 84 因此，对于非负约束的极值问题，其一阶条件包括以下(21)n个方程： *),0,0ff(x(x0 xxxx (3.83) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 85 3.2.5 约束极值问题：不等式约束约束极值问题：不等式约束 考虑以下更一般的不等式约束极值问题： 1min( )( ,). .( ),nff xxs txxg xb x0 (3.84) 其中，1( )( )( )mggg xxx，而1()mbbb。求解方 法 之 一 为 ， 引 入m个 “ 松 弛 变 量 ” (slack variables)1( ,)msss： 1( )()msssbg x (3.85) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 86 将上式代入目标函数，可将不等式约束变为等式约束： 1min( )( ,). .( ),nff xxs t xxg xsb x0 s0 (3.86) 相应的拉格朗日函数为 , ,min( , )( )( )Lfx s x x bg xs (3.87) 由于存在非负约束x0，故有关x的一阶条件为 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 87 )( )( ),0,Lff(xg x(xg x0 xxxxxx (3.88) 有关拉格朗日乘子的一阶条件依然为约束条件： ( )L bg xs0 (3.89) 由于松弛变量s受到非负约束s0，故有关s的一阶条件为 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 88 ,0,LL 0s ss0ss (3.90) 在 一 阶 条 件 (3.89) 与 (3.90) 中 ， 代 入 松 弛 变 量 的 表 达 式( )sbg x，可将一阶条件简化(消去s)： ( )bg x0 (3.91) 0 (3.92) ( )0 bg x (3.93) 其中，表达式(3.91)就是原来的不等式约束( ) g xb。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 89 表达式(3.92)表明，拉格朗日乘子0，这意味着放松约束条件“( ) g xb”(即增加b)，可行解的集合变大，只会使得最优的目标函数下降或不变(这是最小化问题)。 方程(3.93)也是“互补松弛条件” ，它意味着，要么拉格朗日乘子0(影子价格为 0)，此时可允许“( ) g xb”(资源不必用尽)； 要么拉格朗日乘子0(影子价格为负， 有助于降低目标函数)，此时必须有“( ) g xb”(资源完全用尽)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 90 在上述推导中，松弛变量s仅起到桥梁作用，并不出现于最终的表达式，故也可仍使用原来(不包含s)的拉格朗日函数： ,min( , )( )( )Lfx x x bg x (3.94) 然后直接得到相应的一阶条件： )( )Lf(xg x0 xxx (3.95) )( )0Lf(xg xxxxxx (3.96) x0 (3.97) (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 91 ( )Lbg x0 (3.98) ( )0L bg x (3.99) 0 (3.100) 表达式(3.95)-(3.100)即所谓“Karush-Kuhn-Tucker conditions” ，简记“KKT 条件” 。这些条件刻画了(characterize)不等式约束极值问题(3.84)的最优解*(,)x 。在具体求解时，一般仍需使用某种“迭代算法”(iterative algorithm)。 (c) 2020，陈强，机器学习及 R 应用，高等教育出版社 92 3.2.6 最优化算法最优化算法 机器学习的最优化问题通常没有解析解，故一般需使用迭代算法来逼近最优解。对于最小化问题min( )fxx，迭代算法的最一般公式为 1tttxxx (3.101) 其中，tx为第t步迭代的取值，1tx为第1t 步迭代的取值