Kupera ohjelmointi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21.11.2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Konveksi ohjelmointi on matemaattisen optimoinnin osakenttä , joka tutkii konveksien funktioiden minimoimisen ongelmaa konveksissa joukoissa . Vaikka monet konveksiohjelmointiongelmien luokat hyväksyvät polynomiaikaiset algoritmit [1] , matemaattinen optimointi on yleensä NP-kovaa [2] [3] [4] .

Konveksilla ohjelmoinnilla on sovelluksia useilla eri aloilla, kuten automaattisissa ohjausjärjestelmissä , signaalien arvioinnissa ja käsittelyssä , tietoliikenteessä ja verkoissa, piiristössä [5] , data-analyysissä ja mallintamisessa, rahoituksessa , tilastoissa ( optimaalinen kokeilusuunnittelu ) [6] ja rakenteellinen optimointi [7] . Tietokonetekniikan ja optimointialgoritmien kehitys on tehnyt konveksista ohjelmoinnista lähes yhtä yksinkertaista kuin lineaarisen ohjelmoinnin [8] .

Määritelmä

Konveksi ohjelmointitehtävä on optimointitehtävä , jossa tavoitefunktio on konveksi ja mahdollisten ratkaisujen alue on konveksi . Funktio , joka kuvaa jonkin osajoukon , on konveksi, jos toimialue on konveksi sekä kaikille että kaikille niiden verkkotunnuksessa . Joukko on kupera, jos sen kaikki alkiot ja mikä tahansa niistä kuuluu myös joukkoon. $f$ $\mathbb {R} ^{n}$ ${\displaystyle \mathbb {R} \cup \{\pm \infty \))$ $\theta \in [0,1]$ $x,y$ $f(\theta x+(1-\theta )y)\leqslant \theta f(x)+(1-\theta )f(y)$ $x,y$ $\theta \in [0,1]$ $\theta x+(1-\theta )y$

Erityisesti kuperan ohjelmoinnin ongelma on löytää joitakin , joista $\mathbf {x^{\ast }} \in C$

{\displaystyle \inf\{f(\mathbf {x} ):\mathbf {x} \in C\))

jossa tavoitefunktio on konveksi, kuten myös mahdollisten ratkaisujen joukko [9] [10] . Jos tällainen piste on olemassa, sitä kutsutaan optimipisteeksi . Kaikkien optimipisteiden joukkoa kutsutaan optimijoukoksi . Jos rajaamaton tai infimumia ei saavuteta, optimoinnin sanotaan olevan rajaton . Jos se on tyhjä, puhutaan tehtävästä , jota ei voida hyväksyä [11] . $f$ $C$ $f$ $C$ $C$

Vakiomuoto

Konveksin ohjelmointitehtävän sanotaan olevan vakiomuodossa, jos se kirjoitetaan muodossa

Minimoida

f(\mathbf {x} )

Ehdoissa

{\begin{aligned}&&g_{i}(\mathbf {x} )\leqslant 0,\quad i=1,\dots ,m\\&&h_{i}(\mathbf {x} )=0, \quad i=1,\dots ,p,\end{tasattu}}

missä on optimointimuuttuja, funktiot ovat konveksia ja funktiot affiineja [11] . $x \in \mathbb{R}^n$ ${\displaystyle f,g_{1},\ldots ,g_{m))$ ${\displaystyle h_{1},\ldots ,h_{p))$

Näissä termeissä funktio on ongelman tavoitefunktio, ja funktioita ja kutsutaan rajoitusfunktioiksi. Optimointitehtävän hyväksyttävä ratkaisujoukko on joukko, joka koostuu kaikista ehdot täyttävistä pisteistä ja . Tämä joukko on konveksi, koska konveksin funktion alitason joukot ovat konveksia, affiiniset joukot ovat myös konveksia ja konveksien joukkojen leikkauspiste on konveksi joukko [12] . $f$ $g_i$ $Hei}$ $x \in \mathbb{R}^n$ $g_{1}(x)\leqslant 0,\ldots ,g_{m}(x)\leqslant 0$ $h_{1}(x)=0,\ldots ,h_{p}(x)=0$

