Regula lui Zadeh (cunoscută și ca regula de utilizare mai mică ) este o îmbunătățire algoritmică a metodei simplex pentru optimizarea liniară .
Regula a fost propusă în anii 1980 de Norman Zade și a devenit populară de atunci în optimizarea convexă [1] .
Zadeh a anunțat o recompensă de 1.000 USD oricui poate demonstra că o regulă duce la un număr polinom de iterații sau poate demonstra că există o familie de probleme de programare liniară pentru care această regulă bazată pe variabile necesită un număr subexponențial de iterații pentru a găsi un optim [2] ] .
Regula lui Zadeh aparține unei familii de îmbunătățiri bazate pe istoric care, pe măsură ce se rulează metoda simplex, dețin date suplimentare în plus față de baza curentă a metodei simplex.
Regula alege dintre toate variabilele care pot fi introduse în bază, pe cea care a fost introdusă cel mai puțin des în bază, sperând intuitiv că variabilele pot da o îmbunătățire semnificativă în mai multe iterații, dar care la fiecare iterație separată dau o mică îmbunătățire.
Structurile de date suplimentare din algoritmul lui Zadeh pot fi astfel modelate ca un număr de apariții care mapează toate variabilele la numere întregi și arată de câte ori o anumită variabilă atinge baza. La fiecare iterație, algoritmul selectează pentru introducere în bază o variabilă corespunzătoare valorii minime din această listă.
Rețineți că regula nu determină fără ambiguitate ce variabilă va fi aleasă dacă numărul de intrări la bază este egal.
Prin construirea unei familii de procese de decizie Markov în care algoritmul necesită un număr superpolinom de pași, s-a demonstrat că regula lui Zadeh are cel puțin complexitate superpolinomială în cel mai rău caz.
Rezultatul a fost prezentat de Oliver Friedman la Conferința din 2011 a Mathematical Optimization Association „Integer Programming and Combinatorial Optimization” [3] . Norman Zade, deși nu mai era angajat în lucrări științifice în acel moment, a participat la conferință și și-a îndeplinit promisiunea [4] .