[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...
More information about the Ml-stat-talks