Сравнительный анализ методов оптимизации

f(x*)=-5.807126299

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

2 Прямые методы безусловной оптимизации многомерной функции

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

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

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

F(x1,x2)=a*x*y+(b*y+c*x)/x*y → min

a=5 b=3.5 c=2.5

x1=

x2=

2.1 Метод покоординатного циклического спуска

Суть метода заключается в том, что в начальном базисе закрепляется значение одной координаты, а переменными считаются остальные, и по этой координате производится одномерная оптимизация

 базисная точка переносится в

,

 базисная точка переносится в

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

Для решения поставленной задачи выбрано приближение ε=0,01 α=0,15

Таблица 3 - Метод покоординатного циклического спуска

α/2< ε, x1=0,2295 x2=0,4145 Z(x1,x2)= -0,8479571

2.2 Метод Хука – Дживса

Метод Хука и Дживса осуществляет два типа поиска - исследующий поиск и поиск по образцу. Первые две итерации процедуры показаны на рисунке 4.

Рисунок 4 – 1-поиск по образцу; 2- исследующий поиск вдоль координатных осей.

При заданном начальном векторе x1 исследующий поиск по координатным направлениям приводит в точку x2 . Последующий поиск по образцу в направлении x1- x2 приводит в точку y. Затем исследующий поиск, начинающийся из точки y, дает точку x3. Следующий этап поиска по образцу вдоль направления x3- x2 дает y*. Затем процесс повторяется.

Рассмотрим вариант метода, использующий одномерную минимизацию вдоль координатных направлений d1,..., dn и направлений поиска по образцу.

Начальный этап. Выбрать число eps > 0 для остановки алгоритма. Выбрать начальную точку x1, положить y1= x1, k=j=1 и перейти к основному этапу.

Основной этап.

Шаг 1. Вычилить lymj - оптимальное решение задачи минимизации f(yj+lym * dj) при условии lym принадлежит E1. Положить y[j+1]= yj+lymj*dj. Если j < n, то заменить j на j+1 и вернуться к шагу 1. Если j=n, то положить x[k+1] = y[n+1]. Если ||x[k+1] - xk|| < eps , то остановиться; в противном случае перейти к шагу 2.

Шаг 2. Положить d = x[k+1] - xk и найти lym - оптимальное решение задачи минимизации f(x[k+1]+lym*d) при условии lym принадлежит E1. Положить y1= x[k+1]+lym*d, j=1, заменить k на k+1 и перейти к шагу 1. Для решения поставленной задачи выбрано приближение ε=0,02, α=0,15

Таблица 4 - Метод Хука-Дживса

Т.к в ε окрестности полученной на 38 шаге точке мы не получаем улучшения (уменьшения значения) функции, то примем x1=0,426999999999999 x2=0,496999999999999,

Страницы: 1, 2, 3, 4