最优化理论与算法

8¹

3Ã å`z3.1 `5^ .....................................3.2 { Ú½9Âñ5.............................3.3 eü{.....................................3.4Úî{.......................................3.5[Úî{......................................3.6

ÝFÝ{.....................................

11412152227

8¹·ii·

1nÙÃ å`z

â1 Ü© {nØÐÚ §3¦) 55y¯K L§¥§· I (½|¢ Ú|¢Ú "(½,:÷X, £ÄÚ ¡ ‘|¢ {"ØÓ |¢ (½ ØÓ {"

§3.1 `5^

x∈Rn

!ïÄà å¯K

minf(x),

(3.1.1)

`5^ ,§ ) ^ Ú ^ .

4 : a.kÛÜ4 :Ú Û4 :ü«.

AT Ñ,¢Sþ 1 ´¦ ÛÜ(½î ÛÜ)4 :, Û4 :. 5`¦ Û4 :´ (J ?Ö.3éõ¢SA^¥,¦ÛÜ4 :®÷v ¯K ¦.Ïd,± ¦4 :,Ï~´ ¦ÛÜ4 :.= ¯Käk,«à5 ,ÛÜ4 :â´ Û4 :.

f êÚ ê 3,…©OL«

g(x)= f(x),

!eü

½Â3.1.1 x,d∈Rn.e 3~êα¯>0¦

f(x+αd)<f(x),

α∈(0,α¯),G(x)= 2f(x).

K¡d´f3x:? eü "e d´f3x? eü §K¡d´f3x:? þ, "

eü Aۿµ :lx?Ñu§÷ d£Ä §f üN4~"e-φ(α)=f(x+αd),

Kd´f3x? eü duφ3 :?üNeü§ φ (0)<0"l k½n3.1.1 fëY … f(x)=0.

£1¤ed÷v f(x)Td<0§K§´f3x? eü "

£2¤eÝ H∈Rn×né¡ ½§K þd= H f(x)´f3x? eü "AO §d= f(x)´f3x? eü "

y²£2¤´£1¤ AÏ /§ y£1¤" f(x)Td<0"dTaylorЪ§ α>0¿© §

f(x+αd)=f(x)+α f(x)Td+o(α)<f(x),=d´f3x? eü "

n=1 §ex ´¯K(3.1.1) )§Kf (x )=0…f (x )≥0., ¡§ex ÷vf (x )=0,f (x )>0§Kx ´¯K(3.1.1) î ÛÜ4 :"þã^ í2 n>1 /"

!7 ^

½n3.1.2( 7 ^ ) f:D Rn→R3m8DþëY .ex ∈D´(3.1.1) ÛÜ4 :,K

f(x )=0.(3.1.2)y² x ´ ÛÜ4 :, ÄS

x(k)=x αk f(x ).

|^TaylorЪ,éu¿© k,k

0≤f(x(k)) f(x )= αk f(x )T f(ηk),

Ù¥ηk´x(k)Úx à|Ü.ü>Óرαk,¿ 4 .duf∈C1, k

0≤ f(x ) 2.

w,,= f(x )=0 ,þª¤á.

½n3.1.3( 7 ^ ) f:D Rn→R3m8Dþ ëY ,ex ∈D´(3.1.1)

ÛÜ4 :,K

f(x )=0, 2f(x ) 0,(3.1.3)y² (3.1.3)¥1 ª3½n3.1.2¥®²y², Ly²1 ª. ÄS x(k)=x +αkd,

d?¿.duf∈C2Ú f(x )=0, dTaylorЪ,éu¿© k,k

0≤f(x(k)) f(x )=

12T2

αd f(ηk)d,2k

12

α,¿ 42k

Ù¥ηk´x(k)Úx à|Ü.dux ´ÛÜ4 :,f∈C2,Kþªü>Óر ,

dT 2f(x )d≥0,

l (2.1.3)1 ª .

d∈Rn.

÷v f(x )=0 :x ¡ ¼êf -½:½7:.XJ f(x )=0,Kx U´4 :, U´4 :, UØ´4 :.QØ´4 : Ø´4 : -½: ‰¼ê Q:.Xx =0 f(x)=x2 4 :§ Ø´f(x)=x3 4 :"

n!¿©^

½n3.1.4( ¿©^ ) f:D Rn→R3m8Dþ ëY ,Kx ∈D´f î ÛÜ4 : ¿©^ ´

f(x )=0… 2f(x ) 0.(3.1.4)y² (3.1.4)¤á,KdTaylorЪ,é?¿ þd,

1

f(x +εd)=f(x )+ε2dT 2f(x +θεd)d.

2

du 2f(x ) ½,f∈C2, ÀJε,¦ x +εd∈Nδ(x ),l dT 2f(x +θεd)d>0,ù

f(x +εd)>f(x ),

=x ´î ÛÜ4 :.

4

5µ½n3.1.4 ^ Ø´7 ^ "~X§x =(0,0)T´f(x)=x41+x2 î ÛÜ4 :§ 2f(x )Ø ½"

~3.1.5|^4 ^ ¦)¯K

minf(x)=

) O µ

f(x)=

x21 2x1x22 1

,

2f(x)=

2x1 20

02x2

.

1313

x1+x2 x21 x2.33

d f(x)=0 -½:µ

0022

x(1)=,x(2)=,x(3)=,x(4)=,

1 11 1q

2f(x(3))=

x(3) 4 :"

/,8I¼ê -½:Ø ½´4 :. e8I¼ê´à¼ê,KÙ-½:Ò´Ù4

:,… Û4 :.

½n3.1.6(à¿©5½n) f:Rn→R´ëY à¼ê.Kf ÛÜ4 : ´Ù Û4 :"…x ´¯K(3.1.1) ) ¿©7 ^ ´ f(x )=0.

2002

,

y² kyf ÛÜ4 : ´ Û :" x ´f ÛÜ4 :§K 3x + U(x )¦

f(x)≥f(x ), x∈U(x ).é?¿x∈Rn§ α>0¿© §x +α(x x )∈U(x ).df à5

f(x )≤f(x +α(x x ))≤αf(x)+(1 α)f(x ).

f(x )≤f(x)§=x ´f Û4 :"

eyx ´¯K(3.1.1) ) ¿ ^ ´ f(x )=0.Ï f´Rnþ à¼ê, f(x )=0, k

f(x) f(x )≥ f(x )(x x )=0, x∈D.ùL²x ´D¥f Û4 :.

§3.2 { Ú½9Âñ5

à å`z eü { Ä g µl, Щ:x(0)Ñu§ E: {x(k)}¦ f(xk+1)<f(x(k)),k=0,1,···. { 8I´: {x(k)}¥ , :½, 4 :´¯K(3.1.1) )½-½:"

!eü {

d(k)´f3x(k)? eü §

f(x(k))Td(k)<0.

K α>0¿© §f(x(k)+αd(k))<f(x(k)).Ïd x(k+1)=x(k)+αkd(k)§Ù¥αk>0¦ f(x(k)+αkd(k))<f(x(k)).

{3.2.1Ú1.‰½Ð©:x(0)∈Rn§°Ýε≥0"-k=0"

Ú2.e f(x(k)) ≤ε§Ê § )x(k)"ÄK=Ú3"Ú3.(½eü d(k)§¦

f(x(k))Td(k)<0.

Ú4.(½Ú αk>0§¦

f(x(k)+αkd(k))<f(x(k)).

Ú5.-x(k+1)=x(k)+αkd(k),k:=k+1§=Ú2"

5µÚ2¥ Ø ª f(x(k)) ≤ε { ª OK§Ù¥°Ýε â¢S¯K I (½" 3nØ©Û §þ ε=0"Ú4¥ αk¡ Ú "(½Ú ~^ {´ ‘ 5|¢"

! ‘|¢

‘|¢kü« ª§°( |¢Ú °( |¢"°( |¢ÏL¦) ‘ `z¯K

minf(x(k)+αd(k)) φ(α)

α>0

(3.2.1)

Ú αk§Kk

f(x(k)+αkd(k))Td(k)=0.

= αk=argminφ(α)=f(x(k)+αd(k))§ù αk¡ `Ú "ù« {Ø=U y÷veü^ § …3d þ¦eüþD=f(x(k)) f(x(k)+αkd(k)) § I O þ"Ù¢§3¢SO L§¥§duO Åi ÚO Ø Ï§nØþ `Ú ´¦Ø § ´ Cq `)"

éu g¼ê4 z¯K

minf(x)=

1T

xQx+qTx,2

α>0(k)

Ù¥Q∈Rn×né¡ ½" d(k) f3x(k)? eü §…÷v f(x(k))Td(k)<0"-φ(α)=f(x(k)+αd(k))

1

=(x(k)+αd(k))TQ(x(k)+αd(k))+qT(x(k)+αd(k))21

=α2d(k)TQd(k)+α f(x(k))Td(k)+f(x(k)),2

Kdφ (α)=0 `Ú

f(x(k))Td(k)

αk= .

dQd

(3.2.2)

°( |¢(½ Ú αk I÷vf(x(k)+αkd(k)) f(x(k))k ½§Ý eü= "=

αk>0§¦eüþD=f(x(k)) f(x(k+1)) É þ§ù αk¡ ÉÚ "ù« {Ø= y÷veü^ § … I O þ"¢ L²§ù« ‘|¢ { éÐ ê O J"

£ ¤°( |¢¨‘7© {£0.618{¤

‘7© {´(½°( |¢Ú « {§§·^u¦ ü¸¼ê 4 ¯K"kÚ?ü «m Vg"

½Â3.2.1 :[a,b]→R"e 3t ∈[a,b]§¦ (t)3[a,t ]þî 4~§3[t ,b]þî 4O§K¡[a,b]´ (t) ü «m"

w, (t)3Ùü «mþk 4 :t "y3y²ü «m ~k^ 5 "½n3.2.2 [a,b]´ (t) ü «m§λ,µ∈[a,b]§λ<µ"

£1¤e (λ)≤ (µ)§K[a,µ]´ (t) ü «m£2¤e (λ)> (µ)§K[λ,b]´ (t) ü «m"

y² t ´ (t)3[a,b] 4 :"

£1¤d[a,b]´ (t) ü «m § Iy²t ≤µ"^ y{§b t >µ§K â[a,b]´ (t) ü «mÚλ<µ (λ)> (µ)§ ^ gñ"Ïd§t ≤µ"

£2¤Ón y"

½n3.2.2 ¿Â3u§ÏL' (t)3ü ØÓ:? ¼ê § òü «mÅÚ "‘7© {Ò´|^ ù 5 "

y3 Ä ‘|¢¯K

minφ(t)s.t.t∈[a,b]

Ù¥[a,b]´φ(t) ü «m§K 3 t ∈[a,b]§¦t ´(3.2.3) `)"

‘7© { g ´µÏL' cü «m¥ ü é¡ Á&:? 8I¼ê §±, ½'~ ü «m§¿¦ # Á&:" ü «m ½§Ý §«m¥ :Ñ (3.2.3) Cq `)"

[ai,bi]´ cü «m§λi,µi∈(ai,bi)´ cÁ&:§λi<µi§¿…λiÚµi'u[ai,bi]顧=

λi ai=bi µi

' (λi)Ú (µi) " â½n3.2.2§

¹1µe (λi)≤ (µi)§K[ai,µi]´ (t) ü «m§ -ai+1=ai,

bi+1=µi

(3.2.5)(3.2.4)(3.2.3)

¹2µe (λi)> (µi)§K[λi,bi]´ (t) ü «m§ -ai+1=λi,

Ó § ¦÷v^

£1¤ü «m± ½'~α∈(0,1) §=

bi+1 ai+1=α(bi ai);

£2¤ ¹1e λi½ ¹2e µi [ai+1,bi+1] ü é¡ Á&: "3 ¹1e§k Ä^ £1¤"d(3.2.6)Ú(3.2.5)§¿“\(3.2.4)

λi=ai+(1 α)(bi ai),

2 Ä^ £2¤"d(3.2.7)!(3.2.5)Ú(3.2.6)§

λi+1=ai+1+(1 α)(bi+1 ai+1)=ai+α(1 α)(bi ai),

(3.2.8)

µi=ai+α(bi ai).

(3.2.7)(3.2.6)

bi+1=bi

µi+1=ai+1+α(bi+1 ai+1)=ai+α2(bi ai),

(3.2.9)

' (3.2.8)Ú(3.2.7)§âα∈(0,1) λi+1Ø U λi § kµi+1=λi§dd α2=1 α§=

√

1α=≈0.6180339887418948.(3.2.10)

23 ¹2e§Ó λi+1=µiÚ(3.2.10)"

√

1

· ¡α= ‘7© X꧑7© {Ò´|^‘7© Xêéü «m?1

2

{"e¡‰Ñ‘7© { äNS“Ú½" {3.2.3£‘7© {¤

Ú1.À½Ð©êâ"‰½Ð©ü «m[a,b]§°Ýëêε>0§‘7© Xêα"eb a≤

=(b+a)/2§ÄK=2"ε§Ê § t

Ú2.Щz"-[a0,b0]=[a,b]§λ0=a0+(1 α)(b0 a0)§µ0=a0+α(b0 a0)§

¦ (λ0)Ú (µ0)"-i=0§=3"

Ú3.' 8I "e (λi)≤ (µi)§=4§ÄK=5"

Ú4. |¢"-ai+1=ai§bi+1=µi§µi+1=λi§ (µi+1)= (λi)§λi+1=ai+1+(bi+1 µi+1)§¦ (λi+1)§=6"

Ú5. m|¢"-ai+1=λi§bi+1=bi§λi+1=µi§ (λi+1)= (µi)§µi+1=bi+1 (λi+1 ai+1)§¦ (µi+1)§=6"

=(bi+1 ai+1)/2§ÄK=7"Ú6.ª O"ebi+1 ai+1≤ε§Ê § t

Ú7.-#m© O"eλi+1<µi+1§Ki=i+1§=3"ÄKa=ai+1§b=bi+1§=2"~3.2.4^‘7© {¦ ‘`z¯K

t∈[0,3]

mint3 t+1

`)"

£ ¤ °( |¢

°( |¢ 8 ´ ¼ `Ú §§ I O þ" °( |¢ 8

K´¦ ¦8I¼ê ½eüþ )§= ÉÚ §§ I O þ"

°( |¢Ò´¦ ‘|¢¯K

minφ(t)s.t.t∈[a,b]

(3.2.11)

§Ù¥φ(t)=f(x(k)+td(k))§x(k)´S“:§d(k)´¯K(3.1.1)3x(k)? |¢ É)t

§K# S“:x(k+1)=x(k)+tkd(k)§e §φ (0)= f(x(k))Td(k)<0"- ÉÚ tk=t

üþ

).D=f(x(k)) f(x(k)+tkd(k))=φ(0) φ(t

e¡0 ü« °( |¢ {"1!Armijo. |¢

d(k)´f3x(k)? eü §÷v f(x(k))Td(k)<0"Armijo. |¢µ‰½σ1∈(0,1)§ αk>0§¦

f(x(k)+αkd(k))≤f(x(k))+σ1αk f(x(k))Td(k),

=

φ(αk)≤φ(0)+σ1αkφ (0).

(3.2.12)

´ §(3.2.12)é¿© αkþ¤á"Ï~F"αk¦ U " β>0,ρ∈(0,1)" αk 8Ü{βρi,i=0,1,···}¥¦ (3.2.12)¤á " {3.2.5£Armijo. |¢¤

Ú1.eαk=1÷v(3.2.12)§K αk=1"ÄK=Ú2"Ú2.‰½~êβ>0,ρ∈(0,1)"-αk=β"

Ú3.eα÷v(3.2.12)§Kª O §¿ Ú αk"ÄK=Ú4"Ú4.-αk:=ραk§=Ú3"

5µ£1¤ü Ú αk=1´é- Ú §§3 { Âñ Ý©Û¥å ©- ^"£2¤Á&ÚU'~ρ §eρ∈(0,1) §K ügÁ&Ú UC §I õg|¢âU αk"eρ∈(0,1) §K ügÁ&Ú UC é §d ²L é |¢Ò αk§ αk Ué "~3.2.6 Äà å¯K

minf(x)=

12

x1+x22.2

x(0)=(1,1)T" yd(0)=(1, 1)T f3x(0)? eü "¿^Armijo |¢(½Ú α0=

0.5i§¦

f(x(0)+α0d(0))≤f(x(0))+0.9α0 f(x(0))Td(0).

2!Wolfe–Powell. |¢

ÑArmijo. |¢ "

本文来源：https://www.bwwdw.com/article/6ci4.html