Xreferat.com » Рефераты по информатике и программированию » Исследование методов оптимизации

Исследование методов оптимизации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ


НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ХАРЬКОВСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ»


Факультет информатики и управления

Кафедра экономической кибернетики и маркетингового менеджмента


КУРСОВАЯ РАБОТА

По математическому программированию

Исследование методов оптимизации


Харьков 2009

РЕФЕРАТ


Данная курсовая работа содержит : 41 страницу, 16 таблиц, 6 графиков.

В курсовой работе рассмотрены теоретические основы двух методов оптимизации математического программирования :

- метод Нелдера-Мида ;

- градиентный метод с дроблением шага.

Произведена минимизация исследуемой функции указанными методами. Выявлена зависимость числа итераций от заданной точности. Сопоставлена трудоемкость и эффективность оптимизации заданной функции различными методами (градиентным и методом Нелдера-Мида).

Ключевые термины:

Градиент – вектор первых частных производных функции.

Линии уровня – множества точек, в которых функция Исследование методов оптимизации принимает постоянные значения, т.е. Исследование методов оптимизации

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

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

СОДЕРЖАНИЕ


1. Введение

2. Математическое описание методов оптимизации

2.1 Метод Нелдера-Мида

2.2 Градиентный метод с дроблением шага

3. Решение задачи минимизации для каждого из методов

3.1 Метод Нелдера-Мида

3.2 Градиентный метод с дроблением шага

4. Графическая интерпретация решения задачи

5. Аналитическое исследование методов

6. Заключение

7. Приложение

8. Список литературы

СПИСОК УСЛОВНЫХ ОБОЗНАЧЕНИЙ


Исследование методов оптимизации - точка

Исследование методов оптимизации - длинна шага

Исследование методов оптимизации- вектор градиент

E - точность

N – количество итераций

Д – матрица координат симплекса

t – длинна ребра симплекса

1. ВВЕДЕНИЕ


Объектом исследования предмета математическое программирование являются задачи оптимизации.

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

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

ПОСТАНОВКА ЗАДАЧИ ( Вариант задания 1)

Исследовать функцию типа :


Исследование методов оптимизации


Используемые методы минимизации Исследование методов оптимизации :

Метод: Нелдера-Мида.

Метод: Градиентный с дроблением шага.

Необходимо :

Решить задачу минимизации Исследование методов оптимизации, начав итерации из выбранной начальной точки x0=(1;1) заданными по варианту методами, необходимая точность решения Исследование методов оптимизации. Привести таблицу результатов расчета типа: Итерация: Исследование методов оптимизации - точка: Исследование методов оптимизациизначение: Исследование методов оптимизациикритерий: Исследование методов оптимизации.

Рассчитать 3 линии уровня функции и изобразить их на графике.

Отобразить на графиках линий уровня для каждого из заданных методов траекторию движения по итерациям (траекторию спуска).

Выявить зависимость числа итераций N от заданной точности E, значения точности: Исследование методов оптимизации, Исследование методов оптимизации, Исследование методов оптимизации, Исследование методов оптимизации, Исследование методов оптимизации, Исследование методов оптимизации. Привести таблицу результатов как в п.1 для каждого значения E.

5. Сравнить эффективность рассмотренных в варианте методов по числу итераций N, построить графики N=F(E).

2. МАТЕМАТИЧЕСКОЕ ОПИСАНИЕ МЕТОДОВ ОПТИМИЗАЦИИ


2.1 Метод Нелдера-Мида


Вводится симплекс, координаты вершин которого заданы таблицей (одна из вершин в начале координат).


Исследование методов оптимизации

Исследование методов оптимизацииИсследование методов оптимизации

Исследование методов оптимизацииИсследование методов оптимизации


t – некоторое выбранное число.

Если n = 2, то при t = 1 имеем


Исследование методов оптимизации

Исследование методов оптимизации


Расположение симплекса показано на рисунке 2.1


Рисунок 2.1- Начальное расположение симплекса

Легко убедиться в том, что если координаты вершин симплекса задать в соответствии с матрицей Д0 , то расстояние между двумя любыми вершинами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n .

Действительно, расстояние между любой вершиной xj , j= 2,3,.., n+1, и вершиной x1 равно


Исследование методов оптимизации


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


Исследование методов оптимизации


Вычислим значения оптимизируемой функции в точках Исследование методов оптимизации и переномеруем точки так, чтобы выполнялись неравенства :


Исследование методов оптимизации.


Найдем координаты центра тяжести фигуры , получающейся в результате удаления вершины Исследование методов оптимизации :


Исследование методов оптимизации


Осуществим отражение вершины Исследование методов оптимизации относительно центра тяжести. Получим точку


Исследование методов оптимизации.


Если a=1 , то получим зеркальное отражение. В одномерном случае процедура отражения, обеспечивающая получение точки Исследование методов оптимизации , симметричной точке Исследование методов оптимизации относительно Исследование методов оптимизации иллюстрируется рис. 2.2


Исследование методов оптимизации


Исследование методов оптимизации


Рисунок 2.2 - Построение точки Исследование методов оптимизации


Сравним теперь между собой значения Исследование методов оптимизации

Возможны следующие варианты

