[учебник] Основы оптимизации. Новикова (1998) ([учебник] Основы оптимизации. Новикова (1998).pdf), страница 9

tEOREMAkUNA-tAKKERA. pONQTIE O REGULQRNOSTI OGRANI^ENIJ NERAWENSTW WZADA^E mp. mETOD MNOVITELEJ lAGRANVA.1. w \TOM PARAGRAFE BUDEM RASSMATRIWATX ZADA^U USLOWNOJ OPTIMIZACII (1) S X Rn ; X =6 ;, PO PREIMU]ESTWU, S OGRANI^ENIQMI NERAWENSTWAMI (3). kAK UVE OTME^ALOSX, USLOWIE RAWENSTWA NUL@GRADIENTA DLQ TAKIH ZADA^ MOVET NE IMETX NIKAKOGO OTNO[ENIQ KTO^KAM USLOWNOGO \KSTREMUMA. pO\TOMU WYWEDEM SOOTWETSTWU@]IENEOBHODIMYE USLOWIQ DLQ RASSMATRIWAEMOGO SLU^AQ. wNA^ALE ONIBUDUT DANY W DOSTATO^NO OB]EJ FORME, DOPUSKA@]EJ PRIMENENIEDLQ [IROKOGO KLASSA ZADA^ mp (KUSO^NO-GLADKIH I PRI PROIZWOLXNYM OBRAZOM ZADANNYH OGRANI^ENIQH, A TAKVE NE OBQZATELXNO KONE^NOMERNYH). zATEM PROWEDEM KONKRETIZACI@ DLQ OGRANI^ENIJ (3).dLQ OBY^NYH ZADA^ mp (KONE^NOMERNYH, S NEPRERYWNO DIFFERENCIRUEMYMI FUNKCIQMI) SPRAWEDLIWY WSE DALXNEJ[IE POSTROENIQ IWYWODY PRI ZAMENE ZNAKA r OBY^NYM GRADIENTOM.

tAKIM OBRAZOM,OSNOWOJ OBOB]ENIQ QWLQETSQ SLEDU@]EEoPREDELENIE 4. fUNKCIQ f NAZYWAETSQ DIFFERENCIRUEMOJ POaDAMARU W TO^KE x 2 Rn , ESLI SU]ESTWUET WEKTOR rf (x) 2 Rn , TAKOJ^TO 8y 2 Rn WYPOLNENO:f (x + y )lim!(+0;y)0(;y0 )f (x)= hrf (x); yi:dLQ BESKONE^NOMERNYH ZADA^, KOGDA f | FUNKCIONAL: E ! R1 , GDE ENEKOTOROE FUNKCIONALXNOE PROSTRANSTWO, TREBUETSQ: rf (x) 2 E 0 DLQPROSTRANSTWA E 0 , SOPRQVENNOGO K E , I x; y 2 E . w GLADKOM SLU^AErf (x) = gradf (x) I MOVNO POLOVITX y0 TOVDESTWENNO RAWNYM y.46w BEZUSLOWNOJ OPTIMIZACII SU]ESTWENNU@ ROLX IGRALI NAPRAWLENIQ SPUSKA (UBYWANIQ CELEWOJ FUNKCII). w USLOWNOJ OPTIMIZACII,KROME UBYWANIQ CELEWOJ FUNKCII, TREBUETSQ OTSLEVIWATX E]E I NEWYHOD ZA OGRANI^ENIQ.

