Alright before we start, I’m gonna call the Conditional Gradient Algorithm as Frank-Wolfe Algorithm (FW), attributing to the authors of the first ever paper on these methods viz., Marguerite Frank and Philip Wolfe in 1956! The simplex method (one of the top 10 algorithms of the 20th century, I’d say that simplex gets the first place for me) was introduced by Dantzig (I strongly encourage to read the history in the wiki page, it’s amazing!) in 1947 for solving linear optimization (LO) problems. A LO algorithm solves the following question: Let’s say we are given with the following two types of data viz., 1. A linear function in say ; 2. Legal set: A (sub)set of points that can described just using linear equations or inequalities. Now how can I pick the point in the legal set where achieves the minimum value **(or maximum value, it doesn’t matter in this case only, in general this is not true)**.

# Conditional Gradient Algorithms – A gentle introduction (7 mins read)

Leave a reply

Advertisements