[Ml-stat-talks] Princeton Optimization Seminar: Yinyu Ye, Stanford - *TODAY* April 6, 4:30

Amir Ali Ahmadi a_a_a at Princeton.EDU
Mon Apr 6 11:15:39 EDT 2015

-----   Princeton Optimization Seminar   -----

DATE:  Monday, April 6, 2015, 4:30 PM (note the unusual date)

TIME:  4:30 pm

LOCATION:  Sherrerd Hall 101

SPEAKER: Yinyu Ye, Stanford University

TITLE:  Distributed Algorithms for the Markov Decision Process and Linear Programming<https://orfe.princeton.edu/abstracts/optimization-seminar/distributed-algorithms-markov-decision-process-and-linear-programming>

We present two results related to distributed algorithms for the Markov decision process or linear programming at large.
i) We prove that the classical policy-iteration method (Howard 1960), including the simple policy-iteration (or simplex method, Dantzig 1947) with the most-negative-reduced-cost pivoting rule, is a strongly polynomial-time algorithm for solving discounted Markov decision processes (MDP) of any fixed discount factor. The result is surprising since almost all complexity results on the simplex and policy-iteration methods are negative, while in practice they are most effectively used for solving MDPs.
ii) We show that the direct extension of ADMM of three-block for linear programming is not necessarily convergent, although its convergence proof was established 40 years ago with one and two-block. We also propose possibly simple and efficient variants, which could be applied to solving very large-scale linear programs.

If you would like to subscribe to the mailing list of the optimization seminar series, please visit the link below or send an email with
SUBSCRIBE opt-seminar in the body to listserv at lists.princeton.edu<mailto:listserv at lists.princeton.edu>.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cs.princeton.edu/pipermail/ml-stat-talks/attachments/20150406/644e8f55/attachment.html>

More information about the Ml-stat-talks mailing list