gradiens módszer. A legegyszerűbb gradiens módszer

Mint már említettük, az optimalizálási probléma a tényezők ilyen értékeinek megtalálásának problémája x 1 = x 1* , x 2 = x 2* , …, xk = xk * , amelyre a válaszfüggvény ( nál nél) szélső értéket ér el nál nél= ext (optimum).

ismert különféle módszerek optimalizálási probléma megoldása. Az egyik legszélesebb körben alkalmazott a gradiens módszer, amelyet Box-Wilson módszernek és meredek emelkedési módszernek is neveznek.

Tekintsük a gradiens módszer lényegét egy kéttényezős válaszfüggvény példáján! y=f(x 1 , X 2 ). ábrán. 4.3 a faktortérben görbék láthatók egyenlő értékeket válaszfüggvények (szintgörbék). Pont koordinátákkal x 1 *, x A 2 * a válaszfüggvény szélső értékének felel meg nál nél ext.

Ha a faktortér bármely pontját választjuk kiindulópontnak ( x 1 0 , x 2 0), akkor a legrövidebb utat a válaszfüggvény tetejére ettől a ponttól a görbe menti út, amelynek érintője minden pontban egybeesik a szintgörbe normáljával, azaz. ez az út a válaszfüggvény gradiensének irányába.

Folytonos egyértékű függvény gradiense y=f(x 1 , X 2) egy vektor, amelyet a gradiens iránya határoz meg koordinátákkal:

ahol én,j egységvektorok a koordinátatengelyek irányában x 1 és x 2. Parciális deriváltak és a vektor irányának jellemzése.

Mivel nem ismerjük a függőség típusát y=f(x 1 , X 2), nem tudjuk megtalálni a parciális deriváltokat és nem tudjuk meghatározni a gradiens valódi irányát.

A gradiens módszer szerint a faktortér valamely részén a kiindulási pont (kezdeti szintek) kerül kiválasztásra x 1 0 , x húsz . Ezekre a kezdeti szintekre tekintettel készül a kísérlet szimmetrikus kétszintű terve. Ráadásul a variációs intervallumot olyan kicsire választjuk, hogy a lineáris modell megfelelő legyen. Ismeretes, hogy egy kellően kis területen bármely görbe közelíthető lineáris modellel.

A szimmetrikus kétszintű terv elkészítése után megoldódik az interpolációs feladat, i.e. építés alatt lineáris modell:

és ellenőrizze annak megfelelőségét.

Ha a lineáris modell megfelelőnek bizonyult a kiválasztott variációs intervallumhoz, akkor a gradiens iránya meghatározható:

Így a válaszfüggvény gradiensének irányát a regressziós együtthatók értékei határozzák meg. Ez azt jelenti, hogy a gradiens irányába fogunk haladni, ha egy koordinátákkal rendelkező pontból ( ) menjen a ponthoz a koordinátákkal:

ahol m- egy pozitív szám, amely a gradiens irányába tett lépések mennyiségét adja meg.

Mert a x 1 0 = 0 és x 2 0 = 0, akkor .

A gradiens irányának () meghatározásával és a lépésméret kiválasztásával m, tapasztalatot végzünk alapvonalx 1 0 , x 2 0 .

Ezután teszünk egy lépést a gradiens irányába, azaz. végezze el a kísérletet egy koordinátákkal rendelkező ponton. Ha a válaszfüggvény értéke nőtt a kezdeti szinten lévő értékéhez képest, akkor újabb lépést teszünk a gradiens irányába, azaz. a kísérletet egy koordinátákkal rendelkező pontban hajtjuk végre:

Tovább haladunk a gradiens mentén, amíg a válaszfüggvény csökkenni nem kezd. ábrán. 4.3 a gradiens mentén történő mozgás a pontból kilépő egyenesnek felel meg ( x 1 0 , x húsz). A válaszfüggvény nemlinearitása miatt fokozatosan eltér a gradiens valódi irányától, amelyet szaggatott vonal mutat.

Amint a válaszfüggvény értéke a következő kísérletben lecsökkent, a gradiens mentén történő mozgást leállítjuk, a válaszfüggvény maximális értékével végzett kísérletet új kezdeti szintnek vesszük, új szimmetrikus kétszintű tervet készítünk. elkészítjük, és az interpolációs probléma ismét megoldódik.

Új lineáris modell felépítése , hajtsa végre regresszió analízis. Ha ugyanakkor a tényezők szignifikancia tesztje azt mutatja, hogy legalább egy együttható

ficient , ami azt jelenti, hogy a válaszfüggvény extrémumának tartományát (az optimum tartományát) még nem érték el. A gradiens új iránya meghatározásra kerül, és megkezdődik a mozgás az optimális tartomány felé.

