Материал: Методы оптимального проектирования устройств цифровой обработки и защиты информации. Борисов В.И., Гармонов А.В
Наиболее тривиальный способ решения задач оптимального проектирования
любого сложного технического обьекта, в том числе и
Начало
Рис 3.1 Схема алгоритма метода поисковой оптимизации обобщенных критериев
оптимальности УЦОС Выбор обобщенного
критерия, параметрических ограничений и Qn(0)
Зондирование пространства параметров,
сортировка и оставление таблиц
испытаний
Пересчет порогового значения обобщенного критерия и параметрических ограничений
Критерий
останова выполнения?
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Оптимальное |
|
Принятие решения о |
|||||
|
|||||||
|
продолжении |
или |
|||||
решение |
|
||||||
|
прекращении |
|
|||||
получено? |
|
||||||
поиска |
|||||||
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Выдача оптимального
решения
Конец
114
УЦОС, заключается в минимизации среднестепенных обобщенных критериев оптимальности типа (2.14), (2.15) или (2.22). На практике также распространен частный случай среднестепенного критерия (2.14) при q=2, получивщий название среднеквадратичного [47, 48].
Использование среднестепенных критериев оптимальности в задачах проектирования УЦОС, где, по существу, необходим минимаксный подход, оправдано,
прежде всего, с позиций явления плохой обусловленности. Развитая в настоящее время техника решения негладких оптимизационных задач достаточно сложна и в невыпуклой овражной ситуации многие алгоритмы теряют эффективность. В то же время излагаемые в данной главе методы позволяют получить удовлетворительные результаты для невыпуклых овражных функционалов при условии их гладкости. При этом удается использовать структурные особенности критериев (2.14), (2.15) и (2.22)
для увеличения эффективности соответствующих вычислительных алгоритмов.
Задача оптимизации обобщенных критериев (2.14), (2.15) и (2.22)
формулируется как задача НЛП вида (3.1). Характерной особенностью этой задачи является "гладкость" целевых функций [3, 5, 13, 47, 48]. Подходы к решению этой задачи при наличии ограничений можно разбить на два класса [3, 5, 7, 11, 12 - 13, 18, 28, 93]. В методах первого класса ограничения учитываются непосредственно, с помощью стратегии активного набора ограничений (набора ограничений, равных нулю в данной точке) и необходимых условий оптимальности [11]. Ко второму классу относятся те методы, в которых осуществляется безусловная минимизация функции, получающаяся добавлением штрафа за нарушение ограничений либо к целевой функции, либо функции Лагранжа исходной задачи (3.1) [28].
В первом классе следует выделить метод проекции градиента [48], в котором задача НЛП решалась лишь для случая линейных ограничений. В последующих работах этого направления делались попытки учесть кривизну целевой функции и ограничений (алгоритм обобщенного приведенного градиента) [99], а также с использованием более эффективных способов корректировки матрицы вторых производных [18]. В целом же следует отметить,
что методами первого класса наиболее эффективно решается задача НЛП с линейными ограничениями.
115
Методы второго класса, среди которых большее внимание уделяется применению множителей Лагранжа, обычно применяют при наличии нелинейных ограничений. Оценки множителей Лагранжа [28, 93] вычисляются в большинстве современных алгоритмов.
Изначально для решения задачи НЛП с нелинейными ограничениями использовался метод штрафных функций. Позднее был разработан метод барьерных функций с включением в него процедуры экстраполяции. Этот метод, известный под названием SIMT, успешно применялся для решения практических задач [28]. Однако и он имеет ряд недостатков,
вызванных его плохой обусловленностью. В последующих работах этого направления были разработаны новые штрафные функции, свободные от этого недостатка, а также не имеющие особых точек и позволяющие быстро и с минимальным числом вычислений целевой функции определить ее минимум [28]. Это позволило без модификаций применить процедуру безусловной минимизации для решения ряда задач НЛП за приемлемое время.
Эффективность этой процедуры существенно влияет на эффективность алгоритма оптимизации.
В работе [18] при сравнении этих двух подходов отмечалось, что второй "считается в настоящее время неэффективным с точки зрения объема вычислений". В работе [11] на основании большого опыта решения различных задач оптимизации (в том числе и вида (2.12)
утверждается, что алгоритмы, использующие второй подход, "крайне ненадежны, сходятся очень медленно и критерий прекращения счета по стабилизации результата с заданным числом знаков создает иллюзию успешного решения задачи".
Наибольшее развитие среди методов первой группы получили квазиньютоновские методы (КНМ) и градиентные методы сопряженных направлений, в которых вычисляются значения целевой функции и ее градиента. При этом основная итерационная формула имеет вид
X (k 1) X (k ) |
k |
G(k ) , |
(3.7) |
|
|
|
где X (k 1) , X (k ) - точки в пространстве варьируемых параметров, являющиеся приближением
оптимального решения X * ; G(k ) - вектор спуска (направления поиска); k - шаг вдоль
направления G(k ) .
Все методы безусловной минимизации отличаются друг от друга способом
определения вектора G(k ) и шага k . В КНМ направление поиска находится по формуле:
G (k ) H (k ) Q( X (k ) ) , |
(3.8) |
116
где Q( X (k ) ) - градиент обобщенного критерия; H (k ) - матрица, аппроксимирующая
обратную матрицу Гессе целевой функции [3, 18].
Основные разработки в КНМ были связаны с поисками наиболее точных формул
корректировки матрицы H (k ) |
от |
итерации к |
итерации. При этом первоначально для |
||||||||||
вычисления шага |
k |
применялась процедура точного одномерного поиска, |
в результате |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
которой определялось такое значение |
k |
|
на каждой итерации, которое минимизировало |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
одномерную функцию |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Q( |
) |
Q(X (k ) |
|
|
k |
G(k ) ) . |
|
|
(3.9) |
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим наиболее употребительные формулы коррекции, а также сравним их |
|||||||||||||
относительные преимущества и недостатки. |
|
|
|
|
|
|
|
||||||
Введем обозначения |
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
(k ) |
k |
G(k ) |
X (k 1) |
X (k ) ; |
(3.10) |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(k ) |
g (k 1) |
|
g (k ) , |
|
|
(3.11) |
|||
Тогда разложение в ряд Тейлора величины |
k будет иметь вид [26] |
|
|||||||||||
|
|
|
|
(k ) |
B(k ) |
(k ) |
R( (k ) ) , |
|
|
||||
где B (k ) B( X (k ) ) - матрица вторых производных (Гессиан) целевой функции [26]. |
|||||||||||||
Остаток R( ) , |
включающий |
члены более высокого порядка, равен нулю для |
|||||||||||
квадратичной функции, поэтому им можно пренебречь. |
Поскольку (k ) и |
k определены |
|||||||||||
только после линейного поиска вдоль направления G(k ) , |
справедливо лишь приближенное |
||||||||||||
равенство H (k ) (k ) |
|
(k ) , так как |
H |
B 1 . |
Поэтому |
H (k 1) должно быть выбрано таким |
|||||||
образом, чтобы выполнялось строгое равенство |
|
|
|
|
|||||||||
|
|
|
|
H (k |
1) (k ) |
|
|
(k ) , |
|
|
(3.12) |
||
получившее название квазиньютоновского условия [93]. Существуют различные способы удовлетворения этого условия. При этом основная задача состоит в построении достаточно простой формулы коррекции, требующей небольшого объема вычислений и вместе с тем эффективной.
Наиболее простой является формула коррекции единичного ранга (иногда ее
называют формулой Бройдена) [3, 18, 93]: |
|
|
|
||
H k 1 H |
( |
H )( |
H )T |
, |
(3.13) |
|
( |
H )T |
|||
|
|
|
|
||
117
где второе слагаемое представляет собой n n матрицу единичного ранга. Здесь и в дальнейшем для сокращения обозначений индекс k в правой части формулы коррекции будет опущен. Примечательной особенностью этой формулы является то, что для нее не требуется производить точный линейный поиск. Более того, для сходимости алгоритма не обязательно, чтобы направление поиска определялось по формуле G (k ) 
H (k ) g (k ) . Однако формула (3.13) имеет два существенных недостатка [93]:
-она не гарантирует положительную определенность матрицы H (k ) даже для квадратичных функций;
-знаменатель во втором слагаемом может стать близким или равным нулю, что приведет к срыву процесса минимизации, и поэтому практический алгоритм должен включать в себя дополнительные приемы, позволяющие преодолеть эти недостатки, что в общем нельзя признать наилучшим выходом.
Другой формулой коррекции, получившей широкое распространение в прошлом при решении различных задач оптимизации, является формула Давидона-Флетчера-Пауэлла
(ДФП) [93]:
k 1 |
|
|
T H |
T H |
|
||
H ДФП |
H |
|
|
|
|
|
(3.14) |
T |
|
|
|
T H |
|||
|
|
|
|
|
|
||
В первых программных реализациях метода ДФП применялся очень точный линейный поиск, что позволяло получить хорошие результаты, но требовало большого числа вычислений целевой функции. Дальнейшие исследования формулы (3.14) при менее точном линейном поиске показали, что в этом случае она уступает другим формулам коррекции [18, 93]. Поэтому в настоящее время метод ДФП признан не самым эффективным методом из класса КНМ [93].
Не смотря на то, что все матрицы H (k ) в этом методе должны быть положительно определены, из-за ошибок округления в практических расчетах на ЭВМ положительная определенность матрицы может быть потеряна. Это приведет к шагу в направлении возрастания целевой функции и преждевременному окончанию работы алгоритма. Во избежании этого производится проверка условия
T |
0 |
(3.15) |
|
||
выполнение которого обеспечивает положительную определенность матрицы |
H (k 1) , если |
|
матрица H (k ) также положительно определена. В случае невыполнения условия (3.15) на каком-либо шаге минимизации, матрица H (k 1) заменяется на единичную.
118