数据科学优化方法 课件 第11、12章 坐标下降方法、交替方向乘子方法+附录A 数学基础

数据科学优化方法Optimization

Method

in

Data

Science第11章坐标下降方法11.1随机坐标下降方法11.2加速随机坐标下降方法11.3循环坐标下降方法11.4求解可分正则最优化问题的随机坐标下降方法引入？坐标下降（CD）方法是一种非梯度优化方法.基本思想是通过求解一系列简单的子问题达到最终优化目标函数的目的

方法每次迭代时，在当前迭代点处沿一个坐标轴方向进行一维搜索，以求得目标函数在该方向的局部极小点.

坐标下降方法广泛应用在统计和机器学习领域.引入本章前三节考虑如下的无约束最优化问题

其中，为光滑凸函数.有时还需要具有强凸性，即存在常数使得（11.1）（11.2）设

,若对于任意的和,有则称为目标函数的分量Lipschitz常数.(11.3)定义11.1分量Lipschitz常数引入基于方法收敛性分析的需要，定义以下几种Lipschitz常数.设为函数的分量Lipschitz常数，则称为的坐标Lipschitz常数.定义11.2坐标Lipschitz常数(11.4)标准的Lipschitz常数满足如下不等式由矩阵范数与迹的关系，可以得到假设1为Lipschitz连续可微的凸函数，且在集合

上可以取得极小值.存在有限值,使得由定义的的水平集是有界的，即(11.5)引入第11章坐标下降方法11.1随机坐标下降方法11.2加速随机坐标下降方法11.3循环坐标下降方法11.4求解可分复合最优化问题的随机坐标下降方法随机坐标下降方法随机坐标下降算法的基本原理随机选择的一个分量作为迭代方向一种最简单的情形是从中等概率随机抽取2.更新变量随机坐标下降方法算法11.1：随机坐标下降方法给定初始点，若满足终止准则，则停止迭代从中等概率随机抽取下标计算,转至步骤2.随机坐标下降算法的收敛性假定假设1成立，且为光滑凸函数,最优值为,算法11.1中步长，则对任意，有进一步，若目标函数是强凸函数，则对任意，有

定理11.1随机坐标下降方法(11.6)(11.7)注：符号表示关于随机下标取期望，表示关于所有随机下标取期望.随机坐标下降方法设是一个光滑函数，则对任意两点，有引理4.1.光滑函数的性质1证明：由引理4.1可得随机坐标下降方法上式两边关于随机下标取期望，可得上式两边同时减去，然后关于随机下标

取期望，可得随机坐标下降方法(11.8)令，结合Cauchy-Schwarz不等式，可得(11.9)由于为凸函数，故对于任意有(11.10)后一个不等式成立是因为，故属于(11.5)定义的集合.式子（11.10）两边关于所有随机下标取期望，有随机坐标下降方法将上式代入（11.9），整理得因此上式两边关于求和，可得从而（11.6）成立.随机坐标下降方法设为定义在非空开凸集上的可微函数，则为上的强凸函数当且仅当,有强凸函数一阶判定条件若

是强凸函数，将（11.2）两边关于

取极小值，令，

可得由此得到随机坐标下降方法两边关于所有随机下标取期望，然后代入(11.8)，可得若上述证明中步长更改为更加精细的步长，如，定理11.1的结论同样成立随机坐标下降方法若上述证明中步长更改为更加精细的步长，如，定理11.1的结论同样成立收敛速度的比较随机坐标下降方法(11.11)考虑函数为光滑凸函数的情形.

当负梯度下降法步长取时，由推论（4.1），负梯度方法的收敛速度为当随机坐标下降方法步长取时，随机坐标下降方法的收敛速度为收敛速度的比较随机坐标下降方法由于，因此随机坐标下降算法的收敛速率一般慢于负梯度算法！只有当上述不等式成立时，才具有相同的速度.

