Знакомство с оптимизацией

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

В процессе выполнения этого урока вы узнаете:

1. Что такое оптимизация и как выглядит формальная постановка оптимизационной задачи;

2. Какие бывают задачи оптимизации;

3. Что такое целевая функция и зачем она нужна для решения задачи оптимизации;

1.  Определение оптимизации

Оптимизация - процесс поиска наилучшего (оптимального) варианта решения задачи с заданной целевой функцией, функциями ограничений и критериями сходимости решения задачи.

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

2.  Постановка задачи оптимизации

Задача оптимизации математически формулируется следующим образом:

(1)\[\begin{split}\left\{ \begin{aligned} & \min_{x} f(x) \\ & x \in \chi \end{aligned} \right.\end{split}\]

В задаче оптимизации (1) используются следующие обозначения:

• \(f\) - целевая функция для решения оптимизационной задачи,

• \(x\) - параметр функции (или расчётная точка),

• \(\chi\) - множество допустимых значений параметра функции.

Значение \(x\), которое принадлежит \(\chi\) и которое минимизирует целевую функцию \(f\) является решением задачи оптимизации или параметром (точкой) минимума, обозначаемым \(x^{*}\).

В задаче оптимизации (1) параметр \(x\) может быть как скаляром, представленным в виде вещественного числа (double в Java), так и вектором, представленным в виде набора \(n\) вещественных чисел (3).

(2)\[x = [x_1, x_2, ..., x_n]\]

Целевая функция - функция \(f\), параметр \(x\) которой изменяется оптимизационным алгоритмом с целью достижения минимального значения функции.

3.  Критические точки

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

Критические точки одномерной функции

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

Линии, точки	Описание
Синяя линия	Целевая функция \(f(x) = 5 \cdot \cos(x) + 0.5 \cdot (x - 1.5 \cdot \pi)^2\), \(x \in [0; 11]\)
Оранжевая точка	Точка локального минимума
Зелёная точка	Точка глобального минимума

Критические точки - точки целевой функции \(f(x)\), в которых производная \(f'(x^{*})\) равна нулю. В точке локального минимума \(f'(x^{*}) = 0\) и \(f''(x^{*}) > 0\). Точка глобального минимума имеет наименьшее значение \(f(x)\) на заданном множестве \(x \in \chi\).

Примечание

Также к критическим точкам относятся следующие точки:

• Точки перегиба функции, где \(f''(x^{*}) = 0\) и \(f''\) меняет знак в области данной точки;

• Точки, где производная не существует.

Такие точки в рамках данного урока рассматриваться не будут.

Если оптимизационный алгоритм предназначен для поиска точки локального минимума, то он решает задачу локальной оптимизации. Алгоритм глобальной оптимизации нацелен на поиск точки глобального минимума.

Также к оптимизации относят распространённую задачу поиска корня целевой функции, когда необходимо определить такой \(x\), при котором выполняется условие \(f(x) = \text{const}\). Данная задача будет рассмотрена в рамках отдельного урока.

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

4.  Пример поиска локального минимума параболы

Пусть целевая функция имеет вид следующего полинома \(f(x) = (x - 5)^2 - 20\), для которой известно аналитическое решение. Такая простая функция позволит сосредоточиться на получении навыков работы с Оптимизатором платформы REPEAT VISION.

Парабола со смещением

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

Линии, точки	Описание
Синяя линия	Целевая функция \(f(x) = (x - 5)^2 - 20\), \(x \in [0; 10]\)
Оранжевая точка	Точка локального минимума

4.1.  Аналитическое решение

Парабола обладает производной \(f'(x) = 2 \cdot (x - 5)\), которая равна нулю при \(x^{*} = 5\), а также выполняется условие \(f''(x^{*}) > 0\). Минимум целевой функции \(f(x^{*})\) равен -20.

4.2.  Создание модели в REPEAT VISION

Для создания модели вычисления целевой функции \(f(x) = (x - 5)^2 - 20\) на платформе REPEAT VISION требуется добавить в новый проект, с именем, например, Парабола со смещением, 4 блока библиотеки Автоматика.

Модель расчёта значений параболы в REPEAT VISION

Сначала в проект добавляется блок №1 Константа со свойством Значение константы, равным 0. Данный блок будет использоваться в качестве параметра \(x\) (см. уравнение (1)) целевой функции \(f(x)\).

Далее в проект добавляется блок №2 Смещение со свойством Смещение, равным -5. Данный блок будет использоваться для вычисления смещения \(x - 5\).

Затем добавляется блок №3 Возведение в постоянную степень, со свойством Показатель степени, равным 2. Данный блок будет использоваться для возведения в квадрат ранее вычисленного значения, \((x - 5)^2\).

В завершении подготовки модели необходимо добавить блок №4 Смещение со свойством Смещение, равным -20. Данный блок выполняет последнюю операцию в вычислении целевой функции \(f(x) = (x - 5)^2 - 20\).

Для данной стационарной постановки задачи достаточно будет использовать следующие настройки проекта:

Время моделирования \([с]\)	Шаг интегрирования \([мс]\)	Шаг дискретизации \([мc]\)
0.1	50	50

В следующем разделе выполняется настройка оптимизатора для получения решения оптимизационной задачи.

4.3.  Настройка оптимизатора

Для настройки оптимизатора необходимо нажать на иконку Оптимизация на нижней панели.

Расположение иконки Оптимизация на нижней панели интерфейса REPEAT VISION

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

Основное

В разделе Основное необходимо применить следующие настройки.

Оптимизационная задача	Бюджет оптимизации	Обработка нефизичных величин
Локальная оптимизация	25	Завершить оптимизацию с ошибкой в журнале

Бюджет оптимизации - это количество доступных обращений оптимизатора к расчётной модели вычисления целевой функции. Каждый раз, когда алгоритм передаёт целевой функции очередное значение параметра \(x\) и получает в ответ новое значение целевой функции \(f(x)\), то бюджет уменьшается на 1. Когда бюджет исчерпан, оптимизация принудительно останавливается.

Подсказка

Для простых, гладких, непрерывных целевых функций, схожих с квадратичными функциями, достаточно небольшого бюджета (\(10 \leq budget \leq 100\)) для решения задачи локальной оптимизации.

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

Алгоритм оптимизации

В разделе Алгоритм оптимизации необходимо применить следующие настройки.

Метод оптимизационной задачи	Абсолютное отклонение варьируемого параметра
Ограниченный метод	1e-12

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

Настройке Абсолютное отклонение варьируемого параметра необходимо присвоить значение 1e-12 для фиксации критерия сходимости решения оптимизационной задачи по параметру \(x\).

Примечание

Необходимо отметить, что малое значение 1e-12, близкое к точности вещественного значения типа double в Java, пригодно для Ограниченного метода и гладких, непрерывных целевых функций.

Настройки параметров

В настройке Блок вычисления целевой функции, расположенного в разделе Оптимизируемые параметры, необходимо выбрать порт Выход блока №4 Смещение, который выполняет завершающую операцию вычисления целевой функции \(f(x)\).

В настройке Варьируемое свойство блока, расположенного в разделе Варьируемые свойства, необходимо выбрать свойство Значение константы блока №1 Константа. Значение константы блока будет использовано оптимизатором в качестве изменяемого параметра \(x\) для минимизации целевой функции \(f(x)\) (см. уравнение (1)).

Также необходимо указать границы, в которых выполняется локальная оптимизация. В текущем примере границы целевой функции приняты \(x \in [0; 10]\). Таким образом в поле Минимальное значение необходимо ввести 0, а в поле Максимальное значение необходимо ввести 10.

4.4.  Запуск оптимизации

После завершения настройки оптимизатора необходимо запустить оптимизацию. Для запуска оптимизации необходимо нажать на кнопку Оптимизировать.

Кнопка Оптимизировать для запуска оптимизации

После нажатия кнопки появятся уведомления о запуске оптимизации и об успешном завершении оптимизации.

Уведомления этапов процесса оптимизации

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

4.5.  Анализ результатов оптимизации

Результаты оптимизации доступны в соответствующем разделе для выполнения анализа после успешного завершения оптимизации.

Результаты оптимизации

Оптимизатор определил локальный минимум целевой функции \(f(x)\) при значении параметра \(x\), равным 5, что соответствует точному аналитическому решению.

Далее необходимо нажать на кнопку Применить все для передачи оптимального значения \(x^{*} = 5\) свойству Значение константы блока №1 Константа. После нажатия кнопки появится уведомление об успешном применении оптимальных свойств.

Применение к модели оптимальных свойств

В завершении анализа необходимо выполнить запуск на расчёт модели с оптимальным значением \(x^{*} = 5\) и получить результат расчёта на порте Выход блока №4 Смещение, который выполняет завершающую операцию вычисления целевой функции \(f(x)\).

Минимальное значение целевой функции при x = 5.

В результате расчёта получен локальный минимум целевой функции \(f(x^{*}) = -20\) при оптимальном значении параметра \(x^{*} = 5\), что соответствует точному аналитическому решению.

5.  Выводы

В результате выполнения ознакомительного урока по решению оптимизационных задач, вы узнали:

1. О понятии оптимизации и о математической постановке оптимизационной задачи;

2. О понятии целевой функции и ёё назначении в решении задач оптимизации;

3. О категориях задач оптимизации;

4. На простом примере освоили оптимизатор платформы REPEAT VISION для решения задачи локальной оптимизации.