Tehnici de căutare cu arc pentru metodele cu punct interior

Titlul original:

Arc-Search Techniques for Interior-Point Methods

Conținutul cărții:

Această carte discută un domeniu important al optimizării numerice, numit metoda punctului interior. Acest subiect a fost popular încă din anii 1980, când oamenii au realizat treptat că toți algoritmii simplex nu erau convergenți în timp polinomial și că s-a putut dovedi că mulți algoritmi cu punct interior converg în timp polinomial.

Cu toate acestea, pentru o lungă perioadă de timp, a existat un decalaj vizibil între limitele polinomiale teoretice ale algoritmilor cu punct interior și eficiența acestor algoritmi. Strategiile care erau importante pentru eficiența de calcul au devenit bariere în demonstrarea limitelor polinomiale bune. Cu cât strategiile au fost utilizate mai mult în algoritmi, cu atât limitele polinomiale au devenit mai rele.

Pentru a exacerba și mai mult problema, algoritmul predictor-corector (MPC) al lui Mehrotra (cel mai popular și mai eficient algoritm de punct interior până de curând) utilizează toate strategiile bune și nu reușește să dovedească convergența.

Prin urmare, MPC nu are polinomialitate, o problemă critică cu metoda simplex. Această carte discută evoluțiile recente care rezolvă dilema.

Ea are trei părți principale. Prima, care include capitolele 1, 2, 3 și 4, prezintă unii dintre cei mai importanți algoritmi în timpul dezvoltării metodei punctului interior în jurul anilor 1990, majoritatea dintre aceștia fiind larg cunoscuți. Scopul principal al acestei părți este de a explica dilema descrisă mai sus, analizând limitele polinomiale ale acestor algoritmi și rezumând experiența de calcul asociată cu aceștia.

A doua parte, care include capitolele 5, 6, 7 și 8, descrie modul de rezolvare pas cu pas a dilemei utilizând tehnici de căutare a arcurilor. La sfârșitul acestei părți, este prezentat un algoritm foarte eficient cu cea mai mică limită polinomială. Ultima parte, care include capitolele 9, 10, 11 și 12, extinde tehnicile arc-search la unele probleme mai generale, cum ar fi programarea pătratică convexă, problema complementarității liniare și programarea semi-definită.