Monet optimointiongelmat voidaan pelkistää tähän vakiomuotoon. Esimerkiksi ongelma koveran funktion maksimoimisesta voidaan muotoilla uudelleen vastaavasti kuin konveksin funktion minimoimisen ongelma , joten konveran joukon koveran funktion maksimointiongelmaa kutsutaan usein konveksiksi ohjelmointiongelmaksi. $f$ $-f$

Ominaisuudet

Konveksien ohjelmointiongelmien hyödylliset ominaisuudet [13] [11] :

mikä tahansa paikallinen minimi on globaali minimi ;
optimaalinen joukko on kupera;
jos tavoitefunktio on voimakkaasti kupera, ongelmalla on enintään yksi optimaalinen piste.

Näitä tuloksia käytetään konveksissa minimointiteoriassa yhdessä funktionaalisen analyysin geometristen käsitteiden kanssa ( Hilbert-avaruuksilla ), kuten Hilbertin projektiolause , tukihypertasolause ja Farkasin lemma .

Esimerkkejä

Seuraavat tehtäväluokat ovat konvekseja ohjelmointiongelmia tai ne voidaan pelkistää konvekseihin ohjelmointiongelmiin yksinkertaisilla muunnoksilla [11] [14] :

Pienimmän neliön menetelmä
Lineaarinen ohjelmointi
Kupera neliöllinen optimointi lineaarisilla rajoituksilla
Neliöllinen ohjelmointi neliörajoitteissa
Kartiomainen optimointi
Geometrinen ohjelmointi
Kartioohjelmointi toisen asteen kartiolla
Puolivarma ohjelmointi
Entropian maksimiperiaate asianmukaisin rajoituksin

Lagrange-kertoimien menetelmä

Tarkastellaan vakiomuodossa annettua kuperaa minimointitehtävää kustannusfunktiolla ja epäyhtälörajoitteilla . Sitten määritelmäalue on: $f(x)$ $g_{i}(x)\leqslant 0$ $1\leqslant i\leqslant m$ ${\mathcal {X}}$

{\mathcal {X}}=\left\{x\in X\vert g_{1}(x),\ldots ,g_{m}(x)\leqslant 0\right\}.

Lagrange-toiminto ongelmaan

L(x,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})=\lambda _{0}f(x)+\lambda _{1}g_ {1}(x)+\cdots +\lambda _{m}g_{m}(x).

Jokaiselle pisteelle , joka minimoi arvoon , on olemassa reaalilukuja , joita kutsutaan Lagrange-kertoimiksi ja joille seuraavat ehdot täyttyvät samanaikaisesti: $x$ $X$ $f$ $X$ $\lambda _{0},\lambda _{1},\ldots ,\lambda _{m},$

$x$ minimoi yli kaiken $L(y,\lambda _{0},\lambda _{1},\ldots ,\lambda _{m})$ $y\in X,$
$\lambda _{0},\lambda _{1},\ldots ,\lambda _{m}\geqslant 0,$ ainakin yhden kanssa $\lambda _{k}>0,$
$\lambda _{1}g_{1}(x)=\cdots =\lambda _{m}g_{m}(x)=0$ (täydentävä ei-jäykkyys).

Jos on olemassa "vahva hyväksyttävä kohta", toisin sanoen piste, joka tyydyttää $z$

g_{1}(z),\ldots ,g_{m}(z)<0,

niin yllä olevaa väitettä voidaan vahvistaa vaatimaan . $\lambda _{0}=1$

Päinvastoin, jos jotkut täyttävät ehdot (1)-(3) skalaareille , joissa on , se minimoi ehdottomasti . $x$ $X$ ${\displaystyle \lambda _{0},\ldots ,\lambda _{m))$ $\lambda _{0}=1$ $x$ $f$ $X$

Algoritmit

Kupera ohjelmointiongelma ratkaistaan seuraavilla moderneilla menetelmillä: [15]

Subgradienttisädemenetelmät } (Wolf, Lemerical, Kivel),
Pohjaprojisointimenetelmät (Polyak),
Sisäpistemenetelmä [1] , jossa käytetään itseyhdenmukaisia estefunktioita [16] ja itsesäännöllisiä estefunktioita [17] .
Leikkaustason menetelmä
Ellipsoidi menetelmä
Alakaltevuusmenetelmät
Drift-kaltevuus ja drift+rangaistusmenetelmä