直观的解释是只使用梯度的一个分量进行更新会降低收敛速度.随机坐标下降方法有放回vs无放回随机坐标下降方法除了从中有放回的抽取将要更新的下标，另一种自然的想法是无放回抽样:将次连续迭代视为一期（epoch）,每一期的迭代方向为的一个随机重排，这样每一期遍历更新全部的坐标然后继续下一轮.第11章坐标下降方法11.1随机坐标下降方法11.2加速随机坐标下降方法11.3循环坐标下降方法11.4求解可分正则最优化问题的随机坐标下降方法加速随机坐标下降方法假设已知强凸参数和分量Lipschitz常数算法11.2：加速随机坐标下降方法给定初始点，，，若满足终止准则，则停止迭代.求解二次方程,为该方程的最大根，令,.4.计算.加速随机坐标下降方法假设已知强凸参数和分量Lipschitz常数算法11.2：加速随机坐标下降方法5.从中等概率随机抽取，令6.计算.7.计算.8.,转步2.注：加速随机坐标下降方法的迭代方向结合了新梯度信息和历史迭代方向.将上述算法中的全部替换为，算法依然有效.加速随机坐标下降方法假定假设1成立，且问题（11.1）中的为光滑,

强凸函数,令则对任意有

（11.12）（11.13）定理11.2加速随机坐标下降方法注：当为强凸函数时，随着迭代次数的增加，不等式（11.12）右边的第一项逐渐占据主要地位，因此加速随机坐标下降算法的速度更快.对于一般的凸函数,（11.13）也成立.对比随机坐标下降算法收敛速度由

提升到了.第11章坐标下降方法11.1随机坐标下降方法11.2加速随机坐标下降方法11.3循环坐标下降方法11.4求解可分正则最优化问题的随机坐标下降方法循环坐标下降方法循环坐标下降方法中每次迭代的下标是按照顺序循环产生的，例如（11.14）循环坐标下降方法记循环轮数为，表示第T次循环下的第k个迭代点.算法11.3：循环坐标下降方法给定初始点，.若满足终止准则，则停止迭代.令.按照（11.14）生成.5.计算.6.令7.，转至步骤2.循环坐标下降方法设问题（11.1）中为光滑函数,算法11.3的步长取为,则对于任意的有引理11.1（11.15）循环坐标下降方法证明：由的光滑性和可知，对于任意的有于是（11.16）对(11.16)两边关于从到求和，可得（11.17）循环坐标下降方法由于，故对任意，有从而循环坐标下降方法因此，对任意，有循环坐标下降方法对最后一个不等式两边关于从到求和，可得将上式代入式（11.17），即可得到式（11.15）.循环坐标下降方法假定假设1成立，问题（11.1）中的是凸函数，算法（11.3）的步长

，则对任意，有

引理11.2（11.18）循环坐标下降方法证明：由的凸性可知，对于任意的，有于是,由Cauchy-schwarz不等式可得整理得到将上式代入式（11.15），便可得到式（11.18）.循环坐标下降方法设为非负实值序列且对于某些整数和有则对任意的有引理11.3循环坐标下降方法证明：对任意，有最后一个不等号成立是因为是单调非增序列.由此可得循环坐标下降方法假定假设1成立，问题（11.1）中的为光滑凸函数,算法11.3的步长，则对任意的，有进一步，若是还是强凸函数，则对任意，有定理11.3（11.19）（11.20）循环坐标下降方法证明：由的光滑性，有因为，故由上式可得又由引理11.2，可知令，则由引理11.3可得到式(11.19).循环坐标下降方法若是强凸函数，将(11.2)两边关于取极小值，可得（11.21）结合式(11.21)和引理11.1，可得循环坐标下降方法从而由此得到式（11.20）.循环坐标下降方法注：在实际应用中，可以被替换为其他取值更大的量，只需其满足条件（11.3）

和（11.4）即可.不同的

会得到不同的收敛速度，例如当时，式（11.19)的上界变为收敛速度的比较循环坐标下降方法考虑函数为光滑凸函数的情形.

当负梯度下降法步长取，迭代次数

负梯度方法的收敛速度为当循环坐标下降方法步长取，约为负梯度方法上界的倍！第11章坐标下降方法11.1随机坐标下降方法11.2加速随机坐标下降方法11.3循环坐标下降方法11.4求解可分复合最优化问题的随机坐标下降方法本节考虑如下最优化问题

（11.22）（11.23）其中常见的可分正则化函数包括范数：等.其中为光滑、强凸函数，是正则函数、凸函数，可能是非光滑的，为正则化参数.假设是可分的，即求解可分复合最优化问题的坐标下降方法求解可分复合最优化问题的坐标下降方法算法11.4：求解可分正则最优化问题(11.22)的随机坐标下降方法的计算步骤给定初始点，若满足终止准则，则停止迭代从中等概率随机抽取下标计算

.计算

，转至步骤2.求解可分复合最优化问题的坐标下降算法用近端算子描述，步骤4可以简写为当正则化项不存在时，上述公式退化为普通的随机坐标下降方法.

在第步迭代中，步骤4中子问题是这样形成的：在当前迭代点处沿第个坐标轴方向对目标函数进行线性近似，并增加一个权重为

的二次项以及正则项.该子问题等价于求解可分正则最优化问题的坐标下降算法对于可分复合最优化问题（11.22），设是光滑、强凸函数,为可分凸函数，且目标函数只在达到极小值，算法11.4中,则对于任意的有定理11.4（11.24）注：当为凸但非强凸函数时，可得到类似于式（11.6）的结论.求解可分复合最优化问题的坐标下降算法证明：由于是强凸函数，是可分凸函数，故是凸函数，且满足（11.25）定义函数函数关于是可分的，且在点处达到极小，其中

是算法11.4中第4步子问题的解。由式（11.2），有求解可分复合最优化问题的坐标下降算法两边关于取极小值，可得其中第三个不等式由（11.25）得到，令，便得到最后一个不等式.（11.26）求解可分复合最优化问题的坐标下降算法由的定义和算法11.4的迭代过程，可得等式两边关于下标取期望，可得求解可分复合最优化问题的坐标下降算法上式两边同时减去，并结合(11.26)，有求解可分复合最优化问题的坐标下降算法两边关于随机下标取期望，可得由此推出(11.24).

求解可分复合最优化问题的坐标下降算法例11.1考虑如下Lasso问题（11.27）其中,,，正则化参数

.求解可分复合最优化问题的坐标下降算法解：应用随机坐标下降方法，设第步抽到下标，求解关于分量的极小化问题其中为软阈值函数.其中，以及.经整理，可得的迭代公式数据科学优化方法Optimization

Method

in

Data

Science第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验引入？交替方向乘子方法（ADMM）是一种求解可分凸优化问题的重要方法.ADMM方法将原始问题分解为若干个可以求解的子问题，并行求解每一个子问题，从而得到原问题的解.

ADMM方法可用来求解大规模优化问题第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验

