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

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

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

ст. гр. СА-09−1 доц. каф. ПМ Щербина Д. В. Наумейко И.В.

Харьков 2012

харьковский национальный университет радиоэлектроники Факультет Прикладной математики и менеджмента Кафедра Прикладной математики Дисциплина Методы оптимизации

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

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

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ студенту Щербине Дарье Владимировне

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

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

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

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

4. Дата выдачи задания: «1 «марта 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 Некоторые методы прямого поиска Простейшим методом поиска является метод покоординатного спуска. Из точки, А мы производим поиск минимума вдоль направления оси и, таким образом, находим точку В, в которой касательная к линии постоянного уровня параллельна оси. Затем, производя поиск из точки В в направлении оси, получаем точку С, производя поиск параллельно оси, получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Очевидным образом эту идую можно применить для функций n-переменных.

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

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

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

Описание этой процедуры представлено ниже:

А. Выбрать начальную базисную точку b1 и шаг длиной h1 для каждой переменной xj, j = 1, 2,…, n.

Б. Вычислить f (х) в базисной точке b1 с целью получения сведений о локальном поведении функции f (x). Эти сведения будут использоваться для нахождения подходящего направления поиска по образцу, с помощью которого можно надеяться достичь большего убывания значения функции. Функция f (x) в базисной точке b1, находится следующим образом:

1. Вычисляется значение функции f (b1) в базисной точке b1.

2. Каждая переменная по очереди изменяется прибавлением длины шага. Таким образом, мы вычисляем значение функции f (b1+h1e1), где e1 — единичный вектор в направлении оси x1. Если это приводит к уменьшению значения функции, то b1 заменяется на b1+h1e1. В противном случае вычисляется значение функции f (b1-h1e1), и если ее значение уменьшилось, то b1 заменяем на b1-h1e1. Если ни один из проделанных шагов не приводит к уменьшению значения функции, то точка b1 остается неизменной и рассматриваются изменения в направлении оси х2, т. е. находится значение функции f (b1+h2e2) и т. д. Когда будут рассмотрены все n переменные, мы будем иметь новую базисную точку b2.

3. Если b2=b1, т. е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки b1, но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

4. Если b2b1, то производится поиск по образцу.

В. При поиске по образцу используется информация, полученная в процессе исследования, и минимизация функции завершается поиском в направлении, заданном образцом. Эта процедура производится следующим образом:

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

P1=b1+2(b2-b1) .

В общем случае

Pi=bi+2(bi+1-bi) .

2. Затем исследование следует продолжать вокруг точки Р1 (Рi) .

3. Если наименьшее значение на шаге В, 2 меньше значения в базисной точке b2 (в общем случае bi+1), то получают новую базисную точку b3 (bi+2), после чего следует повторить шаг В, 1. В противном случае не производить поиск по образцу из точки b2 (bi+1), а продолжить исследования в точке b2 (bi+1).

Г. Завершить этот процесс, когда длина шага (длины шагов) будет уменьшена до заданного малого значения.

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

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

функция минимум оптимальный ограничение

2. ПРАКТИЧЕСКАЯ ЧАСТЬ Постановка задачи Исследовать на минимум функцию Розенброка на области D. Точность по координатам и по значению функции одинаковы: е=0.001. Xнач= (-0.5, 0.5)

Функция Розенброка имеет вид Рис. 1 График функции Розенброка Минимизация методом Хука-Дживса:

Точка минимума с помощью метода Хука-Дживса: (1,1), значение функции .

Программа реализована на Visual Studio 2010 C#

Табл.1 Результаты вычисления

ВЫВОДЫ В данной работе были рассмотрены и запрограммированы следующие метод минимизации функций: метод Хука-Дживса.Он сошелся достаточно быстро.

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

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Сухарев А. Г., Тимохов А. В., Федоров В. В. Курс методов оптимизации. М.: Наука, 1986. 326 с.

2. Банди «Методы оптимизации» М.1992 с.93−97