Образовательный блог – всё для учебы

Определение минимального значения многопараметрической функции Q (х), заданной в n-мерном евклидовом пространстве связано с решением задачи безусловной оптимизации:

min Q(x₁, х₂,…, x_n). (5.1)

Здесь каждая переменная x_i, i= 1, 2, …, n, может принимать значения от —? до +?. Предположим, что функция Q (х) является унимодальной функцией, для которой в каждой точке х может быть получено с помощью градиента ?Q(х)= {?Q/?x₁, …, ?Q/?x_n), а при необходимости и гессиана (матрицы вторых производных)

G(х) = {?₂Q/dx_idx_j}.

Рассмотрим класс алгоритмов, осуществляющих последовательный поиск точки минимума х* функции Q (х) из заданного начального приближения х° по итерационной формуле

x^r+1 = x^r + ?^r = x^r + ?_rS^r, r = 0,1,… (5.2)

где x^r — приближенное решение задачи (5.1), полученное на r-й итерации; ?^r= (х^r+1 — х^r) — приращение варьируемых параметров на r-й итерации; S^r — единичное направление, ведущее к уменьшению функции Q (х); ?_r — длина шага вдоль направления S^r. Последовательность точек испытаний {х^r}, полученная по формуле (5,2) и удовлетворяющая цепочке неравенств

Q(х⁰) > Q(x¹) > … > Q (x^k). (5.3)

называется релаксационной последовательностью.

Разложим функцию Q (х) относительно точки х^r в ряд Тейлора, ограничиваясь членами первого порядка

Q(x^r+1) ? Q(x^r) + (?Q^T(x^r), ?^r). (5.4)

Из условия (5.3) следует, что на каждой итерации приращение А’ должно выбираться таким образом, чтобы выполнялось неравенство: Q (х^r+1) — Q (х^r) < 0. Учитывая соотношение (5.4), получаем, что

(?Q^T(x^r), ?^r) = ?_r(?Q^T(x^r), S^r) < 0. (5.5)

Для обеспечения наибольшей скорости уменьшения функции Q (х) вдоль единичного направления последнее должно совпадать с нормализованным значением антиградиента:

