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

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

Видоизмененная целевая функция может иметь следующий вид:

(1.6.5)

Добавка в целевой функции может иметь и другой вид, важно только чтобы она штрафовала функцию , т.е. увеличивала ее значение при нарушении ограничений V(X).

Коэффициент штрафа «С» в первом цикле безусловной оптимизации выбирается обычно не большим, так чтобы вес самой целевой функции J(X) был бы приближенно равен весу штрафного слагаемого в видоизмененной целевой функции (1.6.5). Проводится полный цикл безусловной оптимизации функции (1.6.5) по параметрам X^*. В оптимальной точке X градиент от целевой функции (1.6.5) обращается в ноль:

(1.6.6)

В точке X^* ограничения еще далеки обычно от нуля и для их большей притяжки к нулю увеличивают коэффициент штрафа С в несколько раз, например, С_l+!=2С_l, где l- номер текущего цикла оптимизации. С новым значением коэффициента штрафа выполняется опять процедура безусловной оптимизации новой целевой функции и т.д., до тех пор пока значения ограничений V(X) не станут меньше заданного значения. Следует отметить, что метод штрафных функций , в принципе, не позволяет найти точное решение задачи условной оптимизации, т.к. на ЭВМ нельзя разрешить неопределенность типа бесконечность на ноль - 0. Однако метод штрафных функций является очень устойчивым, хотя и не быстрым методом решения задач условной оптимизации.

1.6.3 Комбинированный метод Хестенса

Метод Хестенса [20] является комбинированным методом множителей Лагранжа и штрафных функций. Новая целевая функция записывается в виде:

(1.6.7)

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

Градиент от новой целевой функции имеет вид:

(1.6.8)

В этом методе проводится несколько циклов минимизаций и множители Лагранжа пересчитываются по формуле:

(1.6.9)

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

откуда: (1.6.10)

1.6.4 Метод разделения параметров

Решение задачи условной оптимизации путем преобразования целевой функции и приведение ее к задаче безусловной оптимизации с помощью методов штрафных функций, множителей Лагранжа или комбинированного метода Хестенса приводит к необходимости многократного повторения циклов безусловной оптимизации. Полное решение задачи условной оптимизации получается только в конце всей процедуры поиска. Если учесть, что время одного расчета целевой функции может достигать нескольких минут, то за приемлемое время счета (~ 3-5 часов) можно вообще не решить задачу условной оптимизации, т.е. минимизировать целевую функцию при достаточно точном выполнении ограничений. Для устранения указанного недостатка можно использовать метод разделения параметров, который основан на методе проективного градиента [23]. В этом методе на каждой итерации ограничения выполняются с заданной точностью, поэтому каждый промежуточный результат есть решение задачи, хотя и не самое оптимальное.

Наличие ограничений типа равенств V(X)=0 при решении задачи условной оптимизации позволяет в принципе разделить n поисковых параметров X на n-r независимых параметров A и r зависимых параметров B (базисных переменных), которые являются какими-то функциями от A, т.е.

B=(A). (1.6.11)

Задача условной оптимизации сводится теперь к поиску таких значений параметров A^*, которые бы соответствовали минимуму функции цели:

A^*: min_a(J(A,(A)). (1.6.12)

Градиент от функции цели J по параметрам A можно определить как градиент от сложной функции:

(1.6.13)

Здесь нижний индекс определяет частные производные по соответствующим параметрам, значок «^T»- транспонирование вектора или матрицы. При поиске минимума целевой функции будем так выбирать поисковое направление, чтобы значения ограничений не менялись хотя бы в близи начальной точки. Это означает, что направление поиска должно быть выбрано в плоскости касания поверхности равного уровня ограничений V=const0 и направление поиска нужно рассчитывать исходя из проекции полного градиента на касательную плоскость к поверхности равного уровня ограничений, т.е. должно выполняться условие:

dV=V_AdA+V_BdB=0. (1.6.14)

Отсюда следует, что

B_A=-V_B^-1V_A. (1.6.15)

Проекцию вектора градиента на гиперповерхность ограничений можно получить подстановкой (1.6.15) в (1.6.13) :

(1.6.16)

Для определения характера функции (A) можно использовать линейную часть разложения ограничений V(A,B) в ряд Тейлора относительно значений A_k, B_k :

(1.6.17)

Это линейная зависимость B от A. Можно уточнить эту зависимость не производя разложение ограничений в ряд по параметрам A. Тогда

(1.6.18)

дает нелинейную зависимость B от A.

Реализация формулы (1.6.18) приводит к необходимости для каждого нового значения A рассчитывать не только ограничения V(A,B_k ), но и значения обратной матрицы производных V_B^-1(A,B_k), а это уже требует существенных затрат машинного времени. Можно пойти на компромисс и рассчитывать B по формуле:

(1.6.19)

которая дает тоже нелинейную приближенную зависимость B от A, но увеличивает время расчетов всего в 2 раза по сравнению с расчетом по формуле (1.6.17). Вначале рассчитываются значения V(A,B_k), затем определяются B по формуле (1.6.19), которые уже используются для расчета J(A,B) при поиске минимума в заданном направлении.

Алгоритм метода разделения параметров в итоге состоит в следующем.

{{{ Начало алгоритма.

1) Разделяем все n поисковых параметров X на n-r независимых параметров A и r зависимых параметров B. Обычно это делается исходя из физической постановки задачи. Например, в задачах электроники СВЧ при оптимизации клистронов независимыми параметрами резонаторов могут быть добротность и расстройка резонаторов, а зависимыми напряженность ВЧ-поля и его фаза, а связывает их условия само согласования полей в резонаторах.

Задаемся какими-то начальными значениями A₀, B₀. Полагаем номер текущей итерации k=0 и ,соответственно, A_k=A₀, B_k=B₀. Матрицу текущей метрики полагаем единичной матрице: H_k=I.

2) Для заданного значения A_k находим такое значение вектора зависимых параметров B_k, которое обращало бы ограничения в ноль с заданной точностью , т.е. |V(A_k,B_k)|<. Для этого можно, например, использовать метод Ньютона:

(1.6.20)

3) Для заданных значений A_k ,B_k рассчитываются значения целевой функции J(A_k,B_k), ограничения V(A_k,B_k) и производные J_A, J_B, V_A, V_B. Расчет производных производится или методом конечных разностей или АУС-методом (см. раздел 1.8.2). Вычисляется полное значение градиента по формуле (1.6.16). Согласно алгоритму оптимизации с переменной метрикой пересчитывается матрица метрики H_k+1=H_k+E_k. На первой итерации E_k полагают равной нулю. Рассчитывается поисковое направление P_k=-H_k+1 grad_AJ(A_k,B(A_k)).

4) Производится поиск минимума целевой функции по параметрам A в заданном направлении P_k:

A_k+1: min_J(A_k+P_k,B(A_k+P_k)). (1.6.21)

Значения зависимых параметров B при этом рассчитываются или по формуле (1.6.17) или (1.6.20). В последнем случае приходится пересчитывать целевую функцию и ограничения дважды - для параметров A_k+P_k, B_k и A_k+P_k, B(A_k+P_k).

5) Если |A_k+1-A_k| , то полагаем A_k=A_k+1, B_k=B(A_k+1), k=k+1 и переходим опять к пункту 2), иначе заканчиваем процесс оптимизации.

}}} Конец алгоритма.