Algorithmic efficiency. The simplex method minimizes linear functions by moving between extreme…
Algorithmic efficiency. The simplex method minimizes linear functions by moving between extreme points of a polyhedral region so that each transition decreases the objective function. Suppose there are n extreme points and they are numbered in increasing order of their values. Consider the Markov chain in which In words, when we leave j we are equally likely to go to any of the extreme points with better value. (a) Use (1.27) to show that for i > 1
(b) Let Ij = 1 if the chain visits j on the way from n to 1. Show that for j
to get another proof of the result and conclude that I1….. In-1 are independent.