机器学习是目前信息技术中最激动人心的方向之一，其应用已经深入到生活的各个层面且与普通人的日常生活密切相关。本系列博文梳理了机器学习核心基础概念、主流算法思想与入门必备知识，在《数据结构强化笔记》所开创的博文模板基础上，进一步优化了统一规整的撰文体例，由浅入深拆解原理要点，搭配通俗解读与基础实例，助力零基础读者快速搭建机器学习知识框架。

1 初识机器学习

【西瓜例】傍晚小街路面上沁出微雨后的湿润，和熙的细风吹来，抬头看看天边的晚霞，嗯，明天又是一个好天气。走到水果摊旁，挑了个根蒂蜷缩、敲起来声音浊响的青绿西瓜，一边满心期待着皮薄肉厚瓢甜的爽落感，一边愉快地想着，这个月狠下了工夫，基础概念弄得清清楚楚，算法原理也是信手拈来，这篇HyPress博文一定差不了！哈哈，也希望本站这个月的SEO取得一个好成绩！

1.1 机器学习的定义

正如我们根据过去的经验来判断明天的天气，吃货们希望从购买经验中挑选一个好瓜，那能不能让计算机帮助人类来实现这个呢？机器学习正是这样的一门学科，人的“经验”对应计算机中的“数据”，让计算机来学习这些经验数据，生成一个算法模型，在面对新的情况中，计算机便能作出有效的判断，这便是机器学习。

另一本经典教材的作者Mitchell给出了一个形式化的定义，假设：

• P：计算机程序在某任务类T上的性能
• T：计算机程序希望实现的任务类
• E：表示经验，即历史的数据集

若该计算机程序通过利用经验E在任务T上获得了性能P的改善，则称该程序对E进行了学习。

机器学习十大算法：线性回归、逻辑回归、决策树、支持向量机、朴素贝叶斯、随机森林、K-均值、K-近邻、降维（如PCA）、人工神经网络

1.2 机器学习基本术语

假设我们收集了一批西瓜的数据，例如：(色泽=青绿; 根蒂=蜷缩; 敲声=浊响)、(色泽=乌黑; 根蒂=稍蜷; 敲声=沉闷)、(色泽=浅紫; 根蒂=硬挺; 敲声=清脆)……每对括号内是一个西瓜的记录，定义：

• 所有记录的集合：数据集
• 每一条记录：一个实例（Instance）或样本（Sample）
• 单个样本的特点（例如色泽或敲声）：特征（Feature）或属性（Attribute）
• 对于一条记录，如果在坐标轴上表示，每个西瓜都可以用坐标轴中的一个点表示，一个点也是一个向量，例如(青绿, 蜷缩, 浊响)，即每个西瓜为一个特征向量（Feature Vector）
• 一个样本的特征数：维数（Dimensionality）。上述西瓜例中维数为3，当维数非常大时，即为平日常说的“维数灾难”

计算机程序学习经验数据生成算法模型的过程中，每一条记录称为一个“训练样本”，同时在训练好模型后，通常希望使用新的样本来测试模型的效果，则每一个新的样本称为一个“测试样本”。定义：

• 所有训练样本的集合：训练集（Trainning Set）——特殊
• 所有测试样本的集合：测试集（Test Set）——一般
• 机器学习训练所得的模型适用于新样本的能力：泛化能力（Generalization），即从特殊到一般。

在上述西瓜例中，计算机通过学习西瓜的特征数据，训练出一个决策模型，来判断一个新的西瓜是否是好瓜，即预测的是西瓜是好是坏，即结果仅含好瓜与差瓜两个离散值。同样地，亦可通过历年的人口数据，来预测未来的人口数量，人口数量则是连续值。定义：

• 预测值为离散值的问题：分类（Classification）
• 预测值为连续值的问题：回归（Regression）

在预测西瓜是否是好瓜的过程中，很明显对于训练集中的西瓜，事先已经知道了该瓜是否是好瓜，学习器通过学习这些好瓜或差瓜的特征，从而总结出规律，即训练集中的西瓜都做了标记，称为标记信息。但亦有无标记信息的情形，例如欲将一堆西瓜根据特征分成两个小堆，使得某一堆的西瓜尽可能相似，即都是好瓜或差瓜，对于这种问题，事先并不知道西瓜的好坏，样本没有标记信息。定义：

