X-PDF

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

Поделиться статьей

Описание алгоритма:

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

приводится к виду сумма полных квадратов

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

В методе Пауэлла поиск реализуется в виде:

вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.

Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить одномерных поисков.

Алгоритм метода:

Шаг 1. Задать исходные точки , и направление . В частности, направление может совпадать с направлением координатной оси .

Шаг 2. Произвести одномерный поиск из точки в направлении получить точку , являющуюся точкой экстремума на заданном направлении .

Шаг 3. Произвести одномерный поиск из точки в направлении получить точку .

Шаг 4. Вычислить направление .

Шаг 5. Провести одномерный поиск из точки (либо ) в направлении с выводом в точку .

Ход решения:

Исходные данные:

Шаг 1.

Пусть .

Итерация 1:

Шаг 2.

1) найдём значение , при котором минимизируется в направлении , т.е.

Произвольная точка на луче из точки в направлении определяется как:

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

2) Аналогично находим значение , при котором минимизируется в направлении , т.е.

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

3) Аналогично находим значение , при котором минимизируется в направлении , т.е.

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Шаг 3.

Положим .

Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 990

Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.

Шаг4.

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

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Итерация 2:

Шаг 2.

1) найдём значение , при котором минимизируется в направлении , т.е.

Произвольная точка на луче из точки в направлении определяется как:

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

2) Аналогично находим значение , при котором минимизируется в направлении , т.е.

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

3)Аналогично находим значение , при котором минимизируется в направлении , т.е.

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Шаг 3.

Положим .

Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.

Шаг 4.

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

, откуда , . Подставляя эти значения в выражение целевой функции, получаем:

Дифференцируем по и приравниваем к 0, получаем:

Получаем:

Решение поставленной задачи методом сопряжённых направлений Пауэлла представлено на рисунке 3.

Рисунок 3 – решение задачи методом сопряжённых направлений Пауэлла


Поделиться статьей
Автор статьи
Анастасия
Анастасия
Задать вопрос
Эксперт
Представленная информация была полезной?
ДА
58.69%
НЕТ
41.31%
Проголосовало: 990

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram

ОБРАЗЦЫ ВОПРОСОВ ДЛЯ ТУРНИРА ЧГК

Поделиться статьей

Поделиться статьей(Выдержка из Чемпионата Днепропетровской области по «Что? Где? Когда?» среди юношей (09.11.2008) Редакторы: Оксана Балазанова, Александр Чижов) [Указания ведущим:


Поделиться статьей

ЛИТЕЙНЫЕ ДЕФЕКТЫ

Поделиться статьей

Поделиться статьейЛитейные дефекты — понятие относительное. Строго говоря, де­фект отливки следует рассматривать лишь как отступление от заданных требований. Например, одни


Поделиться статьей

Введение. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси

Поделиться статьей

Поделиться статьей1. Псковская Судная грамота – крупнейший памятник феодального права эпохи феодальной раздробленности на Руси. Специфика периода феодальной раздробленности –


Поделиться статьей

Нравственные проблемы современной биологии

Поделиться статьей

Поделиться статьейЭтические проблемы современной науки являются чрезвычайно актуальными и значимыми. В связи с экспоненциальным ростом той силы, которая попадает в


Поделиться статьей

Семейство Первоцветные — Primulaceae

Поделиться статьей

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


Поделиться статьей

Вопрос 1. Понятие цены, функции и виды. Порядок ценообразования

Поделиться статьей

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


Поделиться статьей

или напишите нам прямо сейчас:

Написать в WhatsApp Написать в Telegram
Заявка
на расчет