A gradiens irányának finomítása és a gradiens mentén történő mozgás mindaddig folytatódik, amíg a következő interpolációs feladat megoldása során a faktorok szignifikanciájának ellenőrzése során kiderül, hogy minden tényező jelentéktelen, ti. összes . Ez azt jelenti, hogy elértük az optimális régiót. Ekkor az optimalizálási feladat megoldása leáll, és a válaszfüggvény maximális értékével végzett kísérletet vesszük optimumnak.

NÁL NÉL Általános nézet az optimalizálási feladat gradiens módszerrel történő megoldásához szükséges műveletsort folyamatábra formájában ábrázolhatjuk (4.4. ábra).

1) a tényezők kezdeti szintjei ( xj 0) az optimális ponthoz a lehető legközelebb kell választani, ha van valamilyen előzetes információ a helyzetéről;

2) variációs intervallumok (Δ xj) úgy kell megválasztani, hogy a lineáris modell valószínűleg megfelelő legyen. Alsó szegély Δ xj ebben az esetben a változási intervallum azon minimális értéke, amelynél a válaszfüggvény szignifikáns marad;

3) lépésérték ( t) a gradiens mentén történő mozgás során úgy választják meg őket, hogy a termékek közül a legnagyobb ne haladja meg a felső és a alacsonyabb szintek tényezők normalizált formában

Következésképpen, . Nál nél kisebb érték t a válaszfüggvény közötti különbség a kezdeti szinten és a koordinátákkal ellátott pont között jelentéktelennek bizonyulhat. Nál nél nagyobb értelme lépésnél fennáll a veszély, hogy elcsúszik a válaszfüggvény optimuma.

A módszer a képlet következő iteratív módosításán alapul

x k +1 = x k + a k s(x k),

x k+1 = x k - a k Ñ f(x k), ahol

a - adott pozitív együttható;

Ñ f(x k) - az elsőrendű célfüggvény gradiense.

Hibák:

megfelelő  érték kiválasztásának szükségessége;

lassú konvergencia a minimumponthoz a f(x k) kicsisége miatt ennek a pontnak a közelében.

Legmeredekebb süllyedés módszere

Mentes a legegyszerűbbek első hibájától gradiens módszer, mert a k kiszámítása a Ñ f(x k) minimalizálási feladat megoldásával történik Ñ f(x k) irányban az x k+1 = x k - a k Ñ f(x k) egydimenziós optimalizálási módszerek valamelyikével.

Ezt a módszert néha Cauchy-módszernek is nevezik.

Az algoritmust a gyakorlati problémák megoldásának alacsony konvergencia aránya jellemzi. Ez azzal magyarázható, hogy a változók változása közvetlenül függ a gradiens nagyságától, amely a minimumpont közelében nullára hajlik, és az utolsó iterációknál nincs gyorsító mechanizmus. Ezért, figyelembe véve az algoritmus stabilitását, gyakran a legmeredekebb süllyedés módszerét használják a megoldás megtalálásának kezdeti eljárásaként (a minimális ponttól jelentős távolságra lévő pontokból).

Konjugált iránymódszer

A megkötések nélküli nemlineáris programozás általános problémája a következő: f(x), x E n minimalizálása, ahol f(x) a célfüggvény. A probléma megoldása során olyan minimalizálási módszereket alkalmazunk, amelyek az f(x *)=0 egyenlettel definiált stacionárius f(x) ponthoz vezetnek. A konjugált irány módszer olyan korlátlan minimalizálási módszerekre vonatkozik, amelyek származékokat használnak. Feladat: f(x), x E n minimalizálása, ahol f(x) n független változó célfüggvénye. Fontos tulajdonság gyors konvergencia annak köszönhetően, hogy az irány kiválasztásakor a Hess-mátrixot használják, amely leírja a válaszfelület topológiájának területét. Különösen, ha a célfüggvény másodfokú, akkor a minimumpont legfeljebb annyi lépésben érhető el, amelyek megegyeznek a probléma dimenziójával.

A módszer gyakorlati alkalmazásához ki kell egészíteni az irányrendszer konvergenciáját és lineáris függetlenségét ellenőrző eljárásokkal. Másodrendű módszerek

Newton módszere

A másodfokú közelítési séma egymást követő alkalmazása a Newton-féle optimalizálási módszer megvalósításához vezet a képlet szerint

x k +1 = x k - Ñ 2 f(x k -1) Ñ f(x k).

A Newton-módszer hátránya a nem kellő megbízhatóság a nem másodfokú célfüggvények optimalizálásakor. Ezért gyakran módosítják:

