Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Метод сопряженных направлений (метод Пауэлла)

Читайте также:
  1. A. Методы измерения мертвого времени
  2. HR– менеджмент: технологии, функции и методы работы
  3. I метод.
  4. I. 2. 1. Марксистско-ленинская философия - методологическая основа научной психологии
  5. I. 2.4. Принципы и методы исследования современной психологии
  6. I. Анализ методической структуры и содержания урока
  7. I. Методические указания к изучению курса

В методе сопряженных направлений (методе Пауэлла [Powell M.J.D.]) ис­пользуется факт, что минимум квадратичной функции может быть найден не бо­лее чем за шагов при условии, что поиск ведется вдоль сопряженных относи­тельно матрицы Гессе направлений. Так как достаточно большой класс целевых функций может быть представлен в окрестности точки минимума своей квадра­тичной аппроксимацией, описанная идея применяется и для неквадратичных функций. Задается начальная точка и направления , совпадающие с координатными. Находится минимум при последовательном движении по направлениям с помощью одного из методов одномерной минимизации. При этом полученная ранее точка минимума берется в качестве исходной для поиска по следующему направлению, а направление использу­ется как при первом , так и последнем поиске. Находится новое на­правление поиска, сопряженное с . Оно проходит через точки, полученные при первом и последнем поиске. Заменяется на , на и т.д. Направление заменяется сопряженным направлением, после чего повторяется поиск по направлениям, уже не содержащим старого направления . Для квадратичных функций последовательность одномерных поисков приводит к точке минимума (если все операции выполнены точно). Построение сопряженного направления для квадратичной функции при изображено на рисунке 3.8. Оно проходит через точки 1 и 3.

Рисунок 3.8

 

Алгоритм:

Шаг 1. Задать начальную точку , число для окончания алгоритма, начальные направления поиска

Положим .

Шаг 2. Найти , где шаг находится в результате поиска минимума

функции по одним из методов одномерной минимизации.

Шаг 3. Проверить условия:

а) Если , то положить и перейти к шагу 2;

б) Если , проверить успешность поиска по последним направлениям. Если , то поиск завершить: , иначе положить и перейти к шагу 2;

в) Если , проверить успешность поиска по первым направлениям. Если , то поиск завершить: , иначе перейти к шагу 4 для построения сопряженного направления.

Шаг 4. Положить и проверить условие окончания:

а) если , то поиск завершить: ;

б) иначе положить (новое направление); (исключается старое направление). Если при этом , то новая система направлений линейно независима. В этом случае положить: , , , и перейти к шагу 2.

Если при этом , то новая система направлений линейно зависима. Тогда следует продолжать поиск в старых направлениях. Для этого положить: , , , и перейти к шагу 2.

 

Пример: Методом сопряженных направлений найти локальный минимум функции

Решение:

1. Зададим начальную точку , ,

20. Получаем . Найдем минимум функции по . Применим метод квадратичной интерполяции, т.к. минимизируемая функция квадратичная. Получим .

30. Имеем i = 0 < n – 1 = 1, поэтому i = i + 1 = 1 и переходим к шагу 2.

21. Получаем . Найдем минимум функции по . Применим метод квадратичной интерполяции, т.к. минимизируемая функция квадратичная. Получим .

31. Имеем , поэтому i = i + 1 = 2 и переходим к шагу 2.

22. Получаем . Найдем минимум функции . Получим .

32. Имеем . Переходим к шагу 4.

40. Находим Т.к. положим . Т.к. , то новая система линейно независима. Положим

и перейдем к шагу 2.

23. Получаем . Найдем минимум функции по . Получим .

33. Имеем i = 0 < n – 1 = 1, поэтому i = i + 1 = 1 и переходим к шагу 2.

24. Получаем . Найдем минимум функции по . Получим .

34. Имеем , поэтому i = i + 1 = 2 и переходим к шагу 2.

25. Получаем . Найдем минимум функции . Получим .

32. T.к. , то процесс поиска минимума завершается: .

 


Дата добавления: 2015-07-20; просмотров: 838 | Нарушение авторских прав


Читайте в этой же книге: Общие принципы методов поиска безусловного экстремума | Метод конфигураций (метод Хука - Дживса) | Метод деформируемого многогранника | Метод градиентного спуска с постоянным шагом | Метод наискорейшего градиентного спуска (Метод Коши) | Метод Гаусса - Зейделя | Метод Ньютона | Метод Ньютона - Рафсона | Метод Марквардта | Пример отчета по лабораторной работе |
<== предыдущая страница | следующая страница ==>
Метод вращающихся координат (метод Розенброка)| Методы первого порядка

mybiblioteka.su - 2015-2024 год. (0.009 сек.)