Вход на сайт

Научные направления

Поделиться:

Статьи из раздела: Степени заполненности / незаполненности разрядов чисел. Великая теорема Харта. Хартовы тройки чисел

ПРИМЕНЕНИЕ НЕЙРОННЫХ СЕТЕЙ В МОБИЛЬНОМ ПРИЛОЖЕНИИ ДЛЯ ДИАГНОСТИКИ АРТРИТА КИСТЕЙ РУК

Религия Матери Мира, подтвержденная математикой

ДОКАЗАТЕЛЬСТВО ВЕЛИКОЙ ТЕОРЕМЫ ФЕРМА

Эпидемическое моделирование с использованием клеточных автоматов

Статья опубликована в №21 (май) 2015
Разделы: Информационные технологии, Математика
Размещена 10.05.2015. Последняя правка: 09.05.2015.
Просмотров - 2641

Об одной поисковой стратегии для одномерной оптимизации без использования производной

Борисевич Алексей Валерьевич

кандидат технических наук

Санкт-Петербургский государственный политехнический университет

доцент кафедры «Автоматы»

Аннотация:

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

Abstract:

In this paper the one-dimensional optimization algorithm is considered, in case when the direction of search is known. The method is characterized in that if does not require information on the functions derivative. And also the advantage of method is the continuous and unidirectional search trajectory. An analysis of the optimization accuracy and the algorithm convergence is provided. The algorithm behavior is demonstrated in Matlab.

Ключевые слова:

безусловная оптимизация; численные методы; выпуклая функция; сходимость

Keywords:

unconstrained optimization; derivative-free methods; convex function; convergance

УДК 519.6

Введение

Рассматривается задача минимизации скалярной выпуклой непрерывной функции $f: RR \to RR$ на конечном интервале $\displaystyle{\left[{a},{b}\right]}$ . Обозначим $\displaystyle{{x}}^{\cdot}$ – точка минимума: $f(x^*) \le f(x), x \in [a,b]$ , а также $\displaystyle{x}_{{0}}$ – начальное приближение к решению.

Предположение 1. Априори известен знак разности $\displaystyle{{x}}^{\cdot}-{x}_{{0}}$ . Т.е. до начала поиска известно, где относительно $\displaystyle{x}_{{0}}$ находится искомый минимум $\displaystyle{{x}}^{\cdot}$ .

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

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

1. Равномерное изменение аргумента

Обозначим значение функции $\displaystyle{y}={f{{\left({x}\right)}}}$ . Рассмотрим следующий прототип поискового алгоритма, состоящий из двух параллельно выполняющихся действий:

1. Линейно изменять аргумент $\dot x = c$ , где $\displaystyle{c}$ – константа, знак которой выбран заранне так, что $\sign c = \sign ( x^* - x_0)$ , $\displaystyle{x}{\left({0}\right)}={x}_{{0}}$ .

2. Если $|\dot y| = |{df} / {dt} | <\epsilon$ , то прекратить поиск.

Здесь и далее мы будем описывать динамику алгоритма в непрерывном времени, предполагая что дискретизация может быть выполнена тривиально.

