Zadeh's rule


In mathematical optimization, Zadeh's rule is an algorithmic refinement of the simplex method for linear optimization.
The rule was proposed around 1980 by Norman Zadeh, and has entered the folklore of convex optimization since then.
Zadeh offered a reward of $1,000 to anyone who can show that the rule admits polynomially many iterations or to prove that there is a family of linear programs on which the pivoting rule requires subexponentially many iterations to find the optimum.

Algorithm

Zadeh's rule belongs to the family of history-based improvement rules which, during a run of the simplex algorithm, retain supplementary data in addition to the current basis of the linear program.
In particular, the rule chooses among all improving variables one which has entered the basis least often, intuitively ensuring that variables that might yield a substantive improvement in the long run but only a small improvement in a single step will be applied after a linear number of steps.
The supplementary data structure in Zadeh's algorithm can therefore be modeled as an occurrence record, mapping all variables to natural numbers, monitoring how often a particular variable has entered the basis. In every iteration, the algorithm then selects an improving variable that is minimal with respect to the retained occurrence record.
Note that the rule does not explicitly specify which particular improving variable should enter the basis in case of a tie.

Superpolynomial lower bound

Zadeh's rule has been shown to have at least super-polynomial time complexity in the worse-case by constructing a family of Markov decision processes on which the policy iteration algorithm requires a super-polynomial number of steps.
Running the simplex algorithm with Zadeh's rule on the induced linear program then yields a super-polynomial lower bound.
The result was presented at the "Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?" IPAM workshop in 2011 by Oliver Friedmann. Zadeh, although not working in academia anymore at that time, attended the Workshop and honored his original proposal.