pO\TOMU WWODITSQ PONQTIE WOZMOVNOGO ILIDOPUSTIMOGO NAPRAWLENIQ W TO^KE x 2 X DLQ MNOVESTWA OGRANI^ENIJ X KAK TAKOGO WEKTORA y, DLQ KOTOROGO 9 0 > 0 : x + y 2 X 8 2[0; 0]. zAMYKANIE MNOVESTWA WSEH DOPUSTIMYH NAPRAWLENIJ W TO^KEx DLQ X DAET SLEDU@]EEoPREDELENIE 5. kONTINGENTNYM KONUSOM K MNOVESTWU X W TO^KE x NAZYWAETSQ MNOVESTWO WEKTOROWK (X; x) =: fyj 9 f(t ; yt )gt1=1 : (t ; yt ) ! (+0; y); x + t yt 2 X 8tg:o^EWIDNO, DLQ x^ 62 X K (X; x^) = ;, A DLQ x0 2 intX K (X; x0 ) =nR .

dLQ x 2 @X W SLU^AE GLADKOJ GRANICY KONUS K (X; x) NAZYWAETSQ TAKVE KONUSOM KASATELXNYH I SOOTWETSTWUET KASATELXNYMNAPRAWLENIQM DLQ OGRANI^ENIJ-RAWENSTW.tEOREMA 1 (OB]IJ WID NEOBHODIMYH USLOWIJ LOKALXNOGO MINIMUMA W ZADA^E (1)). pUSTX FUNKCIQ f DIFFERENCIRUEMA PO aDAMARU,X Rn ; X 6= ;; x0 | TO^KA LOKALXNOGO MINIMUMA f W ZADA^E (1),TOGDA 8y 2 K (X; x0 ) hrf (x0 ); yi 0:dOKAZATELXSTWO. wYBEREM y 2 K (X; x0 ). dLQ SOOTWETSTWU@]IH EMU PO OPREDELENI@ 5 ft ; yt g WYPOLNENO x0 + t yt 2 X , I, NA^INAQ S DOSTATO^NO BOLX[OGO t; x0 + t yt 2 X \ O" (x0 ) (IBO t ! 0),SLEDOWATELXNO, PO OPREDELENI@ 1 f (x0 + t yt ) f (x0 ). w PREDELEPOLU^IMf (x0 + y0 )lim!(+0;y)(;y0 )f (x0 )f (x0 + t yt )= (t;ytlimt)!(+0;y)f (x0 ) 0;I TREBUEMOE SOOTNO[ENIE WYTEKAET IZ OPREDELENIQ 4.sODERVATELXNO DANNYE USLOWIQ OZNA^A@T, ^TO SREDI DOPUSTIMYHNAPRAWLENIJ W TO^KE LOKALXNOGO MINIMUMA NE DOLVNO BYTX NAPRAWLENIJ UBYWANIQ CELEWOJ FUNKCII (SM.

UTWERVDENIE 3 x8). oDNAKO WTAKOM OB]EM WIDE \TIMI USLOWIQMI NEUDOBNO POLXZOWATXSQ.kONKRETIZIRUEM POLU^ENNYE USLOWIQ DLQ OGRANI^ENIJ NERAWENSTW, KOGDA X ZADAETSQ FORMULOJ (3). wWEDEM 8x 2 X MNOVESTWO47INDEKSOW J (x) = fi 2 M j gi (x) = 0g | AKTIWNYH OGRANI^ENIJ W TO^KEx, T.E. TAKIH NERAWENSTW IZ (3), KOTORYE W \TOJ TO^KE WYPOLNENY KAKRAWENSTWA.

i OPREDELIM MNOVESTWO (KONUS)G(x) =: fy 2 Rn j hrgj (x); yi 0 8j 2 J (x)g:oPREDELENIE 6. mNOVESTWO X DLQ OGRANI^ENIJ NERAWENSTW (3)NAZYWAETSQ REGULQRNYM W TO^KE x 2 X , ESLI G(x) K (X; x).tEOREMA 2 (NEOBHODIMYE USLOWIQ LOKALXNOGO MINIMUMA S OGRANI^ENIQMI NERAWENSTWAMI). pUSTX FUNKCII f; gi 8i 2 M DIFFERENCIRUEMY PO aDAMARU, X =6 ;; x0 | TO^KA LOKALXNOGO MINIMUMA fW ZADA^E (1),(3) I MNOVESTWO X REGULQRNO W TO^KE x0 . tOGDA9j 0 : rff (x0 ) +dOKAZATELXSTWO.Xj 2J (x0 )j gj (x0 )g = 0:(5)pO TEOREME 1 I IZ OPREDELENIQ REGULQRNOSTIX W x0 SLEDUET, ^TO hrf (x0 ); yi 0 DLQ WSEH y, UDOWLETWORQ@]IHUSLOWI@ hrgj (x0 ); yi 0 8j 2 J (x0 ).

