Broyden-Fletcher-Goldfarb-Shanno módszer

A matematikában a Broyden-Fletcher-Goldfarb-Shanno ( BFGS ) módszer egy módszer egy nemlineáris optimalizálási probléma korlátok nélküli megoldására .

A BFGS módszer olyan megoldás, amelyet gyakran használnak, ha az algoritmust leereszkedési irányokkal kívánja meg .

Ennek a módszernek az az alapgondolata , hogy a különböző egymást követő gradiensek elemzésével elkerülhető legyen a Hessian-mátrix kifejezett felépítése, és ehelyett a minimalizálandó függvény második deriváltjának inverzének közelítése épüljön fel . Ez a közelítés a származékok a függvény vezet egy kvázi-Newton módszer (egy változata a Newton-módszer ), hogy megtalálja a minimális a paraméter térben.

A Hessian-mátrixot nem kell újratervezni az algoritmus minden egyes iterációjánál. A módszer azonban azt feltételezi, hogy a függvény lokálisan megközelíthető egy másodfokú korlátozott kiterjesztéssel az optimum körül.

Alapján

A cél az, hogy minimalizáljuk , és és egy valós értékű differenciálható függvény. f(x){\ displaystyle f (\ mathbf {x})}x∈Rnem{\ displaystyle \ mathbf {x} \ in \ mathbb {R} ^ {n}}f{\ displaystyle f}

Az ereszkedés irányának keresését a szakaszban a következő egyenlet megoldása adja meg, egyenértékű Newton egyenletével: ok{\ displaystyle \ mathrm {p} _ {k}}k{\ displaystyle k}

Bkok=-∇f(xk){\ displaystyle \ mathrm {B} _ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k})}

ahol a Hessian-mátrix közelítése a lépésben , és a grádiens értéke a . Bk{\ displaystyle B_ {k}}k{\ displaystyle k}∇f(xk){\ displaystyle \ nabla f (\ mathbf {x} _ {k})}f{\ displaystyle f}xk{\ displaystyle \ mathrm {x} _ {k}}

Ezután az irányban lineáris keresést használunk a következő pont megtalálásához . ok{\ displaystyle \ mathrm {p} _ {k}}xk+1{\ displaystyle \ mathrm {x} _ {k + 1}}

Ahelyett, hogy a hesseni mátrixhoz hasonlóan kellene kiszámítani a pontot , az iteráció során megközelített hessianust két mátrix hozzáadásával frissítik: Bk+1 {\ displaystyle B_ {k + 1} ~}xk+1{\ displaystyle \ mathrm {x} _ {k + 1}}k{\ displaystyle k}

Bk+1=Bk+Uk+Vk{\ displaystyle \ mathrm {B} _ {k + 1} = \ mathrm {B} _ {k} + \ mathrm {U} _ {k} + \ mathrm {V} _ {k}}

hol és hol vannak az 1. rangú szimmetrikus mátrixok, de eltérő alapokkal rendelkeznek. Egy mátrix akkor és csak akkor szimmetrikus az 1. rangban, ha formába írható , hol van egy oszlopmátrix és egy skalár. Uk{\ displaystyle \ mathrm {U} _ {k}}Vk{\ displaystyle \ mathrm {V} _ {k}}vs.NÁL NÉLNÁL NÉLT{\ displaystyle cAA ^ {T}}NÁL NÉL{\ displaystyle A}vs.{\ displaystyle c}

Ekvivalens módon, és készítsen egy rangsorolási 2. mátrixot, amely robusztus a léptékproblémák szempontjából, amelyek gyakran büntetik a módszerek gradiensét (mint a Broyden (in) módszer , a sokdimenziós analóg a secant módszer ). A frissítés feltételei: Uk{\ displaystyle \ mathrm {U} _ {k}}Vk{\ displaystyle \ mathrm {V} _ {k}} 

Bk+1(xk+1-xk)=∇f(xk+1)-∇f(xk){\ displaystyle \ mathrm {B} _ {k + 1} (\ mathbf {x} _ {k + 1} - \ mathbf {x} _ {k}) = \ nabla f (\ mathbf {x} _ {k +1}) - \ nabla f (\ mathbf {x} _ {k})}.

