Frank-Wolfe可行方向法求解算法设计与实现，有没有关于此算法比较简单的C++代码？

Question

在无约束最优化问题的基础上，我们可以进一步来求解约束最优化问题。约束最优化问题的一般形式为：
minf(x)s.t.gi(x)≥0,i=1,...,m
minf(x)s.t.gi(x)≥0,i=1,...,m
先考虑gi(x)gi(x)均为线性函数的情况，此时问题与线性规划的约束条件相同，仅仅是目标函数变成了非线性的。我们可以用泰勒展开对目标函数进行近似，将它线性化。将f(x)f(x)在xkxk处展开，有
f(x)≈f(xk)+∇f(xk)T(x−xk)
f(x)≈f(xk)+∇f(xk)T(x−xk)

故原问题近似于
minf(x)≈f(xk)+∇f(xk)T(x−xk)s.t.x∈S
minf(x)≈f(xk)+∇f(xk)T(x−xk)s.t.x∈S

其中 SS为线性约束构成的可行域。去掉常量后，问题可以写为
minf(x)≈∇f(xk)Txs.t.x∈S
minf(x)≈∇f(xk)Txs.t.x∈S

设此问题的最优解为 ykyk，则直观上 dk=yk−xkdk=yk−xk 应当为原问题的可行下降方向。沿着此方向做一维搜索则可进行一次迭代。为了防止一维搜索的结果超出可行域，我们限制步长 0≤λ≤10≤λ≤1。注意到线性规划的可行域为凸集，由于 xkxk和 ykyk均为可行点，它们确定的连线均在可行域中。限制步长 0≤λ≤10≤λ≤1保证了一维搜索的结果在可行域中。
Frank-Wolfe算法的步骤总结如下：

选择初值。初始点x0∈Sx0∈S，给定允许误差ϵ>0ϵ>0，令k=0k=0。
求解近似线性规划：
min∇f(xk)Txs.t.x∈S
min∇f(xk)Txs.t.x∈S
得最优解ykyk。
构造可行下降方向。令dk=yk−xkdk=yk−xk。若∇f(xk)Tdk≤ϵ ∇f(xk)Tdk≤ϵ ，停止计算，输出xkxk；否则，转4。
进行一维搜索：
min0≤λ≤1f(xk+λdk)
min0≤λ≤1f(xk+λdk)
得步长λkλk。令
xk+1=xk+λkdkk←k+1
xk+1=xk+λkdkk←k+1
，转2。

Answer 1

你好，我是有问必答小助手，非常抱歉，本次您提出的有问必答问题，目前超出我们的服务范围，暂时无法为您解答。

首次提问人员可免费体验一次有问必答服务。目前首次提问的问题服务范围为：编程语言、Java开发、python、数据库、前端开发 领域专业技术问题，为您提供问题的解决思路和指导。不提供源码代写、项目文档代写、论文代写、作业代写、安装包资源发送或安装、软件使用指导等服务。

我们后续会持续优化，扩大我们的服务范围，为您带来更好地服务。