Stay inside the fence每一步都留在围栏里

Imagine walking toward a target while staying inside a triangular field. A gradient step points downhill but may cross the fence. Frank–Wolfe instead asks which allowed corner looks best under the current local slope, then travels only part of the way toward it. The whole segment stays inside a convex field.想象你要走向一个目标，但必须留在三角形场地里。直接沿梯度下坡可能越过围栏。Frank–Wolfe 则先问：按当前位置的坡度，哪个允许到达的角点最有利？再沿着通往它的线段走一部分。凸场地里的这整条线段都不会越界。

We consider a differentiable convex objective on a nonempty compact convex set. Compactness ensures that the linear subproblem attains a solution. Smoothness with bounded curvature supports the usual convergence guarantees; “convex” alone is not the entire set of assumptions.这里考虑非空紧凸集上的可微凸目标函数。紧性保证线性子问题能取得解；具有有界曲率的光滑性则支撑常见收敛保证。只说“凸”并不足以交代全部前提。

1.1

Watch one step at a time一步一步看它怎么走

The green triangle is x₁ ≥ 0, x₂ ≥ 0, x₁+x₂ ≤ 1. We minimize half the squared distance to the target. The path is the sequence of feasible iterates; the dashed segment points toward the corner selected at the current iterate. The gap is an upper bound on remaining objective error, not distance to the target.绿色三角形满足 x₁ ≥ 0、x₂ ≥ 0、x₁+x₂ ≤ 1。目标是让到目标点的距离平方的一半最小。折线表示历次可行迭代点，虚线指向当前选择的角点。间隙是剩余目标函数误差的上界，不是到目标点的距离。

Green: feasible set · cyan: target · white: iterate · orange: selected corner绿色：可行域 · 蓝色：目标 · 白色：迭代点 · 橙色：选中的角点

Separate direction from step length方向和步长，分开来想

3.1

The linear oracle chooses a direction. The step size chooses how far to go. Since the new point is a convex combination of two feasible points, no projection is needed. But the oracle still has a computational cost: projection-free does not mean constraint-free or cost-free.线性求解器负责选方向，步长负责决定走多远。新点是两个可行点的凸组合，因此不需要投影。但线性求解器本身仍有计算成本：无需投影，不等于没有约束，也不等于没有代价。

A common general schedule is γₜ = 2/(t+2), starting with t = 0. This article’s experiment instead uses exact line search for its quadratic objective. With gradient g = x−a and direction d, the unconstrained minimizing step is −g·d/(d·d); clipping it to [0,1] keeps the move on the segment.常见通用步长为 γₜ = 2/(t+2)，从 t = 0 开始。本文实验采用针对这个二次目标的精确线搜索。梯度 g = x−a、方向为 d 时，无约束最优步长是 −g·d/(d·d)；将它截到 [0,1]，就把移动限制在线段上。

3.2

For the outside target a = (0.8,0.6), starting at (0,0) gives gradient (−0.8,−0.6). The oracle picks (1,0), and line search gives γ = 0.8, so the first iterate is (0.8,0). The constrained optimum is (0.6,0.4), on the fence; its objective is 0.04, not zero.对于外部目标 a = (0.8,0.6)，从 (0,0) 出发，梯度为 (−0.8,−0.6)。线性求解器选 (1,0)，线搜索给出 γ = 0.8，于是第一步到达 (0.8,0)。约束最优点为围栏上的 (0.6,0.4)，目标函数值是 0.04，而不是零。

Know when you are close enough怎样知道已经足够接近？

4.1

Convexity gives f(x*) ≥ f(x)+∇f(x)·(x*−x). Because the oracle minimizes the linear term, replacing x* by s can only lower that linear value. Rearranging gives the gap bound above. This certificate does not require knowing the optimum; our example has a known optimum only so we can check the certificate too.由凸性可得 f(x*) ≥ f(x)+∇f(x)·(x*−x)。线性求解器最小化其中的线性项，因此用 s 替换 x*，该线性值只会更低。移项就得到上面的间隙界。这个证书不要求事先知道最优点；本例特意选已知最优点，是为了连证书本身也一起检查。

The exact oracle matters. If an approximate subproblem solution is used, its error must be accounted for before claiming the same upper bound. A small step size by itself is not a reliable stopping rule. At a zero direction, stop rather than divide by zero in the line-search formula.这里需要准确求解线性子问题。若使用近似解，在声称同样的误差上界之前必须计入子问题误差。步长很小本身不是可靠的停止条件。若方向为零，应直接停止，不要在线搜索公式中除以零。

