Материал: Методы оптимального проектирования устройств цифровой обработки и защиты информации. Борисов В.И., Гармонов А.В
Кроме того в методе ДФП, матрица H (k ) может стать неопределенной или почти неопределенной. Это может произойти в том случае, если величина знаменателя T H
будет
близка или равна нулю, что вызовет переполнение разрядной сетки ЭВМ или очень большой шаг в направлении G(k ) . Во избежании этого в ряде исследований предлагалось заменить
матрицу H (k 1) на единичную H 2 через каждые k итераций, что позволяет обеспечить
сходимость к стационарной точке. Но скорость сходимости метода при этом существенно замедляется.
При коррекции матрицы H (k ) ошибки округления часто приводят к тому, что направление поиска G(k ) будет почти перпендикулярно к градиенту целевой функции, т.е.
будет сильно отличаться от направления ее наискорейшего убывания. Поэтому, если выполняется условие
|
|
|
|
Hg T |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
, |
0 , |
(3.16) |
|
|
||||||||||||||
|
|
Hg |
|
g |
|
|
|
|
|||||||
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
||||||
то есть косинус угла между g и Hg меньше некоторого малого |
, а матрицу H (k 1) также |
||||||||||||||
следует заменить на единичную или на другую, положительно определенную матрицу.
Улучшенными вычислительными возможностями обладает метод Бройдена-
Флетчера-Гольдфарба-Шанно |
(БФГШ), |
в |
котором матрица H (k 1) |
определяется из |
|||||||
выражения [48,93]: |
|
|
|
|
|
|
|
|
|
|
|
k 1 |
|
|
T H |
|
|
T |
|
T HH |
T |
|
|
H ДФГШ |
H |
1 |
|
|
|
|
|
|
|
. |
(3.17) |
T |
|
T |
|
|
T |
|
|||||
Его основным преимуществом является малая критичность к точности линейного поиска, что делает его весьма эффективным с точки зрения объема вычислений. Формула коррекции (3.15) сохраняет все важные теоретические свойства КНМ. Кроме того,
теоретически доказана глобальная сходимость метода БФГШ с приближенным линейным
поиском.
Соотношения (3.13) и (3.15) в своей линейной комбинации образуют однопараметрическое семейство формул коррекции второго ранга, получившее название
семейства Бройдена [18, 48, 93]:
k 1 |
k 1 |
k 1 |
|
HФ |
(1 Ф)H ДФП |
ФH ДФГШ . |
(3.18) |
Это семейство включает в себя и формулу ДФП (Ф=0), и формулу БФГШ (Ф=1), и ряд других формул. Важным является то, что многие свойства формул коррекции ДФП и БФГШ
119
являются общими для всего семейства формул (3.17) В несколько преобразованном виде с учетом выражений (3.14), (3.15) формулу (3.18) можно представить так:
k 1 |
k 1 |
ФVV |
T |
, |
|
HФ |
H ДФП |
|
(3.19) |
где
|
|
|
|
|
H |
|
V |
T H |
|
|
. |
||
|
|
|
|
|||
|
T |
|
T H |
|||
|
|
|
|
|
Анализ собственных чисел матрицы HФk 1 показывает, что ее положительная Ф
определенность будет обеспечена, если параметр будет удовлетворять условию [3, 12, 18, 93]:
|
|
Ф 1/[(1 T H T E1 ) / T 2 ] |
|
(3.20) |
где E1 |
H 1 . |
|
|
|
|
Для |
квадратичных функций Флетчер показал, |
что собственные |
числа матрицы |
B1/ 2 H (k ) B1/ 2 |
монотонно стремятся к единице в том и только в том случае, |
когда параметры |
||
Ф(k ) |
[0,1]. |
Это означает, что стабильные формулы |
коррекции ограничиваются лишь |
|
выпуклым классом формул, принадлежащих семейству (3.19). Для выбора значения параметра Ф Флетчер предложил выполнять проверку следующего условия [93]:
T |
T H . |
(3.21) |
При еѐ выполнении Ф 1, и |
для коррекции используется |
формула БФГШ. В |
противном случае Ф 0 и применяется формула ДФП. Этот метод в сочетании с процедурой приближенного линейного поиска хорошо зарекомендовал себя при решении ряда тестовых задач и в настоящее время широко используется во многих программах оптимизации.
Впервых программах, использовавших целевую функцию вида (2.14),
предпринимались попытки решать задачу оптимизации как общую задачу НЛП с последовательным увеличением q от итерации к итерации [28]. Это приводило к потере точности и устойчивости вычислительного процесса вследствие оперирования с очень большими и очень малыми числами (т.е. задача была плохо обусловлена). Отметим, что целевая функция (2.15) свободна от этого недостатка и входящий в нее показатель степени принимает небольшие положительные целочисленные значения. Поэтому на практике при решении задачи оптимизации УЦОС чаще применяется целевая функция (2.15).
Решение задач минимизации обобщенных критериев оптимальности рассмотренными методами может быть представлено следующим алгоритмом:
120
Шаг 1. |
Установить k 0, X (0) D . |
Шаг 2. |
Определить направление поиска G(k ) . |
Шаг 3. |
Решить задачу одномерного поиска |
min Q( X (k ) 
k G(k ) ).
k
Шаг 4. Установить k k 1; если не выполнено условие останова, то перейти к шагу
2.
Повышение эффективности решения поставленной задачи означает уменьшение общего количества определений целевой функции на шагах 2 и 3. Рассмотрим вопросы
уменьшения количества определений целевой функции на шаге 3.
В настоящей работе использован алгоритм одномерной минимизации, построенный на приближенном вычислении целевой функции, изложенном в п. 2.2. Его применение тем более целесообразно, чем сложнее математическая модель УЦОС, расчет которой необходим для вычисления значения целевой функции (обобщенного критерия). Здесь минимизация
целевой функции сведена к многошаговой процедуре, на каждом l -том шаге которой методом дихотомии [31] минимизируется не функция Q , а ее приближенное значение Qp и в точке минимума приближенной функции рассчитывается относительная погрешность Q
расчета функции. Особенность используемого алгоритма заключается в том, что каждая из
функций Qi ( X |
G) заменяется параболой (см. п. 2.2). |
|||
В случае, если либо |
Q |
0 , где |
0 - допустимая погрешность воспроизведения |
|
целевой функции, либо k |
kmax , где kmax |
- допустимое количество шагов, одномерная |
||
минимизация |
заканчивается. |
В противном случае производится переопределение точек |
||
X (0) , X (1) , X (2) |
интервала, |
содержащего |
минимум целевой функции, и переход к |
|
следующему шагу.
Кроме того в реализованном алгоритме направление движения к оптимуму на шаге 2
определяется по формуле
G(k ) |
Z |
k |
G(k 1) ; |
k 1 |
yT |
1 |
Z |
k |
/(yT |
G(k 1) |
, |
(3.22) |
|
|
|
k 1 |
|
k |
|
k |
1 |
|
|
||||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
yk 1 |
Q(X (k ) ) |
Q(X (k 1) );Zk |
|
|
|
Hk 1 |
Q(X (k ) ) . |
|
|||||
Приведенная формула реализует метод сопряженных градиентов с улучшенной обусловленностью, что заметно повышает эффективность реализованного алгоритма при решении задач оптимизации типа (3.1) с целевыми функциями (2.15) и (2.22).
121
3.3 Алгоритмы минимизации минимаксных критериев оптимальности
УЦОС
Обобщенный критерий вида (2.12) очень часто бывает наиболее предпочтительным,
поскольку в точке минимума функция максимума обладает альтернансными свойствами [21, 47, 48, 79], т.е. имеется несколько отклонений, равных максимальному. Это означает, что при решении минимаксных задач получают более качественные решения, обеспечивающие укладывание характеристик в зоны с максимальным запасом. Однако этот критерий не сохраняют свойства гладкости целевых функций, что требует привлечения специальных
методов оптимизации.
Зачастую задача векторной оптимизации УЦОС решается в случае, когда задача (2.12)
является линейной минимаксной задачей без ограничений. При скалярной оптимизации решение этой задачи обычно осуществляется методом последовательных чебышевских интерполяций Е. Я. Ремеза [21,79]. Для решения задач векторной оптимизации другого класса устройств этот метод впервые применен в работах [33, 38, 90]. Метод минимакса [21]
весьма схож с оптимизацией линейной свертки. Решается задача
min max{ |
i Qi ( X )}, |
|
(3.23) |
X i |
|
|
|
в которой подбором компонент весового вектора |
i |
можно найти все множество Парето. |
|
|
|
|
|
Существенным преимуществом данного метода перед другими является то, что линейная свертка позволяет решать лишь выпуклые (вогнутые) задачи, в то время как минимаксная оптимизация дает точки Парето для любых задач [11]. Однако минимаксная оптимизация в вычислительном плане сложнее метода взвешенной суммы. Стандартный алгоритм Ремеза не приспособлен к эффективному решению задачи (3.23). В первую очередь это связано с недостаточной скоростью его сходимости, так как в рассматриваемом случае задачу (3.23)
приходится решать многократно. В связи с этим в стандартный алгоритм Ремеза введены процедура вычисления «хороших» начальных значений точек альтернанса и процедура выравнивания максимумов. модифицирован путем введения следующим образом. Схема модифицированного алгоритма Ремеза приведена на рис. 3.2.
При формализации задачи векторной оптимизации УЦОС, например,
122
Начало
K=0
Определение направления поиска
Одномерный поиск
K=K+1
Нет |
Сходимость |
Да |
|
|
|
|
достигнута |
|
Конец
Рис. 3.2 Структурная схема алгоритма минимизации обобщенных критериев
123