Реферат: Исследование методов оптимизации

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

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

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

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

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

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

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

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

Харьков 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)

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

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

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

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

Необходимо :

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

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

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

4. Выявить зависимость числа итераций 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) приобретает вид :

Ясно, то если />, выбирать достаточно малым, то это обеспечит убывание/>, нопотребуется весьма большое число шагов. Если же неосторожно выбрать /> большим, то можно проскочить минимум, а это опасно всвязи с возможным осциллированием. Для выбора шага используется правилоГолдстейна-Армийо :

а) /> (2.14)

б) /> (2.15)

Выполнение условия а)обеспечивает выбор /> не слишком большим. Выполнениеусловия б) не дает возможность выбрать /> слишком малым.

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

3. РЕШЕНИЕЗАДАЧИ МИНИМИЗАЦИИ ДЛЯ КАЖДОГО ИЗ МЕТОДОВ

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

Построим симплекссостоящий из 3-х вершин. Длину ребра t возьмем равной 1 .

Начальные координатысимплекса :

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

Для осуществленияоптимизации вычислим новую точку как отражение самой «плохой» вершиныотносительно центра тяжести симплекса. Формула для вычисления новой точки:

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

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

Замена происходит вслучае, если новая точка лучше чем лучшая.

Если выполняется условие />, то при этомреализуется отражение. Точка /> заменяет />.

При выполнении условия /> осуществляетсясжатие и отыскивается точка /> :

Параметр /> принимается равным 0,5.Точка /> заменяет/>. Такимобразом полученная точка заменяет самую «плохую»

Если новая точка окажетсясамой «плохой», необходимо осуществить редукцию (уменьшение размера симплексапутем приближения всех его вершин к лучшей вершине)

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

Результат работы методапредставлен в таблице 3.1

Таблица 3.1 – Решениезадачи минимизации при помощи метода Нелдера-Мида

В результате решениязадачи минимизации с помощью метода Нелдера-Мида получено следующее значениефункции: /> .Данный оптимум достигается в точке />. Этот метод позволяет найтиминимум (при начальной точке Х (1; 1)) за 29 итераций при точности решения />. При этомпараметр останова равен 0,0000921.

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

Для реализации процедурынеобходимо вычислить градиент:

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

/>,

где E – заданная точностьрешения (в данной задаче E=/>).

Результат работы методапредставлен в таблице 3.2

Вследствие того, чтотаблица содержит 1263 итерации, целесообразно предоставить первые и последние25 итераций.

Таблица 3.2 – Решениезадачи минимизации при помощи градиентного метода

Номер итерации Х1 Х2 Функция Параметр останова 1 0,992187500 0,976562500 14,872248322711100 5,725771436 2 0,972112596 0,966700991 14,755778561425900 5,391343315 3 0,960252606 0,949298075 14,647453457158200 5,170831157 4 0,944120479 0,937143394 14,545808827169400 4,999364954 5 0,931250704 0,922455245 14,450015755630300 4,851038521 6 0,917052669 0,909905567 14,359522419103900 4,715343849 7 0,904265341 0,896648294 14,273894939963900 4,588117156 8 0,891210499 0,884368998 14,192768112137200 4,467486611 9 0,878869537 0,872030350 14,115817843495700 4,352565782 10 0,866628626 0,860230552 14,042753034754000 4,242801681 11 0,854831609 0,848589700 13,973308662686200 4,137814211 12 0,843250897 0,837314037 13,907242987828300 4,037283606 13 0,832001542 0,826261206 13,844334505896600 3,940936337 14 0,820995553 0,815497743 13,784380045189000 3,848521743 15 0,810266979 0,804966957 13,727192808899800 3,759812059 16 0,799778396 0,794686358 13,672600853099300 3,674595835 17 0,789535800 0,784630345 13,620445636362400 3,592677880 18 0,779520366 0,774799711 13,570580790710000 3,513876598 19 0,769728817 0,765180416 13,522870992857600 3,438023378 20 0,760149472 0,755767918 13,477190974079800 3,364961115 21 0,750776352 0,746552749 13,433424623226000 3,294543452 22 0,741600798 0,737528983 13,391464187766000 3,226633778 23 0,732616368 0,728689198 13,351209552529500 3,161104506 24 0,723815911 0,720027406 13,312567592195300 3,097836320