Executable C++ with geometric checks带几何校验的 C++ 程序

#include <algorithm>
#include <array>
#include <cmath>
#include <iomanip>
#include <iostream>
using Point=std::array<double,2>;
const std::array<Point,3> vertices={Point{0,0},Point{1,0},Point{0,1}};
double dot(Point a,Point b) {return a[0]*b[0]+a[1]*b[1];}
Point sub(Point a,Point b) {return {a[0]-b[0],a[1]-b[1]};}
double objective(Point x,Point target) {auto d=sub(x,target);return 0.5*dot(d,d);}
Point oracle(Point gradient) {
    return *std::min_element(vertices.begin(),vertices.end(),[&](Point a,Point b){
        return dot(gradient,a)<dot(gradient,b);
    });
}
int main() {
    const Point target={0.8,0.6},optimum={0.6,0.4};
    Point x={0,0};
    bool valid=true;
    int steps=0;
    for(;steps<1000;++steps) {
        const Point gradient=sub(x,target),s=oracle(gradient),d=sub(s,x);
        const double gap=-dot(gradient,d);
        if(gap<=1e-8) break;
        const double length2=dot(d,d);
        if(length2==0) break;
        // Exact line search for this particular squared-distance objective.
        const double gamma=std::clamp(gap/length2,0.0,1.0);
        const Point next={x[0]+gamma*d[0],x[1]+gamma*d[1]};
        valid &= next[0]>=-1e-12 && next[1]>=-1e-12 && next[0]+next[1]<=1+1e-12;
        valid &= objective(next,target)<=objective(x,target)+1e-12;
        x=next;
    }
    const Point gradient=sub(x,target);
    const double gap=dot(gradient,sub(x,oracle(gradient)));
    const double suboptimality=objective(x,target)-objective(optimum,target);
    valid &= suboptimality>=-1e-12 && suboptimality<=gap+1e-12;
    std::cout << std::fixed << std::setprecision(8)
              << "steps=" << steps << " x=" << x[0] << ',' << x[1]
              << "\nf=" << objective(x,target) << " gap=" << gap
              << " suboptimality=" << suboptimality
              << "\nfeasible, monotone, certificate valid=" << std::boolalpha << valid << '\n';
    return valid ? 0 : 1;
}

Each step is checked for feasibility and nonincreasing objective. The final objective error is checked against the Frank–Wolfe gap. After 1,000 steps, this example gives an objective near 0.04023 and a gap near 0.00038; the printed values are the actual run results. Reaching the iteration limit is not the same as satisfying the 10⁻⁸ gap tolerance.每一步都检查可行性和目标值不增，最后还会检查目标误差不超过 Frank–Wolfe 间隙。运行 1,000 步后，本例目标值约为 0.04023、间隙约为 0.00038；页面输出的是实际运行结果。达到迭代上限，不等于满足 10⁻⁸ 的间隙停止阈值。

Why sparse steps can be useful稀疏的一步，为什么有用？

Starting at a vertex and adding at most one vertex per iteration means the iterate can be represented using at most t+1 selected vertices after t steps. For an ℓ₁ ball of radius R, the oracle picks the coordinate with the largest gradient magnitude and moves toward the opposite signed axis point. This can be cheaper than a full projection when the representation is large.从一个顶点出发，每次至多引入一个新顶点，做完 t 步后就能用至多 t+1 个已选顶点表示当前点。对于半径 R 的 ℓ₁ 球，线性求解器选择梯度绝对值最大的坐标，并指向符号相反的轴上点。表示规模很大时，这可能比完整投影更便宜。

6.1

On an ℓ₂ ball the answer is −Rg/‖g‖₂ instead; a zero gradient permits any feasible oracle output. The familiar O(1/t) objective-error rate assumes a smooth convex objective and a suitable compact domain and step rule. Strong convexity of the objective alone does not make the ordinary method uniformly linearly convergent; geometry and algorithm variants matter.若约束是 ℓ₂ 球，答案则是 −Rg/‖g‖₂；梯度为零时，任意可行点都能作为线性子问题的解。常见的 O(1/t) 目标误差收敛率需要光滑凸目标、适当的紧致定义域和步长规则。仅有目标函数强凸，并不能保证普通方法统一地线性收敛；可行域几何与算法变体都很重要。

Read further继续阅读

Jaggi (2013): Frank–Wolfe, sparse iterates, and duality-gap certificatesJaggi（2013）：Frank–Wolfe、稀疏迭代与对偶间隙证书