zNA^IT, PO OPREDELENI@ 3 x7,LINEJNOE NERAWENSTWO hrf (x0 ); yi 0 QWLQETSQ SLEDSTWIEM SISTEMY LINEJNYH NERAWENSTW fhrgj (x0 ); yi 0 8j 2 J (x0 )g. pRIWEDQ\TO NERAWENSTWO K STANDARTNOMU WIDU h rf (x0 ); yi 0 I PRIMENIWAFINNU@ LEMMU fARKA[A (x7), POLU^IM, ^TO9j 0 :rf (x0 ) =Xj 2J (x )0j rgj (x0 ):tAKIM OBRAZOM, DLQ REGULQRNYH OGRANI^ENIJ NEOBHODIMYM USLOWIEM LOKALXNOGO MINIMUMA W GLADKOJ ZADA^E (1),(3) QWLQETSQ RAWENSTWO NUL@ DIFFERENCIALA FUNKCII W FIGURNYH SKOBKAH W (5) DLQHOTX KAKIH-NIBUDX j 0. ~TOBY NE ZAPISYWATX W QWNOM WIDE MNOVESTWO AKTIWNYH OGRANI^ENIJ, WWODQT FUNKCI@ lAGRANVAXL(; x) =: f (x) +j gj (x) =: f (x) + h; g(x0 )ij 2M(REGULQRNOJ) ZADA^I (1),(3), GDE WEKTOR-FUNKCIQ g() =: (gj ()j j 2 M ).iZ TEOREMY 2 SLEDUET, ^TO RAWENSTWO NUL@ DIFFERENCIALA FUNKCII lAGRANVA DLQ j 0 TAKVE QWLQETSQ NEOBHODIMYM USLOWIEM48LOKALXNOGO MINIMUMA W REGULQRNOJ ZADA^E (1),(3), IBO MNOVITELIlAGRANVA j , SOOTWETSTWU@]IE NEAKTIWNYM OGRANI^ENIQM, MOVNOWZQTX RAWNYMI NUL@.

pOSLEDNEE USLOWIE ZAPISYWAETSQ KAK(6)h; g(x0 )i = 0I NAZYWAETSQ USLOWIEM DOPOLNQ@]EJ NEVESTKOSTI. iTAK, DOKAZANAtEOREMA 3 (PRINCIP OPTIMALXNOSTI lAGRANVA). w PREDPOLOVENIQH TEOREMY 2 DLQ ZADA^I (1),(3) SU]ESTWUET NEOTRICATELXNYJWEKTOR MNOVITELEJ lAGRANVA 0, TAKOJ, ^TO DLQ x0 WYPOLNENYUSLOWIQ OPTIMALXNOSTI: rx L(x0 ; ) = 0 I (6).dLQ WYPUKLYH ZADA^ (1),(3) DANNYE NEOBHODIMYE USLOWIQ QWLQ@TSQ W REGULQRNOM SLU^AE I DOSTATO^NYMI, I MOVET BYTX DOKAZANAtEOREMA 4 (kUNA, tAKKERA). eSLI W ZADA^E (1),(3) FUNKCIIf; gj 2 C1 (Rn ) WYPUKLY I MNOVESTWO X REGULQRNO (W L@BOJ TO^KE), TO x | TO^KA OPTIMUMA W \TOJ ZADA^E TOGDA I TOLXKO TOGDA,KOGDA W NEJ WYPOLNENY USLOWIQ OPTIMALXNOSTI DLQ 0.dOKAZATELXSTWO. nEOBHODIMOSTX SLEDUET IZ PREDYDU]IH TEOREM, POKAVEM DOSTATO^NOSTX.