0,715193248 0,711537292 13,275451586431100 3,036717546 1239 0,000042461 0,000042461 12,000000003605800 0,000120097 1240 0,000042129 0,000042129 12,000000003549700 0,000119159 1241 0,000041800 0,000041800 12,000000003494500 0,000118228 1242 0,000041473 0,000041473 12,000000003440100 0,000117304 1243 0,000041149 0,000041149 12,000000003386500 0,000116388 1244 0,000040828 0,000040828 12,000000003333800 0,000115479 1245 0,000040509 0,000040509 12,000000003281900 0,000114576 1246 0,000040192 0,000040192 12,000000003230900 0,000113681 1247 0,000039878 0,000039878 12,000000003180600 0,000112793 1248 0,000039567 0,000039567 12,000000003131100 0,000111912 1249 0,000039258 0,000039258 12,000000003082300 0,000111038 1250 0,000038951 0,000038951 12,000000003034400 0,000110170 1251 0,000038647 0,000038647 12,000000002987100 0,000109309 1252 0,000038345 0,000038345 12,000000002940600 0,000108455 1253 0,000038045 0,000038045 12,000000002894900 0,000107608 1254 0,000037748 0,000037748 12,000000002849800 0,000106767 1255 0,000037453 0,000037453 12,000000002805500 0,000105933 1256 0,000037161 0,000037161 12,000000002761800 0,000105106 1257 0,000036870 0,000036870 12,000000002718800 0,000104285 1258 0,000036582 0,000036582 12,000000002676500 0,000103470 1259 0,000036296 0,000036296 12,000000002634800 0,000102662 1260 0,000036013 0,000036013 12,000000002593800 0,000101860 1261 0,000035731 0,000035731 12,000000002553500 0,000101064 1262 0,000035452 0,000035452 12,000000002513700 0,000100274 1263 0,000035175 0,000035175 12,000000002474600 0,000099491

