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

最新推荐文章于 2024-03-10 01:14:18 发布

超级无敌小小顺利

最新推荐文章于 2024-03-10 01:14:18 发布

阅读量5.8k

点赞数 7

分类专栏：最优化理论与算法文章标签：约束优化算法最优化 Frank-Wolfe方法

本文链接： https://blog.csdn.net/qq_36342854/article/details/103740879

版权

最优化理论与算法专栏收录该内容

6 篇文章 11 订阅

订阅专栏

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

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

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

二、确定可行方向

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

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

三、确定移动步长

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