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

Задача не имеющая ограничений называются задачей безусловной оптимизации. Рассмотрим задачу безусловной оптимизации:

f(x)=F(x1..xn) -> min x ,

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

K – номер итерации; - направление поиска на к-ой итерации. - величина шага в данном направлении.

В координатной форме эта схема имеет вид:

Процесс поиска начинается с некоторой точки X⁰, которая называется начальным приближением и задается пользователем. По этой точке определяются точки X¹ , X² и т.д. Полученная последовательность точек называется траекторией поиска и сходится к оптимальной точке Х*. Методы безусловной оптимизации отличаются друг от друга способами выбора направления поиска и величиной шага .

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

Методы нулевого порядка – это методы, в которых для определения направления поиска используется только значение целевой функции. Производные при этом не используются. Они называются методами прямого поиска или поисковыми методами оптимизации.

Методы первого порядка – методы, в которых для определения направления поиска используются первые производные целевой функции. Эти методы называются градиентными методами оптимизации.

Методы второго порядка – это методы, в которых для определения направления поиска используются вторые производные целевой функции. К этому классу относят метод Ньютона и его модификации.

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

В зависимости от способа выбора направления поиска все эти методы делятся на группы.

1) Методы покоординатной оптимизации - поиск осуществляется вдоль координатных осей:

А) Алгоритм покоординатной оптимизации с постоянным шагом Н- осуществляется движение из точки Х^К c определенным шагом вдоль первой координатной оси, затем сравниваются значения целевой функции, если значение уменьшилось, то переход в точку , в противном случае осуществляется шаг в обратном направлении. Если это не приводит к уменьшению значения целевой функции, то рассматривается следующая координатная ось. Если в результате движения вдоль всех координатных осей значение целевой функции не уменьшилось, то происходит дробление шага и процедура повторяется.

Б) Метод Гауса-Зейделя- метод, реализующий стратегию определения оптимальной длины шага. На каждой итерации определяется длины шагов вдоль каждого координатного направления в результате решения вспомогательных задач одномерной оптимизации. При этом на каждой итерации осуществляется циклический покоординатный спуск из точки Х^К вдоль каждой координатной оси.

В) Метод Хука- Дживса или метод конфигураций- этап циклического покоординатного спуска чередуется с этапом экстраполяции- движение в направлении соединяющие точки Х^К и Х^К+1 на 2 последовательных шагах.

Г) Метод вращения осей Розенброка, метод сопряженных направлений Пауэлла.

2) Метод переменного многогранника Нелдора-Мида и его модификация- Метод заключается в построении в n мерном пространстве многогранника из (n+1) точки и перемещении его в направление оптимальной точки с помощью 3 основных операций: отражение, растяжение, сжатие.

3) Методы случайного поиска. Направление поиска на каждой итерации выбирается случайным образом.

Данные методы имеют невысокую скорость сходимости.