在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
$$
\begin{aligned}
&\min f(x) \\
&s.t. \quad g_i(x)\ge0, i=1,...,m
\end{aligned}
$$

先考虑$g_i(x)$均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将$f(x)$在$x_k$处展开，有
$$
f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k)
$$
故原问题近似于
$$
\begin{aligned}
&\min f(x)\approx f(x_k) + \nabla f(x_k)^T(x-x_k) \\
&s.t.\quad x \in S
\end{aligned}
$$
其中$S$为线性约束构成的可行域。去掉常量后，问题可以写为
$$
\begin{aligned}
&\min f(x)\approx \nabla f(x_k)^Tx \\
&s.t.\quad x \in S
\end{aligned}
$$
设此问题的最优解为$y_k$，则直观上$d_k=y_k-x_k$ 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长$0\leq\lambda\leq1$。注意到线性规划的可行域为凸集，由于$x_k$和$y_k$均为可行点，它们确定的连线均在可行域中。限制步长$0\leq\lambda\leq1$保证了一维搜索的结果在可行域中。

Frank-Wolfe算法的步骤总结如下：

1. 选择初值。初始点$x_0\in S$，给定允许误差$\epsilon>0$，令$k=0$。
2. 求解近似线性规划：$$ \begin{aligned}&\min \nabla f(x_k)^Tx \\ &s.t.\quad x \in S\end{aligned}$$ 得最优解$y_k$。
3. 构造可行下降方向。令$d_k=y_k-x_k$。若$||\nabla f(x_k)^Td_k \leq \epsilon||$，停止计算，输出$x_k$；否则，转4。
4. 进行一维搜索：$$\min_{0\leq \lambda \leq 1} f(x_k+\lambda d_k)$$得步长$\lambda_k$。令$$x_{k+1}=x_k+\lambda_k d_k \\ k \leftarrow k+1 $$，转2。

Frank-Wolfe方法将线性约束最优化问题转化为一系列线性规划问题和一维搜索问题求解。可以证明，当$f$具有连续一阶偏导数，且可行域$S$有界，Frank-Wolfe方法是收敛的。

这一段时间学习优化理论中的一些经典方法，写下一些要点和体会，帮助自己和有需要的人理解最优化方法。

１.基础知识

首先来看无约束最优化问题：
\begin{equation}
\min f(x)
\end{equation}
其中函数 $f:R^n\rightarrow R$.求解此问题的方法方法分为两大类：最优条件法和迭代法。

所谓的最优条件法，是指当函数存在解析形式，能够通过最优性条件求解出显式最优解。对于无约束最优化问题，如果$f(x)$在最优点$\bar{x}$附近可微，那么$\bar{x}$是局部极小点的必要条件为：
\begin{equation}
\nabla f(\bar{x})=0
\end{equation}

我们常常就是通过这个必要条件去求取可能的极小值点，再验证这些点是否真的是极小值点。当上式方程可以求解的时候，无约束最优化问题基本就解决了。实际中，这个方程往往难以求解。这就引出了第二大类方法：迭代法。

迭代法，也称为“搜索”法，主要思想是通过简单的运算构造点列，逐渐逼近问题的最优解。这里说的“点”是多维空间中的点，也称为“向量”。还有少部分算法通过构造点的集合来逼近问题的最优解，如单纯形调优法。

用于求解无约束最优化问题的方法可以分为解析法和直接法两大类。解析法在构造迭代公式的过程中往往使用了泰勒展开来作近似或者推导，因此迭代步骤中含有梯度$\nabla f(x)$或黑塞(Hessian)矩阵$\nabla^2f(x)$，在问题的解析形态较好的情况下使用往往能获得比较快的收敛速度。而直接法则从物理角度思考如何递推，不会用到梯度或者黑塞矩阵，它对问题的解析形态几乎没有要求，只要能计算出函数值即可。当然，它的收敛速度往往难于保证。
继续阅读 →