Исследование методов оптимизации
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
бще говоря, остается неизвестным в ходе всей процедуры спуска. Поэтому для всех таких процедур принципиальной остается проблема останова. В вычислительной практике часто используются следующие критерии останова:
(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-х вершин. Длину ребра t возьмем равной 1 .
Начальные координаты симплекса :
Проводим сортировку по значениям функции для поиска точки с наименьшей функцией. Далее записываем симплекс таким образом, чтобы первая точка была лучшей, а каждая последующая хуже.
Для осуществления оптимизации вычислим новую точку как отражение самой плохой вершины относительно центра тяжести симплекса. Формула для вычисления новой точки:
Затем, после сравнения значения функции в новой точке со значениями функции в остальных трех, а также после осуществления одного из четырех действий (замены, сжатия, растяжения и редукции), строится новый симплекс.
Одно из четырех действий, указанных выше, выполняется в соответствии с значением функции в новой точке, по отношению к значению функции в старых точках.
Замена происходит в случае, если новая точка лучше чем лучшая.
Если выполняется условие , то при этом реализуется отражение. Точка заменяет .
При выполнении условия осуществляется сжатие и отыскивается точка :
Параметр принимается равным 0,5. Точка заменяет . Таким образом полученная точка заменяет самую плохую
Если новая точка окажется самой плохой, необходимо осуществить редукцию (уменьшение размера симплекса путем приближения всех его вершин к лучшей вершине)
После выполнения указанных действий проверяется параметр останова. В случае, если он признан большим, чем выбранное значение точности, действия повторяются снова. Параметр останова рассчитывается по формуле :
Результат работы метода представлен в таблице 3.1
Таблица 3.1 Решение задачи минимизации при помощи метода Нелдера-Мида
Номер итерацииХ1Х2ФункцияПараметр останова10,40666670,406666745,63112349226714,588528920,44333330,268333329,8700636616342,847153830,31416670,270416716,4568833648400,830800540,24958330,271458313,6678625200210,330151650,21947920,203072912,6622204109420,154097460,17966150,186497412,2813269018930,087051770,15465490,148160812,1368917330070,055870880,12849450,130288912,0728454630970,039465590,10945110,106652612,0443252080990,0355389100,03808680,047272512,0320575452390,0204381110,01072400,020609412,0210175392130,0124410120,02172440,028788612,0110939400340,013006813-0,0220008-0,016358512,0087328673060,008910914-0,0274319-0,023555612,0052484042760,005311015-0,0178584-0,014068112,0032931045150,004201916-0,0191470-0,018975012,0020694163050,003079417-0,0146824-0,015457912,0011216156180,002532018-0,0132441-0,013352012,0006552464930,002672519-0,0028766-0,004211912,0005046347540,0015212200,0004344-0,000873912,0003393472680,000924821-0,0013297-0,002324512,0001830346130,0009948220,00352820,002901012,0001371175790,0007582230,00386070,003482112,0000784767320,0004900240,00272930,002321012,0000503206790,0004156250,00226280,002322212,0000316843860,0002830260,00158040,001741912,0000178949790,0002411270,00152650,001596612,0000099691130,0002705280,00010790,000290712,0000080364640,000159429-0,0002737-0,000108412,0000054032900,0000921
В результате решения задачи минимизации с помощью метода Нелдера-Мида получено следующее значение функции : . Данный оптимум достигается в точке . Этот метод позволяет найти минимум (при начальной точке Х (1 ; 1)) за 29 ит