Polytope Conditioning and Linear Convergence of the Frank–Wolfe Algorithm

References

• Ahipasaoglu S, Sun P, Todd M (2008) Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optim. Methods Software 23(1):5–19.Crossref, Google Scholar
• Beck A, Shtern S (2017) Linearly convergent away-step conditional gradient for non-strongly convex functions. Math. Programming 164(1):1–27.Crossref, Google Scholar
• Beck A, Teboulle M (2004) A conditional gradient method with linear rate of convergence for solving convex linear systems. Math. Methods Oper. Res. 59(2):235–247.Crossref, Google Scholar
• Bertsekas D (1999) Nonlinear Programming (Athena Scientific, Belmont, MA).Google Scholar
• Epelman M, Freund RM (2000) Condition number complexity of an elementary algorithm for computing a reliable solution of a conic linear system. Math. Programming 88(3):451–485.Crossref, Google Scholar
• Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Quart. 3(1–2):95–110.Crossref, Google Scholar
• Garber D, Hazan E (2016) A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM J. Optim. 26(3):1493–1528.Crossref, Google Scholar
• Guélat J, Marcotte P (1986) Some comments on Wolfe’s ‘away step.’ Math. Programming 35(1):110–119.Crossref, Google Scholar
• Jaggi M (2013) Revisiting Frank-Wolfe: Projection-free sparse convex optimization. Dasgupta S, McAllester D, eds. Proc. 30th Internat. Conf. Machine Learning (ICML ‘13), vol. 28 (JMLR.org), 427–435.Google Scholar
• Kumar P, Yildirim EA (2011) A linearly convergent linear-time first-order algorithm for support vector classification with a core set result. INFORMS J. Comput. 23(3):377–391.Link, Google Scholar
• Lacoste-Julien S, Jaggi M (2015) On the global linear convergence of Frank-Wolfe optimization variants. Cortes C, Lee DD, Sugiyama M, Garnett R, eds. Proc. Adv. Neural Inform. Processing Systems (NIPS ‘15) (MIT Press, Cambridge, MA), 496–504.Google Scholar
• Ñanculef R, Frandi E, Sartori C, Allende H (2014) A novel Frank-Wolfe algorithm. Analysis and applications to large-scale SVM training. Inform. Sci. 285(C):66–99.Crossref, Google Scholar
• Nesterov Y (2004) Introductory Lectures on Convex Optimization: A Basic Course, Applied Optimization (Kluwer Academic Publishers, Norwell, MA).Crossref, Google Scholar
• Peña J, Rodríguez D, Soheili N (2016) On the von Neumann and Frank-Wolfe algorithms with away steps. SIAM J. Optim. 26(1):499–512.Crossref, Google Scholar
• Wolfe P (1970) Convergence theory in nonlinear programming. Abadie J, ed. Integer and Nonlinear Programming (North-Holland, Amsterdam), 1–36.Google Scholar