Методы Оптимизации Систем Автоматизированного Проектирования

Основные определения методов штрафных функций

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

при ограничениях:

Они преобразуют задачу с ограничениями в последовательность задач безусловной оптимизации.
, где - некоторая вспомогательная функция, которая подбирается так, чтобы с рос-том номера k она мало отличалась от исходной функции f(x) на множестве допустимых решений G и быстро возрастала на множестве .
Быстрый рост функции вне G приводит к тому, что при больших k нижняя грань этой функции на будет достигаться в точках близких к множеству G, и решение вспомогательной задачи безусловной оптимизации будет приближаться при определенных условиях к решению исходной задачи условной оптимизации. При этом имеется достаточно большой произвол в выборе функции , что позволяет выбрать ее наиболее удобный вид и использовать наиболее простые методы безусловной оптимизации.

Определение. Функция называется штрафной функцией множества G, если для любых параметров

Из определения видно, что при больших за нарушение правила придется платить большой штраф, в то время как при штраф стремится к нулю с ростом k.

В общем случае вспомогательная функция имеет вид: F(x,a) =f(x) +Ф(х, а).

Здесь f(x) - целевая функция задачи оптимизации; Ф(х, а) - “штрафная” функция;
параметр а >0. Точку безусловного минимума функции F(x, a) будем обозначать через х(а). И приходим к задаче безусловной оптимизации:

Таким образом, задача условной минимизации f (x) заменяется последовательностью задач безусловной минимизации при k =1,2,.... При этом, исходя из заданной начальной точки x0, находится последовательность точек сходящаяся при определенных условиях к решению исходной задачи.

В зависимости от вида Ф(х, а) различают методы внешних штрафных функций и методы внутренних штрафных функций или барьерных функций.