кандидат технических наук
Санкт-Петербургский государственный политехнический университет
доцент кафедры «Автоматы»
УДК 519.6
Введение
Рассматривается задача минимизации скалярной выпуклой непрерывной функции на конечном интервале
. Обозначим
– точка минимума:
, а также
– начальное приближение к решению.
Несмотря на то, что такая постановка задачи кажется тривиальной и непрактичной, в действительности ряд технических приложений сводится к оптимизации подобного рода. Например, мощность потерь в векторно управляемом асинхронном электроприводе является выпуклой функцией от тока намагничивания ротора [1]. При этом заранее известно по характеристикам переходных процессов при изменении нагрузки, необходимо ли уменьшить или увеличить ток для достижения оптимума. Аналогичная задача, известная как отслеживание точки максимальной мощности, возникает в преобразователях для солнечных панелей [2] или ветрогенераторов [3].
Целью статьи является разработка и анализ алгоритма минимизации скалярной функции, в условиях когда доступны только значения функции. Алгоритм отличается тем, что достигается непрерывная однонаправленная траектория поиска, а также простотой концепции и программной реализации.
1. Равномерное изменение аргумента
Обозначим значение функции . Рассмотрим следующий прототип поискового алгоритма, состоящий из двух параллельно выполняющихся действий:
1. Линейно изменять аргумент , где
– константа, знак которой выбран заранне так, что
,
.
2. Если , то прекратить поиск.
Здесь и далее мы будем описывать динамику алгоритма в непрерывном времени, предполагая что дискретизация может быть выполнена тривиально.
Оценим как влияет на точность определения точки минимума. Если
достаточно мало, то стандартным подходом является разложение функции
в степенной ряд в окрестности
(с учетом, что
Для дальнейшего анализа без потери общности можно предполагать и аппроксимировать функцию в окрестности
пораболой:
.
Отсюда производная по времени
.
Остановка алгоритма осуществляется в момент
(1)
Таким образом, абсолютная ошибка определения минимума выражается как
.
2. Эффект численного дифференцирования
В практических задачах оптимального управления значение показателя y является измеряемой физической величиной, в которой присутствует аддитивный шум. Поэтому для вычисления используется фильтр верхних частот (ФВЧ), имеющий ограниченную полосу пропускания.
Обозначим – численная оценка
, полученная с помощью цифрового дифференцирования.
Простейшим для анализа является фильтр первого порядка, описываемый в операторной области следующим образом
(2)
где – операторное отображение
,
– операторное отображение
.
Тоже самое во временной области:
,
,
где – постоянная времени фильтра,
– переменная состояния.
Известно, что аналитическое выражение реакции системы первого порядка на воздействие u(t) с нулевым начальным состоянием может быть записано в виде
,
где ,
для рассматриваемой системы.
Поскольку, , то при квадратичной аппроксимации целевой функции, получаем
.
Непосредственное интегрирование и упрощение полученного выражения дает:
.
При малом экспонента в первом слагаемом быстро стремится к 0, отсюда можно записать выражение для установившегося состояния
:
.
Остановка поиска осуществляется, когда
.
Здесь следует сделать комментарий о природе погрешностей остановки поиска. При остановке согласно (1) по идеальной оценке производной , ошибка возникает в результате того, что поиск заканчивается раньше времени, и значение
не достигает
. При использовании ФВЧ для оценки производной
, возникает задержка между действительным значением
и
, в результате поиск останавливается с задержкой c
. Отсюда, погрешности, связанные с конечной точностью
и ограниченной полосой дифференциатора, должны быть взяты с разным знаком:
(3)
3. Ускорение сходимости
Траектория слишком тривиальна и не учитывает ландшафта оптимизируемой функции. Для ускорения поиска предлагается использовать значение производной по времени, согласно измененному правилу:
где – некоторая константа.
Поскольку погрешность установки точки минимума (3) зависит от скорости изменения аргумента x, то для обеспечения заданной точности поиска необходимо ограничить значение сверху:
где – отношение максимальной скорости изменения параметра
к начальной
. Заметим, что эта формула записана для случая
, в противном случае, очевидно, операцию взятия минимума необходимо заменить на операцию взятия максимума.
С другой стороны, для обеспечения безусловного прироста скорости сходимости, необходимо исключить случаи когда .
Отсюда получаем окончательное выражение для изменения аргумента:
4. Алгоритм
В этом параграфе мы сформулируем окончательный алгоритм для поиска минимума с учетом сказанного в предыдущих разделах.
В описании алгоритма используются введенные выше параметры . Также используется дополнительный параметр
– время, необходимое для определения
в начальный момент, в течение которого выполняется безусловное изменение
. Также промежуточная переменная
используется для обозначения направления поиска.
1. Если , то
, иначе
.
2. Пока выполнять
.
3. Пока выполнять:
3.1 Если
3.1.1 Если , то
, иначе
иначе
Параллельно с выполнением описанного алгоритма осуществляется вычисление с помощью фильтра верхних частот (2).
5. Анализ сходимости
Поведение алгоритма может быть охарактеризовано с помощью следующей теоремы.
Теорема 1. Если выполняются следующие условия:
(4)
(5)
то алгоритм из параграфа 4 находит локальный минимум функции с точностью
Доказательство.
Первое условие означает, что точка минимума
не находится внутри интервала
, где остановка алгоритма невозможна.
Благодаря второму условию в момент времени
переходной процесс в фильтре оценки производной закончился, и отсюда
при линейном изменении
вблизи
.
Поскольку функция выпукла, то это означает, что на интервале
значение производной
убывает и, соответственно, значение
также убывает при неувеличивающимся
. Отсюда, после перехода к динамике
всегда существует момент времени, где
и поиск всегда заканчивается линейным изменением аргумента. Таким образом, являющееся утверждением теоремы соотношение (3) всегда соблюдается в конечной фазе алгоритма. Что и требовалось доказать.
С практической точки зрения условие (4) означает, что начальное приближение находится достаточно далеко от искомого
. Удовлетворительной с инженерной точки зрения интерпретацией условия (5) является выбор
.
Моделирование
Предложенный алгоритм был реализован в среде Matlab / Simulink. Для демонстрации работы алгоритма на рисунке 1 представлены результаты применения алгоритма к тривиальной функции . Алгоритм завершил работу в точке x = 0,0395; y = 0,0016.
Рисунок 1 - Результат моделирования алгоритма на функции
Также для тестирования была использована функция с более сложным ландшафтом, график которой приведен на рисунке 2:
Рисунок 2 - Полиномиальная тестовая функция
Функция имеет минимум в точке x = 6,4073 где y = -0,3336.
Рисунок 3 - Результат моделирования алгоритма для полиномиальной функции
На рисунке 3 представлены результаты применения алгоритма для данной функции. Алгоритм завершил работу в точке x = -0,3332; y = 6,3953.
В обоих случаях использовались одни и те же значения параметров алгоритма: = 0,
= 0.2, c = 1, k = 0.5,
= 10,
= 0.1.
Заключение
В настоящей работе был рассмотрен алгоритм поиска локального экстремума скалярной функции, не использующий информацию о производной.
Метод выгодно отличается тем, что траектория аргумента в процессе поиска непрерывна и не меняет своего направления, что важно в применении к задачам оптимального управления [4-5]. Алгоритм сформулирован в непрерывном времени, приведен анализ точности и его сходимости.
Результаты работы алгоритма продемонстрированы с помощью моделирования в системе Matlab. Реализованные модели алгоритма в Simulink можно скачать по ссылке: https://sites.google.com/site/akpc806a/Ramp_optimization_post.rar?attredirects=0&d=1
Рецензии:
20.06.2015, 21:35 Каменев Александр Юрьевич
Рецензия: Индекс УДК, пожалуй, следует детализировать. Рекомендуется к печати.
Комментарии пользователей:
20.05.2015, 7:23 Булыгин Владимир Викторович Отзыв: Хорошая статья. Поэтому удивляет, что так и не дана на нее рецензия. |