dLQ DANNOGO W TO^KE x WYPOLNENOUSLOWIE \KSTREMALXNOSTI x DLQ FUNKCII L(; ). s U^ETOM NEOTRICATELXNOSTI \TA FUNKCIQ WYPUKLA PO x, ZNA^IT, x QWLQETSQ TO^KOJEE MINIMUMA (SM. UTWERVDENIE 2 x8). oTS@DA I IZ USLOWIQ DOPOLNQ@]EJ NEVESTKOSTIPOLU^IM, ^TO f (x ) = f (x )+h; g(x )i = L(x ; ) :L(x; ) = f (x) + h; g(x)i f (x) 8x 2 X (IBO gj (x) 0 DLQ x, UDOWLETWORQ@]IH OGRANI^ENIQM), ^TO I TREBUETSQ W OPREDELENII (2).aNALOGI^NYE TEOREMAM 2{4 UTWERVDENIQ SPRAWEDLIWY I DLQ SLU^AQ, KOGDA X ZADAETSQ OGRANI^ENIQMI-RAWENSTWAMI, I DLQ SME[ANNYH SISTEM OGRANI^ENIJ RAWENSTW I NERAWENSTW: gj (x) 0; gi (x) = 0.tOLXKO NA SOOTWETSTWU@]IE OGRANI^ENIQM-RAWENSTWAM MNOVITELIlAGRANVA i NE NADO NAKLADYWATX USLOWIQ NEOTRICATELXNOSTI, ANA USLOWIE DOPOLNQ@]EJ NEVESTKOSTI \TI OGRANI^ENIQ NE WLIQ@T(W SLU^AE OGRANI^ENIJ-RAWENSTW WOOB]E OPUSKAEM (6) I PRIHODIM KKLASSI^ESKOMU PRAWILU MNOVITELEJ lAGRANVA).2.

tEPERX WSPOMNIM, ^TO POLU^ENNYE USLOWIQ QWLQ@TSQ ZNA^IMYMI LI[X W PREDPOLOVENII REGULQRNOSTI OGRANI^ENIJ, DLQ KOTOROGOOPREDELENIE 6 NE DAET KONSTRUKTIWNOGO SPOSOBA PROWERKI. w DANNOM49PUNKTE BUDUT RASSMOTRENY NEKOTORYE DOSTATO^NYE USLOWIQ REGULQRNOSTI OGRANI^ENIJ NERAWENSTW (3) DLQ GLADKIH ZADA^.kROME G(x), OPREDELENNOGO W P.1, WWEDEM TAKVE MNOVESTWOG0 (x) =: fy 2 Rn j hrgj (x); yi < 0 8j 2 J (x)g;OTLI^A@]EESQ ZAMENOJ NESTROGOGO NERAWENSTWA STROGIM.

nO \TO MNOVESTWO UVE WKL@^AETSQ W KONTINGENTNYJ KONUS.uTWERVDENIE 5. w PREDPOLOVENII DIFFERENCIRUEMOSTI POaDAMARU (ILI NEPRERYWNOJ DIFFERENCIRUEMOSTI) FUNKCIJ gj , ZADA@]IH OGRANI^ENIQ (3), G0 (x) K (X; x) 8x 2 X .dOKAZATELXSTWO (OT PROTIWNOGO). pUSTX SU]ESTWUET NAPRAWLENIE y 2 G0 (x), NE WHODQ]EE W K (X; x), T.E.

