A Zadeh-szabály (más néven a kisebb használat szabálya ) a lineáris optimalizálás szimplex módszerének algoritmikus továbbfejlesztése .
A szabályt az 1980-as években Norman Zade javasolta, és azóta népszerűvé vált a konvex optimalizálásban [1] .
Zadeh 1000 dolláros jutalmat hirdetett meg mindenkinek, aki be tudja mutatni, hogy egy szabály polinomiális számú iterációhoz vezet, vagy bebizonyítja, hogy létezik olyan lineáris programozási problémacsalád, amelyre ez a változó alapú szabály szubexponenciális számú iterációt igényel az optimum megtalálásához [2 ] .
A Zadeh-szabály a történelmileg vezérelt fejlesztések családjába tartozik, amelyek a szimplex módszer futása során további adatokat tartalmaznak a szimplex módszer jelenlegi alapjain kívül.
A szabály az összes bázisba beilleszthető változó közül azt választja ki, amelyik a legritkábban került be a bázisba, intuitív módon abban a reményben, hogy a változók több iterációban is jelentős javulást eredményezhetnek, de minden egyes iterációnál egy kis javulást adnak.
A Zadeh-algoritmus további adatstruktúrái így modellezhetők számos előfordulásként, amelyek az összes változót egész számokra képezik le, és megmutatják, hogy egy adott változó hányszor találja el a bázist. Az algoritmus minden iterációnál kiválaszt egy, a listában szereplő minimális értéknek megfelelő változót az alapba történő bevitelhez.
Vegye figyelembe, hogy a szabály nem határozza meg egyértelműen, hogy melyik változót választjuk, ha a bázis bemeneteinek száma egyenlő.
A Markov-döntési folyamatok családjának felépítésével , amelyben az algoritmus szuperpolinomiális számú lépést igényel, bebizonyosodott, hogy a Zadeh-szabály a legrosszabb esetben legalább szuperpolinomiális komplexitású .
Az eredményt Oliver Friedman mutatta be a Mathematical Optimization Association "Integer Programming and Combinatorial Optimization" [3] 2011-es konferenciáján . Norman Zade, bár ekkor már nem foglalkozott tudományos munkával, részt vett a konferencián és beváltotta ígéretét [4] .