考虑等式约束的凸优化问题方法基础其中，,为凸函数.（12.1）s.t.方法基础12.1.1对偶上升方法12.1.2增广Lagrange函数和乘子方法对偶上升方法问题（12.1）的Lagrange函数以及相应的对偶函数分别为其中为Lagrange乘子或对偶变量.（12.1）的对偶问题为（12.2）对偶上升法求解原理由对偶原理，当为严格凸函数时，原问题（12.1）与对偶问题（12.2)同解,即其中对偶上升方法由此推出对偶上升方法的第步迭代公式（12.3）（12.4）其中为步长.(12.3)是的极小化步，（12.4）是对偶变量的更新步.在合适步长下，对偶函数将随着迭代进行而逐渐上升，即，故该方法被称为对偶上升.定义，则对偶上升方法对偶上升方法的收敛性如果步长选择合适,可以证明在一定条件下，与分别收敛到原问题与对偶问题的最优解.对偶上升方法存在的问题对偶上升法的收敛条件在实际中难以满足，因此对偶上升方法经常无法使用。例如，当为仿射函数时，对于大部分，Lagrange函数关于无下界，从而导致最小化步失效.对偶上升方法对偶分解考虑可分目标函数其中，为的子向量.令，得，Lagrange函数为对于可分的目标函数，对偶上升方法很容易实现并行化对偶上升方法由Lagrange函数的可分性可以得到如下并行迭代公式上述对偶上升方法也被称之为对偶分解（DualDecompositon）方法.（12.5）（12.6）对偶上升方法对偶分解方法的一次迭代包括“广播”和“收集”两步广播步：每一个节点利用“广播”得到的，执行的极小步（12.5）并上传本地结果.收集步：中央服务器利用收集的信息更新得到新的对偶变量.方法基础12.1.1对偶上升方法12.1.2增广Lagrange函数和乘子方法增广Lagrange函数和乘子方法问题（12.1）的增广Lagrange函数为其中为惩罚参数，为标准的Lagrange函数.（12.7）（12.1）s.t.增广Lagrange函数和乘子方法该问题的对偶函数为称为增广对偶函数.增广Lagrange函数可以视为如下最优化问题的Lagrange函数.由于任意可行解都满足，故该问题等价于原问题（12.1）. s.t.（12.8）增广Lagrange函数和乘子方法对问题（12.8）应用对偶上升法可得如下迭代公式（12.9）（12.10）该方法称为乘子方法.增广Lagrange函数和乘子方法乘子方法和对偶上升方法的区别乘子方法在极小化步使用的是增广Lagrange函数在对偶变量的更新公式中，乘子方法使用惩罚参数代替步长，不再随迭代的进行逐渐增大乘子方法相比于对偶上升法收敛条件更一般，允许目标函数取值正无穷或非严格凸等.增广Lagrange函数和乘子方法乘子方法步长的解释由KKT条件可知，问题（12.1）的最优解满足下式其中为对应的Lagrange乘子，由于极小化,于是有乘子方法在迭代过程中始终满足KKT条件的第一个等式.随着迭代进行逐渐趋于，从而满足等式约束，进而得到问题（12.1）的最优解.增广Lagrange函数和乘子方法乘子方法的优点乘子方法相比于对偶上升算法在收敛性上有了极大的改善二次惩罚项的引入会使得增广Lagrange函数不再可分，从而导致的极小化步难以并行化.乘子方法的不足第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验本节考虑如下的等式约束优化问题ADMM方法的一般形式和理论性质（12.11）其中为优化变量，，，和均为凸函数.注：本节考虑的优化问题中，优化变量与目标函数都拆分成了两部分.

ADMM方法的一般形式和理论性质12.2.1迭代公式12.2.2收敛性分析12.2.3最优性条件

12.2.4终止准则12.2.5惩罚参数的选择迭代公式问题（12.11）的增广Lagrange函数为由此得到乘子方法的迭代公式ADMM方法将联合优化改为交替优化，迭代公式为（12.12）（12.13）（12.14）（12.15）（12.13)、（12.14）、（12.15）分别称为极小化步、极小化步式和对偶变量更新步.迭代公式ADMM迭代公式标准化形式定义原始残差则原Lagrange函数可以改写为由此得到ADMM迭代公式的标准化形式（12.16）（12.17）（12.18）迭代公式例12.1考虑经典Lasso问题其中，,正则化参数.迭代公式解：先将Lasso问题改写成如下的约束最优化问题其中，.应用（12.16）-（12.18）可得如下ADMM迭代公式（12.19）迭代公式如果，可利用Shermann-Morrision-Woodbury公式计算.ADMM方法的一般形式和理论性质12.2.1迭代公式12.2.2收敛性分析12.2.3最优性条件

12.2.4终止准则12.2.5惩罚参数的选择收敛性分析假设1

和为正

常闭凸函数.假设2

Lagrange函数至少有一个鞍点.假设1成立的充要条件是和的上图为非空闭凸集.该假设蕴含着更新步式（12.16）和（12.17）可解.若假设2成立,则存在使得由此可知，为原问题（12.11）的解，为对偶问题的最优解，且原问题和对偶问题的最优解相等.收敛性分析假定假设1和假设2成立，则ADMM方法具有如下收敛结果：残差收敛.，其中目标函数值收敛.其中表示最优化问题（12.11）的最优值.对偶变量收敛.定理12.1下面先证明三个引理，然后推出定理12.1结论.收敛性分析假定假设1和假设2成立，设为的一个鞍点,则有

