Reader question: Portfolio constraints can make ordinary gradient steps infeasible. Must every iteration solve an expensive projection back into the feasible set, or can we move through the constraint geometry using only a simpler linear optimisation problem?

The Frank–Wolfe algorithm—also called the conditional-gradient method—replaces projection with a linear minimization oracle. At each iteration it asks which feasible extreme point is most aligned with the negative gradient, then moves partway toward that point.

For long-only fully invested portfolios, this creates a particularly transparent geometry: every iterate is a convex combination of feasible vertices, so feasibility is preserved automatically and early iterates are naturally sparse.

This article owns one precise computational job: projection-free first-order optimisation of smooth convex portfolio objectives over compact convex constraint sets. It does not own covariance estimation, nonconvex cardinality optimisation, ADMM/proximal splitting, interior-point quadratic programming or portfolio theory itself.

This is public mathematical and computational education. It is not an investment recommendation and does not imply that a mathematically optimal portfolio is economically optimal out of sample.

1. A portfolio optimisation template

Consider a long-only mean–variance objective:

f(w) = ½ w^TΣw − λ μ^Tw,

subject to:

w_i ≥ 0,

1^Tw = 1.

Here:

w is the vector of portfolio weights;
Σ is the covariance matrix;
μ is the expected-return vector;
λ controls return preference relative to variance.

The feasible set is the probability simplex.

2. Why projected gradient can be awkward

An unconstrained gradient step is:

z_t+1 = w_t − η∇f(w_t).

But z may contain negative weights and fail to sum to one.

Projected gradient repairs it through:

w_t+1 = Π_D(z_t+1),

where Π_D is the Euclidean projection onto feasible set D.

For a simplex, projection is manageable. For more complex polytopes, flow constraints, atomic norm balls or structured feasible sets, projection can be materially harder than linear optimisation.

Frank–Wolfe asks whether we can avoid projection entirely.

3. Linearize the objective

At current iterate w_t, approximate the smooth convex objective by its first-order model:

f(w) ≈ f(w_t) + ∇f(w_t)^T(w−w_t).

The constant terms do not affect the minimizer, so solve:

s_t = argmin_s∈D ∇f(w_t)^Ts.

This is the linear minimization oracle (LMO).

4. On the simplex, the oracle is almost trivial

The simplex vertices are the unit vectors e₁,…,e_n.

A linear function over a simplex attains its minimum at a vertex.

Therefore:

j* = argmin_j [∇f(w_t)]_j,

s_t = e_j*.

For the mean–variance objective:

∇f(w) = Σw − λμ.

The oracle selects the asset whose gradient coordinate offers the strongest local improvement.

5. Move toward the oracle solution

Define direction:

d_t = s_t − w_t.

Update:

w_t+1 = w_t + γ_td_t,

where:

0 ≤ γ_t ≤ 1.

Because w_t+1 is a convex combination of two feasible points, it remains feasible automatically.

6. Step-size choices

Common choices include:

open-loop: γ_t = 2/(t+2);
exact line search: minimize f(w_t+γd_t) over γ∈[0,1];
short-step/backtracking: use smoothness information or adaptive sufficient decrease.

For a convex quadratic objective, exact line search is inexpensive.

7. Exact line search for mean–variance

For:

f(w)=½w^TΣw−λμ^Tw

and direction d, the derivative along γ is:

d/dγ f(w+γd) = ∇f(w)^Td + γ d^TΣd.

If d^TΣd > 0, the unconstrained minimizer is:

γ* = −∇f(w)^Td / (d^TΣd).

Then clip:

γ_FW = min(1,max(0,γ*)).

If the quadratic curvature denominator is nearly zero, numerical safeguards are required.

8. The Frank–Wolfe duality gap

Define:

g(w_t) = ∇f(w_t)^T(w_t−s_t).

For convex differentiable f over compact convex D:

f(w_t) − f(w*) ≤ g(w_t).

The gap is therefore both:

a first-order stationarity measure;
an upper bound on primal suboptimality in the convex setting.

This is one of Frank–Wolfe’s strongest audit features: the linear oracle generates its own stopping certificate.

9. Why early iterates are sparse

Start from one simplex vertex.

Every classical Frank–Wolfe iteration adds at most one new vertex to the convex combination.

After t iterations, the iterate can be represented using at most roughly t+1 active vertices.

For portfolios, that means early stopping creates a sparse portfolio without explicitly adding an ℓ₀ cardinality constraint.

This sparsity is algorithmic, not a proof that the sparse portfolio is the optimum of a cardinality-constrained problem.

10. The classical convergence rate

For a smooth convex objective with bounded curvature over a compact set, classical Frank–Wolfe achieves an objective gap of order:

