кандидат технических наук
Санкт-Петербургский государственный политехнический университет
доцент кафедры «Автоматы»
УДК 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 Булыгин Владимир Викторович Отзыв: Хорошая статья. Поэтому удивляет, что так и не дана на нее рецензия. |