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

Поиск оптимального решения. Простейший способ исключения ограничений. Многомерные методы оптимизации, основанные на вычислении целевой функции. Метод покоординатного спуска. Модифицированный метод Хука-Дживса. Исследование на минимум функции Розенброка.
Краткое сожержание материала:

Размещено на

Размещено на

министерство образования и науки Украины

харьковский национальный университет

радиоэлектроники

Кафедра Прикладной математики

пояснительная записка

к курсовой работе

по дисциплине: Методы оптимизации

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

Выполнил: Руководитель:

ст. гр. СА-09-1 доц. каф. ПМ

Щербина Д.В. Наумейко И.В.

Харьков 2012

харьковский национальный университет радиоэлектроники

Факультет Прикладной математики и менеджмента

Кафедра Прикладной математики

Дисциплина Методы оптимизации

Специальность Системный анализ

Курс 3 Группа СА-09-1 Семестр 6

ЗАДАНИЕ

НА КУРСОВУЮ РАБОТУ

студенту Щербине Дарье Владимировне

(фамилия, имя, отчество)

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

2. Дата подачи законченного проекта: " 16 апреля 2012г.

3. Содержание пояснительной записки: постановка задачи; описание заданных методов и обоснование их сходимости; результаты вычислительного эксперимента по решению указанной задачи заданными методами.

4. Дата выдачи задания: " 1 " марта 2012г.

Руководитель работы ______________ доц. каф. ПМ Наумейко И.В.

Задание принял к исполнению _____________ Щербина Д.В.

КАЛЕНДАРНЫЙ ПЛАН

Номер	Название этапов курсовой работы	Срок выполнения этапов работы	Примечание
1	Подбор и проработка литературы по заданной теме	до 10.03.2012
2	Изучение теоретического материала	до 12.03.2012
3	Разработка программного средства: реализация алгоритма	до 25.03.2012
4	Разработка программного средства: реализация ввода, сохранения и загрузки исходных данных	до 1.04.2012
5	Реализация экспериментального расчета	до 07.04.2012
6	Оформление материалов пояснительной записки	до 16.04.2012

Студент Щербина Д.В.

Руководитель работы доц. каф. ПМ Наумейко И.В.

АНОТАЦІЯ

Пояснювальна записка складає 27тр., 3 рис., 1 іст.

Пояснювальна записка складається з теоретичної і практичної частин. Теоретична частина містить опис вказаних методів мінімізації, обгрунтування їх сходження. Практична частина містить результати обчислюванного експерименту по рішенню задачі мінімізациї функції Розенброка .

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

ГРАДІЄНТ, ОПОРНИЙ ВЕКТОР, ЗАДАЧА ЛІНЕЙНОГО ПРОГРАМУВАННЯ,

ЗАДАЧА КВАДРАТИЧНОГО ПРОГРАМУВАННЯ, ЦІЛЬОВА ФУНКЦІЯ, ВИПУКЛА ФУНКЦІЯ.

Explanatory note consists of theoretical and practical parts. The theoretical part includes a description of these methods of minimization, justification of their convergence. The practical partcontains the results of computer simulation to address the problem of minimizing the Rosenbrock function.

Upon completion of this course the project was to obtain a solution to the original problem by this method with accuracy, and draw conclusions about

the effectiveness of its use for the task.

gradient, support vector, Linear programming, quadratic programming problems, the objective function, convex function.

СОДЕРЖАНИЕ

Введение

1. Теоретическая часть

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

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

1.1.2 Некоторые методы прямого поиска

1.2 Метод Хука-Дживса

1.2.1 Постановка задачи

1.2.2 Алгоритм

1.2.3 Вычислительные аспекты

2. Практическая часть

2.1 Постановка задачи.

2.2 Вычислительный эксперимент для метода Хука-Дживса

Выводы

Список использованных источников

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

1.2 Некоторые методы прямого поиска

Простейш...