Narození |
3. května 1952 Svatý Petr |
---|---|
Smrt |
April 29 , 2005(ve věku 52) New Jersey |
Jméno v rodném jazyce | Լեոնիդ Գենրիխովիչ Խաչիյան |
Národnosti |
Sovětský arménský |
Domov | Rusko |
Výcvik | Fakulta managementu a aplikované matematiky Moskevského institutu fyziky a technologie ( d ) |
Činnosti | Matematik , počítačový vědec , univerzitní profesor |
Dítě | Anna Khachiyan ( v ) |
Pracoval pro | Rutgers University , Cornell University |
---|---|
Oblasti | Aplikovaná matematika , diskrétní matematika |
Ocenění |
Cena Komsomolu Cena Fulkersona (1982) |
Elipsoidní metoda |
Leonid Genrikhovich Khatchian (nar3. května 1952v Petrohradě - zemřel dne29.dubna 2005v South Brunswick , New Jersey) je americký matematik arménského původu, který učil informatiku na Rutgers University . Celosvětovou slávu získal jako vynálezce elipsoidního algoritmu (1979), který převrátil převládající koncepce lineární optimalizace a ukázal existenci algoritmu polynomiálních nákladů : od konce 40. let byl nejznámějším algoritmem ve skutečnosti simplexní algoritmus, který, i když velmi efektivní ve většině případů, je za exponenciální cenu. Přes stále velmi teoretický charakter Khatchianova vynálezu (časové náklady byly samozřejmě polynomy, ale vysoké míry ), to byl rozhodující průlom, který podnítil výzkum konvexní optimalizace ( pravděpodobnostní algoritmy ).
Khatchianova rodina se přestěhovala do Moskvy, když mu bylo pouhých 9 let. Byl přidělen do výpočetního střediska Akademie věd SSSR a obhájil první disertační práci v oboru digitálních věd (1978) a poté v oboru počítačových věd (1984). Ve svém článku Polynomial Algorithms in Linear Programming (1980) ukázal, jak lze některé lineární programy, pro které je simplexní algoritmus neefektivní, zpracovat vytvořením řady elipsoidů zapsaných do konvexu spojeného s problémem. Jak napsal Michael D. Grigoriadis, profesor na Rutgersově univerzitě, tento objev v té době narušil disciplínu a dokonce si zasloužil pozornost New York Times : „Tato práce přinesla zcela novou vizi a umožnila navrhnout nové algoritmy určené k řešení ještě složitějších problémů. „ Metodu elipsoidů vylepšili jiní vědci v 80. letech a našli různé aplikace, od financí po logistiku, přes průmysl pro optimalizaci tras a optimální alokaci zdrojů.
V roce 1982 mu Americká matematická společnost udělila prestižní Fulkersonovu cenu za výzkum diskrétní matematiky . Stále učil na Moskevském fyzikálním a technologickém institutu a poté emigroval do Spojených států (1989), kde jej jako hostujícího profesora přivítal Ústav operačního výzkumu a průmyslového inženýrství na Cornellově univerzitě . Následující rok byl přijat na Rutgers University . Tam pokračoval v tempu myšlenek, které v Rusku vyvolal na extrémních konvexech a ve složitosti výpočtu vepsaného elipsoidu o maximálním objemu, což vyústilo v článek věnovaný polyedrickému přístupu . S Bahmanem Kalantari věnoval sérii článků o škálování matic a rozložení zátěže v paralelním výpočtu . Zajímá se také o cyklické problémy, které se vyskytují v oblasti umělé inteligence a teorie her .
Khatchian zemřel na infarkt, když mu bylo pouhých 52 let.
Elipsoidní metoda je iterační optimalizační technika, kterou navrhli David Youdine, Arcadi Nemirovski a nezávisle Nahum Chor (1976–77); ale jeho použití Khatchiana k řešení lineárních programů je skutečná síla cesty, protože algoritmus vyžadoval výpočet odhadu vzdálenosti k optimálnímu; za tímto účelem Khatchian stanovil určitý počet přirážek na objemy mnohostěnů a analyzoval výpočetní přesnost požadovanou pro proveditelnost metody. Tyto výsledky zveřejnil bez důkazů ve čtyřstránkové poznámce Sovětské matematiky Doklady (Únor 1979). Algoritmus se dozvěděl o západních vědcích během konference na Matematickém programovacím sympoziu v Montrealu v měsíciSrpna 1979, pak díky článku Petera Gácse a Laci Lovásze, který se vyhnul neustálým změnám souřadnicových systémů známých ruským matematikům. Nakonec Khatchian v článku publikovaném v roce 1980 zveřejnil své demonstrace.
Od svého vynálezu Georgem Dantzigem v roce 1947 metoda simplexu diskvalifikovala řadu dřívějších heuristik pro řešení problémů s přiřazením pod lineárními omezeními, zejména iterací převádějících problém do konkurence mezi dvěma hráči. V průběhu padesátých a šedesátých let byla aplikována na větší a větší problémy, až na začátku sedmdesátých let Victor Klee a George Minty (de) poukázali na existenci programů, u nichž Danzigův algoritmus vede k prozkoumání řady otočných bodů exponenciálně rostoucích problém.
V této souvislosti měl Khatchianův výsledek účinek bomby: namísto výpočtů otočných čepů a oběhu podél okrajů mnohostěn konvergujících v konečném počtu kroků k optimálnímu, bylo nyní třeba začít od sféry v který jeden vepsal elipsoidy s klesajícími objemy, střed minimálního elipsoidu, který dává aproximaci optima. Nakonec tento algoritmus připomínal iterativní algoritmy opuštěné v padesátých letech, až na to, že se metrika měnila s každým novým elipsoidem.
Problémy s optimalizací byly takovým problémem, že mainstreamový tisk toto zjištění ohlásil. Gene Lawler shrnuje tehdejší rozruch v článku nazvaném „ The Great Mathematical Sputnik of 1979“ . "
V matematické komunitě se však několik vědců marně pokoušelo konkrétně využít Khatchianovu metodu; ale zdálo se, že algoritmus, i když má polynomiální cenu, vyžaduje v praxi vždy vysoký počet iterací, blízký tomu, který je vyžadován pro nejhorší případ ; navíc to vedlo k rozlišení špatně podmíněných lineárních systémů , kterému se Khatchian v následujících letech věnoval.
Ale nadšení pro Khatchianovu metodu upozornilo na teorii Yudina a Nemirovského, která se týkala složitosti problémů s nelineární optimalizací; a někteří matematici ( Martin Grötschel , Laci Lovász a Lex Schrijver ) si uvědomili, že elipsoidní metoda může představovat mocný nástroj kombinatorické optimalizace.