47278 (608198), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Рассмотрим вопрос о выборе направления , обеспечивающего (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). В случае его удовлетворения продвижение к минимуму продолжается с тем же шагом. Если же оно не удовлетворяется, то параметр , определяющий длину шага, делят пополам до тех пор, пока это неравенство не будет выполнено. Затем выполняется очередной шаг. Процедура продолжается до выполнения критерия останова.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Характеристики

Список файлов курсовой работы