[учебник] Основы оптимизации. Новикова (1998) (1186147), страница 8
Текст из файла (страница 8)
fUNKCIQ f NAZYWAETSQ WYPUKLOJ NA X, ESLI EENADGRAFIK epigrafX f =: f(x; y)j y f (x); x 2 X g | WYPUKLOE MNOVESTWO. fUNKCIQ, WYPUKLAQ NA WSEJ OBLASTI OPREDELENIQ, NAZYWAETSQWYPUKLOJ. mNOVESTWO NAZYWAETSQ WYPUKLYM, ESLI WMESTE S L@BYMI40DWUMQ SWOIMI TO^KAMI ONO SODERVIT OTREZOK, IH SOEDINQ@]IJ.uTWERVDENIE 2. l@BAQ TO^KA LOKALXNOGO MINIMUMA WYPUKLOJFUNKCII QWLQETSQ TO^KOJ EE GLOBALXNOGO MINIMUMA.dOKAZATELXSTWO.
pUSTX f (x0 ) > f (x ). tOGDA f (x0 ) > f (x) DLQWSEH TO^EK x POLUINTERWALA (x0 ; x ] (PO OPREDELENI@ 2), A ZNA^IT, IW NEKOTOROJ OKRESTNOSTI x0 | PROTIWORE^IE S OPREDELENIEM 1. MEdLQ RE[ENIQ ZADA^ WYPUKLOGO PROGRAMMIROWANIQ PRIMENIMTOD \LLIPSOIDOW, PRI^EM W GLADKOM SLU^AE OTSE^ENIE POLU\LLIPSOIDA PROWODITSQ NA OSNOWE GRADIENTA NEWYPOLNENNOGO OGRANI^ENIQW POLNOJ ANALOGII S ALGORITMOM IZ x6.
pO\TOMU ZADA^A POISKA "PRIBLIVENNOGO RE[ENIQ ZADA^I WYPUKLOGO PROGRAMMIROWANIQ OKAZYWAETSQ POLINOMIALXNO RAZRE[IMOJ. dLQ OSTRYH ZADA^ WYPUKLOGOPROGRAMMIROWANIQ | KOGDA FUNKCIQ CELI UBYWAET W OKRESTNOSTIMINIMUMA NE MEDLENNEE NEKOTOROJ LINEJNOJ FUNKCII | MOVNO POLU^ITX I TO^NOE RE[ENIE.2. oB]IMI METODAMI LOKALXNOJ OPTIMIZACII (DLQ PROIZWOLXNOGO, NE OBQZATELXNO WYPUKLOGO, SLU^AQ) QWLQ@TSQ METODY LOKALXNOGOSPUSKA.oPREDELENIE 3. wEKTOR h 2 Rn NAZYWAETSQ NAPRAWLENIEM UBYWANIQ FUNKCII f W TO^KE x, ESLI f (x+h) < f (x) DLQ WSEH DOSTATO^NOMALYH > 0.uTWERVDENIE 3. pUSTX f DIFFERENCIRUEMA W TO^KE x.
tOGDA,ESLI hgradf (x); hi < 0, TO h | NAPRAWLENIE UBYWANIQ FUNKCII f WTO^KE x, A ESLI h | NAPRAWLENIE UBYWANIQ FUNKCII f W TO^KE x, TOhgradf (x); hi 0.dOKAZATELXSTWO. iZ USLOWIQ DIFFERENCIRUEMOSTI f IMEEM DLQDOSTATO^NO MALYH > 0: f (x + h) f (x) = hgradf (x); hi + o() =fhgradf (x); hi + o()=g. o^EWIDNO, POSLEDNQQ DOBAWKA NE IZMENITZNAKA WYRAVENIQ W FIGURNYH SKOBKAH, ESLI SKALQRNOE PROIZWEDENIESTROGO OTRICATELXNO ILI STROGO POLOVITELXNO. oTS@DA AWTOMATI^ESKI WYTEKAET TREBUEMOE UTWERVDENIE.tAKIM OBRAZOM, NAPRAWLENIE LOKALXNOGO UBYWANIQ DIFFERENCIRUEMOJ FUNKCII DOLVNO SOSTAWLQTX OSTRYJ UGOL S EE ANTIGRADIENTOM, KOTORYJ QWLQETSQ W SMYSLE LINEJNOGO PRIBLIVENIQ NAILU^[IMNAPRAWLENIEM UBYWANIQ. dLQ MNEMONIKI PRIWEDEM \PIGRAF K GLAWE,POSWQ]ENNOJ GRADIENTNYM METODAM MINIMIZACII, IZ 1-GO IZDANIQ41KNIGI f.
p. wASILXEWA ~ISLENNYE METODY RE[ENIQ \KSTREMALXNYHZADA^: \wOT KTO-TO S GORO^KI SPUSTILSQ | ANTIGRADIENT!"eSLI gradf (x) = 0, TO x BUDET STACIONARNOJ TO^KOJ. oTMETIM,^TO W USLOWNOJ OPTIMIZACII RAWENSTWO NUL@ GRADIENTA UVE NE QWLQETSQ NEOBHODIMYM USLOWIEM MINIMUMA (SOOTWETSTWU@]IE USLOWIQBUDUT RASSMOTRENY W x9). nO W BOLEE PROSTOM SLU^AE X = Rn MOVNO,DWIGAQSX NEBOLX[IMI [AGAMI W NAPRAWLENII ANTIGRADIENTA FUNKCII f W TEKU]EJ TO^KE, PRIJTI W STACIONARNU@ TO^KU, KAK PRAWILO,LOKALXNOGO MINIMUMA. tAK MY POLU^AEM IDE@ GRADIENTNOGO METODABEZUSLOWNOJ MINIMIZACII, ZADAWAEMOGO ITERATIWNOJ PROCEDUROJxt+1 = xt t gradf (xt ); t = 1; 2; : : : ; 8x1 2 Rn :pARAMETR t NAZYWAETSQ [AGOWYM MNOVITELEM I MOVET WYBIRATXSQ,ISHODQ IZ RAZLI^NYH SOOBRAVENIJ, RAZNYMI SPOSOBAMI.1) pASSIWNYE SPOSOBY | ftg WYBIRAETSQ ZARANEE.pOSTOQNNYJ [AG | t = 0 DLQ DOSTATO^NO MALYH 0 .uBYWA@]IJ[AG (ESLI0 NE IZWESTNO ILI PRI NALI^II POMEH) |PPt # 0;t = 1;2t < 1, NAPRIMER t = 1=t.2) aDAPTIWNYE SPOSOBY | ftg ZAWISIT OT REALIZU@]EJSQfxt g.ttmETOD SKOREJ[EGO SPUSKA | t 2 Arg min>0 f (x gradf (x )):mETOD DROBLENIQ [AGA (DELENIQ POPOLAM) | ESLI f (xt+1 ) > f (xt ), TOWOZWRAT K t-J ITERACII S t := t =2.
(wOZMOVNO I UWELI^ENIE [AGAPRI STABILXNOM UBYWANII f , T.E. PRIBLIVENNYJ SKOREJ[IJ SPUSK.)pRAWILO aRMIHO | PUTEM DROBLENIQ [AGA DOBIWAEMSQ DLQ t WYPOLNENIQ USLOWIQ f (xt t gradf (xt )) f (xt ) "t kgradf (xt )k2 .w OB]EM SLU^AE DIFFERENCIRUEMOJ, OGRANI^ENNOJ SNIZU f MOVNO POLU^ITX SHODIMOSTX GRADIENTNOGO METODA K MNOVESTWU STACIONARNYH TO^EK, A PRI DOPOLNITELXNYH PREDPOLOVENIQH DOKAZYWAETSQ(ZA ISKL@^ENIEM WARIANTA S UBYWA@]IM [AGOM) LINEJNAQ SKOROSTXSHODIMOSTI, KOTORAQ W WYPUKLYH ZADA^AH OZNA^AET kxt+1 x k qkxt x k DLQ NEKOTOROGO 0 < q < 1.
uKAZANNAQ LINEJNAQ OCENKAOB_QSNQETSQ TEM, ^TO W PROCESSE MINIMIZACII GRADIENTNYM METODOMISPOLXZUETSQ LINEJNAQ APPROKSIMACIQ CELEWOJ FUNKCII NA KAVDOM[AGE. bOLEE WYSOKU@ SKOROSTX SHODIMOSTI POLU^A@T DLQ METODOW,OSNOWANNYH NA KWADRATI^NOJ APPROKSIMACII, W PREDPOLOVENII DWAVDY DIFFERENCIRUEMOSTI f . tIPI^NYM PRIMEROM ZDESX QWLQETSQMETOD nX@TONA.42pUSTX f 2 C2 (Rn ), RAZLOVIM FUNKCI@ f W RQD tEJLORA W OKRESTNOSTI TEKU]EJ TO^KI xt :12f (x) f (xt ) = hgradf (xt ); x xt i+ hf 00 (xt )(x xt ); x xt i+o(kx xt k2 ):wYBEREM xt+1 IZ USLOWIQ MINIMIZACII KWADRATI^NOJ APPROKSIMACII f (x) W TO^KE xt , T.E.
KWADRATI^NOJ ^ASTI PRIRA]ENIQ f (x) f (xt ),POLU^IM METOD nX@TONA:xt+1 = xt(f 00(xt)) 1gradf (xt); t = 1; 2; : : : ;GDE NA^ALXNOE PRIBLIVENIE x1 DOLVNO NAHODITXSQ DOSTATO^NO BLIZKO K TO^KE OPTIMUMA x . w TAKOM SLU^AE (I PRI DOPOLNITELXNYHPREDPOLOVENIQH, BOLEE SILXNYH, ^EM DLQ PRIWEDENNOJ RANEE OCENKI SKOROSTI SHODIMOSTI GRADIENTNOGO METODA) DLQ METODA nX@TONABUDET SPRAWEDLIWA KWADRATI^NAQ SKOROSTX SHODIMOSTIkxt+1 x k Qkxt x k2 ; T:E: kxt+1 x k Q1 (Qkx1 x k)2t ;^TO PREDPOLAGAET kx1 x k < 1=Q (OCENKU DLQ Q SM., NAPRIMER,W [5, S. 192]). e]E RAZ POD^ERKNEM, ^TO GRADIENTNYJ METOD W OTLI^IE OT NX@TONOWSKOGO SHODITSQ PRI L@BOM NA^ALXNOM PRIBLIVENII.iZ OPREDELENIQ METODA nX@TONA TAKVE SLEDUET TREBOWANIE NEWYROVDENNOSTI MATRICY WTORYH PROIZWODNYH (GESSIANA) FUNKCII f .nETRUDNO WIDETX, ^TO POLU^ENNAQ FORMULA METODA nX@TONA RE[ENIQ ZADA^ BEZUSLOWNOJ MINIMIZACII SOWPADAET S FORMULOJ METODAnX@TONA RE[ENIQ SISTEMY URAWNENIJ gradf (x) = 0, SOOTWETSTWU@]EJ NEOBHODIMYM USLOWIQM \KSTREMUMA.3: dLQ ZADA^ USLOWNOJ MINIMIZACII; NAPRIMER min x2 ;x2[1;2]PREDLOVENNYE METODY NUVDA@TSQ W MODIFIKACII.
w ^ASTNOSTI, DLQPRIWEDENNOGO PRIMERA, KOGDA MNOVESTWO X IMEET DOSTATO^NO PROSTU@ STRUKTURU, UKAZANNYE WY[E FORMULY SOWME]A@TSQ S PROCEDUROJ PROEKTIROWANIQ NA X NA KAVDOM [AGE METODA. tAK PRIHODIM KMETODU PROEKCII GRADIENTAxt+1 = PrX fxt t gradf (xt )g; t = 1; 2; : : : ; 8x1 2 Rn :43dLQ BOLEE SLOVNYH MNOVESTW X , DOPUSTIM, ZADAWAEMYH OGRANI^ENIQMI NERAWENSTWAMIX =: fx 2 Rn j gi (x) 0 8i 2 M g;(3)UNIWERSALXNYM SPOSOBOM OSWOBOVDENIQ OT OGRANI^ENIJ QWLQETSQ IH[TRAFOWANIE. a IMENNO DLQ DOSTATO^NO BOLX[OJ KONSTANTY C > 0WMESTO ZADA^I USLOWNOJ MINIMIZACII (1),(3) RASSMATRIWA@T ZADA^UBEZUSLOWNOJ MINIMIZACII O[TRAFOWANNOJ CELEWOJ FUNKCIIX+ (x)]p g; GDE X [g + (x)]pminf(x)+C[gfiinx2Ri2Mi2M\TO FUNKCIQ [TRAFA([TRAFNAQ FUNKCIQ) DLQ OGRANI^ENIJ NERAWENSTW, g+ () =: max[0; g()] | SREZKA g, PARAMETR [TRAFA p 1.(dRUGIE WIDY FUNKCIJ [TRAFA SM. W [4,5].) w USLOWIQH NEPRERYWNOSTI FUNKCIJ f; gi , NEPUSTOTY X I OGRANI^ENNOSTI MNOVESTWA lEBEGAFUNKCII f MOVNO DOKAZATX, ^TO S ROSTOM KONSTANTY [TRAFAXlimminf (x) + C [gi+ (x)]p g = f :(4)fnxR2C "1i2M, [TRAFNAQ FUNKCIQeSLI p = 1 (FUNKCIQ-SREZKA I, SLEDOWATELXNOPQWLQETSQ OSTROJ), TO 9C : minff (x)+ C i2M gi+ (x)g = f (SU]ESTWUET TO^NYJ [TRAF).
oDNAKO PRI p > 1 | GLADKIJ [TRAF PODOBNOE RAWENSTWO OZNA^ALO BY NESU]ESTWENNOSTX OGRANI^ENIJ x 2 X(TO^KA BEZUSLOWNOGO MINIMUMA I TAK NAHODITSQW X ).1 (Rn ), WYPUKLY, p > 1 I 9C :f;gCuTWERVDENIE 4. pUSTX2iPxC =: arg minff (x) + C [gi+ (x)]p g 2 X , TOGDAxC 2 Arg xminf (x); T:E: xminf (x) = xminf (x):2X2R n2R ndOKAZATELXSTWO. tAK KAK xC | TO^KA BEZUSLOWNOGO \KSTREMUMADIFFERENCIRUEMOJ FUNKCII, TO GRADIENTO[TRAFOWANNOJ FUNKCIIPCELI W NEJ RAWEN NUL@: gradf (xC )+C p [gi+(xC )]p 1 gradgi (xC ) = 0.nO IZ USLOWIQ xC 2 X WSE WYRAVENIQ W KWADRATNYH SKOBKAH, A ZNA^IT, I WTOROE SLAGAEMOE RAWNY NUL@.
oTS@DA SLEDUET gradf (xC ) = 0,T.E. NEOBHODIMOE USLOWIE \KSTREMALXNOSTI TO^KI xC DLQ ZADA^I BEZUSLOWNOJ OPTIMIZACII, KOTOROE W WYPUKLOM SLU^AE OKAZYWAETSQ I44DOSTATO^NYM (SM. UTWERVDENIE 2). pO\TOMU xC | TO^KA BEZUSLOWNOGO MINIMUMA f . nO xC 2 X , TAK ^TO xC | I TO^KA USLOWNOGOMINIMUMA f NA X , IBO BEZUSLOWNYJ MINIMUM NE PREWY[AET USLOWNOGO. uTWERVDENIE DOKAZANO.tAKIM OBRAZOM, DLQ GLADKOGO [TRAFA NE UDAETSQ SWESTI ZADA^UUSLOWNOJ MINIMIZACII K BEZUSLOWNOJ, TEM NE MENEE FORMULA (4) POZWOLQET ITERATIWNO KOMBINIROWATX METOD [TRAFOW I GRADIENTNYJMETOD W SLEDU@]EJ PROCEDURE: 8x1 2 RnXxt+1 = xt t fgradf (xt )+ Ct p [gi+ (xt )]p 1 gradgi (xt )g; t = 1; 2; : : : ;i 2MKOTORAQ SHODITSQ PRI OPREDELENNYH SOOTNO[ENIQHMEVDU ft g IP2 C 2 < 1 (NAPRIfCt g, W ^ASTNOSTI DLQUBYWA@]EGO[AGAPRIttpMER, t = 1=t; Ct < t).uTWERVDENIE 4 POKAZYWAET, ^TO TRAEKTORII METODA [TRAFA PROHODQT, WOOB]E GOWORQ, WNE MNOVESTWA OGRANI^ENIJ X , HOTQ I SHODQTSQ K DANNOMU MNOVESTWU.
iZ-ZA \TOGO RASSMOTRENNYJ METOD INOGDATAKVE NAZYWA@T METODOM WNE[NIH [TRAFOW W OTLI^IE OT METODOWWNUTRENNEJ TO^KI, ILI BARXEROW. tIPI^NYM PRIMEROM PRIMENENIQMETODA BARXEROW QWLQETSQ OPISANNYJ W x7 METOD kARMARKARA, KOGDAZADA^A (9), \KWIWALENTNAQ ZADA^E USLOWNOJ MINIMIZACIIx0;minx =N p(x);PjSWODITSQ K BEZUSLOWNOJ MINIMIZACII SPECIALXNOJ BARXERNOJ FUNKCII k(x), NE POZWOLQ@]EJ METODU nX@TONA WYJTI ZA OGRANI^ENIQx > 0, ESLI W \TIH OGRANI^ENIQH WYBRANO NA^ALXNOE PRIBLIVENIE.rAZLI^NYE WIDY BARXERNYH FUNKCIJ SM.
W [4,5] | DLQ NIH HARAKTERNO BYSTROE WOZRASTANIE PRI PRIBLIVENII IZNUTRI K GRANICE MNOVESTWA OGRANI^ENIJ (TOGDA KAK [TRAFNAQ FUNKCIQ STREMITSQ K NUL@PRI PRIBLIVENII K MNOVESTWU OGRANI^ENIJ | IZWNE). dLQ RE[ENIQ OB]EJ ZADA^I mp (1),(3) S OGRANI^ENIQMI NERAWENSTWAMI METODU kARMARKARA SOOTWETSTWUET ISPOLXZOWANIE WMESTO RASSMOTRENNOJWY[E [TRAFNOJ FUNKCII, OSNOWANNOJ NA SREZKE, LOGARIFMI^ESKOJBARXERNOJ FUNKCII, RAWNOJ1XC i2Mln[ gi(x)]45PRI gi (x) < 0 8i 2 M I +1 W PROTIWNOM SLU^AE. |TA FUNKCIQ TAKVEPRIBAWLQETSQ K CELEWOJ, I SPRAWEDLIWO SOOTNO[ENIE, ANALOGI^NOE(4).dRUGIE SPOSOBY SWEDENIQ ZADA^ USLOWNOJ OPTIMIZACII K BEZUSLOWNOJ, OSNOWANNYE NA METODE MNOVITELEJ lAGRANVA, BUDUT WYTEKATXIZ REZULXTATOW SLEDU@]EGO PARAGRAFA.x9. dWOJSTWENNOSTX W mpnEOBHODIMYE USLOWIQ LOKALXNOGO MINIMUMA OBOB]ENNO DIFFERENCIRUEMYH FUNKCIJ PRI OGRANI^ENIQH NERAWENSTWAH.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
