本文对凸优化问题的解法进行简单的归纳整理，仅供引入，对于详细的使用与证明请自行查阅资料。
下降方法
无约束优化问题
\[
\min f(x)
\]
其中 \(f: \mathbb{R}^n →
\mathbb{R}\) 是二次可微凸函数(这意味着 domf 是开集)。我们假定
该问题存在唯一的最优点 ，用 \[p^*\] 表示最优值 \[\inf_x f(x) = f(x^*)\]
目标函数在 \(S\) 上是强凸的，存在
\(m>0\) 使得 \(\nabla ^2 f(x) > mI\) 对任意的 \(x\in S\) 都成立。
无约束问题中我们讨论下降方法。方法需要一个适当的初始点
\(x^{(0)}\) 必须属于 $f $，
并且下水平集是闭集。
算法产生一个优化点列 \(x^{(k)},k =
1,...\), 其中
\[
x^{(k+1)} = x^{(k)} + t^{(k)}\Delta x^{(k)}
\]
且当 \(x^{(k)}\) 不是最优点时，\(t^{(k)} >0\)。其中， \(\Delta x\in \mathbb{R}^n\)
称为步径或搜索方向，\(t^{(k)}
\ge0\)称为步长。对于下降方法，我们需要满足 \(x^{(k)}\) 不是最优点时 \(f(x^{(k+1)}) 因此，搜索方向必须满足\(\nabla f(x^{(k)})^T\Delta x^{(k)}<0\) , 即它与负梯度方向夹角必须是锐角，称这样的方向为下降方向。 对于步长考虑两种方法： 精确直线搜索： \[t = \arg\min_{s\ge0} f(x+s\Delta x)\], 即对得到的方向找到下降最大的步长 回溯直线搜索 ：给定下降方向与参数 \(\alpha,\beta, 0<\alpha < 0.5, 0<\beta<1\)。\(t := 1\)。当 \(f(x+\Delta x)>f(x) + \alpha t\nabla f(x)^T\Delta x\) 时，令 \(t:=\beta x\)。回溯直线搜索并不需要得到一个精确的步长，只是希望得到一个步长使函数指有一定的减小，即 \(f(x+\Delta x)\le f(x) + \alpha t\nabla f(x)^T\Delta x\)，落在下图的虚线之间 (图源：《凸优化》，Stephen Boyd等著，王书宁等译) image-20200101101514620 接下来我们介绍几个下降方法 梯度下降方法 用负梯度作搜索方向，即令\(\Delta x = -\nabla f(x)\)， 是一种自然的选择。相应的方法被称为梯度下降方法。 最速下降方法 规范化的最速下降方向：令 \(\vert\vert \cdot \vert\vert\) 为 \(\mathbb{R}^n\) 上的任意范数。定义一个规范化的最速下降方向 (相对于范数) 为 \[ \Delta x_{\mathrm{nsd}} = \arg\min\{\nabla f(x)^Tv\quad\vert \quad\vert\vert v\vert\vert = 1\} \] 非规范化的最速下降方向 ：\[\vert\vert\cdot\vert\vert_* \] 表示对偶范数 \[ \Delta x_{\mathrm{sd}} = \vert\vert\nabla f(x)\vert\vert_*\Delta x_{\mathrm{nsd}}, \] 当范数为 Euclid 范数时，最速下降方向就是负梯度方向。采用 Euclid 范数的最速下降方法就是梯度下降方法。 Newton 方法 对于 \(x\in\mathbf{dom}f\)， 称向量 \[ \Delta x_{\mathrm{nt}} = -\nabla^2f(x)^{-1}\nabla f(x) \] 为 ( \(f\) 在 \(x\) 处的) Newton 步径。由 \(\nabla ^2f(x)\) 的正定性可知，当 \(\nabla f(x) \neq 0\)，有 \[ \nabla f(x)^T\Delta x_{\mathrm{nt}} = -\nabla f(x)^T\nabla^2f(x)^{-1}\nabla f(x) < 0 \] 因此 Newton 步径是下降方向(除非 \(x\) 是最优点)。 Newton 步径是 \(x\) 处采用 Hessian 矩阵定义的二次范数 \(\vert\vert u\vert\vert_{\nabla^2f(x)} = (y^t\nabla^2f(x)u)^{1/2}\) 导出的最速下降方法。函数 \(f\) 在 \(x\) 处的二阶 Taylor 近似是关于 \(v\) 的二阶凸函数，且在 \(v = \Delta x_{\mathrm{nt}}\) 时达到最小值。因此Newton 方法在 \(x^*\) 附近二阶近似的方法。 等式约束优化 等式约束优化问题 \[ \min f(x)\\ \mathbf{s.t.} Ax = b \] 其中 \(f: \mathbb{R}^n → \mathbb{R}\) 是二次连续可微凸函数。我们假定 $A^{pn}， A = p < n $, 即等式约束数少于变量数且等式约束相互独立 该问题存在唯一的最优点 ，用 \(p^*\) 表示最优值 \(\inf\{f(x)\vert Ax = b\} = f(x^*)\) 消除等式约束 可行解 \[ \{x\vert Ax = b\} = \{Fz+\hat{x}\vert z \in \mathbb{R}^{n-p}\}\], 新的优化问题为： \[ \min \tilde{f}(z) = f(Fz+\hat{x}) \] 用对偶方法求解 即 \(f^*\) 为\(f\) 的共轭，对偶问题为 \[ \max -b^Tv-f^*(-A^Tv) \] 若原问题存在最优解，Slater 条件成立，强对偶性成立，最优对偶目标可以达到。如果对偶函数 \(g\) 是二次可微的，可以无约束优化方法极大化 \(g\), 一旦找到最优的对偶变量 \[v^*\]，我们就可以由它构造出原问题的最优解 \[x^*\]。 障碍方法 含有不等式约的凸束优化问题 \[ \min f_0(x)\\ \mathbf{s.t.} f_i(x)\le 0, i = 1,...,m\\ Ax = b\\ \] 其中 \(f_0,...,f_m: \mathbb{R}^n → \mathbb{R}\) 是二次连续可微凸函数。我们假定 $A^{pn}， A = p < n $, 即等式约束数少于变量数且等式约束相互独立 该问题存在唯一的最优点 ，用 \[p^*\] 表示最优值 \[\inf\{f(x)\vert Ax = b\} = f(x^*)\] 内点法通过将其简化成一系列线性等式约束问题求解线性等式和不等式约束的优化问题。我们将集中讨论一种特殊的内点法，障碍法。 对数障碍函数 我们知道，可以用示性函数将不等式约束隐含在目标函数中： \[ \min F(x) = f_0(x) + \sum_{i = 1}^m I\_(f_i(x)) + \sum_{i=1}^pI_0(h_i(x))\\ \mathbf{s.t.}Ax = b\\ \] 其中 \[ \begin{equation} I\_(u)= \begin{cases} 0& u\le0\\ \infty& u>0 \end{cases} \end{equation} \] 障碍方法的基本思想是用函数近似示性函数, 主要使用以下函数 \[ \hat{I}\_(u) = -(1/t)\log(-u) \] 我们将函数 \[ \phi (x) = -\sum_{i = 1}^m \log(-f_i(x)) \] 称为问题的对数障碍函数或对数障碍。其定义域是满足问题的严格不等式约束的点集。不管正参数 t 取什么值， 对于任意 \(i\)，当 \(f_i(x) → 0\) 时，对数障碍函数将趋于无穷大。 障碍方法 image-20200101145804053 (图源：《凸优化》，Stephen Boyd等著，王书宁等译) 障碍方法给不等式约束一个无穷大的惩罚从而使得到的解一定满足原问题可行。然而这不能得到原问题的最优解。但随着 \(t\) 逐渐增加，当 \(t → \infty\) 时，障碍函数的影响较小，我们可以得到最优解。 外部罚函数法 外部罚函数法通过给原问题增加一个惩罚函数将有约束最优化问题转化为求解无约束最优化问题。它是在不可行解中得到最优解，通过迭代使解逐渐可行。（障碍法也被称为内部罚函数法） 这里只做简单介绍：外部罚函数法添加的罚函数会对不满足约束的的变量一个较大的惩罚，与对偶函数不同的是，它不会给满足约束的变量奖励。外部罚函数法得到的不一定是可行解，与障碍法相同，它通过迭代改变原函数与惩罚函数的比例，通过逐渐增大惩罚函数因子使最优解逐渐可行。