Algoritmus

Egy kezdeti értékből és egy hozzávetőleges Hessian-mátrixból a következő iterációkat ismételjük, amíg össze nem konvergál a megoldáshoz. x0{\ displaystyle {\ textbf {x}} _ {0}}B0{\ displaystyle \ mathrm {B} _ {0}}x{\ displaystyle {\ textbf {x}}}

1. Keresse megoldása: .ok{\ displaystyle \ mathbf {p} _ {k}}Bkok=-∇f(xk){\ displaystyle \ mathrm {B} _ {k} \ mathbf {p} _ {k} = - \ nabla f (\ mathbf {x} _ {k})}
2. Végezzen lineáris keresést az optimális hangmagasság megtalálásához az 1. részben megadott irányban, majd frissítse .αk{\ displaystyle \ alpha _ {k}}xk+1=xk+αkok=xk+sk{\ displaystyle \ mathbf {x} _ {k + 1} = \ mathbf {x} _ {k} + \ alpha _ {k} \ mathbf {p} _ {k} = \ mathbf {x} _ {k} + \ mathbf {s} _ {k}}
3. yk=∇f(xk+1)-∇f(xk){\ displaystyle \ mathbf {y} _ {k} = \ nabla f (\ mathbf {x} _ {k + 1}) - \ nabla f (\ mathbf {x} _ {k})}.
4. Bk+1=Bk+(ykyk⊤)/(yk⊤sk)-(Bksksk⊤Bk)/(sk⊤Bksk){\ displaystyle \ mathrm {B} _ {k + 1} = \ mathrm {B} _ {k} + (\ mathbf {y} _ {k} \ mathbf {y} _ {k} ^ {\ top}) / (\ mathbf {y} _ {k} ^ {\ top} \ mathbf {s} _ {k}) - (\ mathrm {B} _ {k} \ mathbf {s} _ {k} \ mathbf {s } _ {k} ^ {\ top} \ mathrm {B} _ {k}) / (\ mathbf {s} _ {k} ^ {\ top} \ mathrm {B} _ {k} \ mathbf {s} _ {k})}.

A Funkció az a funkció, amelyet minimalizálni kell. A konvergencia tesztelhető a gradiens norma kiszámításával . A gyakorlatban ezzel inicializálható , és az első iteráció ekvivalens lesz a gradiens algoritmuséval , de a többi iteráció a hesseni közelítésnek köszönhetően egyre jobban finomítja . f(x){\ displaystyle f (\ mathbf {x})}|∇f(xk)|{\ displaystyle \ left | \ nabla f (\ mathbf {x} _ {k}) \ right |}B0{\ displaystyle \ mathrm {B} _ {0}}B0=én{\ displaystyle \ mathrm {B} _ {0} = \ mathrm {I}}B{\ displaystyle \ mathrm {B}}

Mi lehet számítani a megbízhatósági intervalluma a megoldást a fordítottja az utolsó hesseni mátrixban.

Bibliográfia

• CG Broyden , „  A kettős rangú minimalizálási algoritmusok osztályának konvergenciája  ”, Journal of the Institute of Mathematics and Applications , vol.  6,1970, P.  76-90.
• R. Fletcher , „  A változó metrikus algoritmusok új megközelítése  ”, Computer Journal , vol.  13,1970, P.  317-322.
• D. Goldfarb , „  Változó eszközökből származó változó metrikus frissítések családja  ”, Matematika a számításból , vol.  24,1970, P.  23–26.
• DF Shanno , „  A kvázi-newtoni módszerek kondicionálása a funkciók minimalizálására  ”, Matematika a számításból , vol.  24,1970, P.  647-656.
• Mordecai Avriel , Nemlineáris programozás: Elemzések és módszerek , Dover Publishing,2003, 512  p. ( ISBN  0-486-43227-0 , online olvasás ).

Lásd is

• Newton módszere

Hivatkozások

• (fr) Ez a cikk részben vagy egészben venni a Wikipedia cikket angolul című „  BFGS módszer  ” ( lásd a szerzők listáját ) .

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">