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

Обобщенный критерий вида (2.12) очень часто бывает наиболее предпочтительным, поскольку в точке минимума функция максимума обладает альтернансными свойствами [21, 47, 48, 79], т.е. имеется несколько отклонений, равных максимальному. Это означает, что при решении минимаксных задач получают более качественные решения, обеспечивающие укладывание характеристик в зоны с максимальным запасом. Однако этот критерий не сохраняют свойства гладкости целевых функций, что требует привлечения специальных методов оптимизации.

Зачастую задача векторной оптимизации УЦОС решается в случае, когда задача (2.12) является линейной минимаксной задачей без ограничений. При скалярной оптимизации решение этой задачи обычно осуществляется методом последовательных чебышевских интерполяций Е. Я. Ремеза [21,79]. Для решения задач векторной оптимизации другого класса устройств этот метод впервые применен в работах [33, 38, 90]. Метод минимакса [21] весьма схож с оптимизацией линейной свертки. Решается задача

, (3.23)

в которой подбором компонент весового вектора можно найти все множество Парето. Существенным преимуществом данного метода перед другими является то, что линейная свертка позволяет решать лишь выпуклые (вогнутые) задачи, в то время как минимаксная оптимизация дает точки Парето для любых задач [11]. Однако минимаксная оптимизация в вычислительном плане сложнее метода взвешенной суммы. Стандартный алгоритм Ремеза не приспособлен к эффективному решению задачи (3.23). В первую очередь это связано с недостаточной скоростью его сходимости, так как в рассматриваемом случае задачу (3.23) приходится решать многократно. В связи с этим в стандартный алгоритм Ремеза введены процедура вычисления «хороших» начальных значений точек альтернанса и процедура выравнивания максимумов. модифицирован путем введения следующим образом. Схема модифицированного алгоритма Ремеза приведена на рис. 3.2.

При формализации задачи векторной оптимизации УЦОС, например, цифровых фильтров с одновременно заданными произвольными АЧХ и ФЧХ (ГВЗ), а также в ряде других случаев задача НЛП (3.1) очень часто формулируется как нелинейная минимаксная [37]:

(3.24)

Введем обозначение . В формуле (3.24) - фиксированный набор индексов. В дальнейшем будем пользоваться также понятиями набора -активных функций и ограничений [21]:

;

(3.25)

,

где

Так же, как и при решении гладкой задачи НЛП (3.1.), существуют два подхода для учета ограничений в задаче (3.24). В первом исходная задача преобразуется к безусловной путем добавления к целевой функции некоторой скалярной функции штрафа, зависящей от функций ограничений и параметров (метод штрафных функций). При этом решается последовательность задач безусловной оптимизации, в промежутках между которыми выполняется коррекция параметров штрафной функции (коэффициентов штрафа). Другой подход основывается на непосредственном учете ограничений: стратегии набора активных ограничений и необходимых условий оптимальности. В дальнейшем при решении нелинейной минимаксной задачи для учета ограничений будем использовать, как и в п.3.2 стратегию набора активных ограничений и необходимых условий оптимальности.

В зависимости от степени учета структуры и особенностей функции максимума можно выделить несколько групп методов, которые можно использовать для решения задачи (3.24): методы сглаживания функции максимума (МСФМ) [11]; методы обобщенного градиентного спуска (ОГС) [99] или  - субградиента; методы  - наискорейшего спуска (МНС) [25]; методы выравнивания максимумов (МВМ) [48, 90]; методы возможных направлений (МВН) [28, 48, 69 - 71]; комбинированные методы (КМ) [54, 67].

В МСФМ негладкая функция аппроксимируется некоторой гладкой целевой функцией, которая затем минимизируется одним из подходящих методов оптимизации. Эти методы аналогичны методу штрафных функций со всеми свойственными ему недостатками. Наиболее часто в качестве сглаженной целевой функции используется среднестепенной критерий (2.14) при больших степенях q, либо его модификации (2.15), (2.22). Для минимизации критериев (2.14), (2.15) и (2.22) в данной работе применяется алгоритмы, рассмотренные в п.3.1 и п.3.2 данной главы. Сглаженная целевая функция, как правило, хуже учитывает свойства функции максимума Q(X) и имеет достаточно сложный "овражный" характер. Поэтому в алгоритмах данной группы многое зависит от эффективности и надежности используемых алгоритмов.

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

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

(3.26)

где означает градиент любой из функций , , составляющих функцию , для которой выполняется условие .

Последовательность шагов _k в этих методах должна удовлетворять условию При этом, сделав в направлении некоторый шаг _k >0, получим точку X^k+1, в которой может оказаться, что , но тем не менее точка X ^k+1 ближе к точке минимума X^*, чем точка X^k, т. е. ||X^k+1 – X^k|| < ||X^k+1 – X^*||. Данный метод выигрывает в простоте, но проигрывает за счет этого в скорости сходимости. По этой причине метод ОГС в данной работе не используется для решения нелинейных минимаксных.

