Metoda Strongin

Versiunea actuală a paginii nu a fost încă revizuită de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 1 septembrie 2017; verificările necesită 2 modificări .

Metoda lui Strongin este o metodă de rezolvare a problemelor unidimensionale ale optimizării Lipschitz condiționate. Vă permite să găsiți o soluție optimă la nivel global în problemele cu constrângeri de inegalitate, cu condiția ca funcția obiectivă a problemei și părțile din stânga ale inegalităților să satisfacă condiția Lipschitz din zona de căutare.

Enunțul problemei de optimizare

Este necesar să se găsească un punct astfel încât . Se presupune că funcțiile și satisfac condiția Lipschitz pe intervalul . $x^{*}\in [a;\;b]$ $f(x^{*})=\min \left\{f(x)\colon 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]$

Notați , atunci pentru următoarele inegalități sunt valabile: $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,

unde sunt constantele Lipschitz. $L_{j}\geqslant 0$

Descrierea schemei contabile de constrângeri

Lasă . Constrângerea numerotată este satisfăcută în toate punctele din regiunea , care se numește admisibilă pentru această constrângere. În acest caz, aria admisibilă a problemei inițiale este determinată de egalitatea: $Q_{0}=[a;\;b]$ $j$ $Q_{j}=\left\{x\in [a;\;b]\colon g_{j}(x)\leqslant 0\right\)$ $Q$

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

Testul la un punct constă în calculul secvenţial al valorilor cantităţilor , unde valoarea indicelui este determinată de condiţiile: $x\in[a;\;b]$ $g_{1}(x),\;\ldots ,\;g_{\nu }(x)$ $\nu$

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

Detectarea primei constrângeri încălcate încheie testul la punctul . În cazul în care punctul este valid, adică testul include calculul tuturor funcțiilor problemei. În acest caz, se presupune că valoarea indexului este egală cu . $X$ $X$ $x\in Q$ $\nu=m+1$

Perechea în care se află indicele în limite se numește rezultatul testului în punctul . $\nu =\nu (x),\;z=g_{\nu }(x)$ $\nu$ $1\leqslant \nu \leqslant m+1$ $X$

Această abordare a testării ne permite să reducem problema inițială cu constrângeri funcționale la problema necondiționată a minimizării unei funcții discontinue:

\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}}

Aici , un . $M=\max \left\{\nu (x)\colon x\in [a;\;b]\right\)$ $g_{M}^{*}=\min \left\{g_{M}(x)\colon x\in \bigcap _{i=0}^{M-1}Q_{i}\right \}$

În virtutea definiției numărului , problema găsirii are întotdeauna o soluție, iar dacă , atunci . $M$ $g_{M}^{*}$ $M=m+1$ $g_{M}^{*}=f(x^{*})$

Arcele unei funcții sunt Lipschitz pe mulțimi cu constantă 1 și poate avea ea însăși discontinuități de primul fel pe limitele acestor mulțimi. $\psi(x)$ $\bigcap _{i=0}^{j}Q_{i},\;0\leqslant j\leqslant M-1$ $\psi(x)$

În ciuda faptului că valorile constantelor Lipschitz și magnitudinea nu sunt cunoscute în avans, acestea pot fi estimate în procesul de rezolvare a problemei. $g_{M}^{*}$

Descrierea metodei

Lasă . Se presupune că indicii punctelor finale sunt nuli, iar valorile lor sunt nedefinite. Primul test se efectuează la punctul . Alegerea oricărui punct de testare ulterior este guvernată de următoarele reguli: $x^{0}=a,\;x^{1}=b$ $z$ $x^{3}=(a+b)/2$ $x^{k+1},\;k\geqslant 3$

Renumerotați punctele testelor anterioare cu indicele în ordinea valorilor crescătoare ale coordonatei: și comparați-le cu valorile . $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))$
Pentru fiecare număr întreg, determinați setul corespunzător de indice ale punctelor în care au fost calculate valorile funcțiilor : $\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 .$ De asemenea, determinați valoarea maximă a indicelui $M=\max\{\nu (x_{i}),\;1\leqslant i\leqslant k\}.$
Calculați estimările curente pentru constantele Lipschitz necunoscute: $\mu _{\nu }=\max\{|g_{\nu }(x_{i})-g_{\nu }(x_{j})|/(x_{i}-x_{j })\colon i,\;j\in I_{\nu },\;i>j\}.$ Dacă setul conține mai puțin de două elemente sau dacă valoarea este egală cu zero, atunci acceptați . ${\displaystyle I_{\nu ))$ $\mu _{\nu }$ $\mu _{\nu }=1$
Pentru toate seturile nevide, calculați estimări $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}}$ unde vectorul cu coordonate nenegative se numește vector de rezervă . $\varepsilon _{R}=(\varepsilon _{1},\;\ldots,\;\varepsilon _{m})$
Pentru fiecare interval , calculați caracteristica $(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}}$ unde . $\Delta _{i}=x_{i}-x_{i-1)$ Valorile sunt parametrii algoritmului. Produsele utilizate în calcularea caracteristicilor ca estimări ale constantelor Lipschitz necunoscute depind de acestea . $r_{\nu }>1,\;\nu ={\overline {1,\;m))$ ${\displaystyle r_{\nu }\mu _{\nu ))$
Să se determine intervalul căruia îi corespunde caracteristica maximă . $(x_{t-1};\;x_{t})$ $R(t)=\max\{R(i),\;1\leqslant i\leqslant k\)$
Efectuați un alt test la mijlocul intervalului dacă indicii punctelor sale finale nu se potrivesc: $(x_{t-1};\;x_{t})$ $x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1}).$ În caz contrar, testați la punctul $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}),$ creste cu 1. $k$
Dacă ( este precizia specificată a metodei), atunci opriți algoritmul, altfel treceți la pasul 1. $x_{t}-x_{t-1}<\varepsilon$ $\varepsilon >0$