Aligradienttimenetelmät voidaan toteuttaa yksinkertaisesti siksi, että niitä käytetään laajalti [18] [19] . Kaksoisgradienttimenetelmät ovat aligradienttimenetelmiä, joita sovelletaan kaksoisongelmaan . Drift+penalty-menetelmä on samanlainen kuin dual subgradient -menetelmä, mutta käyttää päämuuttujien aikakeskiarvoa.

Laajennukset

Konveksin ohjelmoinnin laajennukset sisältävät optimoinnit kaksoiskuperille , pseudokuperille ja kvasikonveksille funktioille. Laajennuksia konveksianalyysin teoriaan ja iteratiivisia menetelmiä ei-konveksien optimointiongelmien likimääräiseen ratkaisuun esiintyy yleisen konveksiuden alalla , joka tunnetaan abstraktina konveksiana analyysinä.

Katso myös

Muistiinpanot

↑ 1 2 Nesterov ja Nemirovskii, 1994 .
↑ Murty ja Kabadi 1987 , s. 117–129.
↑ Sahni, 1974 , s. 262-279.
↑ Pardalos ja Vavasis, 1991 , s. 15-22.
↑ Boyd ja Vandenberghe 2004 , s. 17.
↑ Christensen, Klarbring, 2008 , s. kappale neljä.
↑ Boyd, Vandenberghe, 2004 .
↑ Boyd ja Vandenberghe 2004 , s. kahdeksan.
↑ Hiriart-Urruty, Lemaréchal, 1996 , s. 291.
↑ Ben-Tal, Nemirovskiĭ, 2001 , s. 335–336.
↑ 1 2 3 4 Boyd, Vandenberghe, 2004 , s. kappale neljä.
↑ Boyd ja Vandenberghe 2004 , s. kappale 2.
↑ Rockafellar, 1993 , s. 183-238.
↑ Agrawal, Verschueren, Diamond, Boyd, 2018 , s. 42–60.
↑ Katso konveksin ohjelmoinnin menetelmiä Irriart-Urrutin ja Lemericalin kirjoista (useita kirjoja) sekä Rushczynskin, Bercekasin ja Boydin ja Vanderbergen kirjoista (sisäpistemenetelmät).
↑ Nesterov, Nemirovskii, 1995 .
↑ Peng, Roos, Terlaky, 2002 , s. 129-171.
↑ Bertsekas, 2009 .
↑ Bertsekas, 2015 .

