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

3

МЕТОДЫ ШТРАФНЫХ ФУНКЦИЙ

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

Методы подразделяются на: 1) методы внутренней точки; 2) методы внешней точки; 3) комбинированные методы.

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

2. Методы внешней точки, наоборот, генерируют последовательность точек, которые выходят за пределы допустимой области, но в пределе дают допустимое решение.

3. Наконец, в комбинированных методах, которые необходимо использовать при ограничениях-равенствах, в процессе оптимизации одни из ограничений удовлетворяются, а другие – нет. Однако при достижении искомого решения все условия в пределах заданного допуска выполняются.

Итак, пусть задача НП имеет следующий вид:

минимизировать                    (6.8.1)

при ограничениях  ,              (6.8.2)

 .                          (6.8.3)

В основу штрафных функций положено преобразование задачи (6.8.1)-(6.8.3) в задачу минимизаци без ограничений вида

 ,              (6.8.4)

где  – штрафная функция;  – весовые коэффициенты;  – некоторые функционалы.

Выбирая вид функционала , руководствуются следующими вариантами [50]:

 при .

Для чего необходимо, чтобы точка  всегда была внутренней точкой, т.е. чтобы выполнялось условие

 при .

При таком выборе функционала  оперируют только с внешними точками, для которых выполняется условие  

 при  и  при .

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

При выборе функционала для ограничений-равенств вводится требование  при . При этом обычно полагают . Наконец, при любом выборе функционалов  требуется, чтобы

,                        (6.8.5)

,

 .                      (6.8.6)

Метод барьерных поверхностей

Метод барьерных поверхностей (МБП) относится к группе методов внутренней точки и основан на использовании барьерной поверхности вида

 ,                       (6.8.7)

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

При этом барьерная функция (поверхность)  неограниченно возрастает при .

Примерами барьерных функций являются:

       а) обратная функция         ,                          (6.8.8)

б) логарифмическая функция .

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

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

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

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

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

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

Пусть, как и выше, имеется задача НП:

минимизировать                       (6.8.10)

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

,                           (6.8.11)

.                        (6.8.12)

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

В частности, для ограничений типа (6.8.11), (6.8.12) целесообразно использовать штрафную функцию следующего вида:

 ,              (6.8.13)

где  – непрерывные функции, которые удовлетворяют условиям:

 , если  и , если ,

 , если  и , если .

Типичными являются следующие выражения для функций :

 , где  – целое положительное число.

Таким образом, штрафная функция  обычно имеет вид

 .                  (6.8.14)

Далее от задачи НП (6.8.10)-(6.8.12) переходим к задаче безусловной оптимизации вспомогательной функции:

минимизировать ,               (6.8.15)

где   – штрафной коэффициент.