3.2 Алгоритм минимизации среднестепенных критериев оптимальности устройств цифровой обработки сигналов

Наиболее тривиальный способ решения задач оптимального проектирования любого сложного технического объекта, в том числе и УЦОС, заключается в минимизации среднестепенных обобщенных критериев оптимальности типа (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]. В целом же следует отметить, что методами первого класса наиболее эффективно решается задача НЛП с линейными ограничениями.

Методы второго класса, среди которых большее внимание уделяется применению множителей Лагранжа, обычно применяют при наличии нелинейных ограничений. Оценки множителей Лагранжа [28, 93] вычисляются в большинстве современных алгоритмов.

Изначально для решения задачи НЛП с нелинейными ограничениями использовался метод штрафных функций. Позднее был разработан метод барьерных функций с включением в него процедуры экстраполяции. Этот метод, известный под названием SIMT, успешно применялся для решения практических задач [28]. Однако и он имеет ряд недостатков, вызванных его плохой обусловленностью. В последующих работах этого направления были разработаны новые штрафные функции, свободные от этого недостатка, а также не имеющие особых точек и позволяющие быстро и с минимальным числом вычислений целевой функции определить ее минимум [28]. Это позволило без модификаций применить процедуру безусловной минимизации для решения ряда задач НЛП за приемлемое время.

Эффективность этой процедуры существенно влияет на эффективность алгоритма оптимизации.

