Sisäpistemenetelmä

Sisäpistemenetelmä  on menetelmä, jonka avulla voidaan ratkaista konveksia optimointitehtäviä epäyhtälöiden muodossa määritellyillä ehdoilla, jolloin alkuperäinen ongelma pelkistetään kuperaksi optimointitehtäväksi.

Sitä käytetään materiaalien lujuusongelmien ratkaisemiseen , matemaattiseen mallinnukseen ja ekonometriaan.

Sisäpistemenetelmän mainitsi ensimmäisen kerran I. I. Dikin vuonna 1967 . [1] . Näitä tutkimuksia jatkettiin, mukaan lukien kotimaiset tutkijat. 1970-luvulla V.G. Zhadan onnistui saamaan tärkeimmät tulokset ja kehittämään yleisen lähestymistavan sisäpistemenetelmien rakentamiseen lineaarisen ja epälineaarisen ohjelmoinnin ongelmien ratkaisemiseksi, jotka perustuvat tilojen muuntamiseen; ehdottaa esteprojektiivisia ja este-newtonilaisia ​​numeerisia menetelmiä.

Länsimainen kirjallisuus väittää, että sisäpistemenetelmää ehdotti ensimmäisenä John von Neumann , eikä sillä alkuperäisessä muodossaan ollut polynomikompleksia eikä se ollut tehokas. Käytännössä se oli jopa huonompi kuin simpleksimenetelmä , jolla ei myöskään ollut polynomin monimutkaisuutta [2] . Kuitenkin vuonna 1984 intialaisen matemaatikon Narendra Karmarkarin ehdottama lineaarinen ohjelmointialgoritmi osoitti, että polynomiaika jopa ylitti simpleksimenetelmän.

Sisäpistemenetelmien (toisin sanoen estefunktiomenetelmiksi) mukaan haun lähdepiste voidaan valita vain sallitun alueen sisällä.

Haun lähtökohdan valinta tapahtuu ongelman muotoilun mukaan. Jos rajoituksia tai niiden muuntamista ulkoisella pisteellä varustetuiksi rangaistusfunktioiksi ei ole, aloituspiste valitaan mielivaltaisesti. Rajoitusten tai niiden muuntamisen sisäpisteen sisältäviksi rangaistusfunktioiksi aloituspiste valitaan sallitun alueen sisäpuolelta

Tässä tapauksessa pisteet jaetaan hyväksyttäviin ja ei-hyväksyttäviin rajoituksista riippuen. Hyväksyttyjen pisteiden joukko puolestaan ​​​​jaetaan rajoituksista riippuen myös raja- ja sisäisiksi.

Logaritminen este ja keskuspolku

Keskipolun algoritmien alkuperä juontaa juurensa K. Frischin ajatukseen sisällyttää tavoitefunktioon rangaistustermejä epäyhtälisyysrajoitusten logaritmin muodossa parametrilla, joka pienenee monotonisesti nollaan.

Karmarkar-algoritmin [51] ilmestyminen sai tutkijat käyttämään aktiivisesti logaritmisia estefunktioita lineaarisissa ohjelmointiongelmissa.

Estemenetelmä

Karmakar-menetelmä on samanlainen kuin logbarrier-menetelmä.

Vaihe 1

Estemenetelmän suorittamiseksi sinun on määritettävä alkuperäinen sisäinen piste, ts. piste x, jolle fi(x) < 0 ∀i. Yleisessä tapauksessa sisäpisteen x löytäminen voi olla ei-triviaali tehtävä. Menetelmiä tämän ongelman ratkaisemiseksi kutsutaan ensimmäisen vaiheen menetelmiksi. Näitä ovat estemenetelmä ja suora kaksois-Newton-menetelmä.

Katso myös

• Newtonin menetelmä

Muistiinpanot

1. ↑ Dikin I. I. Lineaarisen ja toisen asteen ohjelmointiongelmien iteratiivinen ratkaisu // Dokl. Neuvostoliiton tiedeakatemia. - 1967. - T. 174 , nro 4 . - S. 747-748 .
2. ↑ Dantzig, George B.; Thapa, Mukund N. Lineaarinen ohjelmointi 2 : Teoria ja laajennukset  . - Springer-Verlag , 2003.

Kirjallisuus

• Järjestelmäanalyysi ja toimintatutkimus. Tekijät: Yu. Chernikov
• Bonnans, J. Frederic; Gilbert, J. Charles; Lemarechal, Claude; Sagastizábal, Claudia A. Numeerinen optimointi: teoreettiset ja käytännön näkökohdat  (englanniksi) . — Toinen tarkistettu painos. 1997 ranskan kielen käännöksestä. - Berliini: Springer-Verlag , 2006. - P. xiv+490. — (Yliopistoteksti). — ISBN 3-540-35445-X . - doi : 10.1007/978-3-540-35447-5 .
• Karmarkar, N. Proceedings of the kuudestoista vuotuinen ACM symposium on Theory of Computing - STOC '84   : Journal . - 1984. - s. 302 . — ISBN 0-89791-133-4 . - doi : 10.1145/800057.808695 . Arkistoitu alkuperäisestä 28. joulukuuta 2013. Arkistoitu 28. joulukuuta 2013 Wayback Machineen
• Mehrotra, Sanjay. Primal-Dual Interior Point -menetelmän toteuttamisesta  //  SIAM Journal on Optimization : Journal. - 1992. - Voi. 2 , ei. 4 . - s. 575 . - doi : 10.1137/0802028 .
• Nocedal, George; Stephen Wright. Numeerinen optimointi  (rajoittamaton) . - New York, NY: Springer, 1999. - ISBN 0-387-98793-2 .
• Press, W.H.; Teukolsky, SA; Vetterling, WT; Flannery, BP jakso 10.11. Lineaarinen ohjelmointi: sisäpistemenetelmät // Numeeriset reseptit: Tieteellisen laskennan taito  . – 3. - New York: Cambridge University Press , 2007. - ISBN 978-0-521-88068-8 .
• Wright, Stephen. Primal-Dual Interior-Point -menetelmät  (rajoittamaton) . - Philadelphia, PA: SIAM, 1997. - ISBN 0-89871-382-X .
• Boyd, Stephen; Vandenberghe, Lieven. Kupera optimointi  (määrätön) . - Cambridge University Press , 2004.
• Babynin M. S., Zhadan V. G. Suora sisäpistemenetelmä puolimääräisen ohjelmoinnin lineaariseen ongelmaan , ZhVMiMF, 48:10 (2008), 1780–1801
• Zhadan V. G., Orlov A. A. Kahden sisäisen pisteen menetelmät lineaariseen puolimääräiseen ohjelmointiongelmaan , ZhVMiMF, 51:12 (2011), 2158–2180
• Zhadan VG, Orlov AA Hyväksytty kahden sisäpisteen menetelmä lineaariseen puolimääräiseen ohjelmointiongelmaan , Avtomat. i Telemekh., 2012, 2, 25–40

Linkit

• Koneoppimisen optimointitekniikat: Interior Point -menetelmä