这一章介绍无约束的优化问题
Unconstrained minimization problems
无约束优化问题是最基本的优化问题。这一章讨论怎么求无约束的凸函数的最小值，特别地，假设 $f$ 总是二阶可微的。
如果 $x^\ast$ 是 $f$ 的最小值点，那么必然 $\nabla f(x^\ast) = 0$，这说明我们可以解一个可能是非线性的方程组来计算函数的最值。
当然，更多的情况下，我们会使用迭代的方法。选取一个可行的初始点 $x^{(0)}$，再不断迭代逼近问题的最优解，使得 $f(x^{(k)}) - p^\ast \leq \epsilon$，达到我们需要的精度。
在以下的讨论中，我们都假定目标函数是闭（closed ）的。函数的闭性等价于它的下半连续性，或者任意 $\alpha-\mathrm{sublevel}$ 都是闭的，或者说其 $\operatorname{epigraph}$ 是闭集。一般而言，连续函数都是闭的（闭集的原像是闭的）。
Examples
无约束优化的例子非常的多，比如：
Unconstrained geometric programming $$ \operatorname{minimize} \quad f(x)=\log \left(\sum_{i=1}^m \exp \left(a_i^T x+b_i\right)\right) $$ Analytic center of linear inequalities $$ \operatorname{minimize} \quad f(x)=-\sum_{i=1}^{m} \log \left(b_{i}-a_{i}^{T} x\right) $$
这个问题的定义域是一个开多面体，当 $x$ 接近多面体的边缘时，$f(x) \to \infty$
上述问题的解叫做这个多面体的 analytic center.
Analytic center of a linear matrix inequality $$ \begin{aligned} & \operatorname{minimize} \quad f(x)=\log \operatorname{det} F(x)^{-1}\\ & \mathrm{where} \quad F(x)=F_{0}+x_{1} F_{1}+\cdots+x_{n} F_{n} \end{aligned} $$
Strong convexity
强凸 (strong convex) 是一个比严格凸更强的性质。定义 $f$ 是强凸的，如果存在 $m > 0$，使得 $$ \begin{equation} f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|_{2}^{2} \label{eq-unconstrained:strong-convexity} \end{equation} $$ 对于任意的 $x, y \in \operatorname{dom} f$ 都成立。这蕴含着强凸函数有着某个二次函数的作为其下界。
强凸函数不一定需要可微，对不可微的函数，可以把上面的梯度换成次微分。
也有不用到微分的等价定义： $$ f(t x+(1-t) y) \leq t f(x)+(1-t) f(y)-\frac{1}{2} m t(1-t)\|x-y\|_{2}^{2}, \quad t \in [0, 1] $$ 如果 $f$ 二阶可微，那么强凸意味着存在 $m > 0$，使得 $$ \nabla^2 f \succeq mI, \;\;\forall x \in \operatorname{dom}f $$
不等式 $\eqref{eq-unconstrained:strong-convexity}$ 可以用来界定 $f(x) - p^{\ast}$ :
如果 $f$ 的Hessian矩阵的特征值有下确界 $m>0$，那在这个条件下，由Taylor展开： $$ f(y)=f(x)+\nabla f(x)^{T}(y-x)+\frac{1}{2}(y-x)^{T} \nabla^{2} f(z)(y-x) $$
其中 $z$ 是线段 $[x,y]$ 上的一点。继而，我们有：
$$ f(y) \geq f(x)+\nabla f(x)^{T}(y-x)+\frac{m}{2}\|y-x\|_{2}^{2} $$
这给出了函数的一个更好的下界。注意到右边是一个二次函数，如果 $y$ 是最优的，也即 $f(y) = p^\star$，我们就能有： $$ \begin{aligned} f(y) & \geq f(x)+\nabla f(x)^T(y-x)+\frac{m}{2}\|y-x\|_2^2 \\ & \geq f(x)+\nabla f(x)^T(\tilde{y}-x)+\frac{m}{2}\|\tilde{y}-x\|_2^2 \\ &=f(x)-\frac{1}{2 m}\|\nabla f(x)\|_2^2 \end{aligned} $$ 取 $\tilde{y}=x-(1 / m) \nabla f(x)$ 最小化了右边的二次函数。上式对所有的 $y$ 都是成立的，于是得到：
$$ p^{\star} \geq f(x)-\frac{1}{2 m}\|\nabla f(x)\|_2^2 \quad \Longleftrightarrow \quad f(x) - p^{\star} \leq \frac{1}{2 m}\|\nabla f(x)\|_2^2 $$
上式说明，当 $\nabla f$ 模长很小很小的时候，$f(x)$ 跟最优值 $p^\ast$ 的距离也很小很小。虽然这个结论看起来很显然，但是我们从数学的角度证明了它！
另一方面，在 $\eqref{eq-unconstrained:strong-convexity}$ 中令 $y=x^\star$，得到 $$ \begin{aligned} p^{\star}=f\left(x^{\star}\right) & \geq f(x)+\nabla f(x)^T\left(x^{\star}-x\right)+\frac{m}{2}\left\|x^{\star}-x\right\|_2^2 \\ & \geq f(x)-\|\nabla f(x)\|_2\left\|x^{\star}-x\right\|_2+\frac{m}{2}\left\|x^{\star}-x\right\|_2^2 \end{aligned} $$
因为 $p^\star \leq f(x)$，就有： $$ -\|\nabla f(x)\|_2\left\|x^{\star}-x\right\|_2+\frac{m}{2}\left\|x^{\star}-x\right\|_2^2 \leq 0 \;\; \Longrightarrow \;\; \left\|x-x^{\star}\right\|_2 \leq \frac{2}{m}\|\nabla f(x)\|_2 $$
当 $f$ 不是强凸的时候，$\nabla f$ 无法刻画与最优值的接近程度。比如 $f(x) = |x|$.
另一个我们常加的条件是，在闭集 $S$ 上，$f$ 的Hessian矩阵的特征值有上确界 $M$（因为闭集，保证了上确界存在）。我们可以得到类似式 $\eqref{eq-unconstrained:strong-convexity}$ 的结论
$$ f(y) \leq f(x)+\nabla f(x)^{T}(y-x)+\frac{M}{2} \|y-x\|_{2}^{2}\tag{3} $$
这其实就给出了函数的一个上界。
$\nabla^2 f \preceq MI$ 这个条件可以推出 $\nabla f$ 这个多元向量值函数满足 Lipschiz 条件。
这两个条件综合起来，就是
$$ m I \preceq \nabla^{2} f(x) \preceq M I \;\, ,\quad \forall x \in S $$
类似有结论 $$ p^{\star} \leq f(x)-\frac{1}{2 M}\|\nabla f(x)\|_2^2 $$ 综合起来 $$ \frac{1}{2 M}\|\nabla f(x)\|_2^2 \leq f(x) - p^\star \leq \frac{1}{2 m}\|\nabla f(x)\|_2^2 $$
Condition number of sublevel sets
之前讨论的，给 $f$ 二阶导添加的限制条件 $$ m I \preceq \nabla^2 f(x) \preceq M I $$ $\kappa=M/m$ 是 $\nabla^2 f$ 条件数的上确界，即 $\nabla^2 f$ 最大特征值与其最小特征值的比值。
定义一个凸集的 $C$ 在方向 $q\;\, (\|q\|_2=1)$ 上的宽度为：
$$ W(C, q)=\sup _{z \in C} q^{T} z-\inf _{z \in C} q^{T} z $$
从而一个凸集的最大宽度和最小宽度定义为：
$$ W_{\min }=\inf _{\|q\|_{2}=1} W(C, q), \quad W_{\max }=\sup _{\|q\|_{2}=1} W(C, q) $$
凸集 $C$ 的条件数被定义为： $$ \operatorname{cond}(C)=\frac{W_{\max }^{2}}{W_{\min }^{2}} $$ 条件数在一定程度上反映了凸集的一个形状（比较圆，还是扁的）。
The condition number of $C$ gives a measure of its anisotropy or eccentricity.
对于一个椭球 $\mathcal{E}=\left\{x \mid\left(x-x_0\right)^T A^{-1}\left(x-x_0\right) \leq 1\right\}$，它的条件数就是
$$ \operatorname{cond}(\mathcal{E})=\frac{\lambda_{\max }(A)}{\lambda_{\min }(A)}=\kappa(A) $$
如果凸函数 $f$ 在其 $\alpha$ 下水平集 $C_\alpha$ 上满足
$$ m I \preceq \nabla^{2} f(x) \preceq M I $$
那么 $C_\alpha$ 有一个上界
$$ \operatorname{cond}\left(C_{\alpha}\right) \leq \frac{M}{m} $$
**下水平集的形状会对无约束的凸优化问题某些算法的收敛性产生巨大影响。**就梯度下降法而言，当条件数非常大的时候，梯度下降法的效率很低（zig-zag 现象十分严重）。
Descent methods
下降方法的目标是找一列 $x^{(k)}$，使得函数值慢慢下降，最终收敛的一种算法。
具体来说，每次迭代，我们想找到一个下降方向 (direction/step) $\Delta x^{(k)}$，然后在这个方向上前进步长(step size) $t^{(k)}$，达到一个使函数值更小的点： $$ x^{(k+1)}=x^{(k)}+t^{(k)} \Delta x^{(k)}\quad \text{and} \quad f(x^{(k+1)})<f(x^{(k)}) $$
下降方向 $\Delta x^k$ 都要满足 $\nabla f\left(x^{(k)}\right)^{T} \Delta x^{(k)}<0$ .
下降算法的基本流程是： $$ \begin{aligned} & \text{given a starting point } x \in \text{dom} f. \\ & \textbf{repeat} \\ & \quad \text{1. Determine a descent direction } \Delta x. \\ & \quad \text{2. } \textit{Line search. } \text{ Choose a step size } t > 0. \\ & \quad \text{3. } \textit{Update. } x:= x + t \Delta x. \\ & \textbf{until} \text{ stoping criterion is satisfied.} \end{aligned} $$
线搜索
线搜索（line search）可以分为精确线搜索和非精确线搜索两种，其区别就在于，给定下降方向，是否找到这个方向上的最小点，亦或只要求在这个方向上有一定程度的下降。
Backtracking line search 是一种非精确线性搜索算法。
大致原理如图：
贴一张关于收敛性的结论：
Gradient descent method
梯度下降法是一种直接用梯度作为下降方向的方法。
Convergence analysis
记 $x^{+} = x + t \Delta x, \, \tilde{f}(t) = f(x - t\Delta x)$
$$ \begin{equation} \tilde{f}(t) \leq f(x)-t\|\nabla f(x)\|_2^2+\frac{M t^2}{2}\|\nabla f(x)\|_2^2 \label{eq-unconstrained:convergence-analysis-for-GD} \end{equation} $$
Exact line search
式 $\eqref{eq-unconstrained:convergence-analysis-for-GD}$ 这个不等式的右端是一个关于 $t$ 的二次函数，当 $t=1/M$ 时取得最小 。
$f$ 的 $\beta$-smooth 从理论上保证了梯度下降法是一个下降方法。
于是我们能得到： $$ f\left(x^{+}\right)=\tilde{f}\left(t_{\text {exact }}\right) \leq f(x)-\frac{1}{2 M}\|\nabla(f(x))\|_2^2 . $$ 两边同时减去 $p^\star$ $$ f\left(x^{+}\right)-p^{\star} \leq f(x)-p^{\star}-\frac{1}{2 M}\|\nabla f(x)\|_2^2 . $$ 将 $\|\nabla f(x)\|_2^2 \geq 2 m\left(f(x)-p^{\star}\right)$ 代入，即得 $$ f\left(x^{+}\right)-p^{\star} \leq(1-m / M)\left(f(x)-p^{\star}\right) \;\;\Rightarrow \;\; \frac{f\left(x^{+}\right)-p^{\star}}{f(x)-p^{\star}} \leq 1- \frac{m}{M} $$ 这说明 $f\left(x^{(k)} \right) - p^\star$ 是以 $\left(1 - \displaystyle\frac{m}{M}\right)^k$ 这一速度收敛到0的。
这个线性收敛的理论结果是建立在 $f$ 的 $\alpha$-strongly convex 和 $\beta$-smooth 的性质基础上的。
Backtracking line search
Steepest decent method
$f(x+v)$ 在 $x$ 处的 Taylor 展开是： $$ f(x+v) \approx \widehat{f}(x+v)=f(x)+\nabla f(x)^{T} v $$ 最速下降法企图找到一个方向 (normalized steepest direction) $$ \Delta x_{\mathrm{nsd}}=\operatorname{argmin}\left\{\nabla f(x)^{T} v \mid \|v\|=1\right\} $$
注意，因为选取的范数不一样，情况是会发生变化的。
如果取欧几里得范数（也就是二范数），就是梯度下降法了。因此，可以认为最速下降法的思想是梯度下降法自然的推广。
如果取一个特殊的 quadratic norm：
$$ \|z\|_{P}=\left(z^{T} P z\right)^{1 / 2}=\left\|P^{1 / 2} z\right\|_{2} \; ,\;\; P > 0 $$
最后得到的方向是
$$ \Delta x_{\mathrm{nsd}}=-\left(\nabla f(x)^{T} P^{-1} \nabla f(x)\right)^{-1 / 2} P^{-1} \nabla f(x) $$
$\min \;a^Tx, st. \;x^TPx=1$这个优化问题可以用它的KKT条件解出。
这样做的好处就在于，梯度下降法 当下水平集条件数特别大的时候，收敛性会特别差。但是如果加以适当的坐标变换，把椭圆形状的等高线变换为比较规则的圆形的等高线，就可以大大加快算法收敛的速度。
如果我们可以估计出在最优点$x^\ast$的Hessian矩阵$\hat{H}$，那么取$P=\hat{H}$，这时候的steepest decent method 就可以取得很好的效果！
Newton’s method
Newton step
对 $x \in \text{dom} f$ $$ \Delta x_{\text{nt}}=-\nabla^{2} f(x)^{-1} \nabla f(x) $$
叫做 $f$ 在 $x$ 这点的 Newton step。如果 $\nabla^2 f$ 是正定的，那么 $$ \nabla f(x)^{T} \Delta x_{\mathrm{nt}}=-\nabla f(x)^{T} \nabla^{2} f(x)^{-1} \nabla f(x)<0 \qquad (\text{unless }\; \nabla f(x)=0) $$ Newton 方向自然成为了一个下降方向。Newton 方向可以有多种解释。
Minimizer of second-order approximation
$f$ 在 $x$ 处的二阶近似是 $$ \widehat{f}(x+v)=f(x)+\nabla f(x)^T v+\frac{1}{2} v^T \nabla^2 f(x) v $$ 这是一个关于 $v$ 的二次函数，当 $v = \Delta x_{\text{nt}}$ 时取得最小。
当 $f$ 近似是一个二次函数的时候，$x+\Delta x_{\text{nt}}$ 是 $f$ 最小值点的好的近似。
Steepest descent direction in Hessian norm
定义范数 $$ \begin{equation} \|u\|_{\nabla^2 f(x)}=\left(u^T \nabla^2 f(x) u\right)^{1 / 2} \label{eq:unconstrained-Newton-norm} \end{equation} $$ $\Delta x_{\text{nt}}$ 就是这种范数下，$f$ 下降最快的方向。
Solution of linearized optimality condition
如果 $x$ 在最小值点 $x^\star$ 附近，那么 $$ \nabla f(x+v) \approx \nabla f(x)+\nabla^2 f(x) v=0 $$ $v = \Delta x_{\text{nt}}$ 是这个方程组的解
The Newton decrement
$$ \lambda(x)=\left(\nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x)\right)^{1 / 2} $$
叫做 $f$ 在 $x$ 处的 Newton decrement . 它在收敛性分析中有重要左右，此外，它也是一个重要的停止准则。
注意到： $$ f(x)-\inf _y \widehat{f}(y)=f(x)-\widehat{f}\left(x+\Delta x_{\mathrm{nt}}\right)=\frac{1}{2} \lambda(x)^2 $$ 于是 $\lambda^2/2$ 可以作为 $f(x)-p^\star$ 的一个估计。
$\lambda(x)$ 也可以表示为： $$ \lambda(x)=\left(\Delta x_{\mathrm{nt}}^T \nabla^2 f(x) \Delta x_{\mathrm{nt}}\right)^{1 / 2} $$ 它就是 $\Delta x_{\text{nt}}$ 在范数 $\eqref{eq:unconstrained-Newton-norm}$ 下的范数。
Newton’s method
Newton 方法的过程如下： $$ \begin{aligned} & \text{given a starting point } x \in \operatorname{dom} f, \text{ tolerance } \epsilon>0. \\ & \textbf{repeat} \\ & \quad \text{1. Compute the Newton step and decrement } \\ & \qquad\qquad \Delta x_{\mathrm{nt}}:=-\nabla^2 f(x)^{-1} \nabla f(x) ; \quad \lambda^2:=\nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) . \\ & \quad \text{2. Stopping criterion. } \textbf{quit} \text{ if } \lambda^2 / 2 \leq \epsilon.\\ & \quad \text{3. } \textit{Line search. } \text{ Choose a step size } t > 0 \text{ by backtracking line search.} \\ & \quad \text{4. } \textit{Update. } x:= x + t \Delta x_{\text{nt}}. \\ \end{aligned} $$ 如果我们使用一个固定步长 $t=1$，则叫做 pure Newton method.
Convergence analysis
Self-concordance
Self-concordant functions on $\mathbf{R}$
称 $\mathrm{R}$ 上的凸函数 $f$ self-concordant ，如果： $$ \left|f^{\prime \prime \prime}(x)\right| \leq 2 f^{\prime \prime}(x)^{3 / 2} $$
如果 $\left|f^{\prime \prime \prime}(x)\right| \leq k f^{\prime \prime}(x)^{3 / 2}$，那么 $\tilde{f}(x)=\left(k^2 / 4\right) f(x)$ 就会满足 $\left|f^{\prime \prime \prime}(x)\right| \leq 2 f^{\prime \prime}(x)^{3 / 2}$ .