x k +1 = x k - a k Ñ 2 f(x k -1) Ñ f(x k), ahol

a k olyan paraméter, amelyet úgy választunk meg, hogy f(x k+1) min.

2. Egy függvény szélsőértékének megtalálása megkötés nélkül

Valamely f(x) függvény adott az x argumentum változásának nyitott intervallumán (a, c). Feltételezzük, hogy ezen az intervallumon belül létezik exst (el kell mondani, hogy in általános eset ezt nem tudják előre matematikailag kijelenteni; azonban a technikai alkalmazásokban nagyon gyakran az exst jelenléte az argumentum változási intervallumának változási intervallumán belül fizikai megfontolások alapján megjósolható).

Az exst. Az (a, c) intervallumon megadott f (x) függvénynek az x * max (min) pontja van, ha ez a pont körülvehető ilyen intervallummal (x * -ε, x * + ε), amelyet a (a, c) intervallum, amelynek az (x * -ε, x * +ε) intervallumhoz tartozó összes x pontjára a következő egyenlőtlenség teljesül:

f(x) ≤ f(x *) → max

f(x) ≥ f(x *) → min

Ez a definíció nem szab semmiféle korlátozást az f(x) függvényosztályra, ami természetesen nagyon értékes.

Ha az f(x) függvényekre a sima függvények egy meglehetősen gyakori, de még szűkebb osztályára szorítkozunk (a sima függvények alatt olyan függvényeket értünk, amelyek az argumentum változási intervallumán folytonosak származékaikkal együtt), akkor használjuk a Fermat-tételt, amely megadja az exst létezéséhez szükséges feltételeket.

Fermat-tétel. Legyen az f(x) függvény valamilyen (a, b) intervallumban definiálva, és ennek az intervallumnak a "c" pontjában veszi fel a legnagyobb (legkisebb) értéket. Ha ezen a ponton van egy kétoldalú véges derivált, akkor az exst létezése szükséges.

Jegyzet. A kétoldali származékot a tulajdonság jellemzi, más szóval, beszélgetünk arról, hogy a "c" pontban a derivált a határértékben megegyezik a "c" ponthoz balról és jobbról közelítve, azaz f (x) - sima funkció.

* Abban az esetben, ha min történik, és amikor →max. Végül, ha x=x 0-nál, akkor a 2. derivált használata nem segít, és például az exst definícióját kell használni.

Az I. feladat megoldása során nagyon gyakran alkalmazzuk az exst szükséges feltételeket (vagyis a Fermat-tételt).

Ha az exst egyenletnek valós gyökei vannak, akkor az ezeknek a gyökeknek megfelelő pontok az exst szempontjából gyanúsak (de nem feltétlenül maguk a szélsőségek, mert a szükséges és nem a szükséges és elégséges feltételekkel van dolgunk). Tehát például az X inflexiós pontban p játszódik le, de mint tudod, ez nem szélsőség.

Vegyük észre azt is, hogy:

tól től szükséges feltételeket nem lehet megmondani, hogy milyen típusú extrémumot találtak max vagy min: ennek megállapításához további kutatások szükségesek;

A szükséges feltételekből nem lehet eldönteni, hogy globális szélsőségről vagy lokálisról van-e szó.

Ezért, ha az exst szempontjából gyanús pontokat találunk, akkor azokat tovább vizsgáljuk, például az exst definíciója vagy a 2. derivált alapján.

Tekintsük több változóból álló differenciálható függvény feltétel nélküli minimalizálásának problémáját, közelítsük meg a gradiens értékét egy pontban a minimumhoz. Az alábbiakban tárgyalt gradiens módszernél a pontból való süllyedés irányát közvetlenül választjuk, tehát a gradiens módszer szerint

Létezik különböző módokon lépések kiválasztása, amelyek mindegyike a gradiens módszer egy bizonyos változatát határozza meg.

1. A legmeredekebb ereszkedés módja.

Tekintsük egy skalárváltozó függvényét, és válasszuk ki értékül, amelyre az egyenlőséget

Ezt a módszert, amelyet O. Cauchy 1845-ben javasolt, ma a legmeredekebb ereszkedési módszernek nevezik.

ábrán. A 10.5. ábra ennek a módszernek a geometriai illusztrációját mutatja két változó függvényének minimalizálására. A kiindulási ponttól az irányban a szintvonalra merőlegesen az ereszkedést addig folytatjuk, amíg el nem érjük a sugár menti függvény minimális értékét. A talált pontban ez a sugár érinti a szintvonalat, majd a pontból leereszkedünk merőleges az egyenesre szintirány, amíg a megfelelő sugár egy pontban meg nem érinti az ezen a ponton áthaladó szintvonalat stb.