Kirjallisuus

Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Kupera analyysi- ja minimointialgoritmit: Perusteet . - 1996. - ISBN 9783540568506 .
Aharon Ben-Tal, Arkadi Semenovich Nemirovskiĭ. Luentoja nykyaikaisesta kuperasta optimoinnista: analyysi, algoritmit ja suunnittelusovellukset . - 2001. - ISBN 9780898714913 .
Katta Murty, Santosh Kabadi. Joitakin NP-täydellisiä ongelmia toisen asteen ja epälineaarisen ohjelmoinnin yhteydessä // Matemaattinen ohjelmointi. - 1987. - T. 39 , no. 2 . — s. 117–129 . - doi : 10.1007/BF02592948 .
Sahni S. Laskennallisesti liittyvät ongelmat // SIAM Journal on Computing. - 1974. - Numero. 3 .
Panos M. Pardalos, Stephen A. Vavasis. Toisen asteen ohjelmointi yhdellä negatiivisella ominaisarvolla on NP-hard // Journal of Global Optimization. - 1991. - T. 1 , nro 1 .
R. Tyrrell Rockafellar. Kupera analyysi . - Princeton: Princeton University Press, 1970.
R. Tyrrell Rockafellar. Lagrangen kertoimet ja optimaalisuus // SIAM Review. - 1993. - T. 35 , no. 2 . - doi : 10.1137/1035044 .
Akshay Agrawal, Robin Verschueren, Steven Diamond, Stephen Boyd. Uudelleenkirjoitusjärjestelmä kuperaan optimointiongelmiin // Ohjaus ja päätös. - 2018. - V. 5 , nro 1 . - doi : 10.1080/23307706.2017.1397554 .
Juri Nesterov, Arkadii Nemirovski. Sisäpisteen polynomialgoritmit konveksissa ohjelmoinnissa. - Society for Industrial and Applied Mathematics, 1995. - ISBN 978-0898715156 .
Juri Nesterov, Arkadii Nemirovski. Sisäpisteen polynomimenetelmät kuperassa ohjelmoinnissa. - SIAM, 1994. - V. 13. - (Soveltavan ja numeerisen matematiikan opinnot). - ISBN 978-0-89871-319-0 .
Juri Nesterov. Johdantoluennot kuperasta optimoinnista. - Boston, Dordrecht, Lontoo: Kluwer Academic Publishers, 2004. - T. 87. - (Applied Optimization). — ISBN 1-4020-7553-7 .
Jiming Peng, Cornelis Roos, Tamás Terlaky. Itsesäännölliset funktiot ja uudet hakusuunnat lineaariseen ja puolimääräiseen optimointiin // Matemaattinen ohjelmointi. - 2002. - T. 93 , no. 1 . — ISSN 0025-5610 . - doi : 10.1007/s101070200296 .
Dimitri P. Bertsekas, Angelia Nedic, Asuman Ozdaglar. Kupera analyysi ja optimointi. - Athena Scientific, 2003. - ISBN 978-1-886529-45-8 .
Dimitri P. Bertsekas. Kupera optimointiteoria. - Belmont, MA: Athena Scientific, 2009. - ISBN 978-1-886529-31-1 .
Dimitri P. Bertsekas. Kupera optimointialgoritmit. - Belmont, MA: Athena Scientific, 2015. - ISBN 978-1-886529-28-1 .
Stephen P. Boyd, Lieven Vandenberghe. Kupera optimointi . - Cambridge University Press, 2004. - ISBN 978-0-521-83378-3 .
Jonathan M. Borwein, Adrian Lewis. Kupera analyysi ja epälineaarinen optimointi. - Springer, 2000. - (CMS Books in Mathematics). — ISBN 0-387-29570-4 .
Peter W. Christensen, Anders Klarbring. Johdatus rakenteelliseen optimointiin. - Springer Science & Businees Media, 2008. - V. 153. - ISBN 9781402086663 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konveksin analyysin perusteet. - Berlin: Springer, 2004. - (Grundlehren-tekstipainokset). - ISBN 978-3-540-42205-1 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Kupera analyysi ja minimointialgoritmit, osa I: Fundamentals. - Berliini: Springer-Verlag, 1993. - T. 305. - S. xviii + 417. - ISBN 978-3-540-56850-6 .
Jean-Baptiste Hiriart-Urruty, Claude Lemarechal. Konveksianalyysi- ja minimointialgoritmit, osa II: Kehittynyt teoria ja nippumenetelmät. - Berliini: Springer-Verlag, 1993. - T. 306. - S. xviii + 346. — ISBN 978-3-540-56852-0 .
Krzysztof C. Kiwiel. Laskeutumismenetelmät erottumattomaan optimointiin. - New York: Springer-Verlag, 1985. - (Matematiikan luentomuistiinpanot). - ISBN 978-3-540-15642-0 .
Claude Lemarechal. Lagrangian rentoutuminen // Laskennallinen kombinatorinen optimointi: Papers from the Spring School, joka pidettiin Schloß Dagstuhlissa, 15.–19. toukokuuta 2000. - Berlin: Springer-Verlag, 2001. - Vol. 2241. - P. 112-156. — ISBN 978-3-540-42877-0 . - doi : 10.1007/3-540-45586-8_4 .
Andrzej Ruszczyński. epälineaarinen optimointi. - Princeton University Press, 2006.
Eremin I. I. , Astafiev N. N. Johdatus lineaarisen ja konveksin ohjelmoinnin teoriaan. - M. , Nauka , 1976. - 189 s.
Kamenev GK Optimaaliset adaptiiviset menetelmät kuperoiden kappaleiden polyhedraaliseen approksimaatioon. M.: VTs RAN, 2007, 230 s. ISBN 5-201-09876-2 .
Kamenev GK Numeerinen tutkimus kuperakappaleiden monitahoisen approksimaatiomenetelmien tehokkuudesta. M: Toim. CC RAS, 2010, 118s. ISBN 978-5-91601-043-5 .

Linkit

Stephen Boyd, Lieven Vandenberghe, kupera optimointi (pdf)
EE364a: Convex Optimization I , EE364b: Convex Optimization II , Oxfordin yliopiston kurssisivu
6.253: Convex Analysis and Optimization , MIT OCW -kurssisivu
Brian Borchers, Yleiskatsaus kuperaan optimointiohjelmistoon

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijk menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi