Afinní škálování - Affine scaling

Metoda afinního škálování je metoda vnitřních bodů, což znamená, že tvoří trajektorii bodů přesně uvnitř proveditelný region lineárního programu (na rozdíl od simplexní algoritmus, který prochází rohy proveditelné oblasti).

v matematická optimalizace, afinní škálování je algoritmus k řešení lineární programování problémy. Konkrétně se jedná o metoda vnitřních bodů, objeveno uživatelem sovětský matematik I. I. Dikin v roce 1967 a objevil v NÁS. v polovině 80. let.

Dějiny

Afinní škálování má historii vícenásobný objev. Poprvé to vydal I. I. Dikin v Institutu energetických systémů Ruské akademie věd (Siberian Energy Institute, SSSR Academy of Sc. V té době) v roce 1967 Doklady Akademii Nauk SSSR, následovaný důkazem o jeho konvergenci v roce 1974.^[1] Dikinova práce zůstala do značné míry bez povšimnutí až do objevu roku 1984 Karmarkarův algoritmus, první praktický polynomiální čas algoritmus pro lineární programování. Důležitost a složitost Karmarkarovy metody přiměla matematiky hledat jednodušší verzi.

Několik skupin poté samostatně přišlo s variantou Karmarkarova algoritmu. E. R. Barnes ve společnosti IBM,^[2] tým vedený R. J. Vanderbei na AT&T,^[3] a několik dalších nahradilo projektivní transformace že Karmarkar používá afinní ty. Po několika letech bylo zjištěno, že „nové“ algoritmy afinního škálování byly ve skutečnosti objevy desetiletí starých výsledků Dikina.^[1]^[4] Z nově objevitelů pouze Barnes a Vanderbei et al. se podařilo vytvořit analýzu konvergenčních vlastností afinního škálování. Karmarkar, který v tomto časovém rámci také přišel s afinním měřítkem, se mylně domníval, že se sbíhá stejně rychle jako jeho vlastní algoritmus.^[5]^:346

Algoritmus

Afinní škálování funguje ve dvou fázích, z nichž první najde a proveditelný bod, od kterého se má začít optimalizovat, zatímco druhý provádí skutečnou optimalizaci, přičemž zůstává striktně uvnitř proveditelné oblasti.

Obě fáze řeší lineární programy ve formě rovnosti, viz.

minimalizovat

C \cdot X

podléhá

Sekera = b

,

X \geq 0

.

Tyto problémy jsou řešeny pomocí iterační metoda, který koncepčně pokračuje vynesením trajektorie bodů striktně uvnitř proveditelné oblasti problému, výpočet předpokládané klesání kroky v přeškálované verzi problému, poté krok o krok zpět k původnímu problému. Škálování zajišťuje, že algoritmus může pokračovat ve velkých krocích, i když je uvažovaný bod blízko hranice proveditelné oblasti.^[5]^:337

Formálně je iterační metoda v srdci afinního škálování brána jako vstup $A$ , $b$ , $C$ , počáteční odhad $X 0 > 0$ to je striktně proveditelné (tj. $Sekera 0 = b$ ), tolerance $ε$ a velikost kroku $β$ . Poté pokračuje iterací^[1]^:111

Nechat $D k$ být diagonální matice s $X k$ na jeho úhlopříčce.
Vypočítejte vektor dvojí proměnné:
${ displaystyle w ^ {k} = (AD_ {k} ^ {2} A ^ { operatorname {T}}) ^ {- 1} AD_ {k} ^ {2} c.}$
Vypočítejte vektor snížené náklady, které měří ochablost omezení nerovnosti v duálu:
${ displaystyle r ^ {k} = c-A ^ { operatorname {T}} w ^ {k}.}$
Li ${ displaystyle r ^ {k}> 0}$ a ${ displaystyle mathbf {1} ^ { operatorname {T}} D_ {k} r ^ {k} < varepsilon}$ , aktuální řešení $X k$ je $ε$ -optimální.
Li ${ displaystyle -D_ {k} r ^ {k} geq 0}$ , problém je neomezený.
Aktualizace ${ displaystyle x ^ {k + 1} = x ^ {k} - beta { frac {D_ {k} ^ {2} r ^ {k}} { | D_ {k} r ^ {k} |}}}$

Inicializace

Fáze I, inicializace, řeší pomocný problém s další proměnnou $u$ a použije výsledek k odvození počátečního bodu pro původní problém. Nechat $X 0$ být svévolným, přísně pozitivním bodem; pro původní problém to nemusí být proveditelné. Nemožnost $X 0$ se měří vektorem

{ displaystyle v = b-Ax ^ {0}}

.

Li $proti = 0$ , $X 0$ je proveditelné. Pokud tomu tak není, vyřeší fáze I pomocný problém

minimalizovat

u

podléhá

Sekera + uv = b

,

X \geq 0

,

u \geq 0

.

Tento problém má správnou formu řešení výše uvedeným iterativním algoritmem,^[A] a

{ displaystyle { begin {pmatrix} x ^ {0} 1 end {pmatrix}}}

je proveditelným počátečním bodem. Řešení pomocného problému dává

{ displaystyle { begin {pmatrix} x ^ {*} u ^ {*} end {pmatrix}}}

.

Li $u * = 0$ , pak $X * = 0$ je proveditelné v původním problému (i když ne nutně striktně uvnitř), zatímco pokud $u * > 0$ , původní problém je neproveditelný.^[5]^:343

Analýza

