1612726871-fb2580394fa55ced84747c959fd39192 (Глебов, Кочетов - Учебное пособие), страница 5
Описание файла
PDF-файл из архива "Глебов, Кочетов - Учебное пособие", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 6 семестр, которые можно найти в файловом архиве НГУ. Не смотря на прямую связь этого архива с НГУ, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
C) + +(!, kxk ; xk qk kxk ; xk* qk ! 0 k ! 1 !!!, kxk ; xk C kxk ; xk C 0:+1+1265* ( !" ) ! !, ! !!)* ! + + ( ,". , ) 8: ) ! !( "( ,", ! *!. P + +, ! * ! ! !.4.1 9 ;f 0 (xk ) !! !(.* !," f (x) ! ! !*!. ! ! !! ! pk !*! ," f (x) xk , + !" " !xk+1 = xk ; k f 0 (xk ) k 0: !" ", + !! - !!- .!* !! !*! (*!) ,",! !8 *! ! !8 * *!! ! .!*! k : C: * ! + ! .!*! k ! !! +. ( ! ! .!*: k =: ( | .!*!. I ! ( !!- .!* !!f (xk ; k f 0(xk )) ; f (xk ) ; k kf 0(xk )k2 * | ! !! !! (0 1). ) + xk xk+1 ," f (xk ; f 0 (xk )) :f (xk ; f 0(xk )):k = arg min0H !(.* !.C8:! ! - ! + ! .!*.66 4.1 (! ! +) . f Rn, f (x) f > ;1 -% f 0(x) :kf 0(x) ; f 0(y)k L kx ; yk % 0 < < 2=L: 5f 0(xk ) ! 0 k ! 1 f (xk+1 ) f (xk ) x0:. ) ,( + !:(f (x + y ) = f (x) +Z10hf 0(x + y) yi d8 . 8: :f (x + y) = f (x) + hf 0(x) y i +Z10hf 0(x + y) ; f 0(x) yi d:C! ! x = xk y = ;f 0 (xk ): D*! !! .
- Q* jha bij kak kbk 1."!f (xk+1 ) f (xk ) + hf 0 (xk ) ;f 0(xk )i++Z10jhf 0(xk ; f 0(xk )) ; f 0(xk ) ;f 0(xk )ijd f (xk ) ; kf 0(xk )k +2+Z10kf 0(xk ; f 0(xk )) ; f 0(xk )kkf 0(xk )kd 67f 0(xk ); kkf 0 (xk )= f (xk )2; kZ1+ Lkf 0 (xk )k kf 0(xk )kd =0kf 0(xk )2+ L2kkf 0(xk )2Z1d =0= f (xk ) ; (1 ; L=2)kf 0(xk )k2 = f (xk ) ; kf 0(xk )k2* = (1 ; L=2): ( , > 0 ,!),f (xk+1 ) f (xk ): *, 8* s !:f (xs+1 ) f (x0 ) ; sXk=0kf 0(xk )k :2/, ! *!) ," f ! - Rn ,! " + !+ :sXk=0kf 0(xk )k (f (x ) ; f (xs20+1))= (f (x0) ; f )=:I! +) 8 *!! f 0(xk ) k !1: D! ! !!.
+ 4.1 *!( ! +) !) ff (xk )g ( -( *!inf x f (x) ( ," f (x) !), !8 f (x) * x = limk!1 xk f 0 (x) = 0 ( !( :). C:8 , *! x ! , ! . D , ! ! *!* ! + !+ !) "( ,". G " + ! -( 4.1 !. C!/ !, *! f (x) | ) ! ,".68&" 4.1 $ f ( l > 0), ( x y Rnf (x + y ) f (x) + hf 0(x) y i + lky k2=2:(4.1) 4.1 f ( - l > 0), Rn .. (4.1) !! . - Q* f (x + y) f (x) ; kf 0(x)kky k + lky k2=2:) r = 2kf 0(x)k=l: P ky k > r, f (x + y ) f (x) + kyk(lkyk=2 ; kf 0(x)k) > f (x):(4.2)0! .! B (x r) " x !! r: (.!! ! ," f *! *! ! .! B (x r) ( x .
!!(4.2) , x | ! Rn : 1! ! !!. 4.2 f ( l > 0) x | , x 2 Rn kf 0(x)k 2l(f (x) ; f (x)):2(4.3). D! ! ," f ) !, !! y = x ; x (4.1) ! 8: !f (x) ; f (x) + hf 0(x) x ; xi + lkx ; xk2=2 0:D! !hp2l + ql=2(x ; x) f 0(x)=p2l + ql=2(x ; x)i =f 0(x)=69pq= kf 0(x)= 2l + l=2(x ; x)k2 0kf 0(x)k =2l + hf 0(x) x ; xi + lkx ; x)k =2 0 f (x) ; f (x) + hf 0(x) x ; xi + lkx ; xk =2:222 + !. 1! ! !!. 4.2 (! ! +) . f Rn, , -% f 0(x) : kf 0(x) ; f 0(y)k L kx ; yk % 0 < < 2=L: 5xk ! x k ! 1 kxk ; xk Cq k 0 q < 1:.
) !, ! !) 4.1:f (xk+1 ) f (xk ) ; (1 ; L=2)kf 0(xk )k2: 4.1 : *!)( x ," f:) (4.3), f (xk+1 ) f (xk ) ; l(2 ; L)(f (xk ) ; f (x)):! + !( !! f (x ), f (xk+1 ) ; f (x) (1 ; l(2 ; L))(f (xk ) ; f (x)):(4.4)I ! q1 /,," !- (f (xk ) ; f (x)):, f (xk+1 ) ; f (x) q1k+1 (f (x0) ; f (x )):(4.5), q1 0: 2" f ) (.L!, ! - ) !( -)70!) !!)8 x0 !, f (x0) > f (x) . !! (4.4) k = 0 0 f (x1 ) ; f (x ) q1 (f (x0) ; f (x ))! !.D! ! q1 < 1 f (xk ) ! f (x): #!, f 0 (x ) = 0 (4.1) !!+ y = xk ; x x = x (f (xk ) ; f (x )) lkxk ; xk2 =2:C!),kxk ; xk 2qk (f (x ) ; f (x))=l:210 ! (8 " + !kxk ; xk Cqk p* C = 2(f (x ) ; f (x ))=l q = pq ! !- +) !) fxk g ( ! x : D!01! !!.4.2 3 5:( -8 ! * !, ) 8:* ! ( ," f (x):H : ! )8! ! . !( '(x) = 0 * ' : Rn !Rn.
) (8 !!"8 ," '(x) xk . ! 8: :'(x) = '(xk ) + '0(xk )(x ; xk ) + o(kx ; xk k) = 0:I!! ( / ! -, (8 !( ) * - xk+1 .71D! ! , )8! ! . !( ! 8:( ,(:xk+1 = xk ; ('0(xk ));1 '(xk ):0! ) !(, *! ," '(x) *! ( ," f (x): 2! ! )8! . ! f 0 (x) = 0 * !:xk+1 = xk ; (f 00(xk ));1 f 0 (xk ): / ! )8! - !) ! ! !!( !!" ," f (x) xk : 4.4 .
f | . f | l, ' :k?f 00(x)]; k l; :11. ) ) ( , 8: , + !:( ," f :f (x + y ) ; f (x) =Z1hf 0(x + ty) yidt = hf 0(x + y) yi =10= hf 0 (x) y i + hf 00(x + 2y )y y i=2* 0 1 2 1: ) )( hf 00(x + y)y yi=2 = f (x + y) ; f (x) ; hf 0(x) yi lkyk =2:22L! y ! ty , :hf 00(x + ty)ty tyi lktyk :2272C!),t2 hf 00(x + 2ty )y y i t2 lkyk2: ! t2 t 8, )hf 00(x)y yi lkyk :2- y = (f 00(x));1z , ) ! .-Q*, lk(f 00(x));1z k kz k 8* z: H !!, k?f 00(x)]; k l; :111! ! !!.) !)) fxk g ! :)8 !)8! ! x | *!)( ," f . -8:! ! !!! !!( + !. 4.3 .
- f ( l > 0), -%kf 00(x) ; f 00(y)k L kx ; yk ( x y 2 Rn q = Lkf 0(x0)k=2l2 < 1: 5 xk ! x k ! 1 < ( kxk ; xk (2l=L)q2k:. ) 8:( ,( -+ !:(:g(x + y) = g(x) + hg 0(x) yi+73Z10(g 0(x + y ) ; g 0(x))d:! g 8 ," f , ! .-Q*, kf 0(x + y) ; f 0(x) ; hf 00(x) yik Lkyk =2:D*! x = xk y = ;?f 00 (xk )]; f 0 (xk ) kf 0(xk )k (L=2)k?f 00(xk )]; k kf 0(xk )k :21+11 22 4.4, kf 0(xk )k (L=2l )kf 0(xk )k :+122 / ! k, + !kf 0(xk )k (2l =L) (L| kf 0(x{z)k=2l})+120k+12 2q:I! ! !), kf 0(xk )k lkxk ; xk:+1+1 4.1 )(- hf 0(x) ; f 0(y) x ; yi lkx ; yk :2D*! ! y = x x = xk+1 ! !f 0(x) = 0 lkxk+1 ; xk2 hf 0 (xk+1 ) x ; xk+1 i kf 0(xk )k kx ; xk k+1+1! !.
D! ! !!.744.3 3 6 "!( - !* ! !! ! /! ! *!( ) ! !. 0! !!min f (x)(4.6)'i (x) 0 i = 1 ::: m(4.7)nx2R (4.8)* f (x) 'i(x) { *! ,". ) 8 *!, - !) ,"! !! (:min y(4.9)f (x) y(4.10)'i(x) 0 i = 1 ::: m(4.11)nx2R (4.12)/ *! : !), f (x) =hc xi: ), ! -, Q = fx j 'i(x) 0 i = 1 : : : mg |- + .( !! (4.6)-(4.8), J (x) = fi j'i(x) = 0g C(!.( p ! - !! -! Q x !( 0 > 0 !, + 2 (0 0) ! x + p !- Q:( p ! ! !! ! -! Q x p - !! /( hc pi < 0:G ,!( x 2 Q ! *!)8 !! (* *!! = min (4.13)hc pi (4.14)0h'i(x) pi + i 2 J (x)(4.15)j pl j 1 + l = 1 : : : n:(4.16)75# (4.16) ! !8 .
( (4.16) (4.14) , "! ," (4.13) *!! ! - + .(. D*! ! . !! (* *!! , !( + !) . (p ) !!(4.13)-(4.16). . p = 0 = 0 . *!)( !! , !, 0:-, < 0: D*! hc pi < 0 h'i0 (x) pi < 0 i 2 J (x): C!), p 6= 0 8* !i 2 J (x) 'i(x + p) = 'i (x + p) ; 'i(x) = h'0i(x) pi++o() ( + o()=) < 0 + ! !+ > 0: P i 62 J (x), ) 'i (x) < 0, ," 'i ! 'i(x + p ) < 0 ) + ! !+ > 0: /!( 0 > 0 !, x + p 2 Q + 2 (0 0) ,!), p - !! -! Q x: !! (4.14) , p !- !! !. C!),f (x + p ) ; f (x) = hc pi < 0:P = 0, ) -!), p -!! !! ! x: !, - ! !), hc pi = 0 '0i (x) = 0 * !i 2 J (x): ! :( !! (* *!! )+ ( ! ! = 0 .) + !.
G !! * *!! (4.6)-(4.8) C(! ! !- ! !).76 4.4 (( !)) . (p ) - % x 2 Q: 5 = 0 , x | % (4.6)-(4.8).. !- !). ) x | -!) . !! (4.6)-(4.8) -, < 0:D*! p 6= 0: 0! x + p ! = 8: ! .P i 2 J (x ), h'0i (x) pi < 0: C!), 'i(x +p ) < 0 + 2 (0 i) ! !* i > 0:P i 62 J (x ), ) 'i (x) < 0, ," 'i (x) ! 'i (x + p ) < 0 +! + 2 (0 i) ! !* i > 0: - = mini=1:::mfi g: D*! 8* 2 (0 ) x + p . !! (4.6)-(4.8). hc pi < 0 f (x + p) < f (x), 2 (0 ) !) x :G!- +). ) x !). !! (4.6)-(4.8).
D*! : x 2 Q, *f (x) ; f (x) = hc x ; xi < 0:) p = x ; x : D*! hc pi < 0. P 'i (x) = 0 )i 2 J (x) 8:* !! *!+ +,"('i (x) 'i (x) + h'0i (x) x ; xih'0i(x) pi 0:(4.17)x C(! :!! p* 'i(x) < 0 i = 1 : : : m: ) =x ;x : P i 2 J (x ) !!* (4.17) h'0i(x) pi < 0:77 p = p + p : D*! ! ! ! hc pi < 0 h'0i (x) pi < 0 i 2 J (x ): I8! !, < 0: D! ! !!.P . (p ) !! (4.13)-(4.16) ! < 0!! !8( , / - !8 + ! -+ !!(. E -!) /+ (, ) - J (x) *! (4.15). I. !+ +, ) 8: - fi j; < 'i(x) 0g * |-) .
G* !,/ - *!( !! (4.6)-(4.8), x 8 ! !! )8 > 0:) 0 > 0 x0 2 Q { !!) -.G, k; - xk 2 Q k > 0: -! J k = J (xk k ) = fi j ;k < 'i(xk ) 0gJ0k = fi j 'i (xk ) = 0g:0! 8:8 !! (* *!!:k = min hc pi 0kh'j (x ) pi + j 2 J k j plkmid 1 + l = 1 : : : n:(4.18)(4.19)(4.20)(4.21)I ! / !! P (xk J k ): ! (!" ! -+ !!(. ) (pk k ) | !) . !! P (xk J k ): 0! !:1) P k ;k , !*! k+1 = k :2) P ;k < k < 0, !*! k+1 = k =2:3) P k = 0 !( .
(pk k ) !! P (xk J0k ). k = 0 xk *! 8 !) 78!) . !! (4.6)-(4.8). P - k < 0 !*!k+1 = k =2 pk = pk :! - !) ., ! k = 0 ) -!), pk !! !. /,. !! P (xk J0k ) ! ! 4.4 - ")!) : - xk : P k < 0 ! !! ! ! pk :G! .!*! k 8:( +. ) ki {!).( -)( ) ! 'i (xk + pk ) = 0:D*! !*! k = mini ki xk+1 = xk + k pk J k+1 = J (xk+1 k+1): 4.5 . 'i(x) { , - 1 Q . 51) ff (xk )g ( f = minx2Q f (x) f (xk ) = hc xki ! f k ! 1B2) x fxk g f (x) ( % Q:.
8 !)) ff (xk )g !!8:! , *! -! Q : f^ = limk f (xk ) f (xk ) ; f (xk+1 )! 0 k ! 1:(4.22)! k ! !- .!* !, ! (. !-, = limk!1 k = 0: - , ) > 0: D*! !( K0 !, k = k ; + k > K0. G* !, !! ! K0 !* *! ! ( !(k = : 8 +:8 !))fxki pki g ! (x p). D!! !)) : 79 *! -! Q (4.21).)J = J (x ) = fj j ; < 'j (x) 0g:D*! K1 > K0 + ki > K1 !; = ;ki < 'j (xki ) 0 j 2 J : H !!, J J ki ! ).+ ki: C!),hc pk i k ;h'0j (xk ) pk i k ; j 2 J :D*! ,"( '0j (x) h'0j (x) pi ; j 2 J : C *( , 'j (x) ; j 62 J : I8! iiiii!, : > 0 !, 'j (x + p ) < 0 + j: C ,"( 'j / !!, 'j (xki + pki ) < 0 ! ).+ ki + j: D!! , 8! , ki > : D*! f (xki ) ; f (xki +1 ) =;ki hc pki i > > 0 (4.22). C!), = 0:!-, f^ = f : ) t1 < t2 < ::: < ti < ::: { ! + !"(, *! + k : ! ;ti < ti 0 , limti !1 ti = 0: -!), xti ! x : ) f^ = f (x) > f : D*! !) , :8 p < 0 !, hc pi h'0j (x) pi j 2 J = fi j 'i(x) = 0g:C *( , !( > 0 : 'j (x ) < ; + j 620J0 : ( ,," ,"( 'j (x) , !( K !(, + ti > Khc pi < =2h'0j (xt ) pi < =2 + j 2 J i080(4.23)(4.24)'j (xti ) < ; + j 62 J0 :(4.25) *, + 0 !) fk g ! ; ;ti ! ).+ ti : * !! !! (4.25) J ti J0 + ti).+ * K1 > K: I8!, ! (4.23),(4.24) ! p !hc pi < =2h'0j (xt ) pi < =2 + j 2 J t kpl k 1 + l = 1 : : : n:iD! ! ,iti < =2 < 0 8* ti > K1 + !) fti g 8.