9.9. Грубый метод оптимизации

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

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

вычислениям); и третий — массив из улучшений благодаря изменениям в параметрах (этот массив заполняется позже).

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

Следующий этап расчета состоит в измеиеиии первого параметра на величину которая записывается в массиве неопределенностей и относится к первому параметру, и в повторном вычислении функции . Если разность двух значений отрицательна, то считается, что получено улучшение. Поэтому выполняем еще один шаг той же величины и в том же направлении вдоль оси Это продолжается до тех пор, пока не найдется значение Е, которое будет больше или равно предыдущему. Тогда имеем три последовательных значения параметра которые обозначим Если первое изменение Е заключалось в его увеличении или в сохранении прежней величины, то необходимо сменить их стартовое и первое пробное значения вместе со знаком и продолжать двигаться в этом направлении, производя поиск, как и прежде, относительного минимума для как функции от Как только мы найдем его, то окажемся в том же положении, что и прежде. Если обнаружится, что Е возрастает при движении в любом направлении, то имеем ситуацию, подобную предыдущей: три значения с меньшим в середине.

Через эти три значения проводим параболу

где — среднее из этих трех значений координат параметра Минимум параболы приходится на значение

Поэтому минимум имеет место, когда

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

где (интервал шага)

В нашем методе поиска исключено и поэтому не произойдет деления на нуль (если только все три значения не окажутся одинаковыми!). Теперь мы имеем новое

Имея временно оптимизированный первый параметр, необходимо пополнить соответствующие значения в трех массивах. Очевидно, что минимум параболы принимается в качестве новой записи в первом массиве. Можно взять половину изменения от

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

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

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

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

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

Во-вторых, она показывает, что простая процедура оптимизации может быть несостоятельной. Предположим, например (как это будет сделано в гл. 12), что необходимо снизить максимум пульсаций полинома в некотором интервале. Возможно, что один параметр, скажем уменьшая один пик (или провал) полинома, в то же время будет увеличивать один или больше других экстремумов. Следовательно, изменения в будут действовать до тех пор, пока некоторое другое экстремальное значение не дойдет до той же величины, что и первое. В этот момент они образуют острый «угол»

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

В-третьих, мощные процедуры оптимизации в местной библиотеке программ стремятся делать «мощными» в одном или более смыслах. Они могут обеспечить быстрое достижение минимума, однако этот факт только экономит машинное время, что не является особо важным для тех людей, которые эпизодически занимаются расчетом цифровых фильтров. Они могут быть мощными в том смысле, что обеспечивают нахождение минимума для широкого класса поверхностей, включая такие, в которых отыскиваемые впадины извилистые и имеют крутые скаты, так что нужно беспрестанно изменять направления поиска. Кроме того, мощность может относиться к способности точно указывать минимум. Это свойство часто бывает иллюзорным. Если минимум острый и легко определяется, то характеристика фильтра будет изменяться значительно при небольших изменениях в величинах параметров (в том числе и из-за округления при уменьшении длины чисел), тогда как, если этот минимум тупой, то даже при неточном определении места истиииого минимума почти любая близкая точка даст примерно такие же хорошие результаты.

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