birmaga.ru
добавить свой файл

1
Написать основные соотношения метода простого градиентного спуска и метода деформированного многогранника для минимизации функции из таблицы заданий. Точку минимума определить с указанной в таблице точностью  (Задание 1).


Минимизировать целевую функцию с применением метода Хука-Дживса, описать пошагово последовательность выполнения процедур (Задание 2).

Задание 1.


f(x)





10-10


Задание 2.

Вид целевой функции



Начальные точки

Точность

ε







-4

7

0,3

Пример 1. Минимизировать функцию

с точностью =10-5,

простым градиентным методом.
1. Для минимизации функции f(x,y) используем формулу простого градиентного спуска (2.5):

, (4.1)

где - точка с координатами x0,y0; h - длина шага в направлении антиградиента для заданной функции в точке .

  1. Выбираем координаты начальной точки : x0=1, y0=0 и значение шага h=0.1. В точке вычисляем значение функции f(x,y):


(4.2)
3. Определяем градиент заданной функции g(z0) в точке :



где

(4.3)

4. Проверяем выполнение третьего условия (2.4):

(4.4)

если (4.4) выполняется, то точка является точкой минимума и вычисления заканчиваем, а если нет то выполняем следующие пункты.
5. Вычисляем координаты x1,y1 новой точки согласно (4.1):

(4.4)

6. Вычисляем значение функции f(x,y) в точке :



и сравниваем значения f1 и f0.

Если f1>f0, то шаг уменьшаем в два раза: h=h/2 и повторяем пункт 5. Если f10, то полагаем, что и повторяем пункт 3 и т.д. до выполнения условий (4.4).
Пример 2. Минимизировать с применением метода Хука-Дживса целевую функцию , начальная точка имеет кординаты , изменения координат принять .

1 Найти значение целевой функции в начальной точке , полагая, что точка является базисной точкой.


2. Первая итерация


Выполнить исследующий поиск вокруг базисной точки по каждой из координат:

по координате





по координате



улучшает целевую функцию


В результате исследующего поиска вокруг базисной точки следует выбрать точку

Выполнить поиск по образцу:

найти шаг из базовой точки следующей базовой точки вдоль прямой, соединяющей эти точки:











шаг удачный











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

3. Вторая итерация

Выполнить исследующий поиск вокруг выбранной базисной точки по каждой из координат:

по координате





по координате





В результате исследующего поиска второй итерации следует выбрать новую точку

Выполнить поиск по образцу:

найти шаг из базовой точки следующей базовой точки вдоль прямой, соединяющей эти точки:







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

4. Третья итерация

Выполнить исследующий поиск вокруг выбранной базисной точки по каждой из координат:

по координате







по координате



шаг удачный



шаг удачный
В результате исследующего поиска третьей итерации следует выбрать новую точку

Поиск по образцу:

найти шаг из базовой точки следующей базовой точки вдоль прямой, соединяющей эти точки:



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



Пример 3. Применяя метод Хука-Дживса минимизировать целевую функцию , начальная точка имеет координаты , изменения координат принять , принять ε=0,2

1.Найти значение функции в начальной точке




2. Первая итерация:

Выполнить исследующий поиск по координатам:

по координате :





по координате :







В результате исследующего поиска вокруг базисной точки следует выбрать точку

Выполнить ускоряющий поиск по образцу:

найти шаг из базовой точки следующей базовой точки вдоль прямой, соединяющей эти точки:







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

по координате :




по координате :





Окончательно получим базовую точку и выполним ускоряющий поиск по образцу для следующей базовой точки



Поскольку неудачными оказались шаги по всем выбранным направлениям, то вернемся к предыдущей точке проверим условие окончания алгоритма =2 > ε=0,2, уменьшая приращения в два раза: ; Δx2=1.









Выбираем в качестве базовой точки

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

поэтому возвращаемся к точке и повторяем исследующий поиск.

Осуществляем исследующий поиск по координатам:

по координате :



по координате :





Окончательно выбираем базовую точку

Поскольку пошаговый поиск по образцу не приносит положительных результатов, а также неудачными оказываются шаги по всем направлениям, проверяем условие окончания алгоритма > ε=0,2, уменьшаем приращения в два раза: и переходим к следующей итерации.

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

Проверяем условие окончания поиска =0,125 < ε=0,2 и заканчиваем вычисления.

Таким образом, за точку минимума принимаем значение