Condiții suficiente pentru convergență

Fie ca problema de optimizare originală să aibă o soluție și următoarele condiții sunt îndeplinite: $x^{*}$

fiecare regiune este o unire a unui număr finit de segmente având o lungime pozitivă; $Q_{j},\;j={\overline {1,\;m))$
fiecare functie satisface conditia Lipschitz cu constanta corespunzatoare ; $g_{j}(x),\;j={\overline {1,\;m+1))$ $L_{j)$
componentele vectorului de rezervă satisfac inegalitățile , unde este lungimea segmentului situat în regiunea admisibilă și care conține punctul ; $0\leqslant 2\varepsilon _{\nu <L_{\nu }(\beta -\alpha )$ $\beta-\alpha$ $[\alpha ;\;\beta ]$ $Q$ $x^{*}$
pornind de la o anumita valoare marimile corespunzatoare multimilor nevide satisfac inegalitatile . $k$ $\mu _{\nu }$ ${\displaystyle I_{\nu ))$ ${\displaystyle r_{\nu }\mu _{\nu }>2L_{\nu ))$

Atunci următorul lucru este adevărat:

punctul este punctul limită al secvenței generate de metoda la în starea de oprire; $x^{*}$ $\{x^{k}\}$ $\varepsilon=0$
orice punct limită al secvenței este o soluție la problema de optimizare originală; $x^0$ $\{x^{k}\}$
convergența către punctul limită este bifață dacă . $x^0$ $x^{0}\neq a,\;x^{0}\neq b$

Modificări de metodă

Modificare paralelă

Schema generală a metodei secvenţiale este următoarea:

Sortați punctele testelor anterioare în ordinea crescătoare a coordonatelor lor: . $a=x_{0}<\ldots <x_{i}<\ldots <x_{k}=b$
Calculați pentru fiecare interval caracteristica . $(x_{i-1};\;x_{i}),\;1\leqslant i\leqslant k$ $R(i)$
Să se determine intervalul căruia îi corespunde caracteristica maximă . $(x_{t-1};\;x_{t})$ $R(t)=\max\{R(i),\;1\leqslant i\leqslant k\)$
Efectuați următorul test în punctul , unde este regula de plasare a următorului punct de testare în intervalul cu numărul . $x^{k+1}=d(t)\in (x_{t-1};\;x_{t})$ $d(t)$ $t$
Verificați dacă este îndeplinit criteriul de oprire . $x_{t}-x_{t-1}<\varepsilon$

Modificarea paralelă constă în faptul că la pasul 3, în loc de un interval cu cea mai bună caracteristică, se alege intervale în ordinea descrescătoare a caracteristicilor și se efectuează teste în fiecare dintre ele în paralel. $p>1$

Schema de algoritm paralel:

Sortați punctele testelor anterioare în ordinea crescătoare a coordonatelor lor: . $a=x_{0}<\ldots <x_{i}<\ldots <x_{k}=b$
Calculați pentru fiecare interval caracteristica . $(x_{i-1};\;x_{i}),\;1\leqslant i\leqslant k$ $R(i)$
Sortați caracteristicile intervalelor în ordine descrescătoare: . $R(i_{1})>\ldots >R(i_{k})$
Pentru toate intervalele cu numere , testați în puncte . $i_{1},\;\ldots,\;i_{p)$ $x^{k+j}=d(i_{j})\in (x_{i_{j}-1};\;x_{i_{j))),\;j={\overline { 1,\;p}}$
Verificați dacă este îndeplinit criteriul de oprire: . $\exists j,\;1\leqslant j\leqslant p\colon x_{i_{j}}-x_{i_{j}-1}<\varepsilon$

O astfel de schemă de paralelizare este oportună dacă testul (adică calculul funcțiilor sarcinii) este un proces care necesită multă muncă.

Modificare pentru rezolvarea problemelor cu funcțiile Hölder

Metoda este pur și simplu generalizată în cazul în care funcțiile satisfac condiția Hölder cu exponentul , unde , i.e. $g_{j}(x),\;j={\overline {1,\;m+1))$ $1/n$ $n\în \mathbb{N}$

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

La pasul 3, valorile sunt calculate folosind formula: $\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\}.