O(1/t).

Jaggi’s modern analysis uses a curvature constant and the Frank–Wolfe gap to provide projection-free primal–dual convergence guarantees.

The rate is sublinear, so high precision can require many iterations.

11. Boundary zig-zag is the classic weakness

Suppose the optimum lies on a face spanned by several assets.

Vanilla Frank–Wolfe can repeatedly move toward a new vertex but has no direct mechanism for aggressively removing weight from a previously chosen bad vertex.

It can zig-zag near the boundary with tiny forward steps.

This motivates away-step and pairwise variants.

12. Away-step Frank–Wolfe

Maintain an active set of vertices currently carrying positive weight.

The forward vertex is:

s_t = argmin_s∈D ∇f(w_t)^Ts.

The away vertex is chosen from the active set:

v_t = argmax_{v∈A_t} ∇f(w_t)^Tv.

An away direction:

d_A = w_t − v_t

moves mass away from an unfavourable active vertex.

The maximum away step is limited so that its coefficient does not become negative.

13. Pairwise Frank–Wolfe

Pairwise Frank–Wolfe transfers weight directly:

d_PW = s_t − v_t.

In portfolio language, this is a direct transfer from one active asset toward another feasible extreme point.

Pairwise and away-step methods can converge much faster on polytopes when the optimum lies on a low-dimensional face.

14. Fully corrective Frank–Wolfe

After adding a new vertex, a fully corrective method reoptimizes weights over the entire active vertex set rather than retaining the historical convex weights implied by previous step sizes.

This can reduce zig-zag and remove unnecessary active assets, at the price of solving a small restricted optimisation problem.

15. Inputs and outputs

Inputs can include:

expected-return vector μ;
covariance/risk model Σ;
risk-aversion or target-return parameters;
compact convex feasible set D;
linear minimization oracle;
initial feasible portfolio;
step-size rule;
gap tolerance;
maximum iterations;
away/pairwise/fully-corrective option;
turnover and transaction-cost model if incorporated.

Outputs can include:

portfolio weights;
objective value;
Frank–Wolfe duality gap;
active asset set;
iteration count;
line-search steps;
oracle choices;
turnover;
risk/return decomposition;
convergence trace.

16. The linear oracle defines whether Frank–Wolfe is attractive

The method is compelling when:

linear optimization over D is much easier than Euclidean projection onto D.

For the simplex, the LMO is a minimum-gradient-coordinate lookup.

For a general polytope, the LMO can be a linear program.

For some structured sets, the LMO has a specialised combinatorial solution.

If the LMO itself is expensive, projection-free does not automatically mean fast.

17. Box and sector constraints

Suppose weights satisfy:

l_i ≤ w_i ≤ u_i

plus:

1^Tw=1

and sector bounds.

The Frank–Wolfe step is still conceptually unchanged, but the LMO must solve the resulting linear program.

Every extra constraint changes the vertex geometry and can change the sparsity pattern of iterates.

18. Turnover constraints are not always simple

A turnover cap:

||w−w_old||₁ ≤ τ

creates a polyhedral feasible set when combined with linear constraints.

Frank–Wolfe can still apply if the corresponding LMO is solved reliably.

But non-smooth transaction costs in the objective may be better handled by generalized conditional-gradient or proximal/splitting methods.

19. Frank–Wolfe versus ADMM

ADMM algorithms are strong when the objective and constraints split into pieces with easy proximal operations.

Frank–Wolfe is strong when a linear minimization oracle is easy but projection/proximal steps are difficult.

The correct choice depends on the geometry of the feasible set and the smoothness of the objective.

20. Covariance validity remains upstream

If Σ is not positive semidefinite, the mean–variance objective can become nonconvex.

Then the standard convex Frank–Wolfe gap no longer provides the same global optimality certificate.

Falsifier: inspect eigenvalues before optimisation.

Relevant BTT neighbours include Marchenko–Pastur covariance cleaning and Tyler’s robust scatter estimator.

21. Estimation error can dominate optimisation error

Suppose Frank–Wolfe drives the numerical gap below 10⁻¹⁰, but μ and Σ were estimated with large sampling error.

The portfolio can be numerically optimal for the wrong inputs.

Public lesson: optimisation precision and statistical model accuracy are different error budgets.

22. Evidence polarity

Evidence for confidence includes:

Frank–Wolfe gap decreases steadily;
objective agrees with an independent quadratic-program benchmark;
all iterates remain feasible;
exact line-search steps satisfy first-order conditions;
active set stabilises;
away/pairwise variants improve boundary convergence when expected;
results are stable under reasonable optimisation tolerances;
out-of-sample portfolio behaviour is not hypersensitive to tiny input changes.

