mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...

, Zadeh's rule (also known as the least-entered rule) is an algorithmic refinement of the simplex method for

linear optimization Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...

. The rule was proposed around 1980 by

Norman Zadeh Norman Zada (born Norman Askar Zadeh) is a former adjunct mathematics professor and an entrepreneur. He is the founder of '' Perfect 10'', an adult magazine focusing on women without cosmetic surgery, and runs the United States Investing Competition ...

(son of

Lotfi A. Zadeh Lotfi Aliasker Zadeh (; az, Lütfi Rəhim oğlu Ələsgərzadə; fa, لطفی علی‌عسکرزاده; 4 February 1921 – 6 September 2017) was a mathematician, computer scientist, electrical engineer, artificial intelligence researcher, an ...

), 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...

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 Oliver Friedmann is a German computer scientist and mathematician known for his work on parity games and the simplex algorithm. Friedmann earned his doctorate's degree from the Ludwig Maximilian University of Munich in 2011 under the supervision ...

. Zadeh, although not working in academia anymore at that time, attended the Workshop and honored his original proposal.

Notes

{{Reflist Optimization algorithms and methods Exchange algorithms Oriented matroids Linear programming