Megjegyezzük, hogy minden iterációnál a lépés megválasztása magában foglalja a (10.23) egydimenziós minimalizálási probléma megoldását. Néha ez a művelet analitikusan elvégezhető, például a másodfokú függvény.

A másodfokú függvény minimalizálására a legmeredekebb süllyedés módszerét alkalmazzuk

szimmetrikus pozitív határozott A mátrixszal.

A (10.8) képlet szerint ebben az esetben tehát a (10.22) képlet így néz ki:

vegye észre, az

Ez a függvény az a paraméter másodfokú függvénye, és olyan értéknél éri el a minimumot, amelynél

Így a kvadratikus minimalizálására alkalmazva

függvény (10.24) szerint a legmeredekebb ereszkedési módszer egyenértékű a (10.25) képlet szerinti számítással, ahol

Megjegyzés 1. Mivel a (10.24) függvény minimumpontja egybeesik a rendszer megoldásával, a legmeredekebb süllyedés módszere (10.25), (10.26) is használható iteratív módszerként lineáris rendszerek megoldására. algebrai egyenletek szimmetrikus pozitív határozott mátrixokkal.

Megjegyzés 2. Vegye figyelembe, hogy hol van a Rayleigh-reláció (lásd a 8.1. szakaszt).

10.1. példa. A másodfokú függvény minimalizálására a legmeredekebb süllyedés módszerét alkalmazzuk

Vegye figyelembe, hogy ezért pontos érték a minimumpontot előre ismerjük. Írjuk fel ezt a funkciót a (10.24) formában, ahol a mátrix és a vektor Mint jól látható,

Vegyük a kezdeti közelítést, és számításokat végzünk a (10.25), (10.26) képletekkel.

I iteráció.

II. iteráció.

Megmutatható, hogy az iteráció során mindegyikre megkapjuk az értékeket

Vegye figyelembe, hogy így

a legmeredekebb süllyedés módszerével kapott sorozat ütemben konvergál geometriai progresszió, melynek nevezője

ábrán. A 10.5 pontosan azt a süllyedési pályát mutatja, amelyet ebben a példában kaptunk.

A másodfokú függvény minimalizálása esetén a következő igaz összesített eredmény.

10.1. Tétel. Legyen A szimmetrikus pozitív határozott mátrix, és legyen a (10.24) másodfokú függvény minimalizálva. Ekkor a kezdeti közelítés bármely választása esetén a legmeredekebb süllyedési módszer (10.25), (10.26) konvergál, és a következő hibabecslés igaz:

Itt és Lado a minimum és maximum sajátértékek mátrixok a.

Megjegyezzük, hogy ez a módszer egy geometriai progresszió sebességével konvergál, aminek a nevezője ráadásul, ha közel vannak, akkor kicsi, és a módszer meglehetősen gyorsan konvergál. Például a 10.1. példában van, és ezért Ha Asch, akkor 1, és számítanunk kell arra, hogy a legmeredekebb ereszkedési módszer lassan konvergál.

Példa 10.2. A legmeredekebb ereszkedés módszerének alkalmazása a másodfokú függvény minimalizálására a kezdeti közelítésnél olyan közelítési sorozatot ad, ahol A süllyedés pályája a 2. ábrán látható. 10.6.

A sorozat itt egy geometriai progresszió sebességével konvergál, aminek a nevezője, azaz sokkal lassabb,

mint az előző példában. Mivel itt a kapott eredmény teljes mértékben megegyezik a becsléssel (10,27).

Megjegyzés 1. Tételünket fogalmaztuk meg a legmeredekebb süllyedés módszerének konvergenciájáról abban az esetben, ha a célfüggvény másodfokú. Általános esetben, ha a minimalizálandó függvény szigorúan konvex és minimum x pontja van, akkor a választástól függetlenül is kezdeti közelítés az ezzel a módszerrel kapott sorozat x-hez konvergál pontban. Ebben az esetben a minimális pont kellően kis környezetébe kerülve a konvergencia lineárissá válik, és a megfelelő geometriai progresszió nevezőjét felülről becsüljük meg az értékkel, ahol mind a minimum, mind a maximum sajátértékek Hess-mátrixok

Megjegyzés 2. A másodfokú célfüggvényhez (10.24) az egydimenziós minimalizálási feladat (10.23) megoldása egyszerű formában megtalálható. explicit képlet(10.26). Azonban a legtöbb más számára nemlineáris függvények ezt nem lehet megtenni, és a legmeredekebb ereszkedés módszerével történő számításhoz alkalmazni kell numerikus módszerek az előző fejezetben tárgyalt típusú egydimenziós minimalizálások.

