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

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

1) недифференцируемые точные штрафные функции, безусловный минимум которых по x ищется при фиксированном значении параметра штрафа:

                  ;          (3.1)

2) дифференцируемые точные штрафные функции (для задач с ограничениями типа равенств):

                    ,            (3.2)

где ,  - параметры штрафа, - классическая функция Лагранжа;

                                        ,                                 (3.3)

где - параметр штрафа. Для минимизации недифференцируемых вспомогательных функций можно применять методы нулевого порядка, а для дифференцируемых – также методы, использующие производные. Увеличивать параметр штрафа  до бесконечности не требуется: существует конечное пороговое значение , такое, что  будет точкой безусловного минимума  при любом . Параметр  задаётся достаточно малым положительным числом.

Алгоритм:

Шаг 1. Задать начальную точку ; начальное значение параметров штрафа ; число  для изменения параметров штрафа; максимальное число решаемых задач безусловной минимизации N; малое число  для остановки алгоритма. Положить .

Шаг 2. Составить вспомогательную функцию вида (3.1) или (3.2), или (3.3) в зависимости от типа решаемой задачи.

Шаг 3. Найти точку  или  безусловного минимума вспомогательной функции по x  для (3.1), (3.3), и по для (3.2). В качестве начальной точки взять . Предусмотреть прекращение процесса минимизации, если вспомогательная функция не ограничена снизу.

Шаг 4. Вычислить абсолютное значение соответствующей штрафной функции:

и проверить выполнение условия окончания:

a)      если вычисленное значение меньше или равно , процесс поиска закончить:  или ;

b)      если оно больше  и , процесс закончить и выдать сообщение о неудаче;

c)      если вычисленное значение больше  и , положить  или и перейти к шагу 2.

Замечание:

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

Пример: Найти минимум в задаче

Решение:

Используем недифференцируемую точную штрафную функцию (3.1):

.

Точное решение этой задачи . При этом . Параметр штрафа должен удовлетворять условию: . Тогда является точкой локального минимума . Например, при имеем:

Очевидно, эта функция имеет безусловный минимум в точке (см. рисунок 3.6).

Рисунок 3.6

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