Evidence against confidence includes:

duality gap stalls far above tolerance;
vanilla FW takes tiny oscillating steps near a face;
line search repeatedly clips at numerical extremes;
LMO solutions are inconsistent;
covariance matrix is indefinite;
small μ/Σ perturbations radically change the portfolio;
early sparsity is mistaken for cardinality optimality;
transaction costs reverse the chosen portfolio.

23. Counterexample: optimum uses many assets

An equal-risk diversified optimum may lie in the interior of the simplex.

Vanilla Frank–Wolfe adds assets one at a time, so a highly dense optimum can require many iterations.

Falsifier: compare objective gap against active-set size. If accuracy improves only after most assets become active, sparse iterates are not a practical advantage for this problem.

24. Counterexample: zig-zag near a face

Two assets currently have excessive weights, but each forward step can only add weight toward a new vertex while reducing all existing weights proportionally.

Bad active vertices disappear slowly.

Falsifier: run away-step or pairwise FW. A large acceleration confirms boundary zig-zag was the limiting mechanism.

25. Counterexample: covariance matrix has a negative eigenvalue

Sampling or data-cleaning errors produce an indefinite Σ.

Exact quadratic line search can encounter d^TΣd ≤ 0, and convexity-based gap interpretation fails.

Falsifier: repair or re-estimate the covariance model before claiming convex global convergence.

26. Counterexample: expected returns are noisy

The gradient includes −λμ.

A small estimation error in μ can change which coordinate has the minimum gradient and therefore which asset the LMO selects.

Falsifier: perturb μ within estimation uncertainty and track oracle-selection stability.

27. Counterexample: turnover cost is omitted

A rolling optimisation repeatedly selects different extreme points, creating high turnover despite a low variance objective.

Falsifier: include an explicit turnover constraint or cost and compare net objective/economic performance.

28. Counterexample: projection would actually be cheaper

For a plain simplex, very fast projection routines exist.

If the LMO advantage is negligible and high precision is required, projected or accelerated methods may outperform vanilla Frank–Wolfe.

Falsifier: benchmark wall-clock time at equal objective gap, not just iteration count.

29. Counterexample: nonconvex cardinality constraint

A hard requirement:

||w||₀ ≤ K

is nonconvex.

Vanilla Frank–Wolfe on the simplex does not solve that problem merely because its intermediate iterates are sparse.

Modified relaxations, mixed-integer methods or specialised sparse portfolio algorithms are required if cardinality is a hard constraint.

30. Alternatives

Projected gradient: attractive when projection is simple.

Accelerated projected methods: strong for smooth convex problems with cheap projection.

ADMM/proximal methods: strong for composite non-smooth costs and separable constraints.

Interior-point/QP solvers: strong for medium-sized structured convex quadratic programs and high precision.

Coordinate descent: useful when coordinate updates are cheap and constraints permit.

Away-step/pairwise/fully-corrective FW: preserve projection-free geometry while addressing active-set weaknesses.

32. What would falsify confidence?

Confidence should be withdrawn if the reported portfolio is infeasible; if the Frank–Wolfe gap does not support the claimed numerical tolerance; if an independent convex solver finds a materially better objective; if covariance convexity fails; if small input perturbations cause unstable allocations; or if net performance after realistic constraints/costs reverses the apparent optimisation benefit.

33. Verification and update triggers

Preserve the objective, gradient, feasible-set definition, LMO implementation, initial portfolio, step-size rule, active-set history, gap trace and all risk/return inputs.

Revalidate when:

constraints change;
transaction-cost model changes;
covariance estimator changes;
expected-return model changes;
asset universe expands;
LMO implementation changes;
away/pairwise variants are introduced;
the required optimisation precision changes.

34. Primary and high-quality references

Marguerite Frank and Philip Wolfe, An Algorithm for Quadratic Programming, Naval Research Logistics Quarterly, 1956.
Martin Jaggi, Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization, ICML, 2013.
Modern surveys of Frank–Wolfe/conditional-gradient methods discuss open-loop, exact-line-search, away-step and related variants.
Research on away-step and pairwise Frank–Wolfe establishes faster convergence on suitable polytopes under stronger conditions.

Educational boundary: Frank–Wolfe solves a numerical optimisation problem defined by stated inputs and constraints. It does not validate expected returns, covariance forecasts or the economic usefulness of the resulting portfolio.

Small Group Tutorials

How Frank–Wolfe Algorithms Solve Constrained Portfolio Optimisation Without Projections: Linear Minimization Oracles, Sparse Iterates, Duality Gaps, Away Steps and Boundary Failure