2. A "szurdokok" problémája.

A fenti tárgyalásból az következik, hogy a gradiens módszer meglehetősen gyorsan konvergál, ha a minimalizált függvény szintfelületei közel vannak a gömbökhöz (amikor a szintvonalak közel vannak a körökhöz). Az ilyen függvényekre és 1. A 10.1. Tétel, az 1. megjegyzés és a 10.2. példa eredménye azt jelzi, hogy a konvergencia sebessége meredeken csökken a . A kétdimenziós esetben a megfelelő felület domborzata a szakadékos terephez hasonlít (10.7. ábra). Ezért az ilyen függvényeket általában víznyelőnek nevezik. A "szurdokfenéket" jellemző irányok mentén a szakadék funkciója elenyészően változik, míg a többi, a "szurdoklejtőt" jellemző irányban éles funkcióváltozás következik be.

Ha a kiindulási pont a "szurdok lejtőjére" esik, akkor a lejtős ereszkedés iránya szinte merőlegesnek bizonyul a "szurdokfenékre", és a következő közelítés a szemközti "szurdoklejtőre" esik. A következő lépés a "szurdokfenék" felé visszaadja az eredeti "szurdoklejtő" megközelítését. Ennek eredményeként a süllyedési pálya ahelyett, hogy a „szurdokfenék” mentén haladna a minimumpont felé, cikk-cakk ugrásokat hajt végre a „szakadékon”, szinte meg sem közelítve a célt (10.7. ábra).

A gradiens módszer konvergenciájának felgyorsítására a szakadékfüggvények minimalizálása mellett számos speciális "szakadék" módszert fejlesztettek ki. Adjunk egy ötletet az egyik legegyszerűbb módszerről. Két közeli kiindulási pontról lejtős ereszkedés történik a "szakadék aljára". A talált pontokon egy egyenes vonalat húzunk, amely mentén egy nagy "szurdok" lépést teszünk (10.8. ábra). Az így talált pontból ismét egy gradiens ereszkedési lépést teszünk a pontig, majd a pontokon áthaladó egyenes mentén megtesszük a második „szurdok” lépést. Ennek eredményeként jelentősen felgyorsul a mozgás a "szurdokfenék" mentén a minimális pontig.

Több részletes információk a "szurdokok" és a "gödör" módszerek problémájáról például a , .

3. Az ereszkedési lépés meghatározásának egyéb megközelítései.

Könnyen érthető, hogy minden iterációnál kívánatos lenne egy olyan süllyedési irányt választani, amely közel van ahhoz az irányhoz, amely mentén a mozgás pontból x pontba vezet. Sajnos az antigradiens (általában sikertelen ereszkedési irány. Ez különösen erős a szakadékfüggvényeknél. Ezért kétséges, hogy célszerű-e alapos megoldást keresni az egydimenziós minimalizálási probléma (10.23) megoldására. és csak olyan lépést kívánnak megtenni abba az irányba, amely a funkció "jelentős csökkenését" biztosítaná. Ráadásul a gyakorlatban néha megelégszik egy olyan érték meghatározásával, amely egyszerűen a cél értékének csökkentését biztosítja funkció.

Gauss-Seidel módszer

A módszer abból áll, hogy felváltva megtaláljuk a célfüggvény részleges szélsőértékét minden egyes tényezőre. Ugyanakkor minden szakaszban a (k-1) tényezők stabilizálódnak, és csak egy i-edik tényező változik

Számítási eljárás: a faktortér lokális régiójában előzetes kísérletek alapján kiválasztunk egy pontot, amely megfelel a legjobb eredmény folyamatot, és onnantól elkezdenek haladni az optimum felé. Az egyes tényezők mozgási lépését a kutató határozza meg. Először az összes tényezőt ugyanazon a szinten rögzítjük, és az egyik tényezőt addig változtatjuk, amíg a válaszfüggvény (Y) növekedése (csökkenése) nem következik be, majd a másik tényezőt megváltoztatjuk, míg a többi stabilizálódik stb., amíg a kívánt eredményt el nem érjük. (Y) . A lényeg az, hogy minden tényezőhöz a megfelelő lépést válasszuk ki.

Ez a módszer a legegyszerűbb, leginkább szemléltető, de az optimum felé való elmozdulás hosszú, és a módszer ritkán vezet az optimumhoz. Jelenleg néha gépkísérletekben használják.

Ezek a módszerek az egyenlő válaszvonalakra merőleges egyenes mentén, azaz a válaszfüggvény gradiensének irányában biztosítják az optimumra való elmozdulást.

A gradiens módszereknek számos változata van, amelyek különböznek a variációs lépések és a munkalépések kiválasztásának szabályaiban a szélső részre irányuló mozgás minden szakaszában.

Valamennyi módszer lényege a következő: kezdetben, előzetes kísérletek alapján, alappont. Ezután minden szakaszban a következő bázispont köré szerveződnek a próbakísérletek, amelyek eredményei értékelik a gradiens új irányát, majd egy munkalépést tesznek ebbe az irányba.

A gradiens módszert (normál) a következő séma szerint hajtják végre:

a) válassz egy alappontot;

b) válasszon mozgáslépéseket minden tényezőhöz;

c) meghatározza a vizsgálati pontok koordinátáit;

d) kísérleteket végezni a vizsgálati pontokon. Ennek eredményeként az optimalizálási paraméter (Y) értékeit minden ponton megkapjuk.

e) a kísérletek eredményei alapján minden i-edik tényezőre kiszámítjuk a gradiensvektor komponenseinek becslését az M pontban:

ahol H i az X i mentén történő mozgás lépése.

X i – az előző munkapont koordinátái.

g) ennek a munkapontnak a koordinátáit veszik új alappontnak, amely körül kísérleti pontokon végeznek kísérleteket. A gradienst kiszámítja, és így tovább, amíg el nem éri a kívánt optimalizálási paramétert (Y). A mozgás irányának korrekciója minden lépés után megtörténik.

A módszer előnyei: egyszerűség, optimális mozgási sebesség.

Hátrányok: nagy zavarérzékenység. Ha a görbe rendelkezik összetett forma, a módszer nem biztos, hogy az optimumhoz vezet. Ha a válaszgörbe lapos, a módszer hatástalan. A módszer nem ad információt a tényezők kölcsönhatásáról.

a) Meredek mászás módszere (Box-Wilson).

b) Döntéshozatal meredek emelkedés után.

ban ben) Simplex módszer optimalizálás.

d) A módszerek előnyei és hátrányai.

5.7.3 Meredek mászás módszere (Box-Wilson)

Ez a módszer egy szintézis Legjobb Jellemzők gradiens módszerek, a Gauss-Seidel módszer és a PFE és DFE módszerek - mint a folyamat matematikai modelljének megszerzésének eszköze. Az optimalizálási feladat megoldása ezzel a módszerrel úgy történik, hogy a léptető mozgás az optimalizálási paraméter leggyorsabb növekedése (csökkenése) irányába történik. A mozgás irányának korrekciója (ellentétben a gradiens módszerekkel) nem minden lépés után, hanem a célfüggvény egy adott extrémumának elérésekor történik. Továbbá egy részleges szélsőség pontjain egy új faktoriális kísérletet állítanak fel, egy újat matematikai modellés ismét a meredek emelkedés ismétlődik a globális optimum eléréséig. A gradiens mentén történő mozgás a nullaponttól (a terv közepétől) indul.

A meredek emelkedési módszer magában foglalja az optimum felé történő elmozdulást egy gradiens mentén.

Ahol i,j,k egységvektorok a megfelelő koordinátatengelyek irányába.

Számítási eljárás.

A kiindulási adat a folyamat bármely módszerrel (PFE, DFE stb.) nyert matematikai modellje.

A számításokat a következő sorrendben végezzük:

a) jobb a regressziós egyenletet természetes alakra fordítani a változó kódolási képletekkel:

ahol x x i változó i -kódolt értéke;

Xi - természeti érték változó x i ;

X i C - a faktor központi szintje in természetbeni;

l i - az x i tényező változási intervalluma természetes formában.

b) számítsa ki a mozgás lépéseit az optimumig minden tényezőhöz!

Ehhez számítsa ki a regressziós egyenlet együtthatóinak szorzatait természetes formában a megfelelő variációs intervallumokkal

B i *.l I ,

Ezután a kapott szorzatokból kiválasztjuk a maximális modulót, és az ennek a szorzatnak megfelelő tényezőt vesszük alaptényezőnek (B a l a). Az alaptényezőnél be kell állítani a mozgási lépést, amelyet ajánlatos az alaptényező variációs intervallumánál kisebbre vagy egyenlőre beállítani

Az l a ’ mozgáslépés előjelének meg kell egyeznie a (B a) alaptényezőnek megfelelő regressziós egyenlet együtthatójának előjelével. A többi tényező lépéseinek értékét az alapérték arányában számítják ki a következő képlet szerint:

A mozgási lépések előjeleinek meg kell egyeznie a regressziós egyenlet megfelelő együtthatóinak előjeleivel is.

c) a válaszfüggvényt a terv közepén számoljuk, azaz a faktorok értékeivel egyenlő a faktorok központi szintjével, mivel az optimum felé való mozgás a terv középpontjából indul ki.

Ezután az optimalizálási paraméter kiszámítása megtörténik, növelve a tényezők értékét a megfelelő mozgási lépés értékével, ha Y max -ot szeretne kapni. NÁL NÉL másképp, ha szükséges Y min elérése, a tényezők értékeit a mozgáslépés értékével csökkentjük.

Az eljárást megismételjük, a lépések számát egymás után növelve, amíg el nem érjük az optimalizálási paraméter kívánt értékét (Y). Az egyes tényezők után g lépések számítanak:

Ha Y®max X i \u003d X i c + gl i ` '

ha Y® min . X i \u003d X i c -gl i`.(5.36)

6. előadás

Gradiens módszerek nemlineáris programozási problémák megoldására.

Kérdések: 1. Általános tulajdonságok mód.

2. Gradiens módszer.

3. A legmeredekebb ereszkedés módja.

4. Frank-Fulf módszer.

5. Büntetés-függvények módszere.

1. A módszerek általános jellemzői.

A gradiens módszerek közelítő (iteratív) módszerek egy nemlineáris programozási probléma megoldására, és lehetővé teszik szinte bármilyen probléma megoldását. Ebben az esetben azonban egy lokális szélsőséget határoznak meg. Ezért célszerű ezeket a módszereket alkalmazni olyan konvex programozási problémák megoldására, amelyekben minden lokális szélsőség egyben globális. A probléma megoldásának folyamata abból áll, hogy valamely x (kezdeti) pontból kiindulva egy szekvenciális átmenet megy végbe a gradF (x) irányba, ha a maximális pontot meghatározzuk, és -gradF (x) (anti -gradiens), ha a minimum pontot meghatároztuk, a pontig, amely a probléma megoldása. Ebben az esetben ez a pont a megengedett értékek tartományán belül és annak határán is lehet.

A gradiens módszerek két osztályra (csoportra) oszthatók. Az első csoportba azok a módszerek tartoznak, amelyekben minden vizsgált pont a megengedett területhez tartozik. Ezek a módszerek a következők: a gradiens módszere, a legmeredekebb süllyedés, a Frank-Wolf stb. A második csoportba azok a módszerek tartoznak, amelyekben a vizsgált pontok nem tartoznak a megengedett területhez. E módszerek közül a legelterjedtebb a büntetőfüggvények módszere. A büntetés-függvények minden módszere különbözik egymástól a „büntetés” meghatározásának módjában.

Az összes gradiens módszerben alkalmazott fő fogalom a függvény gradiensének fogalma, mint a függvény leggyorsabb növekedési iránya.

A megoldás gradiens módszerekkel történő meghatározásakor az iteratív folyamat addig folytatódik, amíg:

Vagy grad F(x*) = 0, (pontos megoldás);

ahol
- két egymást követő pont,
egy kis szám, amely a megoldás pontosságát jellemzi.

2. Gradiens módszer.

Képzelj el egy embert, aki egy szakadék lejtőjén áll, akinek le kell mennie (lefelé). A legtermészetesebbnek, úgy tűnik, a legmeredekebb lejtő felé vezető irány, azaz. irány (-grad F(x)). Az így létrejött stratégia, az ún gradiens módszer, lépések sorozata, amelyek mindegyike két műveletet tartalmaz:

a) az ereszkedés (emelkedés) legnagyobb meredekségének irányának meghatározása;

b) mozogjon a választott irányba valamilyen lépéssel.

A megfelelő lépés kiválasztása elengedhetetlen. Minél kisebb a lépés, annál pontosabb az eredmény, de több számítástechnika. A gradiens módszer különféle módosításai abból állnak, hogy különböző módszereket alkalmaznak a lépés meghatározására. Ha valamelyik lépésben nem csökkent az F(x) értéke, ez azt jelenti, hogy a minimum pontot „kihagytuk”, ebben az esetben vissza kell térni az előző ponthoz, és csökkenteni kell a lépést, például felére.

Megoldási séma.

megengedett területhez tartozó

3. A h lépés megválasztása.

x(k+1) = x(k)

"-" - ha min.

5. F(x (k +1)) és:

Ha egy
, a megoldás megvan;

Megjegyzés. Ha grad F(x (k)) = 0, akkor a megoldás pontos lesz.

Példa. F(x) = -6x 1 + 2x 1 2 – 2x 1 x 2 + 2x 2 2
min,

