The Multiplicative Weights Method and Application to Solving LPs

Consider n 'experts' predicting the outcome of, say, the stock market, with errors. At the start of every day, they make a prediction of whether the market is going up or down, and then the actual outcome is revealed to us at the end of the day. We are then free to choose the experts we trust for the next day. The Multiplicative Weights Method is a simple yet powerful method that gives us a way to assign importance to these experts at every round so that over a period of ln n days, the fraction of errors we make is close to that of the best expert.

Surprisingly, this method has been used to solve certain kinds of LP relaxations of combinatorial optimization problems faster than that of a general LP solver. Further, it has been generalized to SDPs and SDP-bsed algorithms as well.

We shall see a proof of correctness of the Multiplicative Weights method, and the application to solving LPs.