В МНС минимум функции ищется с помощью итерационного процесса типа (3.7) [21]. Шаг _k определяется путем одномерного поиска, а вектор спуска находится из решения следующей вспомогательной задачи. Для малого фиксированного числа из индексов ищется множество -активных функций I_(X). Затем производится процедура выравнивания максимумов , .

Необходимое условие минимакса состоит в том, что выпуклая оболочка L(X^k), представляющая собой множество векторов yE^N вида , где u_i0, и должна содержать в себе начало координат. Если X^k не является точкой минимума, то L(X^k) не содержит начала координат, и вектор , исходящий из X^k, направленный на ближайшую точку L(X^k) и взятый со знаком минус, указывает направление наискорейшего убывания функции в точке X^k. Описанный метод аналогичен методу наискорейшего спуска для гладких функций и характеризуется всеми его недостатками и достоинствами.

После шага в направлении наискорейшего спуска часто бывает полезным возвратится на поверхность равных максимумов задачи (3.24) Для этой цели используется МВМ [48]. В МВМ требуется найти решение системы n - нелинейных уравнений:

(3.27)

где . а , - точки валлепуссеновского альтернанса. Функции _j(X) и точки (j[1,n+1]) отыскиваются заново на каждой итерации.

В случае, если область D задается линейными ограничениями, для решения задачи (3.24) можно использовать МВН, в котором направление поиска на -й итерации определяется из решения задачи линейного программирования (ЛП) [4, 69 - 71]

min Z

(3.28)

(3.29)

(3.30)

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

Шаг вдоль найденного направления определяется с помощью одномерного поиска. Метод вырабатывает последовательность значений {Z^k}  0. Условие Z^k = 0 эквивалентно необходимому условию минимакса [71], однако на практике, как правило, ограничиваются условием |Z^k|  ₀, где ₀ - требуемая точность решения. Однако вычислительный опыт автора свидетельствует, что МВН, так же, как и другие ранее рассмотренные методы, обладает малой скоростью сходимости при решении задачи оптимизации УЦОС (3.24). Анализ показал, что причиной плохой сходимости рассмотренных методов является существенная «овражность» целевой функции (3.24). Одной из причин существенной овражности является плохая масштабированность вектора варьируемых параметров.

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

Для преодоления указанных выше трудностей предлагается перед формированием направления поиска выполнить преобразование пространства переменных (E^N  E^N). Сущность метода состоит во введении по каждой из осей пространства E^N масштабных множителей _i, i[1,N] [10, 37]. Нормировка производится по принципу

_i(X_{i max} – X_{i min}) = 1.

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

где K_i - нормализующий коэффициент.

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

Во всех рассмотренных методах на протяжении всего процесса минимизации функции применялся один и тот же алгоритм поиска. Вместе с тем характер поведения этой функции существенно меняется на различных этапах поиска. Эту особенность и пытались учесть авторы различных комбинированных методов. Так, в работе [67] предлагалось в случае одной активной функции использовать метод переменного порядка. В работе [54] предложено использовать двухэтапную процедуру поиска. На первом этапе происходит движение методом наискорейшего спуска до попадания в окрестность гребня, образованного пересечением гиперповерхностей нескольких активных функций. Поиск на втором этапе осуществляется в соответствии со стратегией метода проекции вектора-градиента и требует последовательности выполнения пар шагов. Первый шаг выполняется в сторону гребня, а второй - вдоль него. Этот метод успешно применяется для решения некоторых задач оптимизации электронных схем, однако из-за ряда недостатков вычислительного характера непригоден для решения задач оптимизации УЦОС. Процедура идентификации гребней предусматривает добавление только одной активной функции. На каждой итерации второго этапа дважды выполняется перемножение матриц и дважды решается система линейных уравнений. Если же гребень существенно нелинейный, то перемещение по касательной к нему приведет к тому, что на первом шаге последующей итерации придется неоднократно решать систему линейных уравнений, чтобы снова попасть в -окрестность. Скорость сходимости метода только линейная. В работах [67, 101 - 106] также рассматриваются двухэтапные методы решения задачи (3.24), однако они также не учитывают особенности и специфику задач оптимального проектирования УЦОС.

Таким образом, качественное исследование существующих методов минимаксной оптимизации показало, что наиболее эффективными являются комбинированные методы, использующие растяжение пространства по координатным осям для устранения существенной «овражности» ЦФ. В коллектив оптимизирующих алгоритмов для решения задачи (3.24) целесообразно включить методы ВМ и ВН.