• 训练数据有标记信息的学习任务：监督学习（Supervised Learning），易知上述的分类和回归都是监督学习的范畴
• 训练数据没有标记信息的学习任务：无监督学习（Unsupervised Learning），常见的有聚类和关联规则

---

2 矩阵论

本章回顾线性代数中向量和矩阵的各种运算及其性质。

2.1 矩阵基本运算

记实矩阵\mathbf{A}\in \mathbb{R}^{m\times n}第i行第j列的元素为(\mathbf{A})_{ij}=A_{ij}。矩阵\mathbf{A}的转置（Transpose）记为\mathbf{A}^\top，(\mathbf{A}^\top)_{ij}=A_{ji}，显然

\begin{aligned}
(\mathbf{A}+\mathbf{B})^\top &= \mathbf{A}^\top + \mathbf{B}^\top\\
(\mathbf{A}\mathbf{B})^\top &=\mathbf{B}^\top\mathbf{A}^\top
\end{aligned}

对于矩阵\mathbf{A}\in \mathbb{R}^{m\times n}，若m=n则称其为n阶方阵。用\mathbf{I}_n表示n阶单位矩阵，方阵\mathbf{A}的逆矩阵\mathbf{A}^{-1}满足\mathbf{A}\mathbf{A}^{-1}=\mathbf{A}^{-1}\mathbf{A}=\mathbf{I}。易知

\begin{aligned}
(\mathbf{A}^\top)^{-1} &=(\mathbf{A}^{-1})^\top\\
(\mathbf{A}\mathbf{B})^{-1} &=\mathbf{B}^{-1}\mathbf{A}^{-1}
\end{aligned}

对于n阶方阵\mathbf{A}，其主对角线上的元素之和称为迹（Trace），即\operatorname{tr}(\mathbf{A})=\sum\limits_{i=1}^n A_{ii}。迹的性质如下

\begin{aligned}
\operatorname{tr}(\mathbf{A}^\top) &=\operatorname{tr}(\mathbf{A})\\
\operatorname{tr}(\mathbf{A} + \mathbf{B}) &= \operatorname{tr}(\mathbf{A}) + \operatorname{tr}(\mathbf{B})\\
\operatorname{tr}(\mathbf{A}\mathbf{B}) &= \operatorname{tr}(\mathbf{B}\mathbf{A})\\
\operatorname{tr}(\mathbf{A}\mathbf{B}\mathbf{C}) &= \operatorname{tr}(\mathbf{B}\mathbf{C}\mathbf{A}) = \operatorname{tr}(\mathbf{C}\mathbf{A}\mathbf{B})\\
\end{aligned}

n阶方阵\mathbf{A}的行列式定义为

\begin{aligned}
\operatorname{det}(\mathbf{A})=\sum\limits_{\mathbf{\sigma}\in S_n} \operatorname{par}(\mathbf{\sigma}) A_{1\sigma_1}A_{2\sigma_2}\cdots A_{n\sigma_n}
\end{aligned}

其中S_n为所有n阶排列（Permutation）的集合，\operatorname{par}(\mathbf{\sigma})=-1\text{ or }+1取决于\mathbf{\sigma}=(\sigma_1,\sigma_2,\dots,\sigma_n)为奇排列或偶排列，即其中出现降序的次数为奇数或偶数数（例如(1,3,2)中降序次数为1，(1,4,3,2)中降序次数为2）。对于单位矩阵\mathbf{I}，\operatorname{det}(\mathbf{I})=1；对于2阶方阵\mathbf{A}，\operatorname{det}(\mathbf{A})=\operatorname{det}\left ( \begin{matrix} A_{11} & A_{12}\\ A_{21} & A_{22} \end{matrix} \right)=A_{11}A_{22}-A_{12}A_{21}。n阶方阵A的行列式的性质如下

\begin{aligned}
\operatorname{det}(c\mathbf{A}) &=c^n \operatorname{det}(\mathbf{A})\\
\operatorname{det}(\mathbf{A}^\top) &= \operatorname{det}(\mathbf{A})\\
\operatorname{det}(\mathbf{A}\mathbf{B}) &= \operatorname{det}(\mathbf{A})\operatorname{det}(\mathbf{B})\\
\operatorname{det}(\mathbf{A}^{-1}) &= \operatorname{det}(\mathbf{A})^{-1}\\
\operatorname{det}(\mathbf{A}^n) &= \operatorname{det}(\mathbf{A})^n
\end{aligned}

矩阵\mathbf{A}\in \mathbb{R}^{m\times n}的Frobenius范数定义为

\begin{aligned}
\left \| \mathbf{A} \right \|_{F}=\left(\operatorname{tr}\left (\mathbf{A}^\top \mathbf{A}\right )\right )^{\frac12}=\left( \sum\limits_{i=1}^m \sum\limits_{j=1}^n A_{ij}^2 \right)^{\frac12}
\end{aligned}

可见，矩阵的Frobenius范数就是将矩阵张成向量后的L₂范数。

2.2 矩阵的导数

向量\mathbf{a}相对于标量x的导数（Derivative），以及x相对于\mathbf{a}的导数都是向量，其第i个分量分别为

\begin{aligned}
\left(\frac{\partial \mathbf{a}}{\partial x}\right )_i &=\frac{\partial a_i}{\partial x}\\
\left(\frac{\partial x}{\partial \mathbf{a}}\right )_i &=\frac{\partial x}{\partial a_i}\\
\end{aligned}

类似地，矩阵\mathbf{A}对于标量x的导数，以及x对于\mathbf{A}的导数都是矩阵，其第i行第j列上的元素分别为

\begin{aligned}
\left(\frac{\partial \mathbf{A}}{\partial x}\right)_{ij} &=\frac{\partial A_{ij}}{\partial x}\\
\left(\frac{\partial x}{\partial \mathbf{A}}\right)_{ij} &=\frac{\partial x}{\partial A_{ij}}\\
\end{aligned}

对于函数f(\mathbf{x})，假定其对向量的元素可导，则f(\mathbf{x})关于\mathbf{x}的一阶导数是一个向量，其第i个分量为

\begin{aligned}
(\nabla f(\mathbf{x}))_i = \frac{\partial f(\mathbf{x})}{\partial x_i}
\end{aligned}

f(\mathbf{x})关于\mathbf{x}的二阶导数是称为海森矩阵（Hessian Matrix）的一个方阵，其第i行第j列上的元素为

\begin{aligned}
(\nabla^2 f(\mathbf{x}))_{ij} = \frac{\partial^2 f(\mathbf{x})}{\partial x_i \partial x_j}
\end{aligned}

向量和矩阵的导数满足乘法法则（Product Rule），即

\begin{aligned}
\frac{\partial \mathbf{x}^\top \mathbf{a}}{\partial \mathbf{x}} &=\frac{\partial \mathbf{a}^\top \mathbf{x}}{\partial \mathbf{x}}=\mathbf{a}\\
\frac{\partial \mathbf{A}\mathbf{B}}{\partial \mathbf{x}} &=\frac{\partial \mathbf{A}}{\partial \mathbf{x}}\mathbf{B}+\mathbf{A}\frac{\partial \mathbf{B}}{\partial \mathbf{x}}
\end{aligned}

根据\mathbf{A}^{-1}\mathbf{A}=\mathbf{I}和上述第二条法则，逆矩阵的导数可表示为

\begin{aligned}
\frac{\partial \mathbf{A}^{-1}}{\partial x}=-\mathbf{A}^{-1}\frac{\partial \mathbf{A}}{\partial x}\mathbf{A}^{-1}
\end{aligned}

若求导的标量是矩阵\mathbf{A}的元素，则有

\begin{aligned}
\frac{\partial \operatorname{tr}(\mathbf{A}\mathbf{B})}{\partial A_{ij}} &= B_{ij}\\
\frac{\partial \operatorname{tr}(\mathbf{A}\mathbf{B})}{\partial \mathbf{A}} &= \mathbf{B}^\top
\end{aligned}

进而有

\begin{aligned}
\frac{\partial \operatorname{tr}(\mathbf{A}^\top \mathbf{B})}{\partial \mathbf{A}} &=\mathbf{B}\\
\frac{\partial \operatorname{tr}(\mathbf{A})}{\partial \mathbf{A}} &= \mathbf{I}\\
\frac{\partial \operatorname{tr}(\mathbf{A}\mathbf{B}\mathbf{A}^\top)}{\partial \mathbf{A}} &= \mathbf{A}(\mathbf{B}+\mathbf{B}^\top)
\end{aligned}

根据Frobenius范数的定义和上述第三式，有

\begin{aligned}
\frac{\partial \left\| \mathbf{A} \right\|_{F}^2}{\partial \mathbf{A}}=\frac{\partial \operatorname{tr}(\mathbf{A}\mathbf{A}^\top)}{\partial \mathbf{A}}=2\mathbf{A}
\end{aligned}

链式法则（Chain Rule）是计算复杂导数时的重要工具。若函数f是g和h的复合，即f(x)=g(h(x))，则有

\begin{aligned}
\frac{\partial f(x)}{\partial x}=\frac{\partial g(h(x))}{\partial h(x)} \cdot \frac{\partial h(x)}{\partial x}
\end{aligned}

【例】使用链式法则求(\mathbf{A}\mathbf{x}-\mathbf{b})^\top \mathbf{W}(\mathbf{A}\mathbf{x}-\mathbf{b})关于\mathbf{x}的导数：\dfrac{\partial}{\partial \mathbf{x}}(\mathbf{A}\mathbf{x}-\mathbf{b})^\top \mathbf{W}(\mathbf{A}\mathbf{x}-\mathbf{b}) = \dfrac{\partial (\mathbf{A}\mathbf{x}-\mathbf{b})}{\partial \mathbf{x}}\cdot 2\mathbf{W}(\mathbf{A}\mathbf{x}-\mathbf{b}) = 2\mathbf{A}\mathbf{W}(\mathbf{A}\mathbf{x}-\mathbf{b})

2.3 奇异值分解

任意实矩阵\mathbf{A}\in \mathbb{R}^{m\times n}都可进行奇异值分解（Singular Value Decomposition，SVD），定义式如下

\begin{aligned}
\mathbf{A}=\mathbf{U}\boldsymbol{\Sigma}\mathbf{V}^\top
\end{aligned}

其中，\mathbf{U}\in \mathbb{R}^{m\times m}是满足\mathbf{U}^\top \mathbf{U}=\mathbf{I}的m阶酉矩阵（Unitary Matrix），其列向量\mathbf{u}_i\in \mathbb{R}^{m}称为\mathbf{A}的左奇异向量（Left-singular Vector）；\mathbf{V}\in \mathbb{R}^{n\times n}是满足\mathbf{V}^\top \mathbf{V}=\mathbf{I}的n阶酉矩阵，其列向量\mathbf{v}_i\in \mathbb{R}^{n}称为\mathbf{A}的右奇异向量（Right-singular Vector）；矩阵\boldsymbol{\Sigma}\in \mathbb{R}^{m\times n}的对角线元素(\boldsymbol{\Sigma})_{ii}=\sigma_i，其他元素均为0，其中\sigma_i称为奇异值（Singular Value），常降序排列，即\sigma_1 \ge \sigma_2 \ge \cdots \ge 0。矩阵\mathbf{A}的秩（Rank）等于非零奇异值的个数。

奇异值分解有广泛的用途，例如对于低秩矩阵近似（Low-rank Matrix Approximation）问题，给定一个秩为r的矩阵\mathbf{A}，欲求其最优k秩近似矩阵\mathbf{\tilde A}，k \le r，该问题可形式化为

\begin{aligned}
\underset{\mathbf{\tilde A} \in \mathbb{R}^{m\times n}}{\min} & \left\|\mathbf{A} - \mathbf{\tilde A} \right\|_{F}\\
\text{s.t. } & \operatorname{rank}(\mathbf{\tilde A})=k
\end{aligned}

奇异值分解提供了上述问题的解析解：对矩阵\mathbf{A}进行奇异值分解后，将矩阵\boldsymbol{\Sigma}中的r-k个最小的奇异值置零获得矩阵\boldsymbol{\Sigma}_k，即仅保留最大的k个奇异值，则上式的最优解为

\begin{aligned}
\mathbf{A}_k=\mathbf{U}_k \boldsymbol{\Sigma}_k \mathbf{V}_k^\top
\end{aligned}

其中\mathbf{U}_k,\mathbf{V}_k分别为定义式中的前k列组成的矩阵。该结果称为Eckart-Young-Mirsky定理。

---

3 经典优化方法

本章介绍本系列博文使用过的各种经典优化方法。

3.1 拉格朗日乘子法

拉格朗日乘子法（Lagrange Multipliers）是一种寻找多元函数在一组约束下的极值的方法。通过引入拉格朗日乘子，可将有d个变量与k个约束条件的最优化问题转化为具有d+k个变量的无约束优化问题求解。

3.1.1 KKT条件

首先考虑等式约束的优化问题——寻找d维向量\mathbf{x}的某个取值\mathbf{x}^*，使得目标函数f(\mathbf{x})最小且同时满足约束g(\mathbf{x})=0。从几何角度看，该问题的目标为在由方程g(\mathbf{x})=0确定的d-1维曲面上寻找能使目标函数f(\mathbf{x})最小化的点，则易得以下结论：

• 对于约束曲面上的任意点\mathbf{x}，该点的梯度\nabla g(\mathbf{x})正交于约束曲面。
• 对于最优点\mathbf{x}^*，目标函数在该点的梯度\nabla f(\mathbf{x}^*)正交于约束曲面。

【定理】函数等值线与约束曲面相切。
可通过反证法证明：若梯度\nabla f(\mathbf{x}^*)与约束曲面不正交，则仍可在约束曲面上移动该点使函数值进一步下降。

由此可知，在最优点\mathbf{x}^*，梯度\nabla g(\mathbf{x}),\nabla f(\mathbf{x})的方向必相同或相反（如下图中(a)所示），即存在\lambda \ne 0使得

\begin{aligned}
\nabla f(\mathbf{x}^*)+\lambda \nabla g(\mathbf{x}^*)=0
\end{aligned}

其中\lambda称为拉格朗日乘子，对于等式约束而言，\lambda可能为正也可能为负。故可定义拉格朗日函数，将原优化问题转化为对拉格朗日函数的无约束优化问题，如下所示

\begin{aligned}
L(\mathbf{x},\lambda)=f(\mathbf{x})+\lambda g(\mathbf{x})
\end{aligned}

现在考虑不等式约束g(\mathbf{x})\le 0（如上图中(b)所示），此时最优点或在g(\mathbf{x})\lt 0的区域内，或在边界g(\mathbf{x})=0上。对于g(\mathbf{x})\lt 0的情形，原不等式约束g(\mathbf{x})\le 0不起作用，可直接通过条件\nabla f(\mathbf{x})=0来获得最优点，这等价于将\lambda置零后解\nabla_{\mathbf{x}} L(\mathbf{x},\lambda)=0得到最优点。g(\mathbf{x})=0的情形类似于前述等式约束的分析，但需注意此时\nabla f(\mathbf{x}^*)的方向必与\nabla g(\mathbf{x}^*)相反，即存在常数\lambda \gt 0使得\nabla f(\mathbf{x}^*)+\lambda \nabla g(\mathbf{x}^*)=0。整合这两种情形，必满足\lambda g(\mathbf{x}^*)=0。由此可将原优化问题转化为在如下约束下最小化拉格朗日函数，即

\left\{\begin{aligned}
& g(\mathbf{x})\le 0\\
& \lambda \ge 0\\
& \lambda g(\mathbf{x}) =0
\end{aligned}\right.

上式称为Karush-Kuhn-Tucker条件（KKT条件）。

3.1.2 对偶问题

上一子节的做法可推广到多个约束，考虑具有m个等式约束和n个不等式约束，且可行域\mathbb{D} \subset \mathbb{R}^d非空的优化问题

\begin{aligned}
\min\limits_{\mathbf{x}}\ & f(\mathbf{x})\\
\text{s.t. } & h_i(\mathbf{x})=0\ (i=1,2,\dots,m),\\
& g_j(\mathbf{x}) \le 0\ (j=1,2,\dots,n)
\end{aligned}

引入拉格朗日乘子\boldsymbol{\lambda}=(\lambda_1,\lambda_2,\dots,\lambda_m)^\top,\ \boldsymbol{\mu}=(\mu_1,\mu_2,\dots,\mu_n)^\top，相应的拉格朗日函数为

\begin{aligned}
L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})=f(\mathbf{x})+\sum\limits_{i=1}^m \lambda_i h_i(\mathbf{x})+\sum\limits_{j=1}^n \mu_j g_j(\mathbf{x})
\end{aligned}

由不等式约束引入的KKT条件为

\left\{\begin{aligned}
& g_j(\mathbf{x})\le 0\\
& \mu_j \ge 0\\
& \mu_j g_j(\mathbf{x}) =0
\end{aligned}\right.

一个优化问题可从两个角度来考察，即主问题（Primal Problem）和对偶问题（Dual Problem）。对于主问题（即本子节开头的原优化问题），基于拉格朗日函数表达式，其拉格朗日对偶函数（Dual Function）\Gamma: \mathbb{R}^m \times \mathbb{R}^n \mapsto \mathbb{R}定义为

\begin{aligned}
\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) &= \inf\limits_{\mathbf{x}\in \mathbb{D}} L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu})\\
&= \inf\limits_{\mathbf{x}\in \mathbb{D}} \left( f(\mathbf{x})+\sum\limits_{i=1}^m \lambda_i h_i(\mathbf{x})+\sum\limits_{j=1}^n \mu_j g_j(\mathbf{x}) \right)
\end{aligned}

此时称对偶问题中的\boldsymbol{\lambda},\boldsymbol{\mu}为对偶变量（Dual Variable）。一般情况下，可通过对拉格朗日函数对\mathbf{x}求导并令导数为0，来获得对偶函数的表达形式。若\tilde \mathbf{x} \in \mathbb{D}为主问题的可行域中的点，则对任意\boldsymbol{\mu} \succeq 0¹和\boldsymbol{\lambda}都有

\begin{aligned}
\sum\limits_{i=1}^m \lambda_i h_i(\mathbf{x})+\sum\limits_{j=1}^n \mu_j g_j(\mathbf{x}) \le 0
\end{aligned}

进而有

\begin{aligned}
\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) = \inf\limits_{\mathbf{x}\in \mathbb{D}} L(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \le \inf\limits_{\tilde \mathbf{x}\in \mathbb{D}} L(\tilde \mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}) \le f(\tilde \mathbf{x})
\end{aligned}

若主问题的最优值为p^*，则对任意\boldsymbol{\mu} \succeq 0和\boldsymbol{\lambda}都有

\begin{aligned}
\Gamma(\boldsymbol{\lambda},\boldsymbol{\mu}) \le p^*
\end{aligned}

即对偶函数给出了主问题最优值的下界。显然，该下界取决于\boldsymbol{\lambda},\boldsymbol{\mu}的值，故自然想出一个问题——基于对偶函数能获得的最好下界是什么？由此得到了主问题的对偶问题

\begin{aligned}
\max\limits_{\boldsymbol{\lambda},\boldsymbol{\mu}} \operatorname{\Gamma }(\boldsymbol{\lambda},\boldsymbol{\mu}) \text{ s.t. } \boldsymbol{\mu} \succeq 0
\end{aligned}

无论主问题的凸性如何，对偶问题始终为凸优化问题。若对偶问题的最优值为d^*，显然有d^* \le p^*，则称为弱对偶性（Weak Duality）成立；若d^* = p^*，则称为强对偶性（Strong Duality）成立，此时由对偶问题能获得主问题的最优下界。对于一般的优化问题，强对偶性通常不成立，但若主问题为凸优化问题，如主问题中的f(\mathbf{x}),g_j(\mathbf{x})均为凸函数，h_i(\mathbf{x})为仿射函数，且其可行域中至少有一点使不等式约束严格成立，则此时强对偶性成立，称上述条件为Slater条件。注意在强对偶性成立时，将拉格朗日函数分别对原变量和对偶变量求导并令导数为0，即可得到原变量与对偶变量的数值关系。对偶问题解决了，主问题也就解决了。

3.2 二次规划

二次规划（Quadratic Programming，QP）是一类典型的优化问题，包括凸二次优化和非凸二次优化。在此类问题中，目标函数是变量的二次函数，而约束条件是变量的线性不等式。

假定变量个数为d，约束条件的个数为m，则标准的二次规划问题形如

\begin{aligned}
\min\limits_{\mathbf{x}}\ & \frac{1}{2} \mathbf{x}^\top \mathbf{Q}\mathbf{x}+\mathbf{c}^\top \mathbf{x}\\
\text{s.t. } & \mathbf{A}\mathbf{x} \le \mathbf{b}
\end{aligned}

其中\mathbf{x}为d维向量，\mathbf{Q}\in \mathbb{R}^{d\times d}为实对称矩阵，\mathbf{A}\in \mathbb{R}^{m\times d}为实矩阵，\mathbf{b}\in \mathbb{R}^m,\ \mathbf{c}\in \mathbb{R}^{d}为实向量，\mathbf{A}\mathbf{x} \le \mathbf{b}的每一行对应一个约束。

非标准二次规划问题中可以包含等式约束：等式约束可用两个不等式约束来代替；不等式约束可通过增加松弛变量的方式转化为等式约束。

若\mathbf{Q}为半正定矩阵，则上式的模板函数为凸函数，相应的二次规划是凸二次优化问题；此时若约束条件\mathbf{A}\mathbf{x} \le \mathbf{b}定义的可行域不为空，且目标函数在此可行域有下界，则该问题存在全局最小值。若\mathbf{Q}为正定矩阵，则该问题有唯一的全局最小值。若\mathbf{Q}为非正定矩阵，则上式为有多个平稳点和局部极小点的NP难问题。

常用的二次规划解法有椭球法（Ellipsoid Method）、内点法（Interior
Point）、增广拉格朗日法（Augmented Lagrangian）、梯度投影法（Gradient Projection）等。若\mathbf{Q}为正定矩阵，则相应的二次规划问题可由椭球法在多项式时间内求解。

3.3 半正定规划

半正定规划（Semi-Definite Programming，SDP）是一类凸优化问题，其中的变量可组织成半正定对称矩阵形式，且优化问题的目标函数和约束都是这些变量的线性函数。

给定d\times d的对称矩阵\mathbf{X},\mathbf{C}，则

\begin{aligned}
\mathbf{C}\mathbf{X}=\sum\limits_{i=1}^d\sum\limits_{j=1}^d C_{ij}X_{ij}
\end{aligned}

若\mathbf{A}_i\ (i=1,2,\dots,m)也是d\times d的对称矩阵，b_i\ (i=1,2,\dots,m)为m个实数，则半正定规划问题形如

\begin{aligned}
\min\limits_{\mathbf{X}}\ & \mathbf{C}\mathbf{X}\\
\text{s.t. } & \mathbf{A}_i\mathbf{X}=b_i,\ i=1,2,\dots,m\\
& \mathbf{X} \succeq 0
\end{aligned}

半正定规划与线性规划都拥有线性的目标函数和约束，但半正定规划中的约束\mathbf{X} \succeq 0是一个非线性、非光滑约束条件，在优化理论中，半正定规划具有一定的一般性，能将几种标准的优化问题（如线性规划、二次规划）统一起来。

常见的用于求解线性规划的内点法经过少许改造即可求解半正定规划问题，但半正定规划的计算复杂度较高，难以直接用于大规模问题。

3.4 梯度下降法

梯度下降法（Gradient Descent）是一种常用的一阶（Frst-order）优化方法（仅使用目标函数的一阶导数，不利用其高阶导数），是求解无约束优化问题最简单、最经典的方法之一。

考虑无约束优化问题\min\limits_{\mathbf{x}} f(\mathbf{x})，其中f(\mathbf{x})为连续可微函数。若能构造一个序列\mathbf{x}^0,\mathbf{x}^1,\mathbf{x}^2,\dots满足

\begin{aligned}
f(\mathbf{x}^{t+1}) \lt f(\mathbf{x}^t),\ t=0,1,2,\dots
\end{aligned}

则不断执行该过程即可收敛到局部极小点。欲满足上式，根据一阶泰勒展开式有

\begin{aligned}
f(\mathbf{x}+\Delta \mathbf{x}) \simeq f(\mathbf{x}) + \Delta \mathbf{x} ^\top \nabla f(\mathbf{x})
\end{aligned}

于是，欲满足f(\mathbf{x}+\Delta \mathbf{x}) \lt f(\mathbf{x})，可选择

\begin{aligned}
\Delta \mathbf{x} = -\gamma \nabla f(\mathbf{x})
\end{aligned}

其中步长\gamma是一个小常数，每步的步长\gamma_t可以不同。根据梯度逐步“下降”即可实现优化。

若目标函数f(\mathbf{x})满足一些条件，则通过选取合适的步长，就能确保通过梯度下降收敛到局部极小点。例如若f(\mathbf{x})满足L-Lipschitz条件（\forall \mathbf{x},\exists L,\left\|\nabla f(\mathbf{x}) \right\| \le L），则将步长设置为\dfrac{1}{2L}即可确保收敛到局部极小点。当目标函数为凸函数时，局部极小点直接对应函数的全局最小点，此时梯度下降法可确保收敛到全局最优解。

当模板函数f(\mathbf{x})二阶连续可微时，可改用更精确的二阶泰勒展开式，由此得到了牛顿法（Newton's Method）。这种二阶方法的迭代轮数远小于梯度下降法，但由于使用了二阶导数\nabla^2 f(\mathbf{x})，每轮迭代中涉及到海森矩阵的求逆，计算复杂度极高。若能以较低的计算代价寻找海森矩阵的近似逆矩阵，则可显著降低计算开销，常称该做法为拟牛顿法（Quasi-Newton Method）。

3.5 坐标下降法

坐标下降法（Coordinate Descent）是一种非梯度优化方法，其在每步迭代中沿一个坐标方向进行搜索，通过循环使用不同的坐标方向来达到目标函数的局部极小值。

假设目标为求解函数f(\mathbf{x})的极小值，其中\mathbf{x}=(x_1,x_2,\dots,x_d)^\top \in \mathbb{R}^d。从初始点\mathbf{x}^0开始，坐标下降法通过迭代地构造序列\mathbf{x}^0,\mathbf{x}^1,\mathbf{x}^2,\dots来求解该问题，其中\mathbf{x}^{t+1}的第i个分量构造为

\begin{aligned}
x_{i}^{t+1}=\underset{y\in \mathbb{R}}{\arg \min} \operatorname{\mathit{f\ }}(x_1^{t+1},\dots,x_{i-1}^{t+1},y,x_{i+1}^t,\dots,x_d^t)
\end{aligned}

通过执行此操作，显然有

\begin{aligned}
f(\mathbf{x}^0) \ge f(\mathbf{x}^1) \ge f(\mathbf{x}^2) \ge \cdots
\end{aligned}

与梯度下降法类似，通过迭代执行该过程，序列\mathbf{x}^0,\mathbf{x}^1,\mathbf{x}^2,\dots能收敛到所期望的局部极小点或驻点（Stationary Point）。

坐标下降法无需计算目标函数的梯度，在每步迭代中仅需求解一维搜索问
题，对于某些复杂问题计算较为简便。但若目标函数不光滑，则坐标下降法有可
能陷入非驻点（Non-stationary Point）。

---

A 关于长文拆分

由于机器学习领域分支极多，单篇博文难以尽述，故将原长文《机器学习基础笔记》拆分为数篇中等长度博文，并收录至博文系列页面中。由于工作仓促，部分子节引用表述难以适应对应新文章，日后会逐一修正。

《数据结构强化笔记》的拆分任务描述另见对应篇章。