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

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

Пусть необходимо решить задачу

img01,             (1)

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

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

img02,                (2)

чтобы приближенное решение задачи (1) получалось в результате решения последовательности задач безусловной минимизации функций (2)

img03.                                                     (3)

В методе (внешних) штрафных функций функции img04 и img05 выбираются таким образом, чтобы они становились отличными от нуля (положительными) при нарушении соответствующего ограничения. А так как мы минимизируем (2), то движение в сторону нарушения ограничения становится невыгодным. В данном методе функции img06 и img07 внутри допустимой области должны быть равны нулю. Например, для ограничений неравенств:

img08 при img09.

Приближенное решение задачи (1) получается в результате решения последовательности задач (3) при img10, img11. Соответствующие методы называют еще методами внешней точки.

img12

Рис.

В методе барьерных функций функции img13 и img14 в допустимой области выбираются отличными от нуля и такими, чтобы при приближении к границе допустимой области (изнутри) они возрастали, препятствуя выходу при поиске за границу области. В этом случае эти функции должны быть малыми (положительными или отрицательными) внутри допустимой области и большими положительными вблизи границы (внутри области). Например, для ограничений неравенств:

img15 при img16.

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

img20

Рис.

При выборе функций штрафов для ограничений равенств обычно требуют, чтобы

img21  при  img22.

Это могут быть, например функции следующего вида:

  1. img23,

  2. img24,

  3. img25, при четном img26.

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

img27;

img28.

Этому требованию отвечают, например, функции вида:

  1. img29,

  2. img30,

  3. img31, при четном img32.

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

  1. img33,

  2. img34.

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

  1. На основании задачи (1) строим функцию (2). Выбираем начальное приближение img35 и начальные значения коэффициентов штрафа img36.

  2. Решаем задачу (3).

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

  4. Процесс прекращается, если найденное решение удовлетворяет системе ограничений с определенной точностью.


Hosted by uCoz