а)Исследование методов оптимизации. В этом случае выполняется растяжение симплекса и отыскивается точка Исследование методов оптимизации

Параметр Исследование методов оптимизации обычно принимается равным 1,5.

Полученная точка Исследование методов оптимизации заменяет Исследование методов оптимизации, если Исследование методов оптимизации. В противном случае для замены Исследование методов оптимизации используется точка Исследование методов оптимизации.

б) Исследование методов оптимизации. При этом реализуется отражение. Точка Исследование методов оптимизации заменяет Исследование методов оптимизации.

в) Исследование методов оптимизации. В этом случае осуществляется сжатие и отыскивается точка Исследование методов оптимизации

Параметр Исследование методов оптимизации обычно принимается равным 0,5. Точка Исследование методов оптимизации заменяет Исследование методов оптимизации.

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


Исследование методов оптимизации


Критерий останова вычислительной процедуры имеет вид :


Исследование методов оптимизации

Исследование методов оптимизации


Критерий останова J является составным. При этом его компоненты имеют различный вес в зависимости от того, каков характер поведения оптимизируемой функции в окрестности экстремума. Если в районе экстремума оптимизируемая функция изменяется по типу «глубокая впадина», то больший вклад в численное значение критерия J вносит первое слагаемое, а второе при этом быстро уменьшается. Напротив, если оптимизируемая функция изменяется по типу «пологое плато», то первое слагаемое быстро становится малым и поэтому второе слагаемое вносит больший вклад в величину критерия J.

Модификация метода

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


Исследование методов оптимизации .


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


Исследование методов оптимизации (2.1)


Координаты центра тяжести этого симплекса образуют вектор


Исследование методов оптимизации


Теперь координаты точки Исследование методов оптимизациинайдем из равенства Исследование методов оптимизации=Исследование методов оптимизации, откуда


Исследование методов оптимизации

где Исследование методов оптимизации


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


2.2 Градиентный метод с дроблением шага


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


Исследование методов оптимизации (2.2)


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

Выберем произвольным образом точку Исследование методов оптимизации, направление Исследование методов оптимизации и сконструируем луч


Исследование методов оптимизации. (2.3)


Рассмотрим вопрос о выборе направления Исследование методов оптимизации, обеспечивающего (2.2). Для этого изучим поведение Исследование методов оптимизациивдоль луча Исследование методов оптимизации . Имеем Исследование методов оптимизации

Введем


Исследование методов оптимизации (2.4)

Здесь Исследование методов оптимизации


В соответствии с (2.3)


Исследование методов оптимизации

Тогда Исследование методов оптимизации

Вычислим Исследование методов оптимизации (2.5)


Теперь, чтобы для любого Исследование методов оптимизации обеспечить отрицательность (2.5), достаточно положить Исследование методов оптимизации, где Исследование методов оптимизации произвольная положительно определенная Исследование методов оптимизации матрица. Тогда


Исследование методов оптимизации

При этом Исследование методов оптимизации (2.6)


Выбрав каким-либо образом Исследование методов оптимизации , получим Исследование методов оптимизацииЗатем аналогично рассчитаем Исследование методов оптимизации

Общее рекуррентное соотношение имеет вид :


Исследование методов оптимизации (2.7)


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

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


Исследование методов оптимизации (2.8)

Исследование методов оптимизации (2.9)


где Исследование методов оптимизации и Исследование методов оптимизации -некоторые достаточно малые числа .

Понятно, что критерий (2.8) хорош в тех случаях, когда функция Исследование методов оптимизации в окрестности минимума, используя ранее введенную классификацию, имеет характер «глубокой» впадины. С другой стороны, если функция Исследование методов оптимизации ведет себя как «пологое плато», то более предпочтительным является критерий (2.9). Аналогом критерия (2.8) является другое часто применяемое правило останова :


Исследование методов оптимизации, (2.10)


использующее необходимое условие экстремума функции. Очевидным недостатком критериев (2.8)-(2.10) является то, что их качество существенно зависит от абсолютных значений величины Исследование методов оптимизации и компонентов векторов Исследование методов оптимизации,Исследование методов оптимизации. Более универсальными являются относительные критерии :


Исследование методов оптимизации (2.11)

Исследование методов оптимизации (2.12)

Исследование методов оптимизации (2.13)


Заметим, что очень часто на практике используются составные критерии, представляющие собой линейную комбинацию критериев (2.11)-(2.13), например,


Исследование методов оптимизации

Исследование методов оптимизации


Иногда применяют другой вариант построения составного критерия :


Исследование методов оптимизации


При реализации градиентного метода с дроблением шага в качестве Исследование методов оптимизации выбирают единичную матрицу, то есть


Исследование методов оптимизации


а длину шага определяют путем проверки некоторого неравенства. При этом основное рекуррентное соотношение (2.7) приобретает вид :


Исследование методов оптимизации


Ясно, то если Исследование методов оптимизации, выбирать достаточно малым, то это обеспечит убывание Исследование методов оптимизации, но потребуется весьма большое число шагов. Если же неосторожно выбрать Исследование методов оптимизации большим , то можно проскочить минимум, а это опасно в связи с возможным осциллированием. Для

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

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: