本文涉及矩阵，基本优化方法（拉格朗日，梯度下降，牛顿方法等）对一些常见方法的进行总结记录。

矩阵

了解其基本加减乘除转置运算以及导数的求法。

奇异值分解

<script type="math/tex; mode=display" id="MathJax-Element-1">A=U\sum{}V^{T}</script>
其中U，T都是酉矩阵，∑<script type="math/tex" id="MathJax-Element-2">\sum{}</script>是对角矩阵，且对角元素为σi<script type="math/tex" id="MathJax-Element-3">\sigma_{i}</script>，σi<script type="math/tex" id="MathJax-Element-4">\sigma_{i}</script>非负，而且σ1≥σ2<script type="math/tex" id="MathJax-Element-5">\sigma_{1}\ge\sigma_{2}</script>。

上面的分解就是奇异值分解(Singular Value Decomposition,SVD)。其中U的列向量为A的左奇异向量，V的列向量为右奇异向量。σi<script type="math/tex" id="MathJax-Element-6">\sigma_{i}</script>称为奇异值(singular value)。A的秩(rank)就等于奇异值的个数。

奇异值的用途很广泛，比如低秩矩阵近似(low-rank matrix approximation)。

优化

梯度下降法

梯度下降法是求解无约束最优化问题的一种常见方法。
假设f(x)<script type="math/tex" id="MathJax-Element-7">f(x)</script>是Rn<script type="math/tex" id="MathJax-Element-8">R^n</script>上具有一阶连续偏导的函数，要求解的无约束最优化问题是

<script type="math/tex; mode=display" id="MathJax-Element-9">minf(x)</script>
梯度下降法选取适当的初值x0<script type="math/tex" id="MathJax-Element-10">x^0</script>,由于负梯度方向是使函数值下降最快的方向，以负梯度方向更新x<script type="math/tex" id="MathJax-Element-11">x</script>，直到收敛。
由于f(x)<script type="math/tex" id="MathJax-Element-12">f(x)</script>具有一阶连续偏导，若第k次迭代值为xk<script type="math/tex" id="MathJax-Element-13">x^k</script>，则可将f(x)<script type="math/tex" id="MathJax-Element-14">f(x)</script>在xk<script type="math/tex" id="MathJax-Element-15">x^{k}</script>附近进行一阶泰勒展开：
f(x)=f(xk)+gTk(x−xk)<script type="math/tex" id="MathJax-Element-16">f(x)=f(x^{k})+g_k^T(x-x^{k})</script>
这里，gk=g(xk=∇f(xk))<script type="math/tex" id="MathJax-Element-17">g_k=g(x^{k}=\nabla f(x^{k}))</script>为f(x)<script type="math/tex" id="MathJax-Element-18">f(x)</script>在xk<script type="math/tex" id="MathJax-Element-19">x^{k}</script>的梯度。
求出第k+1次迭代值xk+1<script type="math/tex" id="MathJax-Element-20">x^{k+1}</script>：
<script type="math/tex; mode=display" id="MathJax-Element-21">x^{k+1} \leftarrow x^{k}+\lambda_kp_k</script>
其中，pk<script type="math/tex" id="MathJax-Element-22">p_k</script>是搜索方向，取负梯度方向pk=−∇f(xk)<script type="math/tex" id="MathJax-Element-23">p_k=-\nabla f(x^{k})</script>，λk<script type="math/tex" id="MathJax-Element-24">\lambda_k</script>是步长，由一维搜索确定。

当目标函数是凸函数时，梯度下降是全局最优解。一般情况下，并不是最优解，其速度也未必是很快的。
梯度下降是一种一阶优化方法，牛顿方法是二阶方法，其迭代次数远小于梯度下降法。但牛顿法计算二阶导数时涉及到海森矩阵的求逆，计算复杂度很高，在高维问题中几乎不可行。于是用其近似函数便诞生了拟牛顿方法。

牛顿法与拟牛顿发法

牛顿法(Newton method)和拟牛顿法(quasi Newton method)也是求解无约束最优化问题的常用方法。收敛速度快。牛顿法是迭代算法，每一步要求解目标函数的海赛矩阵(Hesse matrix)的逆矩阵，计算比较复杂。拟牛顿发通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵来简化计算。

牛顿法

假设f(x)<script type="math/tex" id="MathJax-Element-110">f(x)</script>具有二阶连续偏导，若第k次迭代值为xk<script type="math/tex" id="MathJax-Element-111">x^k</script>，则可将f(x)在xk<script type="math/tex" id="MathJax-Element-112">x^k</script>附近二阶泰勒展开：

<script type="math/tex; mode=display" id="MathJax-Element-113">f(x)=f(x^k)+g_k^T(x-x^k)+\frac{1}{2}(x-x^k)^TH(x^k)(x-x^k)</script>
gk<script type="math/tex" id="MathJax-Element-114">g_k</script>是梯度，$H(x^k)是海赛矩阵

<script type="math/tex; mode=display" id="MathJax-Element-30">H(x)=[\frac{\partial^2f}{\partial x_i \partial}]_{n \times n}</script>

在点xk<script type="math/tex" id="MathJax-Element-31">x^k</script>的值。f(x)有极值的必要条件是在极值点处一阶导数为0。特别是当H(xk)<script type="math/tex" id="MathJax-Element-32">H(x^k)</script>是正定矩阵时，f(x)的极值为极小值。
牛顿法利用极小点的必要条件：

<script type="math/tex; mode=display" id="MathJax-Element-33">\nabla f(x)=0</script>
假设∇f(xk+1=0)<script type="math/tex" id="MathJax-Element-34">\nabla f(x^{k+1}=0)</script>:
<script type="math/tex; mode=display" id="MathJax-Element-35">\nabla f(x)=g_k+H_k(x-x^k)</script>
其中Hk=H(xk)<script type="math/tex" id="MathJax-Element-36">H_k=H(x^k)</script>，我们得到：
<script type="math/tex; mode=display" id="MathJax-Element-37">g_k+H_k(x^{k+1}-x^k)=0</script>
所以：
<script type="math/tex; mode=display" id="MathJax-Element-38">x^{k+1}=x^{k}-H_k^{-1}p_k</script>

拟牛顿法

因为求H−1k<script type="math/tex" id="MathJax-Element-105">H_k^{-1}</script>计算比较复杂。考虑用一个n阶矩阵Gk=G(xk)<script type="math/tex" id="MathJax-Element-106">G_k=G(x^k)</script>来近似代替H−1k=H−1xk<script type="math/tex" id="MathJax-Element-107">H_k^{-1}=H^{-1}{x^k}</script>。这就是拟牛顿法基本思想。

在∇f(x)=gk+Hk(x−xk)<script type="math/tex" id="MathJax-Element-108">\nabla f(x)=g_k+H_k(x-x^k)</script>中，取x=xk+1<script type="math/tex" id="MathJax-Element-109">x=x^{k+1}</script>:

<script type="math/tex; mode=display" id="MathJax-Element-44">g_{k+1}-g_{k}=H_k(x^{k+1}-x^k)</script>
记yk=gk+1−gk,δk=xk+1−xk<script type="math/tex" id="MathJax-Element-45">y_k=g_{k+1}-g_{k},\delta_k=x^{k+1}-x^k</script>，则：
<script type="math/tex; mode=display" id="MathJax-Element-46">y_k=H_k\delta_k</script>
或者：
<script type="math/tex; mode=display" id="MathJax-Element-47">H_k^{-1}y_k=\delta_k</script>
这称为拟牛顿条件。

如果Hk<script type="math/tex" id="MathJax-Element-48">H_k</script>是正定的(H−1k<script type="math/tex" id="MathJax-Element-49">H_k^{-1}</script>也是正定的)，那么可以保证牛顿法搜索方向pk<script type="math/tex" id="MathJax-Element-50">p_k</script>是下降方向。
拟牛顿法将Gk<script type="math/tex" id="MathJax-Element-51">G_k</script>作为H−1k<script type="math/tex" id="MathJax-Element-52">H_k^{-1}</script>的近似，要满足拟牛顿条件：

<script type="math/tex; mode=display" id="MathJax-Element-53">G_{k+1}y_k=\delta_k</script>
按照拟牛顿条件，在每次迭代中可以选择更新矩阵Gk+1<script type="math/tex" id="MathJax-Element-54">G_{k+1}</script>:
<script type="math/tex; mode=display" id="MathJax-Element-55">G_{k+1}=G_k+\Delta G_k</script>
这种选择有一定的灵活性，因此有多种具体实现方法。

DPF算法

即Davidon-Fletcher-Powll算法。其选择Gk+1<script type="math/tex" id="MathJax-Element-56">G_{k+1}</script>的方法是假设每一步迭代中Gk+1<script type="math/tex" id="MathJax-Element-57">G_k+1</script>由Gk<script type="math/tex" id="MathJax-Element-58">G_k</script>加上两个附加项构成。

<script type="math/tex; mode=display" id="MathJax-Element-59">G_{k+1}y_k=G_ky_k+P_ky_k+Q_ky_k</script>
为使其满足拟牛顿条件，可令：Pkyk=δk<script type="math/tex" id="MathJax-Element-60">P_ky_k=\delta_k</script>，Qkyk=−Gkyk<script type="math/tex" id="MathJax-Element-61">Q_ky_k=-G_ky_k</script>
我们可以通过如下公式找到符合条件的PQ：
<script type="math/tex; mode=display" id="MathJax-Element-62">P_k=\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}</script>
<script type="math/tex; mode=display" id="MathJax-Element-63">Q_k=-\frac{G_ky_ky_k^TG_k}{y_k^TG_ky_k}</script>

这样就可以得到Gk+1<script type="math/tex" id="MathJax-Element-64">G_{k+1}</script>的迭代公式：

<script type="math/tex; mode=display" id="MathJax-Element-65">G_{k+1}=G_k+\frac{\delta_k\delta_k^T}{\delta_k^Ty_k}-\frac{G_k y_k y_k^T G_k}{y_k^T G_k y_k}</script>

以上就是DFP算法。如果初始G0<script type="math/tex" id="MathJax-Element-66">G_0</script>是正定的，那么可证明迭代过程中Gk<script type="math/tex" id="MathJax-Element-67">G_k</script>都是正定的。

BFGS算法

即Broyden-Fletcher-Goldfarb-Shanno算法，算是最流行的拟牛顿算法。
我们考虑用Bk<script type="math/tex" id="MathJax-Element-68">B_k</script>逼近H<script type="math/tex" id="MathJax-Element-69">H</script>，拟牛顿条件为：
Bk+1δk=yk<script type="math/tex" id="MathJax-Element-70">B_{k+1}\delta_k=y_k</script>
同样的方法：

<script type="math/tex; mode=display" id="MathJax-Element-71">B_{k+1}\delta_k=B_k\delta_k+P_k\delta_k+Q_k\delta_k</script>
<script type="math/tex; mode=display" id="MathJax-Element-72">P_k\delta_k=y_k</script>
<script type="math/tex; mode=display" id="MathJax-Element-73">Q_k\delta_k=-B_k\delta_k</script>

得到迭代公式：

<script type="math/tex; mode=display" id="MathJax-Element-74">B_{k+1}=B_k+\frac{y_ky_k^T}{y_k^T\delta_k}-\frac{B_k\delta_k\delta_k^TB_k}{\delta_k^TB_k\delta_k}</script>
跟DFP算法一样，若B0<script type="math/tex" id="MathJax-Element-75">B_0</script>正定，则Bk<script type="math/tex" id="MathJax-Element-76">B_k</script>正定。

Broyden类算法

简而言之:
Gk+1=aGDFP+(1−a)GBFGS<script type="math/tex" id="MathJax-Element-77">G_{k+1}=aG^{DFP}+(1-a)G^{BFGS}</script>
前两种方法的线性组合也满足拟牛顿条件，而且都是正定的。这里0≤a≤1<script type="math/tex" id="MathJax-Element-78">0 \leq a \leq1</script>，这样得到的一类拟牛顿算法称为Broyden类算法。

坐标下降法

coordinate descent是一种非梯度优化方法，它在每步迭代中沿一个坐标方向进行搜索，通过循环使用不同的坐标方向来达到目标函数的局部最小值。

坐标下降法不需要计算目标函数的梯度，在每步迭代中仅求解一维搜索问题。但若目标函数不光滑，则有可能陷入非驻点。

拉格朗日最优化

上面解决的都是无约束最优化问题，对于余数最优化问题中，我们常用拉格朗日对偶性(Lagrange duality)将其转换。在此我们仅说下结论。
原始问题：假设f(x),c(x),h(x)是R上的连续可微函数，考虑约束最优化：

<script type="math/tex; mode=display" id="MathJax-Element-79">min f(x)</script>
<script type="math/tex; mode=display" id="MathJax-Element-80">s.t. c_i(x)\leq0, i=1,2,\ldots,k</script>
<script type="math/tex; mode=display" id="MathJax-Element-81">h_j(x)=0, j=1,2,\ldots,l</script>

其广义拉格朗日函数(generailized Lagrange function)

<script type="math/tex; mode=display" id="MathJax-Element-82">L(x,a,b)=f(x)+\sum_{i=1}^{k}a_ic_i(x)+\sum_{j=1}^lb_jh_j(x)</script>

如果f(x)和c(x)是凸函数，h(x)是仿射函数，并且不等式约束c(x)是严格可行的，则x,a,b分别是原始问题和对偶问题的解的充要条件是其满足KKT(Karush-Kuhn-Tucker)条件：
∇xL(x,a,b)=0<script type="math/tex" id="MathJax-Element-83">\nabla_xL(x,a,b)=0</script>
∇aL(x,a,b)=0<script type="math/tex" id="MathJax-Element-84">\nabla_aL(x,a,b)=0</script>
∇bL(x,a,b)=0<script type="math/tex" id="MathJax-Element-85">\nabla_bL(x,a,b)=0</script>
aici(x)=0,i=1,2,…,k<script type="math/tex" id="MathJax-Element-86">a_ic_i(x)=0, i=1,2,\ldots,k</script>
ci(x)≤0,i=1,2,…,k<script type="math/tex" id="MathJax-Element-87">c_i(x)\leq 0, i=1,2,\ldots,k</script>
ai(x)≥0,i=1,2,…,k<script type="math/tex" id="MathJax-Element-88">a_i(x)\geq 0, i=1,2,\ldots,k</script>
hj(x)=0,i=1,2,…,l<script type="math/tex" id="MathJax-Element-89">h_j(x)=0, i=1,2,\ldots,l</script>

二次规划

二次规划(Quadratic Programmig, QP)包括凸二次优化和非凸二次优化。常用的解法有椭球法，内点发，增广拉格朗日法，梯度投影法等。