Прямой поиск без ограничений. Метод поиска Хука-Дживса для функции Розенброка

курсовая работа

1.1 Постановка задачи и алгоритм

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

Рассмотрим методы минимизации, в которых используются только значения функции и не используются вектор-градиенты или матрицы Гессе. В тех случаях, когда градиенты или матрицы Гессе могут быть легко вычислены, прямой метод оказывается, менее эффективным. Однако в ряде случаев прямые методы являются единственными практически применимыми, например, если функция f(х) имеет разрывы первой производной. Если f(х) задана не в явном виде, а системой уравнении, относящихся к различным подсистемам некоторой системы (это как раз имеет место при построении моделей реальных систем пли процессов), то аналитическое или численное определение производных становится очень сложным или даже невозможным. И в этом многие методы неприменимы. Другим случаем, когда методы прямого поиска могут конкурировать с другими группами методов, является случай, когда функция f(х) обладает несколькими локальными экстремумами. На разработку методов прямого поиска для определения минимума функций и переменных было затрачено много усилий . Методы прямого поиска являются методами, в которых используются только значения функции. Мы рассмотрим подробно лишь один из них. Практика показала, что этот метод эффективен и применим для широкого числа приложений. Рассмотрим функцию двух переменных. Ее линии постоянного уровня1 на рис. 1, а минимум лежит в точке (x1*,x2*). В методах прямого поиска ограничения учитываются в явном виде. Необходимость разработки этих методов связана с тем, что в инженерных приложениях часто приходится сталкиваться с случаями, когда целевые функции не заданы в явном виде. Эти методы строятся на интуитивных соображениях, не подкреплены строгой теорией и, следовательно, не гарантируется их сходимость. Несмотря на это, в силу своей логической простоты эти методы легко реализуются.

Перед непосредственным применением методов прямого поиска необходимо провести ряд мероприятий по подготовке задачи к решению, а именно

· исключить ограничения в виде равенств;

· определить начальную допустимую точку.

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

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

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

Делись добром ;)