В результате реализацииградиентного метода минимальное значение функции составляет />. Данный оптимумдостигнут в точке />. Этот метод позволяет найтиминимум (при начальной точке Х(1;1) за 1263 итерации при точности решения />. При этомпараметр останова равен 0,000099491.

4.ГРАФИЧЕСКАЯ ИНТЕРПРИТАЦИЯ РЕШЕНИЯ ЗАДАЧИ

График исследуемойфункции /> имеет вид :

Рисунок 4.1 – Графикисследуемой функции

Изобразим на рисунке(4.2) линии уровня функции

Рисунок 4.2 – Линииуровня исследуемой функции

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

Рисунок 4.3 – траекторияспуска (метод Нелдера-Мида)

Рисунок 4.4 – траекторияспуска (градиентный метод)

5. АНАЛИТИЧЕСКОЕИССЛЕДОВАНИЕ МЕТОДОВ

Для выявления зависимостичисла итераций от заданной точности методы реализованы для каждого значенияточности. Результаты представлены в таблицах (5.1-5.6, 5.8-5.13)

Реализация методаНелдера-Мида :

Таблица 5.1 – Реализацияметода Нелдера-Мида при />

Таблица 5.2 – Реализацияметода Нелдера-Мида при />

Таблица 5.3 – Реализацияметода Нелдера-Мида при />

Таблица 5.4 – Реализацияметода Нелдера-Мида при />

Таблица 5.5 – Реализацияметода Нелдера-Мида при />

Номер итерации Х1 Х2 Функция Параметр останова 1 0,4066667 0,4066667 45,631123492267 14,5885289 2 0,4433333 0,2683333 29,870063661634 2,8471538 3 0,3141667 0,2704167 16,456883364840 0,8308005 4 0,2495833 0,2714583 13,667862520021 0,3301516 5 0,2194792 0,2030729 12,662220410942 0,1540974 6 0,1796615 0,1864974 12,281326901893 0,0870517 7 0,1546549 0,1481608 12,136891733007 0,0558708 8 0,1284945 0,1302889 12,072845463097 0,0394655 9 0,1094511 0,1066526 12,044325208099 0,0355389 10 0,0380868 0,0472725 12,032057545239 0,0204381 11 0,0107240 0,0206094 12,021017539213 0,0124410 12 0,0217244 0,0287886 12,011093940034 0,0130068 13 -0,0220008 -0,0163585 12,008732867306 0,0089109 14 -0,0274319 -0,0235556 12,005248404276 0,0053110 15 -0,0178584 -0,0140681 12,003293104515 0,0042019 16 -0,0191470 -0,0189750 12,002069416305 0,0030794 17 -0,0146824 -0,0154579 12,001121615618 0,0025320 18 -0,0132441 -0,0133520 12,000655246493 0,0026725 19 -0,0028766 -0,0042119 12,000504634754 0,0015212 20 0,0004344 -0,0008739 12,000339347268 0,0009248 21 -0,0013297 -0,0023245 12,000183034613 0,0009948 22 0,0035282 0,0029010 12,000137117579 0,0007582 23 0,0038607 0,0034821 12,000078476732 0,0004900 24 0,0027293 0,0023210 12,000050320679 0,0004156 25 0,0022628 0,0023222 12,000031684386 0,0002830 26 0,0015804 0,0017419 12,000017894979 0,0002411 27 0,0015265 0,0015966 12,000009969113 0,0002705 28 0,0001079 0,0002907 12,000008036464 0,0001594 29 -0,0002737 -0,0001084 12,000005403290 0,0000921 30 -0,0000145 0,0001182 12,000003012890 0,0000930 31 -0,0005185 -0,0004534 12,000002135678 0,0000765 32 -0,0005149 -0,0004829 12,000001171711 0,0000537 33 -0,0003880 -0,0003474 12,000000755753 0,0000486 34 -0,0002538 -0,0002710 12,000000487650 0,0000301 35 -0,0001568 -0,0001842 12,000000290103 0,0000249 36 -0,0001661 -0,0001816 12,000000155619 0,0000289 37 0,0000186 -0,0000052 12,000000128281 0,0000180 38 0,0000601 0,0000402 12,000000084592 0,0000102 39 0,0000243 0,0000074 12,000000049029 0,0000094

Таблица 5.6 – Реализацияметода Нелдера-Мида при />

Данные по количествуитераций и заданным точностям для метода Нелдера-Мида сведены в таблицу 5.7

Таблица 5.7 — Зависимостьчисла итераций от точности

Точность Количество итераций 0,1 6 0,01 13 0,001 20 0,0001 29 0,00001 39 0,000001 49

Рисунок 5.1 – Графическоепредставление зависимости количества итераций N от точности E для методаНелдера-Мида.

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

Реализацияградиентного метода:

Таблица 5.8 – Реализацияградиентного метода при />

0,715193248 0,711537292 13,275451586431100 3,036717546 358 0,042588763 0,042587983 12,003630828695700 0,120676586 359 0,042255429 0,042254667 12,003574166022100 0,119728711 360 0,041924713 0,041923969 12,003518389968100 0,118788359 361 0,041596595 0,041595868 12,003463486588100 0,117855470 362 0,041271053 0,041270343 12,003409442157800 0,116929982 363 0,040948069 0,040947375 12,003356243171100 0,116011835 364 0,040627620 0,040626943 12,003303876336500 0,115100970 365 0,040309688 0,040309026 12,003252328573200 0,114197326 366 0,039994251 0,039993605 12,003201587008200 0,113300844 367 0,039681292 0,039680660 12,003151638972600 0,112411467 368 0,039370788 0,039370172 12,003102471998700 0,111529137 369 0,039062723 0,039062121 12,003054073816300 0,110653795 370 0,038757075 0,038756487 12,003006432349600 0,109785386 371 0,038453826 0,038453252 12,002959535714300 0,108923853 372 0,038152957 0,038152396 12,002913372214400 0,108069140 373 0,037854448 0,037853901 12,002867930339100 0,107221192 374 0,037558283 0,037557747 12,002823198760000 0,106379954 375 0,037264440 0,037263918 12,002779166327700 0,105545371 376 0,036972904 0,036972393 12,002735822069600 0,104717390 377 0,036683654 0,036683156 12,002693155186500 0,103895956 378 0,036396674 0,036396187 12,002651155050100 0,103081018 379 0,036111944 0,036111468 12,002609811200200 0,102272522 380 0,035829448 0,035828983 12,002569113341800 0,101470417 381 0,035549167 0,035548714 12,002529051343000 0,100674650 382 0,035271085 0,035270642 12,002489615231500 0,099885171

Таблица 5.9 – Реализацияградиентного метода при />

0,715193248 0,711537292 13,275451586431100 3,036717546 652 0,004240917 0,004240916 12,000035971071500 0,011995339 653 0,004207784 0,004207784 12,000035411204000 0,011901621 654 0,004174910 0,004174910 12,000034860050800 0,011808634 655 0,004142293 0,004142293 12,000034317476100 0,011716375 656 0,004109931 0,004109930 12,000033783346400 0,011624836 657 0,004077822 0,004077821 12,000033257530400 0,011534012 658 0,004045963 0,004045963 12,000032739898600 0,011443898 659 0,004014354 0,004014353 12,000032230323500 0,011354489 660 0,003982991 0,003982990 12,000031728679900 0,011265777 661 0,003951873 0,003951873 12,000031234844100 0,011177759 662 0,003920999 0,003920998 12,000030748694800 0,011090429 663 0,003890366 0,003890365 12,000030270112300 0,011003781 664 0,003859972 0,003859971 12,000029798978700 0,010917810 665 0,003829815 0,003829815 12,000029335178200 0,010832511 666 0,003799894 0,003799894 12,000028878596500 0,010747878 667 0,003770207 0,003770207 12,000028429121400 0,010663907 668 0,003740752 0,003740751 12,000027986642200 0,010580592 669 0,003711527 0,003711526 12,000027551050000 0,010497927 670 0,003682530 0,003682530 12,000027122237600 0,010415909 671 0,003653760 0,003653760 12,000026700099600 0,010334531 672 0,003625215 0,003625214 12,000026284531900 0,010253790 673 0,003596892 0,003596892 12,000025875432400 0,010173679 674 0,003568791 0,003568791 12,000025472700300 0,010094194 675 0,003540910 0,003540909 12,000025076236600 0,010015330 676 0,003513246 0,003513246 12,000024685943600 0,009937082

Таблица 5.10 – Реализацияградиентного метода при />

0,715193248 0,711537292 13,275451586431100 3,036717546 945 0,000426015 0,000426015 12,000000362977700 0,001204953 946 0,000422687 0,000422687 12,000000357328300 0,001195539 947 0,000419385 0,000419385 12,000000351766900 0,001186199 948 0,000416108 0,000416108 12,000000346292000 0,001176932 949 0,000412857 0,000412857 12,000000340902300 0,001167737 950 0,000409632 0,000409632 12,000000335596500 0,001158614 951 0,000406432 0,000406432 12,000000330373300 0,001149562 952 0,000403256 0,000403256 12,000000325231400 0,001140581 953 0,000400106 0,000400106 12,000000320169500 0,001131671 954 0,000396980 0,000396980 12,000000315186400 0,001122829 955 0,000393879 0,000393879 12,000000310280800 0,001114057 956 0,000390801 0,000390801 12,000000305451600 0,001105354 957 0,000387748 0,000387748 12,000000300697600 0,001096718 958 0,000384719 0,000384719 12,000000296017600 0,001088150 959 0,000381713 0,000381713 12,000000291410300 0,001079649 960 0,000378731 0,000378731 12,000000286874800 0,001071214 961 0,000375772 0,000375772 12,000000282409900 0,001062845 962 0,000372837 0,000372837 12,000000278014500 0,001054542 963 0,000369924 0,000369924 12,000000273687500 0,001046303 964 0,000367034 0,000367034 12,000000269427800 0,001038129 965 0,000364166 0,000364166 12,000000265234500 0,001030018 966 0,000361321 0,000361321 12,000000261106400 0,001021971 967 0,000358499 0,000358499 12,000000257042500 0,001013987 968 0,000355698 0,000355698 12,000000253041900 0,001006066 969 0,000352919 0,000352919 12,000000249103600 0,000998206

Таблица 5.11 – Реализацияградиентного метода при />

Таблица 5.12 – Реализацияградиентного метода при />

0,715193248 0,711537292 13,275451586431100 3,036717546 1532 0,000004265 0,000004265 12,000000000036400 0,000012064 1533 0,000004232 0,000004232 12,000000000035800 0,000011970 1534 0,000004199 0,000004199 12,000000000035300 0,000011877 1535 0,000004166 0,000004166 12,000000000034700 0,000011784 1536 0,000004134 0,000004134 12,000000000034200 0,000011692 1537 0,000004101 0,000004101 12,000000000033600 0,000011600 1538 0,000004069 0,000004069 12,000000000033100 0,000011510 1539 0,000004038 0,000004038 12,000000000032600 0,000011420 1540 0,000004006 0,000004006 12,000000000032100 0,000011331 1541 0,000003975 0,000003975 12,000000000031600 0,000011242 1542 0,000003944 0,000003944 12,000000000031100 0,000011154 1543 0,000003913 0,000003913 12,000000000030600 0,000011067 1544 0,000003882 0,000003882 12,000000000030100 0,000010981 1545 0,000003852 0,000003852 12,000000000029700 0,000010895 1546 0,000003822 0,000003822 12,000000000029200 0,000010810 1547 0,000003792 0,000003792 12,000000000028800 0,000010725 1548 0,000003762 0,000003762 12,000000000028300 0,000010641 1549 0,000003733 0,000003733 12,000000000027900 0,000010558 1550 0,000003704 0,000003704 12,000000000027400 0,000010476 1551 0,000003675 0,000003675 12,000000000027000 0,000010394 1552 0,000003646 0,000003646 12,000000000026600 0,000010313 1553 0,000003618 0,000003618 12,000000000026200 0,000010232 1554 0,000003589 0,000003589 12,000000000025800 0,000010152 1555 0,000003561 0,000003561 12,000000000025400 0,000010073 1556 0,000003534 0,000003534 12,000000000025000 0,000009994

Таблица 5.13– Реализацияградиентного метода при />

0,715193248 0,711537292 13,275451586431100 3,036717546 1826 0,000000425 0,000000425 12,000000000000400 0,000001202 1827 0,000000422 0,000000422 12,000000000000400 0,000001193 1828 0,000000419 0,000000419 12,000000000000400 0,000001184 1829 0,000000415 0,000000415 12,000000000000300 0,000001174 1830 0,000000412 0,000000412 12,000000000000300 0,000001165 1831 0,000000409 0,000000409 12,000000000000300 0,000001156 1832 0,000000406 0,000000406 12,000000000000300 0,000001147 1833 0,000000402 0,000000402 12,000000000000300 0,000001138 1834 0,000000399 0,000000399 12,000000000000300 0,000001129 1835 0,000000396 0,000000396 12,000000000000300 0,000001120 1836 0,000000393 0,000000393 12,000000000000300 0,000001112 1837 0,000000390 0,000000390 12,000000000000300 0,000001103 1838 0,000000387 0,000000387 12,000000000000300 0,000001094 1839 0,000000384 0,000000384 12,000000000000300 0,000001086 1840 0,000000381 0,000000381 12,000000000000300 0,000001077 1841 0,000000378 0,000000378 12,000000000000300 0,000001069 1842 0,000000375 0,000000375 12,000000000000300 0,000001061 1843 0,000000372 0,000000372 12,000000000000300 0,000001052 1844 0,000000369 0,000000369 12,000000000000300 0,000001044 1845 0,000000366 0,000000366 12,000000000000300 0,000001036 1846 0,000000363 0,000000363 12,000000000000300 0,000001028 1847 0,000000361 0,000000361 12,000000000000300 0,000001020 1848 0,000000358 0,000000358 12,000000000000300 0,000001012 1849 0,000000355 0,000000355 12,000000000000300 0,000001004 1850 0,000000352 0,000000352 12,000000000000200 0,000000996

Данные по количествуитераций и заданным точностям для градиентного метода сведены в таблицу 5.14

Таблица 5.14 — Зависимость числа итераций от точности

Точность Количество итераций 0,1 382 0,01 676 0,001 969 0,0001 1263 0,00001 1556 0,000001 1850

Рисунок 5.2 – Графическоепредставление зависимости количества итераций N от точности E для градиентного метода.

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

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

6. ЗАКЛЮЧЕНИЕ

В курсовой работепроизведена минимизации функции /> с помощью метода оптимизации нулевого порядка – методаНелдера-Мида и метода оптимизации первого порядка – градиентного метода сдроблением шага.

В результате решениязадачи минимизации с помощью метода Нелдера-Мида получено следующее значениефункции: />.Данный оптимум достигается в точке />. Этот метод позволяет найтиминимум (при начальной точке Х (1; 1)) за 29 итераций при точности решения />. При этомпараметр останова равен 0,0000921.

В результате реализацииградиентного метода минимальное значение функции составляет />. Данный оптимумдостигнут в точке />. Этот метод позволяет найтиминимум (при начальной точке Х(1;1)) за 1263 итерации при точности решения />. При этомпараметр останова равен 0,000099491.

Для каждого из методовбыла установлена зависимость числа итераций от заданной точности. Анализируяполученные результаты, можно сделать вывод о том, что по числу итераций болееэффективным является метод Нелдера-Мида. Однако следует отметить, чтоэффективность этих методов может изменяться в зависимости от выбора начальногоприближения и вида функции. Следует также учесть, что градиентный метод можетбыть непригоден в тех случаях, если расчет производных вызывает затруднение.

7. ПРИЛОЖЕНИЕ

В таблицах представленыкоординаты точек, образующих линии уровня

В настоящем приложениипредставлена реализация программного кода для каждого из методов оптимизации.Используемый язык программирования – Visual StudioC# 2005.

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

namespace GradientL

{public partial class Form1: Form

{public Form1()

{InitializeComponent();}

public static string[] str = new string[100000];

struct Tk

{public double x1, x2;

public Tk(double X, double Y)

{x1 = X;

x2 = Y;}

public static Tk operator /(Tk v1, double q)

{return new Tk(v1.x1 / q, v1.x2 / q);}

public static Tk operator *(Tk v, double d)

{return new Tk(v.x1 * d, v.x2 * d);}

public static Tk operator *(Tk v1, Tk v2)

{return new Tk(v1.x1 * v2.x1, v1.x2 * v2.x2);}

public static Tk operator -(Tk v1, Tk v2)

{return new Tk(v1.x1 — v2.x1, v1.x2 — v2.x2);}

public static Tk operator +(Tk v1, Tk v2)

{return new Tk(v1.x1 + v2.x1, v1.x2 + v2.x2);}

public static double Dist(Tk v1, Tk v2)

{return Math.Sqrt((v1.x1 — v2.x1) * (v1.x1 — v2.x1) + (v1.x2 — v2.x2) *(v1.x2 — v2.x2));}

public override string ToString()

{return "(" + this.x1.ToString(«f5») + ";"+ this.x2.ToString(«f5») + ")";}}

classPr

{public static double f(Tkc)

{return12 + c.x1 * c.x1 + (1 + c.x2 * c.x2) * c.x2 * c.x2 + (c.x1 * c.x1 * c.x2 * c.x2+ 100) * (c.x1 — c.x2) * (c.x1 — c.x2);}

static Tk gradient(Tk c)

{Tk N = new Tk(2 * c.x1 + 2 * c.x1 * c.x2 * c.x2 *

(c.x1 — c.x2)*(c.x1 — c.x2) + 2 * (c.x1 * c.x1 * c.x2 * c.x2 + 100) * (c.x1 — c.x2),

2 *c.x2*c.x2*c.x2+2*c.x2*(1+c.x2*c.x2)+

2*c.x2*c.x1*c.x1*(c.x1-c.x2)*(c.x1-c.x2)-2*(c.x1-c.x2)*

(c.x1*c.x1*c.x2*c.x2+100));

return N;}

public static double Dl(Tk c)

{return Math.Sqrt(c.x1 *c.x1 + c.x2 * c.x2);}

public static void Tr(double eps, ref Tk ca, out double fn, out int i)

{Tk cb = new Tk(1, 1), st =new Tk(0.5, 0.5);

Tk step = new Tk(1, 1), eq; i = 0;

{while(true)

{cb = ca — step *gradient(ca);

eq = st * step * gradient(cb) * gradient(cb);

if (f(cb — step * gradient(cb)) >= (f(cb) — Dl(eq)))

{ step.x1/= 2;

step.x2/= 2;}

else break;}

fn = f(ca);

i++;

str[i] = String.Format("{0}" + ") " + "{1}"+ "; " +

"{2}" + "; " + "{3}" + ".",i.ToString(), ca.ToString(), fn.ToString(«f6»),Dl(gradient(cb)).ToString(«f6»));

ca =cb;}

while (Dl(gradient(cb)) >= eps);

fn = f(cb);}}

private void button1_Click(object sender, EventArgs e)

{listBox1.Items.Clear();

double Et = Convert.ToDouble(textBox3.Text);

double fn;

int j;

Tk mas = new Tk(Convert.ToDouble(textBox1.Text),Convert.ToDouble(textBox2.Text));

Pr.Tr(Et, ref mas, out fn, out j);

Min.Visible = true;

Min.Text = String.Format("{0}" + "; " +"{1}" + "; " +

"{2}", mas.ToString(), fn.ToString(), j.ToString());

for (int i = 1; i < j; i++)

listBox1.Items.Add(str[i]);}

private void Form1_Load(object sender, EventArgs e){}}}

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

namespace Nelder_Method

{public partial class Form1: Form

{public Form1()

{InitializeComponent();}

static double Al = 1.0;

static double Bt = 0.5;

static double Gm = 2.0;

static int n=0;

static string[] op = new string[1000];

const int cap = 2;

struct Tk

{public double x1, x2;

public Tk(double X, double Y)

{x1 = X;

x2 = Y;}

public static Tk operator /(Tk v1, double q)

{return new Tk(v1.x1 / q, v1.x2 / q);}

public static Tk operator *(Tk v, double d)

{return new Tk(v.x1 * d, v.x2 * d);}

public static Tk operator *(Tk v1, Tk v2)

{return new Tk(v1.x1 * v2.x1, v1.x2 * v2.x2);}

public static Tk operator -(Tk v1, Tk v2)

{return new Tk(v1.x1 — v2.x1, v1.x2 — v2.x2);}

public static Tk operator +(Tk v1, Tk v2)

{return new Tk(v1.x1 + v2.x1, v1.x2 + v2.x2);}

public static double Dist(Tk v1, Tk v2)

{return Math.Sqrt((v1.x1 — v2.x1) * (v1.x1 — v2.x1) + (v1.x2 — v2.x2) *(v1.x2 — v2.x2));}

public override string ToString()

{return "(" + this.x1.ToString(«f5») + ";"+ this.x2.ToString(«f5») + ")";}}

class Cnt

{public static double function(Tk c)

{return 12 + c.x1*c.x1 + (1+c.x2*c.x2)*c.x2*c.x2 +(c.x1*c.x1*c.x2*c.x2+100)*(c.x1-c.x2)*(c.x1-c.x2);}

public static void Pr(ref Tk[] c, ref double[] ot)

{double fir; Tk tk;

for (int k = 1; k <= cap; k++)

for (int l = k; l >= 1; l--)

if (ot[l — 1] > ot[l])

{fir = ot[l];

tk = c[l];

ot[l] = ot[l — 1];

c[l] = c[l — 1];

ot[l — 1] = fir;

c[l — 1] = tk;}

else break;}

public static bool Ostanov(Tk[] w, double E, double n, Tk c, out doubleOst)

{double Lp;

double d = 0.5;

double p1 = 0;

Tk p2 = new Tk(0, 0);

for (int i = 0; i <= cap; i++)

{p1 += (function(w[i]) — function(c)) * (function(w[i]) — function(c));

p2 += (w[i] — c) * (w[i] — c);}

Lp = Math.Sqrt(p2.x1 * p2.x1 + p2.x2 * p2.x2);

Ost = d * (Math.Sqrt((1 / (n + 1)) * p1)) + (1 — d) * (Math.Sqrt((1 / (n+ 1)) * Lp));

if (Ost < E)

return true;

elsereturn false;}

public static double Met(Tk[] c, double tchn)

{double[] f = new double[cap + 1];

double val1=0, val2=0, val3 = 0, val4, val5, val6, val7;

Tk sim1, sim2, sim3, sim4, sim5, sim6, sim_cen, sim7;

sim_cen.x1 = sim_cen.x2 = 0;

inti;

doubleJ1;

boolflag;

for(i = 0; i <= cap; i++) // Вычисление значений функции на начальном симплексе

f[i] = function(c[i]);

while(!Ostanov(c, tchn, n, sim_cen, out J1))// Проверка на условие выхода

{n++;

//Шаг 1. Сортировка

Pr(ref c, ref f);

sim1 = c[cap]; val1 = f[cap];

sim2 = c[cap — 1]; val2 = f[cap — 1];

sim3 = c[0]; val3 = f[0];

// Шаг 2. Вычисление центра тяжести симплекса

sim_cen.x1 = sim_cen.x2 = 0;

for (i = 0; i < cap; i++)

sim_cen = sim_cen + c[i];

sim_cen = sim_cen / cap;

// 3Шаг. Отражение

sim4 = sim_cen * (1 + Al) — sim1 * Al; val4 = function(sim4);

// Шаг 4.

if (val4 <= val3)

{ // Шаг 4a.

sim5= sim_cen * (1 — Gm) + sim4 * Gm;

val5 = function(sim5);

if (val5 < val3)

{c[cap] = sim5;

f[cap] = val5;}

else

{c[cap] = sim4;

f[cap] = val4;}}

if ((val3 < val4) && (val4 <= val2))

{ // Шаг 4.b

c[cap] = sim4;

f[cap] = val4;}

flag = false;

if ((val1 >= val4) && (val4 > val2))

{ // Шаг 4c.

flag = true;

val7 = val1;

sim7 = sim1;

c[cap] = sim4;

f[cap] = val4;

sim4 = sim7;

val4 = val7;}

// Шаг 4d.

if (val4 > val1) flag = true;

if(flag)

{ // Шаг 5. Сжатие

sim6 = sim1 * Bt + sim_cen * (1 — Bt);

val6 = function(sim6);

if (val6 < val1)

{ // Шаг 6.

val7 = val1;

sim7 = sim1;

c[cap] = sim6;

f[cap] = val6;

sim6 = sim7;

val6 = val7;}

else

{ // Шаг 7. Глобальное сжатие

for (i = 0; i <= cap; i++)

c[i] = sim3 + (c[i] — sim3) / 2;}}

op[n — 1] = Convert.ToString(n) + "; " + sim1.ToString() +

"; " + sim2.ToString() + "; " + sim3.ToString();}

return (val3 + val1 + val2) / 3;}}

private void button1_Click(object sender, EventArgs e)

{Tk ta = new Tk(0, 0);

Tk tb = new Tk(0.26, 0.96);

Tk tc = new Tk(0.96, 0.26);

Tk[] t = new Tk[3] { ta, tb, tc };

listBox1.Items.Clear();

n = 0;

op = new string[200];

double eps1 = Convert.ToDouble(textBox2.Text);

label4.Text = Cnt.Met(t, eps1).ToString(«f5») + "; "+ Convert.ToString(n) + ".";

for (int i = 0; i < n; i++)

listBox1.Items.Add(op[i]);}

private void Form1_Load(object sender, EventArgs e){}}

8. СПИСОКИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ

1. Агуров П.В. C# в подлиннике (программирование наязыке С#) – Петербург, 2006

2. Агуров П.В.Сборник рецептов по C# — Петербург,2006

3. Банди Б. Методыоптимизации – Москва, 1988

4. Базара М, ШеттиК. Нелинейное программироваине. Теория и алгоритмы – М.: Мир, 1988

5. Поляк Б.Т.Введение в оптимизацию. — М.: Наука, 1983

6. Раскин Л.Г.Математическое программирование: Учебное пособие – Харьков: НТУ «ХПИ», 2002

7. Рихтер Д.Программирование на платформе Microsoft. NET Freamework для профессионалов – М.MicrosoftPress, 2003

8. Серая О.В.Методические указания для проведения лабораторных работ по курсу«Математическое программирование» — Харьков: НТУ «ХПИ», 2003

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

10. Химмельблау Д.Прикладное нелинейное программирование М.: Мир, 1989

еще рефераты

Еще работы по информатике, программированию

Реферат по информатике, программированию

Исследование нелинейных систем

18 Июня 2015

Реферат по информатике, программированию

Исследование нормативно-правовой базы информационной безопасности предприятия отделения Юго-Западного банка Сбербанка России №****

18 Июня 2015

Реферат по информатике, программированию

Исследование операций

18 Июня 2015

Реферат по информатике, программированию

Исследование операций

31 Августа 2013