Zadeh's rule
In mathematical optimization, Zadeh's rule (also known as the least-entered rule) is an algorithmic refinement of the simplex method for linear optimization.
The rule was proposed around 1980 by Norman Zadeh (son of Lotfi A. Zadeh), and has entered the folklore of convex optimization since then.[1]
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.[2]
Algorithm
[edit]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
[edit]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.[3][4]
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.[5] Zadeh, although not working in academia anymore at that time, attended the Workshop and honored his original proposal.[6]
Exponential lower bound
[edit]Friedmann's original result has since been strengthened by the construction of an exponential instance for Zadeh's rule.[7]
Notes
[edit]- ^ Zadeh, Norman (1980). "What is the worst case behaviour of the simplex algorithm?". Technical Report, Department of Operations Research, Stanford.
- ^ Ziegler, Günter (2004). "Typical and extremal linear programs". The Sharpest Cut (MPS-Siam Series on Optimization: 217–230. doi:10.1137/1.9780898718805.ch14. ISBN 978-0-89871-552-1.
- ^ Friedmann, Oliver (2011). "A subexponential lower bound for Zadeh's pivoting rule for solving linear programs and games". Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 192–206.
- ^ Disser, Y.; Hopp, A.V. (2019). "On Friedmann's Subexponential Lower Bound for Zadeh's Pivot Rule". Proceedings of the 20th Conference on Integer Programming and Combinatorial Optimization (IPCO). pp. 168–180.
- ^ "Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?".
- ^ "Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)". 20 January 2011.
- ^ Disser, Yann; Friedmann, Oliver; Hopp, Alexander V. (2022). "An exponential lower bound for Zadeh's pivot rule". Mathematical Programming.