lecture数学基础知识补充

机器学习与数据MachineLearningandData主讲春光模式识别与智能系

专题二：线性模型基本概凸(convex)下降方基本算梯度下降法 最优化问题建模与求解2

minfTxTx

x1,x2,...,xn

Rn f:Rn–如果是最大化问题，则把目标函数加负号、转化为最小化maxfxminf 3寻找一个搜索方向dk ，使得每次迭代时函数值

xk1xkdk

fxk1fxkf(f(x1x20f(x0)f(x0)f(x1)f(x2351x2104如果函数f(x)对于凸优化问题，则每个局部最优解也是全局最5

凸优化问为方便起见，最优化理论中的“最优化”一般是指最小(minimizing)，“凸函数”是指convex函数(下凸函数判断方法定义一阶条件二阶条件：Hessian矩阵为半正定i.e.H2fx复合函数规–S.Boyd:ConvexOptimization,目标函数为凸可行域为凸6初始点、搜索方向7

梯度：增长最快的方向导数：梯度与方向的–8最快下降方寻找最快下降方向等价于如下非问题

minfxTd

dTd–借 不等式f2

fxTd

f2dfx/f29

专题二：线性模型基本概凸(convex)下降方基本算梯度下降法 最优化问题建模与求解根据搜索方向的不同，分为最速下降法(梯度下降法法 伪 最小二乘问最速下降法(Steepestfx 值算最速下降

也称为梯度下降法(GradientDescent)，优点工作量小，缺点当Hessian矩阵2fxk的条件数r 大时

2

minmaxmin特征值的平方根成反2gxfxkfxkTxxkkxxkTxxk2其中k

fxg利用g(x)的最优解x*作为x(k+1)，即得出梯度下降 xk1xk1fk根据搜索方向的不同，分为法 伪 最小二乘问法 法法目标函数要求二次可Taylor确定函数的近似平稳步法二次终止性 法的收敛速 沿 方向函数值一定下降么根据搜索方向的不同，分为法 伪 最小二乘问 与原 法的区增加 方向的一维搜因为含有一维搜索，故每次迭代目标函数 步骤：增加了 方向的一维搜法优点缺点需要计算Hessian矩阵及其逆矩阵 要求Hessian矩阵 根据搜索方向的不同，分为法 伪 最小二乘问动机

克服Hessian矩阵奇异性和不定方法引入矩阵Gk=Hessian+εk只要εk选择合适，则Gk对称正

增加 方向的一维搜索，并引入矩阵法缺点要求Hessian矩阵要可 根据搜索方向的不同，分为法 伪 最小二乘问 用不包含二阶导数的矩阵近 法中的Hessian矩阵的逆矩 迭代中仅需一阶导数，无需计算Hessian当Hk正定时所 量较根据搜索方向的不同，分为法 伪 最小二乘问共轭方向(Conjugate为什么选择共轭方向 小点为何选择共轭梯度方向k易于计算：仅仅利用前一步的下降方向p和当前位置的梯度kpkgk共轭梯度法的基本思

pk

k

gkTApk1pk1TApk 向，并沿这组方向进行搜索，求出目标函数的极小点非线性共轭梯度法被Fletcher&Reeves(1960s)提出，为最早 共轭梯度法的二次终共轭梯度法最多经过有限步(atmostnsteps)对于二次凸函数：FR(Fletcher-Reeves)CG用于一般函数的非线性FRCG于“重置” 量 求解变量多的大规模问题时，可以利用共轭梯度右图中红色路径为共轭梯度绿色路径为梯度下降蓝色路径 根据搜索方向的不同，分为法 伪 最小二乘问最小二乘(LeastSquare)线性最小二乘(LinearLeast根据搜索方向的不同，分为法 伪 最小二乘问基本思想根据搜索方向的不同，分为法 伪 最小二乘问算法的修Q/AnyQuestion?

专题二：线性模型基本概凸(convex)下降方基本算梯度下降法 最优化问题建模与求解从下降方向的定义minfxTd寻找约束条dTd构造有约束最优化minfxTd

s.t.dTd寻找最快下降方向即如下非线性规划问题minfxTd如何求解方法1：借助不等

dTd方法 日乘子法方法 日乘子法寻找最快下降方向等价于如下非问题

minfxTd

dTd–借 不等式f2

fxTd

f2dfx/f2minfxTd

dTd–非凸优化问 Ld,fxTddTd原问题(PrimalProblem)最优性条件dLd,fx2d

d*fx/2*f /2把等式约束放松为不等式约束minfxTd

dTd得到一个不等式约束的凸优化LdfxTddTd原问题(PrimalProblem)最优性条件为

dLd,fx2d带入到辅助函数中，得到对偶问题maxD1fx2

d*fx/*f / 讨论：3种方法的比考虑了目标函数的特殊形式，借助了特定不等日乘子法解决等式约束的最优化问日乘子法解决不等式约束的最优化问Q/AnyQuestion?参考资 StephenBoydandLiewenVandenber