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

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

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

B = y (A). (1.6.11)

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

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

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

(1.6.13)

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

d V = V _A×d A + V _B×d B =0. (1.6.14)

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

B _A=- V _B^-1× V _A. (1.6.15)

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

(1.6.16)

Для определения характера функции y (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, которое обращало бы ограничения в ноль с заданной точностью e, т.е. |V(A_k,B_k)|<e. Для этого можно, например, использовать метод Ньютона:

(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_aJ(A _k+a× P _k, B (A _k+a× P _k)). (1.6.21)

Значения зависимых параметров B при этом рассчитываются или по формуле (1.6.17) или (1.6.20). В последнем случае приходится пересчитывать целевую функцию и ограничения дважды - для параметров A _k+a× P _k, B _k и A _k+a× P _k, B (A _k+a× P _k).

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

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

Дата добавления: 2015-11-14