MacTutor
Greedy Algorithms, Frank-Wolfe and Friends
Marguerite Frank described her discovery of the Frank-Wolfe algorithm in the video 'Marguerite Frank - Inventor of the Frank-Wolfe Algorithm - Honorary Discussion Panel' (6 March 2014) at https://www.youtube.com/watch?v=24e08AX9Eww.
This Discussion Panel was part of the workshop on "Greedy Algorithms, Frank-Wolfe and Friends - A modern perspective" held at Lake Tahoe, Nevada in 2013. In OPTIMA 95: Mathematical Optimization Society Newsletter, there are several articles written after the workshop and, in particular, there is one by Marguerite Frank giving more details than in the interview itself. We present a version of this article, together with the preceding ones putting it into context.
This Discussion Panel was part of the workshop on "Greedy Algorithms, Frank-Wolfe and Friends - A modern perspective" held at Lake Tahoe, Nevada in 2013. In OPTIMA 95: Mathematical Optimization Society Newsletter, there are several articles written after the workshop and, in particular, there is one by Marguerite Frank giving more details than in the interview itself. We present a version of this article, together with the preceding ones putting it into context.
1. Note from the Editors.
Martin Jaggi (ETH Zürich) and Zaid Harchaoui (INRIA Grenoble) jointly with Federico Pierucci organised a workshop on "Greedy Algorithms, Frank-Wolfe and Friends - A modern perspective" at the annual conference of the Neural Information Processing Systems Foundation in 2013 (NIPS 2013) at Lake Tahoe, Nevada. On that occasion they had the chance to interview Marguerite Frank about the invention of the Frank-Wolfe algorithm she developed together with Philip Wolfe in the 1950's. We are very happy to have a column in this issue in which she shares with us her memories on this important moment in the history of mathematical optimisation dating back some 60 years. How influential her's and Philip Wolfe's invention was can be seen also from the scientific article in this issue, in which Martin Jaggi and Zaid Harchaoui describe recent successful applications of the method.
We hope that you will enjoy both the historical and the current aspects of this issue ...
2. Preluding Remarks, by Martin Jaggi and Zaid Harchaoui.
We hope that you will enjoy both the historical and the current aspects of this issue ...
In 1956, Marguerite Frank and Philip Wolfe published a paper entitled "An Algorithm for Quadratic Programming" in Naval Research Logistics Quarterly. The paper's title was a strong understatement, given that it introduces a new algorithm not only for quadratic convex, but general convex optimisation, and proves the convergence rate. The Frank-Wolfe algorithm is widely considered the very first method for general constrained convex optimisation.
Originating in the famous Logistics Project group at Princeton, which was the most prominent place in linear programming and game theory at the time, the new collaboration between Marguerite Frank and Phil Wolfe (both coming from quite different scientific backgrounds) aimed at the following research question: Given the recent successes and tools of linear programming, is it possible to derive a method for the more general case, that is quadratic convex programming, or even general convex programming? The answer is well known to the reader at this point, and in our opinion marks some of the birth hours of the research field of convex optimisation, and a significant and brave departure from the linear programming territory.
Since then, the powerful core idea of the Frank-Wolfe method - to decompose a (hard) general optimisation problem into a sequence of (easy) linear problems - has proven fertile numerous times in a surprisingly large variety of applications, and is continuing to have impact in many fields.
We feel extremely honoured that Marguerite Frank, co-author of the original paper, and one of the first female PhD students in mathematics at Harvard University, has agreed to share her thoughts on these interesting birth years of mathematical optimisation.
We would also like to thank Hallie Wolfe, P Wolfe's wife, and Isabelle Frank, M Frank's daughter, and Anna Nagurney for their constant kindness and generous help in preparing this article. We are indebted to the editors of Optima, Volker Kaibel, Sam Burer, Jeff Linderoth and Katya Scheinberg for many valuable comments, as well as to Alexandre d'Aspremont, Rob Freund, Anatoli Juditsky, Simon Lacoste-Julien, Claude Lemaréchal and Arkadi Nemirovski for fruitful discussions.
3. The History of the Frank-Wolfe Algorithm, by Marguerite Frank.
Originating in the famous Logistics Project group at Princeton, which was the most prominent place in linear programming and game theory at the time, the new collaboration between Marguerite Frank and Phil Wolfe (both coming from quite different scientific backgrounds) aimed at the following research question: Given the recent successes and tools of linear programming, is it possible to derive a method for the more general case, that is quadratic convex programming, or even general convex programming? The answer is well known to the reader at this point, and in our opinion marks some of the birth hours of the research field of convex optimisation, and a significant and brave departure from the linear programming territory.
Since then, the powerful core idea of the Frank-Wolfe method - to decompose a (hard) general optimisation problem into a sequence of (easy) linear problems - has proven fertile numerous times in a surprisingly large variety of applications, and is continuing to have impact in many fields.
We feel extremely honoured that Marguerite Frank, co-author of the original paper, and one of the first female PhD students in mathematics at Harvard University, has agreed to share her thoughts on these interesting birth years of mathematical optimisation.
We would also like to thank Hallie Wolfe, P Wolfe's wife, and Isabelle Frank, M Frank's daughter, and Anna Nagurney for their constant kindness and generous help in preparing this article. We are indebted to the editors of Optima, Volker Kaibel, Sam Burer, Jeff Linderoth and Katya Scheinberg for many valuable comments, as well as to Alexandre d'Aspremont, Rob Freund, Anatoli Juditsky, Simon Lacoste-Julien, Claude Lemaréchal and Arkadi Nemirovski for fruitful discussions.
As far as I can remember - from my idealised early past in Paris, then Toronto, I was interested in maths (Euclid, algebra), reading and ideas. When majoring in maths and physics at the University of Toronto, I was mostly inspired by Harold Scott MacDonald Coxeter, Leopold Infeld and especially Richard Brauer. Graduating in 1947, I went on to Radcliffe-Harvard as a Teaching Fellow at the age of 20. When I left in 1949 with all but a PhD thesis, neither the logic of Willard Van Orman Quine, nor the algebraic geometry of Oscar Zariski worked as substitutes for algebra (I was only 23 years old back then).
During a break of two Parisian years, I got a diploma in History of Mathematics with Alexandre Koyré, and incidentally met my future husband, whom I then followed to the University of Chicago, where I had the great fortune to be accepted as an auditor by the algebraist Abraham Adrian Albert. This led to my defining of new simple Lie algebras, the first in several years, and to more such new classes later.
Then, in 1955, I followed my husband, Joseph Frank, to Princeton, where he was invited as a Gauss Lecturer on the topic of "Existentialism and Dostoevsky". During this time I was fortunate to become a Visitor in Princeton's prestigious Logistics Project, run by Albert W Tucker and Harold W Kuhn. These were the exciting days of Game Theory (von Neumann and Morgenstern, Nash et al.), and of the reigning technique of Linear Programming and the Simplex method of George Dantzig, which served as strong inspirations. There was talk of computers, but none to be actually seen as I recall. A complete neophyte in these new esoteric disciplines, I immersed myself as best I could, attempting to master Linear Programming, Lagrange Multipliers and their new Kuhn-Tucker optimality conditions for inequality constraints, as well as getting used to the subtleties of competitive games.
I was assigned to work with the then post-doc instructor Philip Wolfe - who was already well-trained in the general field of optimisation. Our assigned joint goal was to seek a procedure that might yield the optimum solution for a suitably shaped quadratic function under linear inequality constraints. It all occurred a very long time ago, and what I remember mostly is - working at home - I had no office - covering, as usual, sheets of paper with symbols related - now - by linear inequalities instead of equations. I also attended the famous Fine Hall Afternoon Teas, a daily and informal departmental meeting.
I seem to remember presenting some jottings to Phil in his office and his exclaiming "I think Marguerite has solved the quadratic problem" - then reproaching me for not having established the "convergence" - and immediately doing so himself ... But this evokes more specifically the later general "convex problem" so my memory may be at fault. In any case, Phil rewrote both procedures in their present form, and chose the (at the time) original title. He then continued to work brilliantly in the field.
For me this brief foray in optimisation made it easier later to obtain - after various research and part time jobs - a tenured position in the nearby Rider University Business School, and a later one as Fellow in Stanford's Engineering School O.R. department, where I finally met George Dantzig.
I never received any special acknowledgment or a single bitcoin for the article - only the usual professional interest from Anna Nagurney, and Stella Dafermos, who befriended me in my new guise. Hence my astonishment at being alerted by Michel Balinski, in the fall of 2013, about the NIPS Workshop, at nearby Lake Tahoe - and then invited there by Martin Jaggi and Zaid Harchaoui. I was stunned to learn, as was Phil Wolfe whom I contacted by phone, that Frank-Wolfe when translated into computer code had become useful in various places, including major companies in the current digital economy.
Thinking about the current times of digitalisation in general, I find it ironic that abstract Boolean algebra - that could not possibly have emerged fully formed from a mind-deprived brain, nor from a data cloud - is at the root of what is surely our present technological / cultural paradigm shift.
During a break of two Parisian years, I got a diploma in History of Mathematics with Alexandre Koyré, and incidentally met my future husband, whom I then followed to the University of Chicago, where I had the great fortune to be accepted as an auditor by the algebraist Abraham Adrian Albert. This led to my defining of new simple Lie algebras, the first in several years, and to more such new classes later.
Then, in 1955, I followed my husband, Joseph Frank, to Princeton, where he was invited as a Gauss Lecturer on the topic of "Existentialism and Dostoevsky". During this time I was fortunate to become a Visitor in Princeton's prestigious Logistics Project, run by Albert W Tucker and Harold W Kuhn. These were the exciting days of Game Theory (von Neumann and Morgenstern, Nash et al.), and of the reigning technique of Linear Programming and the Simplex method of George Dantzig, which served as strong inspirations. There was talk of computers, but none to be actually seen as I recall. A complete neophyte in these new esoteric disciplines, I immersed myself as best I could, attempting to master Linear Programming, Lagrange Multipliers and their new Kuhn-Tucker optimality conditions for inequality constraints, as well as getting used to the subtleties of competitive games.
I was assigned to work with the then post-doc instructor Philip Wolfe - who was already well-trained in the general field of optimisation. Our assigned joint goal was to seek a procedure that might yield the optimum solution for a suitably shaped quadratic function under linear inequality constraints. It all occurred a very long time ago, and what I remember mostly is - working at home - I had no office - covering, as usual, sheets of paper with symbols related - now - by linear inequalities instead of equations. I also attended the famous Fine Hall Afternoon Teas, a daily and informal departmental meeting.
I seem to remember presenting some jottings to Phil in his office and his exclaiming "I think Marguerite has solved the quadratic problem" - then reproaching me for not having established the "convergence" - and immediately doing so himself ... But this evokes more specifically the later general "convex problem" so my memory may be at fault. In any case, Phil rewrote both procedures in their present form, and chose the (at the time) original title. He then continued to work brilliantly in the field.
For me this brief foray in optimisation made it easier later to obtain - after various research and part time jobs - a tenured position in the nearby Rider University Business School, and a later one as Fellow in Stanford's Engineering School O.R. department, where I finally met George Dantzig.
I never received any special acknowledgment or a single bitcoin for the article - only the usual professional interest from Anna Nagurney, and Stella Dafermos, who befriended me in my new guise. Hence my astonishment at being alerted by Michel Balinski, in the fall of 2013, about the NIPS Workshop, at nearby Lake Tahoe - and then invited there by Martin Jaggi and Zaid Harchaoui. I was stunned to learn, as was Phil Wolfe whom I contacted by phone, that Frank-Wolfe when translated into computer code had become useful in various places, including major companies in the current digital economy.
Thinking about the current times of digitalisation in general, I find it ironic that abstract Boolean algebra - that could not possibly have emerged fully formed from a mind-deprived brain, nor from a data cloud - is at the root of what is surely our present technological / cultural paradigm shift.
Last Updated November 2020