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

Для перехода от задачи параметрической оптимизации с ограничениями (1.6) к задаче без ограничений, или задаче безусловной оптимизации

Ф(Х)  extr , (1. 17)

используется один из следующих методов: метод неопределенных множителей Лагранжа; метод штрафных функций; метод барьерных функций /5-8/.

В методе неопределенных множителей Лагранжа вводятся дополнительные переменные y1,y2.,…,yL, которые называют неопределенными множителями Лагранжа. Их количество равно числу ограничений L в задаче оптимизации (1.6).

Формула (1.18) применима, если задача (1.6) ставится как задача максимизации, при этом для полученной целевой функции Ф(X,Y) необходимо найти седловую точку, то есть по переменным X = x1, x2.,…,xn) проводится поиск максимума, а по переменным Y = ( y1,y2.,…,ym) – поиск минимума, то есть

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

В методе штрафных функций целевую функцию задачи безусловной оптимизации получают по формуле:

Ф(Х)=f(X)+ k(X)  extr, (1. 20)

где X = (x1, x2.,…,xn) – набор управляемых параметров,  k(X) -

штрафная функция, k-номер итерации (шага) в методе поисковой оптимизации.

На практике задачи параметрической оптимизации решаются в основном итерационными (пошаговыми) методами, которые называют методами поисковой оптимизации. При этом на каждом шаге поиска значение штрафной функции  k(X) уточняется (рассчитывается заново) по формуле:

где r _k=10 ^k. Формула (1.21) применима, если задача (1.6) ставилась как задача минимизации.

Логика построения штрафной функции заключается в следующем: внутри области работоспособности ХР g l (X) ,

L = 1,…,L, на границе – g l (X) , а вне ХР g l (X) >  (рис. 1.2).

Целевая функция задачи безусловной оптимизации Ф(Х) должна быть максимально близкой к целевой функции f(Х) задачи с ограничениями внутри области работоспособности

XР = {X = (x1,x2.,…,xn)gl(X), l = 1,…,L } и быть значительно хуже (больше) функции f(Х) вне области работоспособности, то есть при gl(X) > .

Действительно, внутри области работоспособности ХР gl(X), l = 1,…,L, поэтому max{0, gl(X)} = 0 для всех ограничений, то есть внутри области работоспособности Ф(Х) = f(Х). Если ограничения выполнены, то никакого штрафа на целевую функцию не накладывается. В противном случае, если имеются нарушения одного или нескольких ограничений g t (X) >  1t L, то каждое из них дает свой вклад в штрафную функцию k(X) в виде квадрата слагаемого [ max{0,gt(Х)}], где max{0,gt(Х)}=gt(Х). Метод штрафных функций часто называют методом внешней точки, потому что при проведении дальнейшей оптимизации поисковыми методами для метода штрафных функций не важно, принадлежит ли начальная точка поиска области работоспособности ХР.

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

Ф(Х)=f(X)+ k(X)  extr, (1.22)

где k- номер итерации поискового метода, весовой коэффициент rk=10 ^-k , а барьерная функция  k(X) вычисляется по формуле

Действительно, при приближении к границе ХР gl(Х) 0, так как ХХР (метод внутренней точки) gl (X) , l = 1,…,L, поэтому gl(Х) → - ¥. Именно поэтому в формуле (1.23) используется знак минус: k(X) возрастает до бесконечности при приближении к границе области работоспособности.

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

Таким образом, при небольшом количестве управляемых параметров Х и ограничений gl(X), целесообразно применять метод неопределенных множителей Лагранжа, если проверка принадлежности начальной точки поиска области ХР не слишком трудоемкая задача, то применяем метод барьерных функций, в противном случае – метод штрафных функций, который, хотя и является более универсальным, но впоследствии, в ходе поисковой оптимизации требует большего числа итераций по сравнению с методом барьерных функций.