x1 +x2 2x1 0,x2 0,= 0,1.

3. A legmeredekebb ereszkedés módja.

Ellentétben a gradiens módszerrel, amelyben a gradienst minden lépésben meghatározzák, a legmeredekebb ereszkedési módszernél a gradiens a kiindulópontés a mozgást a talált irányban egyenlő lépésekben folytatjuk, amíg a függvény értéke csökken (növekszik). Ha valamelyik lépésnél F(x) nőtt (csökkent), akkor az ebben az irányban történő mozgás leáll, az utolsó lépést teljesen vagy felére eltávolítjuk, és új gradiens értéket és új irányt számítunk ki.

Megoldási séma.

1. Definíció x 0 \u003d (x 1, x 2, ..., x n),

engedélyezett területhez tartozik,

és F(x 0), k = 0.

2. A gradF(x 0) vagy –gradF(x 0) definíciója.

3. A h lépés megválasztása.

4. A következő pont meghatározása a képlettel

x(k+1) = x(k) h grad F(x (k)), "+" - ha max,

"-" - ha min.

5. F(x (k +1)) és:

Ha egy
, a megoldás megvan;

Ha nem:

a) min keresésekor: - ha F(x (k +1))

Ha F(x (k +1)) >F(x (k)) – ugorjon a 2. pontra;

b) max keresésekor: - ha F(x (k +1)) >F(x (k)) – ugorjon a 4. lépésre;

Ha F(x (k + 1))

Megjegyzések: 1. Ha grad F(x (k)) = 0, akkor a megoldás pontos lesz.

2. A legmeredekebb ereszkedési módszer előnye az egyszerűség és

a számítások csökkentése, mivel a grad F(x) nem minden ponton kerül kiszámításra, ami

nagyszabású problémák esetén fontos.

3. Hátránya, hogy a lépéseknek kicsiknek kell lenniük, hogy ne

hagyja ki az optimális pontot.

Példa. F(x) = 3x1 - 0,2x12 + x 2 - 0,2x22
max,

x 1 + x 2 7x1 0,

x1 + 2x2 10x2 0.

4. Frank-Wolfe módszer.

A módszer egy nemlineáris célfüggvény optimalizálására szolgál lineáris megszorítások mellett. A vizsgált pont közelében a nemlineáris célfüggvényt lineáris függvénnyel helyettesítjük, és a probléma lineáris programozási feladatok szekvenciális megoldására redukálódik.

Megoldási séma.

1. A megengedett területhez tartozó x 0 = (x 1, x 2,…, x n) meghatározás, és F(x 0), k = 0.

2. A grad F(x (k)) definíciója.

3. Hozzon létre egy függvényt

(min - "-"; max - "+").

4. Max(min)f(x) meghatározása kezdeti kényszerek mellett. Legyen ez a z (k) pont.

5. A számítási lépés meghatározása x (k +1) = x (k) + (k) (z (k) –x (k)), ahol (k) – lépés, együttható, 0 1. (k) úgy van megválasztva, hogy az F(x) függvény értéke max (min) legyen az x (k +1) pontban. Ehhez oldja meg az egyenletet
és válassza ki a legkisebb (legnagyobb) gyökeret, de 0 1.

6. F(x (k +1)) meghatározása és további számítások szükségességének ellenőrzése:

Ha egy
vagy grad F(x (k + 1)) = 0, akkor a megoldás megvan;

Ha nem, akkor folytassa a 2. lépéssel.

Példa. F(x) = 4x 1 + 10x 2 – x 1 2 – x 2 2
max,

x1 +x2 4x1 0,

x2 2x2 0.

5. Büntetés-függvények módszere.

Legyen szükséges megtalálni F(x 1 ,x 2 ,…,x n)
max(perc),

g i (x 1 , x 2 ,…, x n) b i , i =
, xj 0, j = .

Az F és g i függvény konvex vagy konkáv.

A büntetőfüggvény módszer ötlete, hogy megtaláljuk az új Q(x) = F(x) + H(x) célfüggvény optimális értékét, amely az eredeti célfüggvény és valamilyen H(x) függvény összege. ) a kényszerrendszer határozza meg, és büntetőfüggvénynek nevezzük. A büntető funkciókat úgy építik fel, hogy biztosítsák a gyors visszatérést a megengedett területre, vagy az onnan való kilépés lehetetlenségét. A büntetőfüggvények módszere a feltételes szélsőérték problémáját egy feltétel nélküli szélsőség feladatsorának megoldására redukálja, ami egyszerűbb. Számos módja van a büntetés-függvény létrehozásának. Leggyakrabban így néz ki:

H(x) =
,