Metoda punctului interior

Metoda punctului interior  este o metodă care permite rezolvarea problemelor de optimizare convexă cu condiții specificate sub formă de inegalități, reducând problema inițială la o problemă de optimizare convexă.

Este utilizat în rezolvarea problemelor de rezistență a materialelor , modelare matematică și econometrie.

Metoda punctului interior a fost menționată pentru prima dată de I. I. Dikin în 1967 . [1] . Aceste studii au fost continuate, inclusiv de către oamenii de știință autohtoni. În anii 1970, V.G. Zhadan a reușit să obțină principalele rezultate și să dezvolte o abordare generală a construcției metodelor punctuale interioare pentru rezolvarea problemelor de programare liniară și neliniară, bazate pe transformarea spațiilor; propune metode numerice barieră-proiectivă și barieră-newtoniene.

Literatura occidentală susține că metoda punctului interior a fost propusă pentru prima dată de John von Neumann și, în forma sa originală, nu avea complexitate polinomială și nici nu era eficientă. În practică, a fost chiar inferioară metodei simplex , care nici nu avea complexitate polinomială [2] . Totuși, în 1984, algoritmul de programare liniară propus de matematicianul indian Narendra Karmarkar a demonstrat că timpul polinomial a depășit chiar metoda simplex.

Conform metodelor punctului interior (denumite altfel metode ale funcției de barieră), punctul sursă pentru căutare poate fi selectat numai în interiorul zonei permise.

Alegerea punctului de plecare al căutării se realizează în funcție de formularea problemei. În absența restricțiilor sau a transformării acestora în funcții de penalizare cu punct extern, punctul de plecare este ales arbitrar. În prezența restricțiilor sau a transformării acestora în funcții de penalizare cu punct interior, punctul de plecare este ales în interiorul zonei admisibile.

În acest caz, setul de puncte este împărțit în admisibil și inadmisibil, în funcție de restricții. La rândul său, setul de puncte admisibile, în funcție de restricții, este de asemenea împărțit în limite și interne.

Bariera logaritmică și calea centrală

Originile algoritmilor de cale centrală se întorc la ideea lui K. Frisch de a include termeni de penalizare în funcția obiectiv sub forma unui logaritm de constrângeri de inegalitate cu un parametru care scade monoton la zero.

Apariția algoritmului Karmarkar [51] i-a determinat pe cercetători să folosească în mod activ funcțiile barierei logaritmice în problemele de programare liniară.

Metoda barierei

Metoda Karmakar este similară cu metoda barieră de bușteni.

Faza 1

Pentru a rula metoda barierei, trebuie să specificați punctul intern inițial, adică. un punct x pentru care fi(x) < 0 ∀i. În cazul general, găsirea unui punct interior x poate fi o sarcină netrivială. Metodele de rezolvare a acestei probleme se numesc metode ale primei faze. Acestea includ metoda barieră și metoda Newton direct-duală.

Vezi și

• metoda lui Newton

Note

1. ↑ Dikin I. I. Rezolvarea iterativă a problemelor de programare liniară și pătratică // Dokl. Academia de Științe a URSS. - 1967. - T. 174 , nr 4 . - S. 747-748 .
2. ↑ Dantzig, George B.; Thapa, Mukund N. Programare liniară 2 : Teorie și extensii  . — Springer-Verlag , 2003.

Literatură

• Analiza sistemului și cercetarea operațională.Autori: Yu. Chernikov
• Bonnans, J. Frederic; Gilbert, J. Charles; Lemarechal, Claude; Sagastizábal, Claudia A. Optimizare numerică: Aspecte teoretice și practice  (engleză) . — Ed. a doua revizuită. de traducere din 1997 franceza. - Berlin: Springer-Verlag , 2006. - P. xiv+490. — (text universitar). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
• Karmarkar, N. Proceedings of the 16th annual ACM symposium on Theory of computing - STOC '84   : journal . - 1984. - P. 302 . — ISBN 0-89791-133-4 . - doi : 10.1145/800057.808695 . Arhivat din original pe 28 decembrie 2013. Arhivat pe 28 decembrie 2013 la Wayback Machine
• Mehrotra, Sanjay. Despre implementarea unei metode de punct interior primal-dublu  //  SIAM Journal on Optimization : journal. - 1992. - Vol. 2 , nr. 4 . — P. 575 . - doi : 10.1137/0802028 .
• Nocedal, George; Stephen Wright. Optimizare numerică  (nedefinită) . - New York, NY: Springer, 1999. - ISBN 0-387-98793-2 .
• Presă, W.H.; Teukolsky, SA; Vetterling, WT; Flannery, BP Secțiunea 10.11. Programare liniară: Metode de punct interior // Rețete numerice: Arta calculului științific  . — al 3-lea. - New York: Cambridge University Press , 2007. - ISBN 978-0-521-88068-8 .
• Wright, Stephen. Metode Primal-Dual Interior-Point  (nedefinite) . - Philadelphia, PA: SIAM, 1997. - ISBN 0-89871-382-X .
• Boyd, Stephen; Vandenberghe, Lieven. Optimizare convexă  (nedefinită) . — Cambridge University Press , 2004.
• Babynin M. S., Zhadan V. G. Metoda punctului interior direct pentru o problemă liniară de programare semidefinită , ZhVMiMF, 48:10 (2008), 1780–1801
• Zhadan V. G., Orlov A. A. Metode cu puncte interioare duble pentru o problemă de programare liniară semidefinită , ZhVMiMF, 51:12 (2011), 2158–2180
• Zhadan VG, Orlov AA Metodă admisibilă a punctului dublu interior pentru o problemă de programare liniară semidefinită , Avtomat. i Telemekh., 2012, 2, 25–40

Link -uri

• Tehnici de optimizare în Machine Learning: Metoda punctului interior