（12.20）引理12.1收敛性分析证明：由于是的一个鞍点，可得由假设1可知取有限值，由此可推出(否则).于是又因为，故.

综上可得收敛性分析假定假设1成立，则有

引理12.2(12.21)收敛性分析由于，将带入上式，整理得由此知是极小值点.证明：由ADMM方法的迭代公式可知，是的极小点.因为和都是正常闭凸函数，故为的极小点的充要条件为收敛性分析于是有(12.22)同理，有将带入上式，整理可得说明是的极小点，由此得到(12.23)将（12.22）和（12.23）相加，利用整理后化简得到（12.21）.收敛性分析假定假设1和假设2成立，定义李雅普洛夫函数（Lyapunovfunction）则有引理12.3(12.24)收敛性分析证明：将不等式（12.20）和（12.21）相加，然后将得到的不等式两边同乘2，整理得(12.25)(12.24)可由（12.25）改写得到.首先改写（12.25）的左边第一项.利用，改写得将带入前两项，可得整理后得(12.26)收敛性分析接下来改写（12.25）的剩余项，即其中来自（12.26).将代入最后一项，整理得进而有将上式和（12.26）应用到（12.25），结合的定义，可得(12.27)收敛性分析为了证明（12.24）成立，只需证明（12.27）右边的交叉项

非正.由引理12.2的证明过程可知是

的极小值点，是的极小值点.

由此可得将上述两个不等式相加可得将带入上式，得到

引理12.3得证.收敛性分析假定假设1和假设2成立，则ADMM方法具有如下收敛结果：残差收敛.，其中目标函数值收敛.其中表示最优化问题（12.11）的最优值.对偶变量收敛.定理12.1收敛性分析证明：由引理12.3可知，序列单调递减，又因为，故序列和均有界，对（12.24）两边关于求和，有由此可得，，进一步有.

另一方面由于，，故由引理12.1可知，由引理12.2知，从而可得.收敛性分析注：ADMM方法只证明能保证收敛到最优值，并不能保证迭代点列会收敛到全局最优解.ADMM方法收敛速度较慢，但是在大部分问题可以以一个较快速度给出中等精度解.

定理对目标函数和约束的要求可以适度放宽.ADMM方法的一般形式和理论性质12.2.1迭代公式12.2.2收敛性分析12.2.3最优性条件

12.2.4终止准则12.2.5惩罚参数的选择最优性条件问题（12.11）是凸优化问题，点为该问题极小点当且仅其当满足一阶最优性条件（KKT条件）其中式(12.28)表示原始问题可行条件，(12.29)和（12.30）表示对偶可行条件.(12.28)(12.29)(12.30)最优性条件由于是的极小点，故有即在迭代过程中迭代序列始终满足（12.30）.最优性条件

由于为的极小点，故有上式等价于因此，可以视为对偶条件式（12.29）的残差，称为对偶残差.最优性条件

问题（12.11）的最优性条件有三个.ADMM方法产生的序列满足最后一个条件.另外两个条件分别等价于随着迭代次数，原始残差

和对偶残差趋于.这两点在定理12.1中得到证明.ADMM方法的一般形式和理论性质12.2.1迭代公式12.2.2收敛性分析12.2.3最优性条件

12.2.4终止准则12.2.5惩罚参数的选择终止准则

由最优性条件的分析可以给出如下的终止准则终止准则其中与分别为原始可行条件（12.28）与对偶可行条件（12.29）的阈值.这两个阈值可以通过绝对准则和相对准则来确定，如其中和分别表示相对阈值和绝对阈值，为约束变量的个数，是优化变量的维度。ADMM方法的一般形式和理论性质12.2.1迭代公式12.2.2收敛性分析12.2.3最优性条件

12.2.4终止准则12.2.5惩罚参数的选择惩罚参数选择

为了提高方法的收敛性，减少对于惩罚参数取值的依赖性，实践中通常会采用变惩罚参数.

当较大时，违反原始可行条件会带来较大惩罚，因而产生较小的原始残差

当较大时，对偶残差变大惩罚参数选择

