Strongin metode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 1. september 2017; checks kræver 2 redigeringer .

Strongins metode er en metode til at løse endimensionelle problemer med betinget Lipschitz-optimering. Giver dig mulighed for at finde en globalt optimal løsning på problemer med ulighedsbegrænsninger, forudsat at den objektive funktion af problemet og de venstre dele af ulighederne opfylder Lipschitz-betingelsen i søgeområdet.

Udtalelse af optimeringsproblemet

Det er nødvendigt at finde et punkt sådan, at . Det antages, at funktionerne og opfylder Lipschitz-betingelsen på intervallet . $x^{*}\in [a;\;b]$ $f(x^{*})=\min \venstre\{f(x)\kolon x\in [a;\;b],\;g_{j}(x)\leqslant 0,\; 1\leqslant j\leqslant m\right\}$ $f(x)$ $g_{j}(x),\;j={\overline {1,\;m))$ $[a;\;b]$

Angiv , så gælder følgende uligheder: $g_{m+1}(x)=f(x)$ $j={\overline {1,\;m+1}}$

|g_{j}(x+\Delta x)-g_{j}(x)|\leqslant L_{j}\Delta x,\;a\leqslant x+\Delta x\leqslant b,

hvor er Lipschitz konstanterne. $L_{j}\geqslant 0$

Beskrivelse af begrænsningsregnskabsordningen

Lad . Den nummererede begrænsning er opfyldt på alle punkter i regionen , hvilket kaldes tilladt for denne begrænsning. I dette tilfælde bestemmes det tilladte område af det oprindelige problem af ligheden: $Q_{0}=[a;\;b]$ $j$ ${\displaystyle Q_{j}=\venstre\{x\in [a;\;b]\colon g_{j}(x)\leqslant 0\right\))$ $Q$

Q=\bigcap _{j=0}^{m}Q_{j}.

Testen på et tidspunkt består i den sekventielle beregning af mængdernes værdier , hvor værdien af indekset bestemmes af betingelserne: $x\in[a;\;b]$ $g_{1}(x),\;\ldots ,\;g_{\nu}(x)$ $\nu$

x\in Q_{j},\;0\leqslant j<\nu ,\;x\notin Q_{\nu }.

Detekteringen af den første overtrådte begrænsning afslutter testen ved punkt . I det tilfælde, hvor punktet er gyldigt, det vil sige, at testen inkluderer beregningen af alle problemets funktioner. I dette tilfælde antages indeksværdien at være lig med . $x$ $x$ $x\in Q$ $\nu=m+1$

Det par , hvor indekset ligger inden for grænserne , kaldes testresultatet på punktet . $\nu =\nu (x),\;z=g_{\nu }(x)$ $\nu$ $1\leqslant \nu \leqslant m+1$ $x$

Denne tilgang til test giver os mulighed for at reducere det oprindelige problem med funktionelle begrænsninger til det ubetingede problem med at minimere en diskontinuerlig funktion:

\psi (x^{*})=\min _{x\in [a;\;b]}\psi (x),

\psi (x)={\begin{cases}g_{\nu}(x)/L_{\nu}&\nu <M,\\(g_{M}(x)-g_{M} ^{*})/L_{M}&\nu =M.\end{cases}}

Her er en . ${\displaystyle M=\max \venstre\{\nu (x)\kolon x\i [a;\;b]\højre\))$ $g_{M}^{*}=\min \left\{g_{M}(x)\colon x\in \bigcap _{i=0}^{M-1}Q_{i}\right \}$

I kraft af definitionen af tallet har problemet med at finde altid en løsning, og hvis , så . $M$ $g_{M}^{*}$ $M=m+1$ $g_{M}^{*}=f(x^{*})$

En funktions buer er Lipschitz på mængder med konstant 1, og den kan selv have diskontinuiteter af den første slags på grænserne af disse mængder. $\psi(x)$ $\bigcap _{i=0}^{j}Q_{i},\;0\leqslant j\leqslant M-1$ $\psi(x)$

På trods af at værdierne af Lipschitz-konstanter og størrelsen ikke er kendt på forhånd, kan de estimeres i processen med at løse problemet. $g_{M}^{*}$

Beskrivelse af metoden

Lad . Endpoint-indekser antages at være nul, og deres værdier er udefinerede. Den første test udføres på punktet . Valget af ethvert efterfølgende testpunkt er underlagt følgende regler: $x^{0}=a,\;x^{1}=b$ $z$ $x^{3}=(a+b)/2$ $x^{k+1},\;k\geqslant 3$

