约束优化方法_2_——Frank-Wolfe方法

Frank-Wolfe方法属于约束优化中可行方向法的一种。上一篇博文对同类型的Zoutendijk可行性方法进行了介绍，这一部分着重关注Frank-Wolfe方法。Frank-Wolfe方法的基本思想是：每次迭代中使用一阶泰勒展开式将目标函数线性化，通过解线性规划得到可行方向，进而沿此方向在可行域内作一维搜索。

一、Frank-Wolfe所针对的优化问题

首先要明确这个算法的提出是针对哪一种问题。之前的Zoutendijk可行性方法可以解 等式线性约束+不等式线性约束，而Frank-Wolfe方法只能解等式线性约束下的非线性规化问题，形式如下 $min f(x) \ \ \ \\ s.t. \ \ \ Ax=b \ \ \ \& \ \ \ x\geqslant 0$minf(x)   s.t.   Ax=b   &   x⩾0

二、确定可行方向

首先在初始可行点$x^{(k)}$x(k)处进行考察，将$f(x)$f(x)在$x^{(k)}$x(k)处进行一阶Taylor多项式进行展开：$f(x)=f(x^{(k)})+\triangledown f(x^{(k)})^T(x-x^{(k)})=\triangledown f(x^{(k)})^T x+[f(x^{(k)})-f(x^{(k)})^Tx^{(k)}]$f(x)=f(x(k))+▽f(x(k))T(x−x(k))=▽f(x(k))Tx+[f(x(k))−f(x(k))Tx(k)]问题转化为在可行域$S$S内最小化这个一阶展开式：$min \ \ \ \triangledown f(x^{(k)})^T x+[f(x^{(k)})-f(x^{(k)})^Tx^{(k)}] \\ s.t. \ \ \ x\in S$min   ▽f(x(k))Tx+[f(x(k))−f(x(k))Tx(k)]s.t.   x∈S考虑到方括号内为常数，去掉之后变为：$min \ \ \ \triangledown f(x^{(k)})^T x \\ s.t. \ \ \ x\in S$min   ▽f(x(k))Txs.t.   x∈S求解这个线性规划可以得到最优解$y^{(k)}$y(k)，由线性规划知识可以知道一定在$S$S的极点达到。
现在研究变动后的$y^{(k)}$y(k)对函数值的影响，也就是运动方向$d$d和函数梯度的乘积$\triangledown f(x^{(k)})^T(y^{(k)}-x^{(k)})$▽f(x(k))T(y(k)−x(k))。此时共有两种情况：

**1.**若乘积为0，则方向无法和梯度构成钝角，x^{(k)}是原问题KT点。
**2.**若乘积小于0，则方向可以和梯度构成钝角，使得函数值继续下降。
(注：$y^{(k)}$y(k)是用于确定方向，而不是下一步迭代点，更像一个“导航点”)

三、确定移动步长

连接初始点$x^{(k)}$x(k)和导航点$y^{(k)}$y(k)，在此直线上进行一维搜索，则步长区[0,1]：$min \ \ \ f(x^{(k)}+\lambda (y^{(k)}-x^{(k)})) \\ s.t. \ \ \ \lambda \in[0,1]$min   f(x(k)+λ(y(k)−x(k)))s.t.   λ∈[0,1]得到$\lambda$λ之后即可得到下一个可行点：$x^{(k+1)}=x^{(k)}+\lambda (y^{(k)}-x^{(k)})$x(k+1)=x(k)+λ(y(k)−x(k))

四、算法分析

Frank-Wolfe方法每次迭代时，搜索方向总时指向某个极点，当接近最优解时，搜索方向和函数梯度趋于正交，并不是最好的搜索方向。但是由于它将非线性规化问题转化为了一系列线性规划问题，有时可以达到好的计算效果。