3.1. Методы прямого поиска

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

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

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

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

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

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

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

Рекуррентная формула для определения точки экстремума большинства методов имеет вид

,

где - направление поиска,- длина шага в выбранном направлении.

Длина шага после выбора направления может быть задана константой или определена из соотношения

.

Для определения вторым способом можно использовать любой метод одномерной оптимизации.

Рассмотренные ниже методы (покоординатный спуск, Хука-Дживса, Розенброка, Нелдера-Мида и др.) являются методами прямого поиска и отличаются выбором направлений поиска и способом определения длины шага.

3.1.1. Метод покоординатного спуска

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

Рис. 5

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