Dual Prices for Frank--Wolfe Algorithms

In this note we observe that for constrained convex minimization problems minx ∈ Pf(x) over a polytope P, dual prices for the linear program minz ∈ P 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.