为了实现残差和能够快速收敛到0，可以采用如下设置其中，为参数，常取，

注：使用可变惩罚参数时,标准化对偶变量，需要在更新后重新标准化.第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验一致性问题12.3.1全局一致性问题12.3.2一致性问题的一般形式

考虑以单一优化变量的若干函数和为目标函数的最优化问题全局一致性问题（12.31）其中，为凸函数，称为局部损失函数.

全局一致性问题

全局一致性问题的定义为了实现分布式计算，可以改写原问题为如下约束优化问题其中被称为局部变量，被称为全局变量.由于约束条件是所有局部变量等于全局变量，因此该问题被称为全局一致性问题.s.t.（12.32）全局一致性问题该问题的增广Lagrange函数为ADMM方法的迭代公式为（12.33）（12.34）（12.35）全局一致性问题令，和，则（12.34）和（12.35）可以改写为（12.36）（12.37）将（12.36）代入式（12.37）得，意味着全局一致性问题全局一致性问题①②③④⑤全局一致性问题带正则项的全局一致性问题在问题（12.32）目标函数的基础上增加正则项，就可得到带正则项的全局一致性问题s.t.（12.38）全局一致性问题ADMM方法迭代公式其标准化形式为（12.39）（12.40）（12.41）全局一致性问题全局一致性问题例12.2机器学习领域的很多问题可归结为如下无约束最优化问题（12.42）其中变量，为特征矩阵，为输出向量，为凸损失函数，为凸正则函数.

全局一致性问题其中为第个样本的损失函数，为第个样本的特征向量，为第个样本的输出向量.通常假设正则函数也是可加的，例如取1或2

范数.

假设损失函数是可加的，例如于是有全局一致性问题解：考虑样本量远大于样本维度的情形.可以通过分割数据集，并将分割后的数据集分给多个节点进行分布式优化以提高效率.先将特征矩阵和输出向量按行划分为份其中，，表示第i个子数据集.全局一致性问题将问题（12.42）改写为如下一致性问题由（12.39）-（12.41）得到该问题的标准迭代公式s.t.（12.43）全局一致性问题当，时,（12.42）变成了Lasso问题，此时ADMM标准化迭代公式为全局一致性问题①②④⑤③一致性问题12.3.1全局一致性问题12.3.2一致性问题的一般形式

一致性问题的一般形式考虑一致性问题的一般形式其中，，(表示元素个数)。其中允许有重叠。为了简便，记为

，称为局部变量，定义局部变量下标到全局变量下标的映射局部变量与全局变量一致等价于（12.44）一致性问题的一般形式定义，满足，则一致性问题（12.44）可改写为如下约束最优化问题（12.45）该问题的增广Lagrange函数为一致性问题的一般形式ADMM迭代公式为（12.46）（12.47）（12.48）

一致性问题的一般形式（12.49）其中即为与对应的局部变量数量。于是的更新结果为所有与对应的的平均值。将（12.49）代入（12.48）可得由于全局变量的更新公式可分，故式（12.47）可改写为分量形式一致性问题的一般形式由此可知，(12.47)时对全局变量的每个分量进行局部平均，而非全局平均.于是（12.47）进一步简化为一致性问题的一般形式通过在问题（12.45）目标函数的基础上增加正则项，可得到带正则项的一致性问题s.t.（12.50）ADMM方法的迭代公式推导留作课后练习.第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验共享问题是另一类常见的无约束最优化问题.