В работе [18] при сравнении этих двух подходов отмечалось, что второй "считается в настоящее время неэффективным с точки зрения объема вычислений". В работе [11] на основании большого опыта решения различных задач оптимизации (в том числе и вида (2.12) утверждается, что алгоритмы, использующие второй подход, "крайне ненадежны, сходятся очень медленно и критерий прекращения счета по стабилизации результата с заданным числом знаков создает иллюзию успешного решения задачи".

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

, (3.7)

где - точки в пространстве варьируемых параметров, являющиеся приближением оптимального решения ; - вектор спуска (направления поиска); - шаг вдоль направления .

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

, (3.8)

где - градиент обобщенного критерия; - матрица, аппроксимирующая обратную матрицу Гессе целевой функции [3, 18].

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

. (3.9)

Рассмотрим наиболее употребительные формулы коррекции, а также сравним их относительные преимущества и недостатки.

Введем обозначения

; (3.10)

, (3.11)

Тогда разложение в ряд Тейлора величины ^k будет иметь вид [26]

,

где - матрица вторых производных (Гессиан) целевой функции [26].

Остаток , включающий члены более высокого порядка, равен нулю для квадратичной функции, поэтому им можно пренебречь. Поскольку и ^k определены только после линейного поиска вдоль направления , справедливо лишь приближенное равенство , так как . Поэтому должно быть выбрано таким образом, чтобы выполнялось строгое равенство

, (3.12)

получившее название квазиньютоновского условия [93]. Существуют различные способы удовлетворения этого условия. При этом основная задача состоит в построении достаточно простой формулы коррекции, требующей небольшого объема вычислений и вместе с тем эффективной.

Наиболее простой является формула коррекции единичного ранга (иногда ее называют формулой Бройдена) [3, 18, 93]:

(3.13)

где второе слагаемое представляет собой nn матрицу единичного ранга. Здесь и в дальнейшем для сокращения обозначений индекс в правой части формулы коррекции будет опущен. Примечательной особенностью этой формулы является то, что для нее не требуется производить точный линейный поиск. Более того, для сходимости алгоритма не обязательно, чтобы направление поиска определялось по формуле . Однако формула (3.13) имеет два существенных недостатка [93]:

- она не гарантирует положительную определенность матрицы даже для квадратичных функций;

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

Другой формулой коррекции, получившей широкое распространение в прошлом при решении различных задач оптимизации, является формула Давидона-Флетчера-Пауэлла (ДФП) [93]:

(3.14)

В первых программных реализациях метода ДФП применялся очень точный линейный поиск, что позволяло получить хорошие результаты, но требовало большого числа вычислений целевой функции. Дальнейшие исследования формулы (3.14) при менее точном линейном поиске показали, что в этом случае она уступает другим формулам коррекции [18, 93]. Поэтому в настоящее время метод ДФП признан не самым эффективным методом из класса КНМ [93].

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

, (3.15)

выполнение которого обеспечивает положительную определенность матрицы , если матрица также положительно определена. В случае невыполнения условия (3.15) на каком-либо шаге минимизации, матрица заменяется на единичную.

Кроме того в методе ДФП, матрица может стать неопределенной или почти неопределенной. Это может произойти в том случае, если величина знаменателя будет близка или равна нулю, что вызовет переполнение разрядной сетки ЭВМ или очень большой шаг в направлении . Во избежании этого в ряде исследований предлагалось заменить матрицу на единичную через каждые итераций, что позволяет обеспечить сходимость к стационарной точке. Но скорость сходимости метода при этом существенно замедляется.

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

, (3.16)

то есть косинус угла между и меньше некоторого малого , а матрицу также следует заменить на единичную или на другую, положительно определенную матрицу.

Улучшенными вычислительными возможностями обладает метод Бройдена-Флетчера-Гольдфарба-Шанно (БФГШ), в котором матрица определяется из выражения [48,93]:

(3.17)

Его основным преимуществом является малая критичность к точности линейного поиска, что делает его весьма эффективным с точки зрения объема вычислений. Формула коррекции (3.15) сохраняет все важные теоретические свойства КНМ. Кроме того, теоретически доказана глобальная сходимость метода БФГШ с приближенным линейным поиском.

Соотношения (3.13) и (3.15) в своей линейной комбинации образуют однопараметрическое семейство формул коррекции второго ранга, получившее название семейства Бройдена [18, 48, 93]:

. (3.18)

Это семейство включает в себя и формулу ДФП (Ф=0), и формулу БФГШ (Ф=1), и ряд других формул. Важным является то, что многие свойства формул коррекции ДФП и БФГШ являются общими для всего семейства формул (3.17) В несколько преобразованном виде с учетом выражений (3.14), (3.15) формулу (3.18) можно представить так:

(3.19)

где

Анализ собственных чисел матрицы показывает, что ее положительная Ф определенность будет обеспечена, если параметр будет удовлетворять условию [3, 12, 18, 93]:

(3.20)

где .

Для квадратичных функций Флетчер показал, что собственные числа матрицы монотонно стремятся к единице в том и только в том случае, когда параметры . Это означает, что стабильные формулы коррекции ограничиваются лишь выпуклым классом формул, принадлежащих семейству (3.19). Для выбора значения параметра Флетчер предложил выполнять проверку следующего условия [93]:

. (3.21)

При её выполнении , и для коррекции используется формула БФГШ. В противном случае и применяется формула ДФП. Этот метод в сочетании с процедурой приближенного линейного поиска хорошо зарекомендовал себя при решении ряда тестовых задач и в настоящее время широко используется во многих программах оптимизации.

В первых программах, использовавших целевую функцию вида (2.14), предпринимались попытки решать задачу оптимизации как общую задачу НЛП с последовательным увеличением от итерации к итерации [28]. Это приводило к потере точности и устойчивости вычислительного процесса вследствие оперирования с очень большими и очень малыми числами (т.е. задача была плохо обусловлена). Отметим, что целевая функция (2.15) свободна от этого недостатка и входящий в нее показатель степени принимает небольшие положительные целочисленные значения. Поэтому на практике при решении задачи оптимизации УЦОС чаще применяется целевая функция (2.15).

Решение задач минимизации обобщенных критериев оптимальности рассмотренными методами может быть представлено следующим алгоритмом:

Шаг 1. Установить .

Шаг 2. Определить направление поиска .

Шаг 3. Решить задачу одномерного поиска

Шаг 4. Установить ; если не выполнено условие останова, то перейти к шагу 2.

Повышение эффективности решения поставленной задачи означает уменьшение общего количества определений целевой функции на шагах 2 и 3. Рассмотрим вопросы уменьшения количества определений целевой функции на шаге 3.

В настоящей работе использован алгоритм одномерной минимизации, построенный на приближенном вычислении целевой функции, изложенном в п. 2.2. Его применение тем более целесообразно, чем сложнее математическая модель УЦОС, расчет которой необходим для вычисления значения целевой функции (обобщенного критерия). Здесь минимизация целевой функции сведена к многошаговой процедуре, на каждом -том шаге которой методом дихотомии [31] минимизируется не функция , а ее приближенное значение и в точке минимума приближенной функции рассчитывается относительная погрешность расчета функции. Особенность используемого алгоритма заключается в том, что каждая из функций заменяется параболой (см. п. 2.2).

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

Кроме того в реализованном алгоритме направление движения к оптимуму на шаге 2 определяется по формуле

, (3.22)

где

.

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