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

Рассмотрим задачу минимизации функции , которая определена во всем пространстве и является выпуклой во всей области определения, при наличии ограничений. Метод штрафных функций сводит решение этой задачи к решению некоторой последовательности задач без ограничений. Для этого вводится функция , где M – неотрицательный параметр (). Функция обладает следующими свойствами:

1. , для всех значений x, входящих в область допустимых планов ;

2. вне области планов ;

3. если :

4. , если .

Введенная таким образом функция называется штрафом, сумма является штрафной функцией задачи. В области допустимых планов штрафная функция совпадает с целевой функцией , вне ее

При этом исходная задача заменяется задачей минимизации штрафной функции без ограничений. Если оптимальный план , полученный при минимизации штрафной функции, лежит в области планов исходной задачи, то он является ее оптимальным планом, поскольку области планов штрафной и исходной функций совпадают. Если оптимальный план задачи минимизации штрафной функции не входит в область планов исходной функции, то оптимальное значение штрафной функции не больше оптимального значения целевой функции исходной задачи .

В основе алгоритма решения задачи минимизации методом штрафных функций лежит следующая теорема.

Теорема. Если функция определена, выпукла, непрерывна во всем пространстве и , а функция непрерывна как функция переменной x, то задачи минимизации исходной целевой и штрафной функций имеют оптимальные планы, и .