该问题的一般形式如下共享问题（12.51）其中，为局部损失函数，为个优化变量和的函数，称为共享目标函数.共享问题的目标是通过调整的值极小化局部损失函数与共享目标函数的和.共享问题将问题（12.51）改写为约束最优化问题形式其中.ADMM方法的标准迭代公式为其中s.t.（12.52）（12.53）（12.54）（12.55）共享问题现关注（12.54），令，则（12.54）等价于求解如下约束最优化问题s.t.（12.56）共享问题固定，关于极小化目标函数，可得其中.s.t.（12.56）（12.57）共享问题通过极小化的目标函数其中，，.式（12.58）表明对偶变量均相等，故可替换为统一变量表示.即可得到的更新值.将（12.57）应用在上，带入（12.55）得（12.58）共享问题共享问题的ADMM最终迭代公式为（12.59）（12.60）（12.61）在实际应用中，更新步(12.59)可由个节点并行执行，将更新后的上传到中心服务器，由中心服务器计算得到、和，再将其传给个节点.共享问题共享问题的ADMM最终迭代公式为（12.59）（12.60）（12.61）共享问题①②③④共享问题（12.42）例12.3考虑最优化问题（12.42），数据集具有特征维度远大于样本量的高维特性.（此情形在生物医学领域、保险金融领域比较常见）其中为可分的正则函数.共享问题解：先对数据作如下的分块:令优化变量其中

，

;相应的，将特征矩阵也进行相应的划分,其中.由正则函数的可分性以及问题（12.42）可改写为令，上述问题可以转换为如下共享问题s.t.（12.62）共享问题由共享问题的ADMM标准迭代公式，得问题（12.62）的迭代公式为其中.在实际中每个节点计算，然后将更新后的上传到服务器.然后由服务器求平均，以此更新

和，并将更新后的和传给

个节点.第12章交替方向乘子方法12.1方法基础12.2ADMM方法的一般形式和理论性质12.3一致性问题

12.4共享问题12.5数值实验本小节以Lasso问题为例比较近端梯度方法、加速近端梯度方法、随机坐标下降方法和ADMM方法的有效性.

数值实验数值实验问题1考虑一个由行，列构成的特征矩阵，其中，特征矩阵的每一列都经过标准化处理，即2范数为1.真实解有100个非零分量，每一个非零分量从标准正态分布中随机产生.响应变量由线性回归模型生成：其中.设置参数，收敛阈值，正则化参数，初始化变量设置为和.初始点设置为.数值实验图12.1（a）迭代过程中原始残差（上）和对偶残差（下）的二范数变化，虚线分别表示（上）和（下）；（b）迭代过程中的变化.由上图可以看出，经过15次迭代之后ADMM算法近似满足收敛准则.数值实验问题2其中.正则化参数.步长ADMM算法的惩罚参数为，收敛阈值，初始化所有变量为0.对于随机坐标下降算法，这里考虑随机块坐标下降，每次抽取200个特征进行，步长设置为0.01.

考虑一个由

行，列构成的特征矩阵，矩阵的元素均从中产生.真实解有100个非0分量，每个非0分量均从

随机产生.响应变量由线性回归模型产生：数值实验从图（12.2）可以看出，近端梯度方法、加速近端梯度方法和ADMM方法能在100步内收敛，随机坐标下方法因为只更新部分特征，收敛速度较慢.

数值实验考虑Python编程语言中的机器学习库scikit-learn中的糖尿病人数据集：diabetes。该数据集共有442个样本，10个特征(年龄、性别、BMI等)，响应变量为一年后疾病发展情况的定量指标.

Lasso问题为其中为特征矩阵.这里应用坐标下降法来求解上述Lasso问题.

问题3数值实验图12.310个特征系数的变化路径如图12.3所示，当正则化参数较大时，所有系数均压缩为0；随着的增大，各个系数也逐渐增大.实际中可以通过交叉检验选择合适惩罚值.数据科学优化方法Optimization

Method

in

Data

Science数学基础A.1线性代数A.2微积分A.3凸分析线性代数A.1.1向量和矩阵A.1.2特征值和特征向量A.1.3内积和范数向量和矩阵维列向量：或者其中表示向量的第个分量，部分章节也使用表示分量.维实向量构成的空间记为.列向量的转置为行向量：向量和矩阵

矩阵：

其中，表示矩阵的第行第列元素，表示矩阵的对角元素.矩阵构成的空间记为.向量和矩阵矩阵的转置：显然.若对任意的有，则称矩阵为上三角矩阵若对于任意的有，则称矩阵

为下三角矩阵向量和矩阵常见的矩阵类型方阵：如果，即矩阵的行数等于矩阵的列数;

只有对角元为1，其余元素均为0的方阵称为单位阵，