S^r = -?Q(x^r)/||?Q(x^r||. (5.6)

Из (5.4) с учетом неравенства (5.5) следует, что единичное направление S^r, обеспечивающее наибольшую скорость уменьшения функции Q (х), является решением экстремальной задачи

min (?Q^T(x^r), S) при условии что (S^T‘, S)= 1.

Методы построения релаксационной последовательности (5.3) с помощью итерационной формулы (5.2), в которой направление поиска S^r зависит от значения антиградиента, называются градиентными методами спуска. При заданном направлении поиска S^r выбор точки очередного испытания согласно (5.2) сводится к определению положительного значения шага ?_r вдоль этого направления. Реализация градиентного метода спуска, в которой оптимальная длина шага ?_r вдоль направления антиградиента (5.6) является решением одномерной задачи минимизации:

Q{x^r + ?_rS^r) = min Q(x^r + ?S_r), (6.10)

называется методом наискорейшего спуска.

Алгоритмы, реализующие метод наискорейшего спуска, отличаются друг от друга способом. решения экстремальной задачи (5.10). Если функция Q (х) является дважды дифференцируемой (Q(х)?С²), то ее можно аппроксимировать в точке (r + 1)-го приближения полиномом второй степени

Q(x^r+1) ? Q (х^r) + ?_r(?Q^T(х^r), S^r) + ?_r²(S^r)^TG(х^r)S^r.

Отсюда получаем, что оптимальным решением задачи (5.10) является выражение

?_r = —(?Q^T(х^r), S^r)/(S^r)^TG(х^r)S^r. (5.13)

Достоинством метода наискорейшего спуска является его простота. Однако он имеет ряд существенных недостатков, среди которых необходимо отметить следующие. Во-первых, это — одношаговый метод, в котором при выборе точки очередного испытания х^r+1 не используется информация о предыдущих испытаниях, кроме испытания в точке x^r. Во-вторых, если гессиан G (х) минимизируемой функции Q (х) является плохо обусловленной матрицей, наименьшее и наибольшее собственные значения которой сильно отличаются друг от друга, то процесс поиска замедляется в связи с зигзагообразностью траектории проводимых испытаний х⁰, х¹,…,х^k (рис. 5.1).

Рис. 5.1. Зигзагообразная траектория приближения к точке минимума x* квадратичной функции с помощью метода наискорейшего спуска

При этом может потребоваться недопустимо большое число итераций, прежде чем будет получена требуемая точность локализации точки локального минимума х*.
Q(x) = x»^x+b^x + a

Рассмотренное свойство метода привод к тому, что он позволяет получить оптимальное решение х* задачи безусловной минимизаций (5.1) за конечное число итераций и в качестве условия окончания поиска обычно используется неравенство

||?Q(x^r)|| ? ?.

Для устранения недостатка метода F²², связанного с игнорированием информации о предыдущих испытаниях, рассмотрим алгоритм, реализующий градиентный метод с памятью, в котором при выборе очередного приращения ?^r учитывается инфор¬мация о приращении ?^r-1 на предыдущем шаге. Для этого потребуем, чтобы на каждой итерации приращение ?^r выбиралось таким образом, чтобы обеспечивалась наибольшая скорость уменьшения функции Q (х) при условии, что квадрат модуля разности приращения ?^r и взвешенного приращения ??^r-1 оставался равным постоянной величине К:

min (?Q^T(x^r), ?). (5.17)

Оптимальным решением задачи (5.17) является линейная комбинация антиградиента функции Q (х), вычисленного в точке х^r и приращения, полученного на предыдущей итерации:

?^r = – ?_r?Q(x^r) + ?_r?^r-1. (5.18)

Значения коэффициентов ?_r и ?_r в формуле (5.18), полученной для построения очередного приращения ?^r, могут быть выбраны из условия обеспечения минимального значения функцир Q (х) вдоль направления ?^r:

Q(x^r – ?_r?Q(x^r) + ?_r?^r-1) = min Q (^r – ?_r?Q(x^r) + ?_r?^r-1). (5.21)

Алгоритмы, реализующие градиентный метод в памятью, отличаются друг от друга способом решения экстремальной задачи (5.21). В качестве одного из подходов к численному решению задачи (5.21) рассмотрим метод квазилинеризации решения эквивалентной ей системы нелинейных уравнений.

О градиентных методах спуска, которые позволяют найтаточку минимума x* = (х₁, …, x₁) квадратичной функции (5.14) не больше, чем за n итераций, говорят, что они обладают квадратичной скоростью сходимости. Более подробно методы локальной оптимизации, обладающие квадратичной скоростью сходимости, будут рассмотрены в следующем посте.

1. Квазиньютоновские методы минимизации
2. Задачи и методы оптимизации в системах имитационного моделирования
3. Минимизация функций без вычисления производных
4. Методы полиномиальной интерполяции
5. Виртуальные и динамические методы, замещающие методы
6. Параллельные методы, комбинирующие пассивные и последовательные стратегии поиска
7. Многомерный случай для задач безусловной минимизации
8. Методы-функции и методы-процедуры – синтаксис объявления, реализация методов и варианты вызова методов
9. Численные методы интегрирования
10. Условия оптимальности для задачи условной оптимизации
11. Позитивизм. Общенаучные методы познания
12. Условия оптимальности для некоторых классов моделей принятия решений
13. Аналитические методы расчета надежности ТЭС и АЭС
14. Абстрактные методы – объявление, наследование, полиморфизм
15. Рассылки сообщений, методы: Dispatch, Perform, Broadcast, NotifyControls, функции Windows API
16. Алгоритм, реализующий метод внутренних точек
17. Использование коллектива независимых стохастических автоматов как некоторой системы поисковой оптимизации