DLQ L@BOJ POSLEDOWATELXNOSTI, FIGURIRU@]EJ W OPREDELENII 5, NAJDETSQ PODPOSLEDOWATELXNOSTX (t ; yt ) ! (+0; y): x + t yt 26 X , SLEDOWATELXNO, 8t 9 INDEKS j ,TAKOJ ^TO gj (x + t yt ) > 0. wOZMOVNYH INDEKSOW | KONE^NOE ^ISLO, ARAZLI^NYH t BESKONE^NO MNOGO, ZNA^IT, NAJDETSQ OGRANI^ENIE, PUSTXi-E, KOTOROE NARU[AETSQ BESKONE^NOE ^ISLO RAZ. rASSMOTRIM SOOTWETSTWU@]U@ PODPOSLEDOWATELXNOSTX ftk g : gi (x+tk ytk ) > 0 I, USTREMLQQ k ! 1, POLU^IM, ^TO gi (x) 0.

nO IZ USLOWIQ x 2 X SPRAWEDLIWOOBRATNOE NERAWENSTWO, OTKUDA SLEDUET RAWENSTWO, T.E. i 2 J (: x). oDNAKO DLQ \TOGO i PO OPREDELENI@ 4 BUDEM IMETX hrgi (x); yi =gi (x + y )=: (;y0)lim!(+0;y)0gi (x)gi (x + tk ytk )= klim!1tkgi (x) 0:pRI[LI K PROTIWORE^I@ S y 2 G0 (x).oTS@DA POLU^AEM SLEDU@]EE USLOWIE REGULQRNOSTI:G(x) = G0 (x):(7)zDESX I DALEE ^ERTA NAD MNOVESTWOM OBOZNA^AET EGO ZAMYKANIE.uTWERVDENIE 6. w SDELANNYH PREDPOLOVENIQH USLOWIE (7) OBESPE^IWAET REGULQRNOSTX X W TO^KE x.dLQ DOKAZATELXSTWA DOSTATO^NO ZAMETITX, ^TO MNOVESTWOK (X; x) QWLQETSQ ZAMKNUTYM, A WKL@^ENIE G0 (x) K (X; x) PRIWODIT K G0 (x) K (X; x) POSLE WZQTIQ OPERACII ZAMYKANIQ.50dOSTATO^NYM DLQ (7) QWLQETSQ6 ;:(8)G0 ( x ) =dOKAZATELXSTWO.

iZ (8) DLQ ALGEBRAI^ESKOJ SUMMY G I G0 SLEDUET: G + G0 G0 , T.E. G + G0 G0 , A G0 0 DAET G + G0 G. iIZ LINEJNOSTI OPERATORA ZAMYKANIQ I ZAMKNUTOSTI G POLU^AEM (7).dLQ WYPUKLYH X WYPOLNENIE (8) I, SLEDOWATELXNO, REGULQRNOSTXTO^KE) OGRANI^ENIJ (3) GARANTIRUETSQ USLOWIEM sL\JTERA(W L@BOJ(9x0 2 X : gi(x0) < 0 8i 2 M ). lINEJNYE OGRANI^ENIQ WSEGDAREGULQRNY (MNOVESTWO G SOWPADAET S KONTINGENTNYM KONUSOM), HOTQUSLOWIE sL\JTERA ILI (8) DLQ NIH MOVET NE WYPOLNQTXSQ.dRUGIE TIPY USLOWIJ REGULQRNOSTI, A TAKVE USLOWIQ REGULQRNOSTI DLQ SME[ANNYH SISTEM OGRANI^ENIJ RAWENSTW I NERAWENSTWSM. W [4{6]. w ^ASTNOSTI, KLASSI^ESKIM USLOWIEM REGULQRNOSTI DLQOGRANI^ENIJ-RAWENSTW QWLQETSQ LINEJNAQ NEZAWISIMOSTX GRADIENTOWOGRANI^ENIJ W \KSTREMALXNOJ TO^KE.uTWERVDENIE7.upravnenie 8.