I když je snadné to říci, afinní škálování bylo těžké analyzovat. Jeho konvergence závisí na velikosti kroku, $β$ . Pro velikosti kroku $β \leq 2 / 3$ Bylo prokázáno, že Vanderbeiova varianta afinního škálování konverguje, zatímco pro $β > 0.995$ je znám příklad problému, který konverguje na suboptimální hodnotu.^[5]^:342 Ukázalo se, že vykazují i další varianty algoritmu chaotický chování i na malé problémy, když $β > 2 / 3$ .^[6]^[7]

Poznámky

^ Struktura pomocného problému umožňuje určité zjednodušení vzorců.^[5]^:344

Reference

^ ^A ^b ^C Vanderbei, R. J .; Lagarias, J. C. (1990). "I. I. Dikinův výsledek konvergence pro algoritmus afinního měřítka". Matematický vývoj vyplývající z lineárního programování (Brunswick, ME, 1988). Současná matematika. 114. Providence, RI: American Mathematical Society. 109–119. doi:10.1090 / conm / 114/1097868. PAN 1097868.
^ Barnes, Earl R. (1986). "Varianta Karmarkarova algoritmu pro řešení problémů lineárního programování". Matematické programování. 36 (2): 174–182. doi:10.1007 / BF02592024.
^ Vanderbei, Robert J .; Meketon, Marc S .; Freedman, Barry A. (1986). „Modifikace Karmarkarova algoritmu lineárního programování“ (PDF). Algorithmica. 1 (1–4): 395–407. doi:10.1007 / BF01840454.
^ Bayer, D. A .; Lagarias, J. C. (1989). „Nelineární geometrie lineárního programování I: Afinní a projektivní trajektorie škálování“ (PDF). Transakce Americké matematické společnosti. 314 (2): 499. doi:10.1090 / S0002-9947-1989-1005525-6.
^ ^A ^b ^C ^d ^E Vanderbei, Robert J. (2001). Lineární programování: základy a rozšíření. Springer Verlag. 333–347.
^ Bruin, H .; Fokkink, R.J .; Gu, G .; Roos, C. (2014). „O chaotickém chování algoritmu škálování prima – duální afinita – pro lineární optimalizaci“ (PDF). Chaos. 24 (4): 043132. arXiv:1409.6108. Bibcode:2014Chaos..24d3132B. doi:10.1063/1.4902900. PMID 25554052.
^ Castillo, Ileana; Barnes, Earl R. (2006). "Chaotické chování algoritmu škálování afinních pro lineární programování". SIAM J. Optim. 11 (3): 781–795. doi:10.1137 / S1052623496314070.

Další čtení

Adler, Ilan; Monteiro, Renato D. C. (1991). „Omezující chování spojitých trajektorií afinního škálování pro problémy lineárního programování“ (PDF). Matematické programování. 50 (1–3): 29–51. doi:10.1007 / bf01594923.
Saigal, Romesh (1996). „Jednoduchý důkaz metody primárního afinního škálování“ (PDF). Annals of Operations Research. 62: 303–324. doi:10.1007 / bf02206821.
Tseng, Paul; Luo, Zhi-Quan (1992). „O konvergenci algoritmu afinního měřítka“ (PDF). Matematické programování. 56 (1–3): 301–319. CiteSeerX 10.1.1.94.7852. doi:10.1007 / bf01580904. hdl:1721.1/3161.

externí odkazy

„15.093 Optimalizační metody, přednáška 21: Algoritmus afinního škálování“ (PDF). MIT OpenCourseWare. 2009.
Mitchell, John (listopad 2010). „Metody vnitřních bodů“. Rensselaer Polytechnic Institute.
„Přednáška 6: Metoda vnitřního bodu“ (PDF). NCTU OpenCourseWare. Archivovány od originál (PDF) dne 2016-10-11. Citováno 2016-02-06.

[6] Struktura pomocného problému umožňuje určité zjednodušení vzorců.^[5]^:344

[vanderbei90-1] A ^b ^C Vanderbei, R. J .; Lagarias, J. C. (1990). "I. I. Dikinův výsledek konvergence pro algoritmus afinního měřítka". Matematický vývoj vyplývající z lineárního programování (Brunswick, ME, 1988). Současná matematika. 114. Providence, RI: American Mathematical Society. 109–119. doi:10.1090 / conm / 114/1097868. PAN 1097868.

[2] Barnes, Earl R. (1986). "Varianta Karmarkarova algoritmu pro řešení problémů lineárního programování". Matematické programování. 36 (2): 174–182. doi:10.1007 / BF02592024.

[3] Vanderbei, Robert J .; Meketon, Marc S .; Freedman, Barry A. (1986). „Modifikace Karmarkarova algoritmu lineárního programování“ (PDF). Algorithmica. 1 (1–4): 395–407. doi:10.1007 / BF01840454.

[4] Bayer, D. A .; Lagarias, J. C. (1989). „Nelineární geometrie lineárního programování I: Afinní a projektivní trajektorie škálování“ (PDF). Transakce Americké matematické společnosti. 314 (2): 499. doi:10.1090 / S0002-9947-1989-1005525-6.

[lpfe-5] A ^b ^C ^d ^E Vanderbei, Robert J. (2001). Lineární programování: základy a rozšíření. Springer Verlag. 333–347.

[7] Bruin, H .; Fokkink, R.J .; Gu, G .; Roos, C. (2014). „O chaotickém chování algoritmu škálování prima – duální afinita – pro lineární optimalizaci“ (PDF). Chaos. 24 (4): 043132. arXiv:1409.6108. Bibcode:2014Chaos..24d3132B. doi:10.1063/1.4902900. PMID 25554052.

[8] Castillo, Ileana; Barnes, Earl R. (2006). "Chaotické chování algoritmu škálování afinních pro lineární programování". SIAM J. Optim. 11 (3): 781–795. doi:10.1137 / S1052623496314070.

[1]

[2]

[3]

[4]

[5]

[A]

[6]

[7]