La pasul 5 . $\Delta _{i}=(x_{i}-x_{i-1})^{1/n)$

La pasul 7, dacă indicii punctelor finale se potrivesc

x^{k+1}={\frac {1}{2}}(x_{t}+x_{t-1})-\operatorname {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}).

La pasul 8, criteriul de oprire ia forma . $(x_{t}-x_{t-1})^{1/n}<\varepsilon$

Note

Parametrii sunt responsabili pentru fiabilitatea metodei. Cu cât valorile lor sunt mai mari, cu atât sunt necesare mai multe iterații ale metodei pentru a obține o acuratețe dată și cu atât este mai probabil să fie îndeplinită condiția de convergență 4 . ${\displaystyle r_{\nu ))$ ${\displaystyle r_{\nu ))$ $R(i)=\Delta _{i)$
Utilizarea unui vector de rezervă diferit de zero face posibilă accelerarea convergenței metodei, dar în acest caz este necesar să se evalueze posibilitatea îndeplinirii condiției de convergență 3.
Metoda unidimensională poate fi aplicată pentru a rezolva probleme multidimensionale fără restricții. Problema multidimensională de pe mulțime este reprezentată ca $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}).

Pentru a rezolva problema , în care algoritmul unidimensional poate fi utilizat, dar pentru a calcula valoarea funcției , este necesar să se rezolve problema de optimizare a dimensiunii . $\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$

Dacă , atunci problema este rezolvată printr-o metodă unidimensională (valoarea variabilei este fixă), în caz contrar i se aplică și procedura de reducere a dimensionalității. Această metodă de rezolvare a problemelor multidimensionale este destul de laborioasă, prin urmare, în practică, este aplicabilă pentru . Prezența constrângerilor funcționale neliniare poate duce la pierderea proprietății Lipschitz în probleme unidimensionale auxiliare. $n=2$ $\min _{a_{2}\leqslant x_{2}\leqslant b_{2}}f(x_{1},\;x_{2})$ $x_{1}$ $n\leqslant 5$

Literatură

Barkalov K. A., Strongin R. D. Metoda de optimizare globală cu ordine de verificare adaptivă a constrângerilor // Zh. Vychisl. matematica. și mat. fizic - 2002. - T. 42. - Nr. 9. - p. 1338-1350.
Gorodetsky S. Yu., Grishagin VA Programare neliniară și optimizare multi-extremă. - Nizhny Novgorod: Nijni Novgorod University Press, 2007.
Strongin R. G. Metode numerice în probleme multi-extremale (algoritmi informaţional-statistici). - M. : Nauka, 1978. - 240 p.
Sergheev Ya. D., Grishagin VA Algoritmi secvențiali și paraleli pentru optimizarea globală // Optimization Methods and Software, 3:1-3, 1994, pp. 111-124.
Markin D. L., Strongin R. G. O metodă pentru rezolvarea problemelor multi-extremale cu constrângeri neconvexe folosind informații a priori despre estimările optime // Zh. Vychisl. matematica. și mat. Fiz., 27:1 (1987), pp. 56-62.

Link -uri

[1] - implementarea metodei în C++.
[2] - Implementarea C++ a modificării metodei metodei de rezolvare a problemelor multidimensionale multicriteriale .

Metode de optimizare
Unidimensional	metoda secțiunii de aur Dihotomie Metoda parabolelor Căutare în grilă Metoda de căutare uniformă a blocurilor Metoda Fibonacci Căutare ternară metoda Piyavsky Metoda Strongin
Comanda zero	metoda Gauss Metoda Nelder-Mead Metoda Hook-Jeeves metoda Rosenbrock Metoda Powell
Prima comanda	coborâre în gradient Metoda Zeutendijk Coordonarea coborârii Metoda gradientului conjugat Metode cvasi-newtoniene Algoritmul Levenberg-Marquardt
a doua comanda	metoda lui Newton Metoda Newton-Raphson Algoritmul Broyden-Fletcher-Goldfarb-Shanno (BFGS)
Stochastic	Metoda Monte Carlo Recoacere simulată Algoritmi evolutivi evolutie diferentiala Algoritmul furnicilor Metoda roiului de particule Algoritmul coloniilor de albine Metoda de mers aleatoriu
Metode de programare liniară	Metoda simplex algoritmul lui Gomori Metoda elipsoidă Metoda potențială
Metode de programare neliniară	Programare secvenţială pătratică