The Frank-Wolfe algorithm

The Frank-Wolfe algorithm was originally proposed by Marguerite Frank and Philip Wolfe in 1956 in the paper 'An algorithm for quadratic programming', Naval Res. Logist. Quart. 3 (1956), 95-110. It is an iterative first-order optimisation algorithm for constrained convex optimisation which is sometimes called the 'conditional gradient method', the 'reduced gradient algorithm' or the 'convex combination algorithm'. The way in which the algorithm was discovered is described in Marguerite Frank's biography in this archive.

For her own description of the discovery, see the video 'Marguerite Frank - Inventor of the Frank-Wolfe Algorithm - Honorary Discussion Panel' (6 March 2014) at https://www.youtube.com/watch?v=24e08AX9Eww.

See also her own written description in the article at THIS LINK.

We give below a version of Marguerite Frank and Philip Wolfe's Introduction to the paper An algorithm for quadratic programming (1956).

Introduction

The problem of maximising a concave quadratic function whose variables are subject to linear inequality constraints has been the subject of several recent studies, from both the computational side and the theoretical. Our aim here has been to develop a method for solving this non-linear programming problem which should be particularly well adapted to high-speed machine computation.

The quadratic programming problem as such, called PI, is set forth in Section 2.

We find in Section 3 that with the aid of generalised Lagrange multipliers the solutions to PI can be exhibited in a simple way as parts of the solutions of a new quadratic programming problem, called PII, which embraces the multipliers. The maximum sought in PII is known to be zero. A test for the existence of solutions to PI arises from the fact that the boundedness of its objective function is equivalent to the feasibility of the (linear) constraints of PII.

In Section 4 we apply to PII an iterative process in which the principal computation is the simplex method change-of-basis. One step of our "gradient and interpolation" method, given an initial feasible point, selects by the simplex routine a secondary basic feasible point whose projection along the gradient of the objective function at the initial point is sufficiently large. The point at which the objective is maximised for the segment joining the initial and secondary points is then chosen as the initial point for the next step.

The values of the objective function on the initial points thus obtained converge to zero; but a remarkable feature of the quadratic problem is that in some step a secondary point which is a solution of the problem will be found, insuring the termination of the process.

A simplex technique machine program requires little alteration for the employment of this method. Limited experience suggests that solving a quadratic program in

n

variables and

m

constraints will take about as long as solving a linear program having

m + n

constraints and a "reasonable" number of variables.

Section 5 discusses, for completeness, some other computational proposals making use of generalised Lagrange multipliers.

Section 6 carries over the applicable part of the method, the gradient-and-interpolation routine, to the maximisation of an arbitrary concave function under linear constraints (with one qualification). Convergence to the maximum is obtained as above, but termination of the process in an exact solution is not, although an estimate of error is readily found.

In Section 7 (the Appendix) are accumulated some facts about linear programs and concave functions which are used throughout the paper.

Last Updated November 2020