Omnummerer punkterne i de tidligere tests med abonnenter i rækkefølge efter stigende værdier af koordinaten: og sammenlign dem med værdierne . ${\displaystyle x^{0},\;\ldots ,\;x^{k))$ $k$ $a=x_{0}<\ldots <x_{i}<\ldots <x_{k}=b$ $z_{i}=g_{\nu}(x_{i}),\;\nu =\nu (x_{i}),\;i={\overline {1,\;k))$
For hvert heltal skal du bestemme det tilsvarende sæt af sænkede punkter på de punkter, hvor værdierne af funktionerne blev beregnet : $\nu ,\;1\leqslant \nu \leqslant m+1$ ${\displaystyle I_{\nu ))$ $g_{\nu }(x)$ $I_{\nu }=\{i\colon \nu (x_{i})=\nu ,\;1\leqslant i\leqslant k\},\;1\leqslant \nu \leqslant m+1 .$ Bestem også den maksimale værdi af indekset $M=\max\{\nu (x_{i}),\;1\leqslant i\leqslant k\}.$
Beregn aktuelle estimater for ukendte Lipschitz-konstanter: $\mu _{\nu }=\max\{|g_{\nu }(x_{i})-g_{\nu}(x_{j})|/(x_{i}-x_{j })\colon i,\;j\in I_{\nu},\;i>j\}.$ Hvis sættet indeholder mindre end to elementer, eller hvis værdien er lig med nul, skal du acceptere . ${\displaystyle I_{\nu ))$ $\mu _{\nu }$ $\mu _{\nu }=1$
Beregn estimater for alle ikke-tomme sæt $I_{\nu},\;\nu ={\overline {1,\;M))$ $z_{\nu }^{*}={\begin{cases}\min\{g_{\nu}(x_{i})\colon x_{i}\in I_{\nu }\}& \nu =M,\\-\varepsilon _{\nu }&\nu <M,\end{cases}}$ hvor vektoren med ikke-negative koordinater kaldes reservevektoren . $\varepsilon _{R}=(\varepsilon _{1},\;\ldots ,\;\varepsilon _{m})$
Beregn karakteristikken for hvert interval $(x_{i-1};\;x_{i}),\;1\leqslant i\leqslant k$ $R(i)={\begin{cases}\Delta _{i}+{\frac {(z_{i}-z_{i-1})^{2}}{(r_{\nu } \mu _{\nu })^{2}\Delta _{i))}-2{\frac {z_{i}+z_{i-1}-2z_{\nu }^{*}}{r_ {\nu }\mu _{\nu ))}&\nu =\nu (x_{i})=\nu (x_{i-1}),\\2\Delta _{i}-4{\ frac {z_{i-1}-z_{\nu }^{*}}{r_{\nu }\mu _{\nu }}}&\nu =\nu (x_{i-1})>\ nu (x_{i}),\\2\Delta _{i}-4{\frac {z_{i}-z_{\nu }^{*}}{r_{\nu }\mu _{\nu }}}&\nu =\nu (x_{i})>\nu (x_{i-1}),\end{cases}}$ hvor . ${\displaystyle \Delta _{i}=x_{i}-x_{i-1))$ Værdierne er parametrene for algoritmen. De produkter, der bruges til at beregne egenskaberne som estimater af de ukendte Lipschitz-konstanter, afhænger af dem . $r_{\nu }>1,\;\nu ={\overline {1,\;m))$ ${\displaystyle r_{\nu }\mu _{\nu))$
Bestem det interval , som den maksimale karakteristik svarer til . $(x_{t-1};\;x_{t})$ ${\displaystyle R(t)=\max\{R(i),\;1\leqslant i\leqslant k\))$
Udfør endnu en test midt i intervallet, hvis indekserne for dets slutpunkter ikke stemmer overens: $(x_{t-1};\;x_{t})$ $x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1}).$ Ellers test på punktet $x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1})-{\frac {z_{t}-z_{t-1} }{2r_{\nu }\mu _{\nu }}},\;\nu =\nu (x_{t})=\nu (x_{t-1}),$ stige med 1. $k$
Hvis ( er den angivne nøjagtighed af metoden), så stop algoritmen, ellers gå til trin 1. $x_{t}-x_{t-1}<\varepsilon$ $\varepsilon >0$

Tilstrækkelige betingelser for konvergens

Lad det oprindelige optimeringsproblem have en løsning, og følgende betingelser er opfyldt: $x^{*}$

hvert område er en forening af et endeligt antal segmenter med en positiv længde; $Q_{j},\;j={\overline {1,\;m))$
hver funktion opfylder Lipschitz-betingelsen med den tilsvarende konstant ; $g_{j}(x),\;j={\overline {1,\;m+1))$ ${\displaystyle L_{j))$
komponenterne i reservevektoren opfylder ulighederne , hvor er længden af segmentet, der ligger i det tilladte område og indeholder punktet ; $0\leqslant 2\varepsilon _{\nu }<L_{\nu }(\beta -\alpha )$ $\beta-\alfa$ $[\alpha ;\;\beta ]$ $Q$ $x^{*}$
ud fra en eller anden værdi opfylder de mængder, der svarer til ikke-tomme sæt , ulighederne . $k$ $\mu _{\nu }$ ${\displaystyle I_{\nu ))$ ${\displaystyle r_{\nu }\mu _{\nu }>2L_{\nu))$

Så er følgende sandt:

punktet er grænsepunktet for sekvensen genereret af metoden i stoptilstanden; $x^{*}$ $\{x^{k}\}$ $\varepsilon=0$
ethvert grænsepunkt for sekvensen er en løsning på det oprindelige optimeringsproblem; $x^0$ $\{x^{k}\}$
konvergens til grænsepunktet er tosidet, hvis . $x^0$ $x^{0}\neq a,\;x^{0}\neq b$

Metodeændringer

Parallel modifikation

Det generelle skema for den sekventielle metode er som følger:

Sorter punkterne for tidligere tests i stigende rækkefølge efter deres koordinater: . $a=x_{0}<\ldots <x_{i}<\ldots <x_{k}=b$
Beregn karakteristikken for hvert interval . $(x_{i-1};\;x_{i}),\;1\leqslant i\leqslant k$ $R(i)$
Bestem det interval , som den maksimale karakteristik svarer til . $(x_{t-1};\;x_{t})$ ${\displaystyle R(t)=\max\{R(i),\;1\leqslant i\leqslant k\))$
Udfør den næste test på det punkt , hvor reglen er for at placere det næste testpunkt i intervallet med tallet . $x^{k+1}=d(t)\in (x_{t-1};\;x_{t})$ $d(t)$ $t$
Tjek om stopkriteriet er opfyldt . $x_{t}-x_{t-1}<\varepsilon$

Parallel modifikation består i, at i trin 3, i stedet for et interval med den bedste karakteristik, skal du vælge intervaller i faldende rækkefølge af karakteristika og udføre test i hver af dem parallelt. $p>1$

Parallel algoritme skema:

Sorter punkterne for tidligere tests i stigende rækkefølge efter deres koordinater: . $a=x_{0}<\ldots <x_{i}<\ldots <x_{k}=b$
Beregn karakteristikken for hvert interval . $(x_{i-1};\;x_{i}),\;1\leqslant i\leqslant k$ $R(i)$
Sorter karakteristika for intervaller i faldende rækkefølge: . $R(i_{1})>\ldots >R(i_{k})$
For alle intervaller med tal , test på punkter . ${\displaystyle i_{1},\;\ldots ,\;i_{p))$ $x^{k+j}=d(i_{j})\in (x_{i_{j}-1};\;x_{i_{j))),\;j={\overline { 1,\;p}}$
Tjek om stopkriteriet er opfyldt: . $\exists j,\;1\leqslant j\leqslant p\colon x_{i_{j}}-x_{i_{j}-1}<\varepsilon$

En sådan paralleliseringsordning er hensigtsmæssig, hvis testen (det vil sige beregningen af opgavefunktionerne) er en arbejdskrævende proces.

Ændring til løsning af problemer med Hölder-funktioner

Metoden er ganske enkelt generaliseret til det tilfælde, hvor funktionerne opfylder Hölder-betingelsen med eksponenten , hvor , dvs. $g_{j}(x),\;j={\overline {1,\;m+1))$ $1/n$ $n\in \mathbb{N}$

|g_{j}(x+\Delta x)-g_{j}(x)|\leqslant H_{j}(\Delta x)^{1/n},\;a\leqslant x+\Delta x \leqslant b

I trin 3 beregnes værdierne ved hjælp af formlen: $\mu _{\nu }$

\mu _{\nu }=\max\{|g_{\nu }(x_{i})-g_{\nu}(x_{j})|/(x_{i}-x_{j })^{1/n}\colon i,\;j\in I_{\nu},\;i>j\}.

Ved trin 5 . ${\displaystyle \Delta _{i}=(x_{i}-x_{i-1})^{1/n))$

I trin 7, hvis indekserne for endepunkterne stemmer overens

x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1})-\operatørnavn {sgn}(z_{t}-z_{t- 1}){\frac {|z_{t}-z_{t-1}|^{n}}{2r_{\nu }\mu _{\nu }^{n}}},\;\nu = \nu (x_{t})=\nu (x_{t-1}).

Ved trin 8 har stopkriteriet formen . $(x_{t}-x_{t-1})^{1/n}<\varepsilon$

Noter

Parametrene er ansvarlige for metodens pålidelighed. Jo større deres værdier, jo flere iterationer af metoden er nødvendige for at opnå en given nøjagtighed, og jo mere sandsynligt er konvergensbetingelsen 4 opfyldt . ${\displaystyle r_{\nu))$ ${\displaystyle r_{\nu))$ ${\displaystyle R(i)=\Delta _{i))$
Brugen af en ikke-nul reservevektor gør det muligt at accelerere konvergensen af metoden, men i dette tilfælde er det nødvendigt at evaluere muligheden for at opfylde konvergensbetingelsen 3.
Den endimensionelle metode kan anvendes til at løse multidimensionelle problemer uden begrænsninger. Det multidimensionelle problem på sættet er repræsenteret som $S=\{(x_{1},\;\ldots ,\;x_{n})\in \mathbb {R} ^{n}\colon a_{i}\leqslant x_{i}\leqslant b_{i},\;i={\overline {1,\;n}}\}$

\min _{(x_{1},\;\ldots ,\;x_{n})\in S}f(x_{1},\;\ldots ,\;x_{n})=\ min _{a_{1}\leqslant x_{1}\leqslant b_{1}}\min _{a_{2}\leqslant x_{2}\leqslant b_{2}}\ldots \min _{a_{n }\leqslant x_{n}\leqslant b_{n}}f(x_{1},\;\ldots ,\;x_{n}).

For at løse problemet , hvor en-dimensionel algoritme kan bruges, men for at beregne værdien af funktionen , er det nødvendigt at løse dimensionsoptimeringsproblemet . $\min _{a_{1}\leqslant x_{1}\leqslant b_{1}}\phi (x_{1})$ $\phi (x_{1})=\min _{a_{2}\leqslant x_{2}\leqslant b_{2}}\ldots \min _{a_{n}\leqslant x_{n}\ leqslant a_{n}}f(x_{1},\;\ldots ,\;x_{n})$ $\phi (x_{1})$ $n-1$

Hvis , så løses problemet ved en endimensionel metode (værdien af variablen er fast), ellers anvendes dimensionsreduktionsproceduren også på den. Denne metode til at løse multidimensionelle problemer er ret besværlig, derfor er den i praksis anvendelig til . Tilstedeværelsen af ikke-lineære funktionelle begrænsninger kan føre til tab af Lipschitz egenskaber i hjælpe endimensionelle problemer. $n=2$ $\min _{a_{2}\leqslant x_{2}\leqslant b_{2}}f(x_{1},\;x_{2})$ $x_{1}$ $n\leqslant 5$

Litteratur

Barkalov K. A., Strongin R. D. Global optimeringsmetode med adaptiv begrænsningskontrolrækkefølge // Zh. Vychisl. matematik. og mat. fysisk - 2002. - T. 42. - Nr. 9. - s. 1338-1350.
Gorodetsky S. Yu., Grishagin VA Ikke-lineær programmering og multi-ekstrem optimering. - Nizhny Novgorod: Nizhny Novgorod University Press, 2007.
Strongin R. G. Numeriske metoder i multiekstremale problemer (informationsstatistiske algoritmer). - M. : Nauka, 1978. - 240 s.
Sergejev Ja. D., Grishagin VA Sekventielle og parallelle algoritmer til global optimering // Optimization Methods and Software, 3:1-3, 1994, pp. 111-124.
Markin D. L., Strongin R. G. En metode til løsning af multiekstremale problemer med ikke-konvekse begrænsninger ved hjælp af a priori information om de optimale estimater // Zh. Vychisl. matematik. og mat. Fiz., 27:1 (1987), s. 56-62.

Links

[1] - implementering af metoden i C++.
[2] - C++ implementering af ændringen af metodemetoden til løsning af multikriterium multidimensionelle problemer.

Optimeringsmetoder _
Endimensionel	gyldne snit metode Modsætning Parabel metode Netsøgning Ensartet bloksøgningsmetode Fibonacci metode Ternær søgning Piyavsky metode Strongin metode
Nul orden	Gauss metode Nelder-Mead metode Hook-Jeeves metode Rosenbrock metode Powell metode
Første ordre	gradient nedstigning Zeutendijk metode Koordinat nedstigning Konjugeret gradientmetode Kvasi-newtonske metoder Levenberg-Marquardt algoritme
anden orden	Newtons metode Newton-Raphson metode Broyden-Fletcher-Goldfarb-Shanno-algoritme (BFGS)
Stokastisk	Monte Carlo metode Simuleret udglødning Evolutionære algoritmer differentiel evolution Myre-algoritme Partikelsværmmetode Algorithme for bikoloni Tilfældig gå-metode
Lineære programmeringsmetoder _	Enkel metode Gomoris algoritme Ellipsoid metode Potentielle metode
Ikke-lineære programmeringsmetoder	Sekventiel kvadratisk programmering