Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Efficiency of the Simplex Method Yinyu Ye Department of Management Science and Engineering Stanford University Stanford CA 94305 U S A http www stanford edu yyye 1 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Hirsch s Conjecture Warren Hirsch conjectured in 1957 that the diameter of the graph of a convex polyhedron defined by n inequalities in m dimensions is at most n m The diameter of the graph is the maximum of the shortest paths between every two vertices 2 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 A Counter Example Francisco Santos 2010 There is a 43 dimensional polytope with 86 facets and of diameter at least 44 There is an infinite family of non Hirsch polytopes with diameter 1 n even in fixed dimension 3 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Size of Basic Feasible Solution and Convergence Rate The simplex method generates a sequence of BFS x k k objective value decreases each step c T xk 1 0 1 where the cT x k Lemma 1 For every BFS xB of a LP problem assume that the sum of its entries be bounded above eT xB and its smallest entry be bounded below min xB 0 for fixed positive numbers and non degenerate case Then after every pivot step we have cT xk 1 z 1 T k c x z where z is the minimal objective value of the LP problem 4 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Proof of Convergence Rate Recall at each pivot step rek minj N rjk 0 so that cT xk z rek On the other hand we have cT xk 1 cT xk rek Thus cT xk 1 z cT xk z re or re cT xk 1 z 1 T k 1 cT x k z c x z 5 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Implicit Elimination Theorem Theorem 1 Let x0 be any given BFS Then there is optimal nonbasic variable j 0 B 0 and j 0 B that would never appear in any of the BFSs generated by m 0 the simplex method after K log steps starting from x Then we have Corollary 1 For every BFS xB of a LP problem let the sum of its entries be bounded above eT xB and its smallest entry be bounded below min xB 0 for fixed positive numbers and Then the Simplex method terminates in n log m steps 6 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Proof of the Theorem If initial BFS x0 is not optimal then s T x0 cT x0 z 0 Then there must be an j 0 B 0 and j 0 B such that s j 0 x0j 0 or cT x 0 z m cT x 0 z m m log steps starting from x0 from the lemma we must s j 0 After K have cT x K z and it holds for all subsequent BFSs cT x0 z m 7 Yinyu Ye MS E Stanford Suppose j 0 MS E310 Lecture Note 06 B K we have s j 0 xK j0 cT x0 z c x z m T K or s j 0 which is a contradiction cT x 0 z m 8 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 The Markov Decision Process Markov Decision Processes MDPs provide a mathematical framework for modeling sequential decision making in situations where outcomes are partly random and partly under the control of a decision maker MDPs are useful for studying a wide range of optimization problems solved via dynamic programming where it was known at least as early as the 1950s cf Shapley 1953 Bellman 1957 Modern applications include dynamic planning reinforcement learning social networking and almost all other dynamic sequential decision making problems in Mathematical Physical Management and Social Sciences 9 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 The Markov Decision Process continued At each time step the process is in some state i 1 m and the decision maker chooses an action j A i that is available in state i The process responds at the next time step by randomly moving into a new state i and giving the decision maker a corresponding cost c j i i The probability that the process enters i as its new state is influenced by the chosen action in state i Specifically it is given by the state transition function P j i i But given i and j the probability is conditionally independent of all previous states and actions in other words the state transitions of an MDP possess the Markov property 10 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 MDP Stationary Policy A stationary policy for the decision maker is a function 1 2 m that specifies an action i Ai that the decision maker will choose for each state i The min present cost MDP is to find a stationary policy to minimize the expected discounted sum over an infinite horizon t E c it it it 1 t 0 where 0 1 is the discount rate Typically 1 1 where is the interest rate 11 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 4 3 2 1 1 0 0 5 1 0 5 0 5 2 0 5 0 5 3 0 5 4 A Markov Decision Process Example Actions are in red blue and black and all actions have zero cost except the state 4 to the absorbing state 12 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 Algorithmic Events of the MDP Methods I Shapley 1953 and Bellman 1957 developed a method called the value iteration method to approximate the optimal state values Another best known method is due to Howard 1960 and is known as the policy iteration method which generate an optimal policy in finite number of iterations in a distributed and decentralized way de Ghellinck 1960 D Epenoux 1960 and Manne 1960 showed that the MDP has an LP representation so that it can be solved by the simplex method of Dantzig 1947 in finite number of steps and the Ellipsoid method of Kachiyan 1979 in polynomial time 13 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 The Fixed Point Model of the MDP minj A1 cj pTj y y1 yi ym minj Ai cj pTj y minj Am cj pTj y where Ai represents all actions available in state i and p j is the state transition probabilities from state i to all states when action j th in state i is taken 14 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 The Dual Linear Programming Form of the MDP maximizey subject to m i 1 yi y1 pTj y yi pTj y ym pTj y cj j A1 cj j Ai cj j Am 15 Yinyu Ye MS E Stanford MS E310 Lecture Note 06 The Interpretations of the LP Dual Formulation The LP …