Метод штрафных функций

Ме́тод штрафны́х фу́нкций, метод сведения условно-экстремальных задач к задачам безусловной оптимизации. Проиллюстрировать метод штрафных функций можно на примере задач математического программирования. Рассматривается задача минимизации функции ${\displaystyle \varphi (x)}$ на множестве ${\displaystyle X=\left\{x:f_{i}(x)\geqslant 0,\,i=1,2,\ldots ,m\right\}}$ из ${\displaystyle n}$-мерного евклидова пространства. Штрафной функцией, или штрафом [за нарушение ограничений ${\displaystyle f_{i}(x)\geqslant 0}$, ${\displaystyle i=1,2,\ldots ,m}$], называется функция ${\displaystyle \psi (x,\alpha )}$, зависящая от ${\displaystyle x}$ и числового параметра ${\displaystyle \alpha }$, обладающая следующими свойствами: ${\displaystyle \psi (x,\alpha )=0}$, если ${\displaystyle x\in X}$, и ${\displaystyle \psi (x,\alpha )>0}$, если ${\displaystyle x\notin X}$. Пусть ${\displaystyle x(\alpha )}$ является любой точкой безусловного глобального минимума функции ${\displaystyle M(x,\alpha )=\varphi (x)+\psi (x,\alpha )}$, а ${\displaystyle X^{*}}$ – множеством решений исходной задачи. Функцию ${\displaystyle \psi (x,\alpha )}$ выбирают таким образом, чтобы расстояние между точками ${\displaystyle x(\alpha )}$ и множеством ${\displaystyle X^{*}}$ стремилось к нулю при ${\displaystyle \alpha \rightarrow \infty }$ либо, если это не удаётся гарантировать, чтобы выполнялось соотношение

${\displaystyle \lim _{\alpha \rightarrow \infty }\varphi (x(\alpha ))=\inf _{x\in X}\varphi (x)}$.

В качестве ${\displaystyle \psi (x,\alpha )}$ часто выбирают функцию

${\displaystyle \psi (x,\alpha )=\alpha \sum _{i=1}^{m}\left|\min \left\{f_{i}(x),0\right\}\right|^{q},\,\,q\geqslant 1,\,{\text{ либо }}\,2}$.

Выбор конкретного вида функции ${\displaystyle \psi (x,\alpha )}$ связан как с проблемой сходимости метода штрафных функций, так и с проблемами, возникающими при решении задачи безусловной минимизации функции ${\displaystyle M(x,\alpha )}$.

В несколько более общей постановке метод штрафных функций заключается в сведении задачи минимизации функции ${\displaystyle \varphi (x)}$ на множестве ${\displaystyle X}$ к задаче минимизации некоторой параметрической функции ${\displaystyle M(x,\alpha )}$ на множестве более простой структуры с точки зрения эффективности применения численных методов минимизации, чем исходное множество ${\displaystyle X}$.

Имеет место следующий весьма общий результат, иллюстрирующий универсальность метода штрафных функций. Пусть ${\displaystyle U}$ и ${\displaystyle V}$ – рефлексивные банаховы пространства; ${\displaystyle R}$ – расширенная действительная прямая; ${\displaystyle \varphi }$ – функция, определённая на ${\displaystyle U}$ со значениями в ${\displaystyle R}$, слабо полунепрерывная снизу; ${\displaystyle f_{i}}$, ${\displaystyle i=1,2,\ldots ,m}$ – функции, определённые на ${\displaystyle U}$ со значениями в ${\displaystyle R}$, непрерывные в слабой топологии пространства ${\displaystyle U}$; ${\displaystyle h_{j}}$, ${\displaystyle j=1,2,\ldots ,n}$ – функции, определённые на ${\displaystyle U}$ со значениями в ${\displaystyle V}$, непрерывные в слабых топологиях пространств ${\displaystyle U}$ и ${\displaystyle V}$; множество ${\displaystyle X=\{x:f_{i}(x)\geqslant 0;\,i=1,2,\ldots ,m;\,h_{j}(x)=0,\,j=1,2,\ldots ,n;\,x\in U\}}$ не пусто. Рассматривается задача отыскания таких ${\displaystyle x^{*}\in U}$, что

${\displaystyle \varphi \left(x^{*}\right)\leqslant \varphi (x)\,{\text{ для всех }}\,x\in X.}$ (*)

Для функции

${\displaystyle {\begin{aligned}&M\left(x,y_{1},y_{2},\ldots ,y_{m},\alpha \right)=\varphi (x)+\\&\quad +\alpha \left\{\sum _{i=1}^{m}\left|f_{i}(x)-y_{i}\right|^{2}+\sum _{j=1}^{n}\left\|h_{j}(x)\right\|_{V}^{2}\right\}\end{aligned}}}$

при ${\displaystyle \alpha >0}$, ${\displaystyle x\in U}$, ${\displaystyle y_{i}\in R}$, ${\displaystyle i=1,2,\ldots ,m}$, рассматривается задача отыскания таких ${\displaystyle x(\alpha )\in U}$ и ${\displaystyle y_{i}(\alpha )\geqslant 0}$, ${\displaystyle i=1,2,\ldots ,m}$, что

${\displaystyle {\begin{aligned}M\left(x(\alpha ),y_{1}(\alpha ),y_{2}(\alpha ),\ldots ,y_{m}(\alpha ),\alpha \right)\leqslant \\\leqslant M\left(x,y_{1},y_{2},\ldots ,y_{m},\alpha \right)\end{aligned}}}$

для всех ${\displaystyle x\in U}$, ${\displaystyle y_{i}\geqslant 0}$, ${\displaystyle i=1,2,\ldots ,m}$. Если

${\displaystyle \lim _{\|x\|\rightarrow \infty }\varphi (x)=+\infty }$,

то каждая слабо предельная точка произвольной последовательности ${\displaystyle \left\{x\left(\alpha _{k}\right)\right\}}$, ${\displaystyle \alpha _{k}\rightarrow \infty }$, ${\displaystyle k\rightarrow \infty }$, является решением задачи ${\displaystyle (*)}$ и, кроме того,

${\displaystyle \lim \varphi (x(\alpha ))=\varphi \left(x^{*}\right),\quad \alpha \rightarrow \infty }$.