Описание алгоритма:
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений ,
, называемых
-сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить
одномерных поисков.
Алгоритм метода:
Шаг 1. Задать исходные точки ,
и направление
. В частности, направление
может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении
получить точку
, являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении
получить точку
;
|
|
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо
) в направлении
с выводом в точку
.
Ход решения:
Исходные данные:
Шаг 1.
Пусть .
Итерация 1:
Шаг 2.
1) найдём значение , при котором
минимизируется в направлении
, т.е.
Произвольная точка на луче из точки в направлении
определяется как:
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
2) Аналогично находим значение , при котором
минимизируется в направлении
, т.е.
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
3) Аналогично находим значение , при котором
минимизируется в направлении
, т.е.
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Шаг 3.
Положим .
Направление оказывается сопряжённым с направлением
. Оптимизация вдоль направления
даёт искомый экстремум.
Шаг4.
Находим значение , при котором
минимизируется в направлении
, т.е.
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Итерация 2:
Шаг 2.
1) найдём значение , при котором
минимизируется в направлении
, т.е.
Произвольная точка на луче из точки в направлении
определяется как:
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
2) Аналогично находим значение , при котором
минимизируется в направлении
, т.е.
|
|
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
3)Аналогично находим значение , при котором
минимизируется в направлении
, т.е.
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Шаг 3.
Положим .
Направление оказывается сопряжённым с направлением
. Оптимизация вдоль направления
даёт искомый экстремум.
Шаг 4.
Находим значение , при котором
минимизируется в направлении
, т.е.
, откуда
,
. Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Решение поставленной задачи методом сопряжённых направлений Пауэлла представлено на рисунке 3.
![]() |
Рисунок 3 – решение задачи методом сопряжённых направлений Пауэлла |