Dual Prices for Frank--Wolfe Algorithms

In this note we observe that for constrained convex minimization problems ${\min }_{x\in P}f(x)$ over a polytope $P$, dual prices for the linear program ${\min }_{z\in P}\mathrm{\nabla }f(x)z$ obtained from linearization at approximately optimal solutions $x$ have a similar interpretation of rate of change in optimal value as for linear programming, providing a convex form of sensitivity analysis. This is of particular interest for Frank–Wolfe algorithms (also called conditional gradients), forming an important class of first-order methods, where a basic building block is linear minimization of gradients of $f$ over $P$, which in most implementations already compute the dual prices as a by-product.