记为.对称阵:若,且;正定阵（半正定阵）：若，且为对称阵，若对于任意的,有().向量和矩阵常见的矩阵类型负定阵（半负定阵）:若，且为对称阵，若对于任意的,有（).

非奇异阵/可逆矩阵:若且.可逆矩阵一定存在逆矩阵,使得.正交阵：若，且.线性代数A.1.1向量和矩阵A.1.2特征值和特征向量A.1.3内积和范数特征值和特征向量特征值的性质与应用设，存在标量(可能是复数）和非零向量满足，则称为矩阵的特征值，为矩阵的特征向量.若矩阵的特征值全部非零，则为非奇异矩阵；实对称矩阵的特征值均为实数，且具有个互相正交的特征向量；矩阵的迹满足；矩阵的行列式等于特征值的积，即特征值和特征向量对称矩阵是正定(半正定)，当且仅当

的所有特征根是正的(非负的)。定理A.1线性代数A.1.1向量和矩阵A.1.2特征值和特征向量A.1.3内积和范数内积与范数常用的向量范数向量的内积与正交性两个向量与的内积为.如果，则称与正交的.

内积与范数范数的等价性上面介绍的三种范数满足如下不等式范数的性质非负性：，且，当且仅当齐次性：，三角不等式：内积与范数设,则有其中等号成立当且仅当存在，使得.定理A.2

Cauchy-Schwarz不等式导出范数:根据已经定义好的向量范数可以诱导出一种相应的矩阵范数，其定义如下

内积与范数当取向量的，，时导出的矩阵范数分别称为矩阵的1范数、2范数和无穷范数矩阵的Frobenius范数也是一种常用的矩阵范数，其定义如下：内积与范数以上四种范数都满足相容性，即矩阵的条件数是判断一个矩阵是否病态的重要指标，其定义为实践中常用二条件数

附录A数学基础A.1线性代数A.2微积分A.3凸分析微积分A.2.1序列和极限A.2.2欧式空间拓扑结构A.2.3连续函数A.2.4导数与梯度A.2.5中值定理和泰勒定理序列和极限收敛序列的定义若序列满足，对于所有的都有则称序列收敛到，记作极限点设，则得到的子序列.子序列的收敛点被称为序列的极限点或者聚点.注：一个序列可以有多个极限点，收敛的序列只有一个极限点.序列和极限有界序列单调收敛定理对于序列，若存在常数,使得对于所有的都有，则称序列有下界.类似的，若满足则称序列有上界.若序列满足对于所有的，都有，则称序列单调不减.类似的若满足，则称序列单调不增.若序列单调不减（增）且有上（下）界，那么序列必收敛.微积分A.2.1序列和极限A.2.2欧式空间拓扑结构A.2.3连续函数A.2.4导数与梯度A.2.5中值定理和泰勒定理欧式空间拓扑结构邻域给定任意，若为包含的开集，则称为点的邻域.以为球心，为半径的球记为.

常见点集设，则为有界集：若存在实数，使得有

开集：若对于任意的，存在使得

闭集：若对于中的所有点列，其极限点都属于微积分A.2.1序列和极限A.2.2欧式空间拓扑结构A.2.3连续函数A.2.4导数与梯度A.2.5中值定理和泰勒定理连续函数连续函数设函数在点的某个邻域内有定义，若有，则称函数在点处连续若函数在定义域内的所有点都连续,则称

为定义域内的连续函数设若存在常数,使得对任意的,有则称为Lipchitz连续函数，其中为Lipschitz常数.定义A.1

Lipschitz连续函数微积分A.2.1序列和极限A.2.2欧式空间拓扑结构A.2.3连续函数A.2.4导数与梯度A.2.5中值定理和泰勒定理导数与梯度导数与梯度设函数，若存在且有限，则称函数在点处一阶可导，上述极

限称为在处的一阶导数，记为或.类似地由导函数可以定义二阶导数.梯度：考虑元函数，在

处的梯度定义为导数与梯度Hesse矩阵多元函数的二阶偏导数矩阵称为Hesse矩阵，定义为可微函数与连续可微函数若函数在任意点处的一阶偏导数