Методы многомерной оптимизации

Введение

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

Статья: Методы многомерной оптимизации

Найди решение своей задачи среди 1 000 000 ответов

Найти решение задачи

Методы оптимизации могут быть классифицированы согласно оптимизационным задачам следующим образом:

1. Локальные методы, которые могут сходиться к какому-либо локальному экстремуму целевой функции. В случае, если целевая функция является унимодальной, то этот экстремум также является единственным и будет глобальным максимумом или минимумом.
2. Глобальные методы, которые могут иметь дело с многоэкстремальными целевыми функциями. При глобальном поиске главной задачей считается определение тенденций глобального поведения целевой функции.

Известные на текущий момент методы поиска могут быть разбиты на следующие основные группы:

1. Методы детерминированного поиска.
2. Методы случайного поиска или стохастические.
3. Методы комбинированного поиска.

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

Методы многомерной оптимизации

Предположим, что задана целевая функция:

$f (x) = x_1^2 + x_2^2$

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

Рисунок 1. График. Автор24 — интернет-биржа студенческих работ

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

Рисунок 2. Концентрические окружности. Автор24 — интернет-биржа студенческих работ

Эти линии называются линиями уровня или линиями постоянных значений. Главной характеристикой любой из линий является тот факт, что в любой точке этой линии значение функции будет постоянным.

Выполним рассечение заданной поверхности функции тремя плоскостями по уровням:

$y_1 = x_1^2 + x_2^2 =1$

$y_2 = x_1^2 + x_2^2 =2$

$y_3 = x_1^2 + x_2^2 =3$

В таком случае линии уровня могут быть представлены следующими уравнениями:

Рисунок 3. Уравнения. Автор24 — интернет-биржа студенческих работ

Или они могут быть представлены как окружности, имеющие соответствующие радиусы:

$R_1 = √1 = 1; R_2 = √2 = 1.4; R_3 = √ 3 = 1.173$

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

1. Методы градиентного типа
2. Методы без градиентного типа.

Градиентом является вектор, который равен сумме произведений частных производных на определенные орты. Орта является единичным связанным вектором, направленным вдоль координатной оси

Главными свойствами градиента являются следующие свойства:

1. Норма градиента способна определять скорость изменения функции в направлении градиента.
2. Градиент всегда обладает направлением в сторону самого быстрого возрастания функции, то есть, в данном направлении норма вектора градиента является максимальной.

Главная идея методов состоит в том, чтобы перемещаться в направлении самого быстрого спуска, а такое направление может быть задано при помощи антиградиента $- ∇F$

Рисунок 4. Формула. Автор24 — интернет-биржа студенческих работ

Здесь$ λ[j]$ может быть выбрана следующим образом:

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

Рисунок 5. Формула. Автор24 — интернет-биржа студенческих работ

В методе наискорейшего спуска следует выбрать:

Рисунок 6. Формула. Автор24 — интернет-биржа студенческих работ

Здесь каждая производная вычисляется при $x_i = x_i^{(j)}$, и она способна уменьшать длину шага $λ[j]$ по мере приближения к минимуму функции $F$.

При аналитических функциях $F$ и малых значениях $fi$, Тейлоровское разложение $F(λ[j])$ предоставляет возможность выбора оптимальной величины шага:

Рисунок 7. Формула. Автор24 — интернет-биржа студенческих работ

Здесь каждая производная должна вычисляться при $x_i = x_i^{(j)}$. Параболическая интерполяция функции $F(λ[j])$ может быть более удобной.

Алгоритм может быть представлен следующей очередностью действий:

1 Задание начального приближения и точности расчетов.

1. Далее следует выполнить расчет:

   
   
   Рисунок 8. Формула. Автор24 — интернет-биржа студенческих работ

2. Осуществление проверки условия останова. Если

   
   
   Рисунок 9. Формула. Автор24 — интернет-биржа студенческих работ

то j = j + 1 и выполнение перехода к шагу два.

В противном случае остановка.

Метод покоординатного спуска способен улучшить рассмотренный выше метод за счет того, что при выполнении очередной итерации спуск реализуется постепенно вдоль по каждой из координат, но при этом требуется определять новые λ «n» раз за один шаг. Алгоритм покоординатного спуска может быть представлен следующим образом:

1. Задание начального приближения и точности расчетов.

2. Осуществление расчета:

   
   
   Рисунок 10. Система уравнений. Автор24 — интернет-биржа студенческих работ

3. Проверка условие останова, если

   
   
   Рисунок 11. Формула. Автор24 — интернет-биржа студенческих работ

   и выполнение перехода к шагу два.

4. В противном случае останов.

Метод сопряженных градиентов базируется на положениях прямого метода многомерной оптимизации, то есть, метода сопряженных направлений. Использование метода с квадратичными функциями предполагает минимально «n» шагов. Алгоритм метода сопряженных градиентов может быть представлен следующим образом:

Рисунок 12. Алгоритм. Автор24 — интернет-биржа студенческих работ

Метод градиентного спуска является методом определения локального минимума (максимума) функции при помощи передвижения вдоль градиента. Для того чтобы минимизировать функцию в направлении градиента применяются методы одномерной оптимизации.