Оценим как влияет $\epsilon$ на точность определения точки минимума. Если $\epsilon$ достаточно мало, то стандартным подходом является разложение функции $\displaystyle{f{{\left({x}\right)}}}$ в степенной ряд в окрестности $\displaystyle{{x}}^{\cdot}$ (с учетом, что $\displaystyle{f{'}}{\left({{x}}^{\cdot}\right)}={0}$

Для дальнейшего анализа без потери общности можно предполагать $\displaystyle{{x}}^{\cdot}={0}$ и аппроксимировать функцию в окрестности $\displaystyle{{x}}^{\cdot}$ пораболой:

$f(x) = {1}/{2} f''(x^*) x^2$ .

Отсюда производная по времени

$\dot y = f''(x^*) x \dot x = c f''(x^*) x$ .

Остановка алгоритма осуществляется в момент

$\dot y = c f''(x^*) x = \epsilon$ (1)

Таким образом, абсолютная ошибка определения минимума $\Delta x = x - x^*$ выражается как

$\Delta x = | {\epsilon}/{f''(x^*) c} |$ .

2. Эффект численного дифференцирования

В практических задачах оптимального управления значение показателя y является измеряемой физической величиной, в которой присутствует аддитивный шум. Поэтому для вычисления $\dot y$ используется фильтр верхних частот (ФВЧ), имеющий ограниченную полосу пропускания.
Обозначим $\hat y$ – численная оценка $\dot y$ , полученная с помощью цифрового дифференцирования.

Простейшим для анализа является фильтр первого порядка, описываемый в операторной области следующим образом

$\hat Y(p) = {p}/{\tau p + 1} Y(p) = {1}/{\tau p + 1} \dot Y(p)$ (2)

где $\hat Y(p)$ – операторное отображение $\hat y(t)$ , $\displaystyle{Y}{\left({p}\right)}$ – операторное отображение $\displaystyle{y}{\left({t}\right)}$ .

Тоже самое во временной области:

$\dot \xi = {1}/{\tau}[\dot y - \xi]$ , $\hat y = \xi$ ,

где $\tau$ – постоянная времени фильтра, $\xi$ – переменная состояния.

Известно, что аналитическое выражение реакции системы первого порядка на воздействие u(t) с нулевым начальным состоянием может быть записано в виде

$\hat y = \int_0^t e^{a (t - s)} b u(s) d s$ ,

где $a = -1/\tau$ , $b = 1/\tau$ для рассматриваемой системы.

Поскольку, $\displaystyle{x}{\left({t}\right)}={x}_{{0}}+{c}{t}$ , то при квадратичной аппроксимации целевой функции, получаем

$u(t) = \dot y = f''(x^*) c (x_0 + c t)$ .

Непосредственное интегрирование и упрощение полученного выражения дает:

$\hat y(t) = c f''(x^*) e^{-t/\tau} \cdot (c \tau-x_0) - c f''(x^*) \cdot (-c t + c \tau-x_0)$ .

При малом $\tau$ экспонента в первом слагаемом быстро стремится к 0, отсюда можно записать выражение для установившегося состояния $\displaystyle{t}\gt\gt{0}$ :

$\hat y(t) \to c f''(x^*) \cdot (x_0 + c t - c \tau) = c f''(x^*) \cdot (x(t) - c \tau)$ .

Остановка поиска осуществляется, когда

$c f''(x^*) \cdot (x(t) - c \tau) = \epsilon$ .

Здесь следует сделать комментарий о природе погрешностей остановки поиска. При остановке согласно (1) по идеальной оценке производной $\dot y$ , ошибка возникает в результате того, что поиск заканчивается раньше времени, и значение $\displaystyle{x}{\left({t}\right)}$ не достигает $\displaystyle{{x}}^{\cdot}$ . При использовании ФВЧ для оценки производной $\hat y$ , возникает задержка между действительным значением $\dot y$ и $\hat y$ , в результате поиск останавливается с задержкой c $\tau$ . Отсюда, погрешности, связанные с конечной точностью $\epsilon$ и ограниченной полосой дифференциатора, должны быть взяты с разным знаком:

$\Delta x = | {\epsilon}/{f''(x^*) c} - c \tau |$ (3)

3. Ускорение сходимости

Траектория $\displaystyle{x}{\left({t}\right)}={x}_{{0}}+{c}{t}$ слишком тривиальна и не учитывает ландшафта оптимизируемой функции. Для ускорения поиска предлагается использовать значение производной по времени, согласно измененному правилу:

$\dot x = - k \cdot \hat y$

где $\displaystyle{k}\gt{0}$ – некоторая константа.

Поскольку погрешность установки точки минимума (3) зависит от скорости изменения аргумента x, то для обеспечения заданной точности поиска необходимо ограничить значение $\dot x$ сверху:

$\dot x = \min \{ - k \cdot \hat y, ~ \gamma \cdot c \}$

где $\gamma gt 1$ – отношение максимальной скорости изменения параметра $\displaystyle{x}$ к начальной $\displaystyle{c}$ . Заметим, что эта формула записана для случая $\displaystyle{c}\gt{0}$ , в противном случае, очевидно, операцию взятия минимума необходимо заменить на операцию взятия максимума.

С другой стороны, для обеспечения безусловного прироста скорости сходимости, необходимо исключить случаи когда $|k \cdot \hat y| lt |c|$ .

Отсюда получаем окончательное выражение для изменения аргумента:

$\dot x = \max\{c, ~ \min \{ - k \cdot \hat y, ~ \gamma \cdot c \} \}$

4. Алгоритм

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

В описании алгоритма используются введенные выше параметры $c gt 0, ~ k gt 0, ~ \gamma gt 1, ~ \epsilon gt 0$ . Также используется дополнительный параметр $\displaystyle{t}_{{0}}$ – время, необходимое для определения $\hat y$ в начальный момент, в течение которого выполняется безусловное изменение $\displaystyle{x}$ . Также промежуточная переменная $d \in \{-1,1\}$ используется для обозначения направления поиска.

1. Если $\displaystyle{{x}}^{\cdot}\gt{x}_{{0}}$ , то $\displaystyle{d}\:={1}$ , иначе $\displaystyle{d}\:=-{1}$ .

2. Пока $\displaystyle{t}\lt{t}_{{0}}$ выполнять $\dot x = d \cdot c$ .

3. Пока $|\hat y| gt \epsilon$ выполнять:

3.1 Если $-k \cdot \hat y gt c$

3.1.1 Если $-k \cdot \hat y lt \gamma \cdot c$ , то $\dot x = -d \cdot k \cdot \hat y$ , иначе $\dot x = d \cdot \gamma \cdot c$

иначе

$\dot x = d \cdot c$

Параллельно с выполнением описанного алгоритма осуществляется вычисление $\hat y$ с помощью фильтра верхних частот (2).

5. Анализ сходимости

Поведение алгоритма может быть охарактеризовано с помощью следующей теоремы.

Теорема 1. Если выполняются следующие условия:

$|c| \cdot t_0 lt |x^* - x_0|$ (4)

$t_0 gtgt \tau$ (5)

то алгоритм из параграфа 4 находит локальный минимум функции $\displaystyle{f{{\left({x}\right)}}}$ с точностью

$\Delta x = | {\epsilon}/{f''(x^*) c} - c \tau |$

Доказательство.

Первое условие $|c| \cdot t_0 lt |x^* - x_0|$ означает, что точка минимума $\displaystyle{{x}}^{\cdot}$ не находится внутри интервала $[x_0, x_0 + c \cdot t_0]$ , где остановка алгоритма невозможна.

Благодаря второму условию $t_0 gtgt \tau$ в момент времени $\displaystyle{t}_{{0}}$ переходной процесс в фильтре оценки производной закончился, и отсюда $\hat y(t) = c f''(x^*) \cdot (x(t) - c \tau)$ при линейном изменении $\displaystyle{x}{\left({t}\right)}={x}_{{0}}+{c}{t}$ вблизи $\displaystyle{{x}}^{\cdot}$ .

Поскольку функция $\displaystyle{f{{\left({x}\right)}}}$ выпукла, то это означает, что на интервале $\displaystyle{\left[{x}_{{0}},{{x}}^{\cdot}\right]}$ значение производной $\displaystyle{f{'}}{\left({x}\right)}$ убывает и, соответственно, значение $\dot y = f'(x) \dot x$ также убывает при неувеличивающимся $\dot x$ . Отсюда, после перехода к динамике $\dot x = - k \cdot \hat y$ всегда существует момент времени, где

$c \ge - k \cdot \hat y$

и поиск всегда заканчивается линейным изменением аргумента. Таким образом, являющееся утверждением теоремы соотношение (3) всегда соблюдается в конечной фазе алгоритма. Что и требовалось доказать.

С практической точки зрения условие (4) означает, что начальное приближение $\displaystyle{x}_{{0}}$ находится достаточно далеко от искомого $\displaystyle{{x}}^{\cdot}$ . Удовлетворительной с инженерной точки зрения интерпретацией условия (5) является выбор $t_0 \ge 3 \tau$ .

Моделирование
Предложенный алгоритм был реализован в среде Matlab / Simulink. Для демонстрации работы алгоритма на рисунке 1 представлены результаты применения алгоритма к тривиальной функции $\displaystyle{y}={{x}}^{{2}}$ . Алгоритм завершил работу в точке x = 0,0395; y = 0,0016.

Рисунок 1 - Результат моделирования алгоритма на функции $\displaystyle{y}={{x}}^{{2}}$

Также для тестирования была использована функция с более сложным ландшафтом, график которой приведен на рисунке 2:

$\displaystyle{f{{\left({x}\right)}}}={0.1}{{x}}^{{4}}-{1.65}{{x}}^{{3}}+{9.45}{{x}}^{{2}}-{23.1}{x}+{25.2}$

Рисунок 2 - Полиномиальная тестовая функция

Функция имеет минимум в точке x = 6,4073 где y = -0,3336.

Рисунок 3 - Результат моделирования алгоритма для полиномиальной функции $\displaystyle{f{{\left({x}\right)}}}$

На рисунке 3 представлены результаты применения алгоритма для данной функции. Алгоритм завершил работу в точке x = -0,3332; y = 6,3953.

В обоих случаях использовались одни и те же значения параметров алгоритма: $\displaystyle{x}_{{0}}$ = 0, $\displaystyle{t}_{{0}}$ = 0.2, c = 1, k = 0.5, $\gamma$ = 10, $\epsilon$ = 0.1.

Заключение

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

Метод выгодно отличается тем, что траектория аргумента в процессе поиска непрерывна и не меняет своего направления, что важно в применении к задачам оптимального управления [4-5]. Алгоритм сформулирован в непрерывном времени, приведен анализ точности и его сходимости.

Результаты работы алгоритма продемонстрированы с помощью моделирования в системе Matlab. Реализованные модели алгоритма в Simulink можно скачать по ссылке: https://sites.google.com/site/akpc806a/Ramp_optimization_post.rar?attredirects=0&d=1

Библиографический список:

1. Энергосберегающее векторное управление асинхронными электродвигателями: обзор состояния и новые результаты: Монография / А.В. Борисевич. - М.: НИЦ ИНФРА-М, 2015. - 104 с
2. Salas V. et al. Review of the maximum power point tracking algorithms for stand-alone photovoltaic systems // Solar energy materials and solar cells. – 2006. – Т. 90. – №. 11. – С. 1555-1578.
3. Abdullah M. A. et al. A review of maximum power point tracking algorithms for wind energy systems // Renewable and Sustainable Energy Reviews. – 2012. – Т. 16. – №. 5. – С. 3220-3227.
4. Нестеров Ю. Е. Введение в выпуклую оптимизацию. М.: МЦНМО, 2010. 280 с
5. Rios L. M., Sahinidis N. V. Derivative-free optimization: A review of algorithms and comparison of software implementations // J. Global Optim., 2013. No. 56. P. 1247–1293.

Рецензии:

20.06.2015, 21:35 Каменев Александр Юрьевич
Рецензия: Индекс УДК, пожалуй, следует детализировать. Рекомендуется к печати.

Комментарии пользователей:

20.05.2015, 7:23 Булыгин Владимир Викторович
Отзыв: Хорошая статья. Поэтому удивляет, что так и не дана на нее рецензия.

Оставить комментарий

E-mail: sci@sci-article.ru
©2013-2023 Электронный периодический научный журнал SCI-ARTICLE.RU
Любое использование размещённых на сайте журнала статей и материалов возможно только с обязательной активной ссылкой на сайт журнала «SCI-ARTICLE.RU».

▲
Вверх

E-mail:
Пароль:
Запомнить
	Регистрация/ Забыли пароль?