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

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

Суть метода заключается в том, что поиск начинается обязательно из внутренней точки и последующие точки не должны выходить из допустимой области. С этой целью задача модифицируется так, что при приближении к границе допустимой области растет барьер, препятствующий выходу на границу. Исходная задача на условный экстремум задается в виде f (x) à min; j_i (x) £ 0, .

Она преобразуется в задачу безусловной минимизации вспомогательной функции

Q (x) = f (x) + mB (x), где B (x) – барьерная функция, m - параметр барьера. Обязательное условие: внутренность области не должна быть пустой (имеются точки, в которых " j_i (x) < 0). Барьерная функция строится так, чтобы она была неотрицательной и непрерывной на допустимом множестве и стремилась к бесконечности при приближении изнутри к границе: Как и в случае штрафной функции, существует несколько конструкций B (x), удовлетворяющих этим условиям. Но в основном используется барьерная функция в виде Решение вспомогательной задачи зависит от значения параметра барьера.

Алгоритм.

1. Выбрать начальную точку x ⁰ так, чтобы " j_i (x ⁰)<0; задать точность e, начальное значение m ₀ и число b Î (0, 1).

2. Минимизировать Q (x) одним из методов безусловной оптимизации, в результате чего определяется .

3. Проверить: если , то остановиться, приняв за оптимальное решение задачи.

5. Положить , за начальную точку принять и вернуться на 2.

Значение m ₀ можно брать из интервала [2, 10]. Важное замечание касается п.2 алгоритма: в процессе поиска минимума вблизи границы из-за дискретности шагов возможен выход за допустимую область, где барьерная функция становится отрицательной, что повлечет расхождение поиска. Поэтому необходима явная проверка на допустимость точек на каждом шаге при минимизации Q.

47. Динамическое программирование (ДП): принцип оптимальности, функциональное уравнение, процедура ДП.

Концепция метода проистекает из следующего свойства оптимального решения. Пусть оптимальный путь из точки A в точку E проходит через точки B, С и D. Тогда любая часть этого пути является оптимальным путем. Принцип оптимальности - оптимальное управление определяется конечной целью управления и состоянием системы в рассматриваемый момент, независимо от того, каким образом она пришла в это состояние; при фиксированном состоянии системы последующее оптимальное решение не зависит от ее предыстории. Он позволяет разложить задачу на ряд задач значительно меньшей размерности. Имеются в виду задачи, которые могут быть представлены как многошаговые. Такие задачи описываются математической моделью, в которой и критерий, и ограничения являются составными. Под составной понимается функция f, образованная частными функциями (подфункциями) f_i, к которым применен один и тот же оператор вхождения (например, оператор сложения), т.е. f =(<оператор> < f ₁, f ₂,..., f_m >).

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