baudos funkcijų metodas

baudos funkcijų metodas

baudõs fùnkcijų metòdas, metodas, taikomas sąlyginiams optimizavimo uždaviniams spręsti. Reikia rasti vektorių x ∈ Rⁿ, kuris tenkintų nelygybių sistemą g_i(x) ≤ 0, i = 1, …, m ir su kuriuo funkcija f(x) įgytų mažiausią (didžiausią) reikšmę. Pažymėjus leistinųjų vektorių aibę X = {x: g_i(x) ≤ 0, i = 1, …, m, x ∈ Rⁿ} erdvėje Rⁿ apibrėžiama funkcija F(x) = f(x) + P(x); čia P(x) = \(\begin{cases} 0, & \text{ kai } x \in X \\ \infty, & \text{ kai } x \notin X \end{cases}\). Funkcija P(x) interpretuojama kaip begalinė bauda už leistinosios aibės X pažeidimą. Vektorius x* yra sąlyginio uždavinio sprendinys tada ir tik tada, kai jis yra nesąlyginio uždavinio $\underset{x\in R^n}{\min }F(x)$ sprendinys. Be to, F(x*) = f(x*). Sąlyginį uždavinį galima keisti nesąlyginiu. Sprendžiant pastarąjį funkcija P(x) aproksimuojama paprastesnių funkcijų seka $(\frac{1}{r_k}B(x))$ (pav., a), o funkcija F(x) – seka (F(x, r_k)) (pav., b); čia B(x) = \(\begin{cases} 0, & \text{ kai } x \in X \\ c > 0, & \text{ kai } x \notin X \end{cases}\), F(x, r_k) = f(x) + $\frac{1}{r_k}B(x)$, ir skaičių seka (r_k), r_k > 0, r_k > r_k+1, k = 1, 2 …, r_k → 0, kai k → ∞. B(x) vadinama baudos funkcija. Naudojant šią funkciją sąlyginis uždavinys keičiamas nesąlyginių uždavinių seka $\underset{x\notin R^n}{\min }F(x,r_k)$, k = 1, 2… Išsprendus k‑ąjį sekos uždavinį gaunamas sąlyginio uždavinio sprendinio artinys x^k (pav., c). Tam tikromis sąlygomis artinių sekos (x^k) konverguojantis posekis konverguoja prie sąlyginio uždavinio tikslaus sprendinio x*. Seka $(\frac{1}{r_k}B(x))$ aproksimuoja funkciją P(x) iš leistinosios aibės X išorės, o seka (x^k) iš išorės artėja prie sprendinio x*, todėl šis metodas kartais vadinamas išorinių baudos funkcijų metodu. Taikant kitą metodą funkcija P(x) aproksimuojama seka funkcijų, kurios apibrėžtos tik leistinųjų vektorių aibės X viduje. Toks metodas vadinamas vidinių baudos funkcijų arba barjerų metodu.

62