Летова Т. А. , Пантелеев А. В. Методы оптимизации. Практический курс, 2011
СХОДИМОСТЬ МЕТОДА Теорема 1. Если квадратичная функция f(x) = (х, Нх) + (b, х) + а с неотрицательно определенной матрицей Н достигает своего минимального значения на Rn, то метод Флетчера-Ривса обеспечивает отыскание точки минимума не более чем за n шагов. Теорема 2. Пусть функция f(x) дифференцируема и ограничена снизу на Rm, а ее градиент удовлетворяет условию Липшица Тогда при произвольной начальной точке Теорема 2 гарантирует сходимость последовательности {xk} к стационарной точке x*, где ▽f(x*)=0. Поэтому найденная точка x* нуждается в дополнительном исследовании для ее классификации. Метод Полака-Рибьера гарантирует сходимость последовательности {xk} к точке минимума только для сильно выпуклых функций. Оценка скорости сходимости получена только для сильно выпуклых функций, в этом случае последовательность {xk} сходится к точке минимума функции f(x) со скоростью: |xk+n – x*| ≤ C|xk – x*|, k = {0, n, 2, …} ПРИМЕР. Найти минимум функции методом сопряженных градиентов: f(X) = 2x12+2x22+2x1x2+20x1+10x2+10. Решение. В качестве направления поиска выберем вектор градиент в текущей точке:
Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f '(x1)=0): 2800*t1-500 = 0 Получим шаг: t0 = 0.1786
Выполнение этого шага приведет в точку:
Итерация №1.
Проверим критерий остановки: |▽f(X1)|<ε X2 = X1 - t1d1 d1 = ▽f(X1) + b0▽f(X0)
Сделаем шаг вдоль направления антиградиента.
f(X2) = 2*(-3.0612*t1-3.5714)2+2*(3.8265*t1-1.7857)2+2*(-3.0612*t1-3.5714)*(3.8265*t1-1.7857)+20*(-3.0612*t1-3.5714)+10*(3.8265*t1-1.7857)+10 → min Найдем такой шаг, чтобы целевая функция достигала минимума вдоль этого направления. Из необходимого условия существования экстремума функции (f '(x2)=0): 49.198250728863*t2-22.9591836734694 = 0 Получим шаг: t0 = 0.4667 Выполнение этого шага приведет в точку:
Итерация №2.
Проверим критерий остановки: |▽f(X2)| < ε
Анализ решения. Найдем матрицу Гессе функции f(X) = 2x12+2x22+2x1x2+20x1+10x2+10.
Так как матрица Гессе является положительно определенной, то функция f(X) строго выпукла и, следовательно, в стационарной точке достигает глобальный минимум. АЛГОРИТМ ДЭВИДОНА - ФЛЕТЧЕРА – ПАУЭЛЛА
Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два.
Рассмотрим алгоритм Дэвидона - Флетчера - Пауэлла минимизации дифференцируемой функции нескольких переменных. В частности, если функция квадратичная, то, как будет показано позднее, метод вырабатывает сопряженные направления и останавливается после выполнения одной итерации, т.е. после поиска вдоль каждого из сопряженных направлений. Начальный этап. Пусть Основной этап. Шаг 1. Если зк Шаг 2. Построить Dj+1 следующим образом:
где pj = ljdj, (2) qj = Заменить j на j + 1 и перейти к шагу 1. Пример. Рассмотрим следующую задачу: Минимизировать (x1 - 2)4 + (x1 - 2x2)2. Результаты вычислений методом Дэвидона - Флетчера - Пауэлла приведены в таблице 1. Таблица 1. Результаты вычислений по методу Дэвидона - Флетчера - Пауэлла.
На каждой итерации вектор dj для j = 1, 2 определяется в виде
Рисунок 1. Метод Дэвидона - Флетчера - Пауэлла. Лемма 1 показывает, что каждая матрица Dj положительно определена и dj является направлением спуска. Для доказательства леммы нам понадобится: Теорема 1. Пусть S - непустое множество в Еn, точка x О cl S. Конусом возможных направлений в точке x называется множество D = {d: d ¹ 0, x + ld О S при всех l О (0, d) для некоторого d > 0}. Определение. Пусть x и y - векторы из Еn и |xTy| - абсолютное значение скалярного произведения xTy. Тогда выполняется следующее неравенство, называемое неравенством Шварца: |xTy| £ ||x|| ||y||. Лемма 1. Пусть y1 О Еn, а D1 – начальная положительно определенная симметрическая матрица. Для j = 1,..., n положим yj+1 = yj + ljdj, где dj = –Dj а lj является оптимальным решением задачи минимизации f(yj + ldj) при l ³ 0. Пусть, кроме того, для j = 1,..., n – 1 матрица Dj+1 определяется по формулам (1) - (3). Если В варианте метода переменной метрики, предложенном Дэвидоном, Флетчером и Пауэллом, для нахождения матрицы Исходная матрица Оценка элементов Алгоритм Дэвидона–Флетчера–Пауэлла получим, если в уравнении (6.2.5) положить
Заметим, что так как матрицы
Роль матрицы
В случае квадратичной функции В большинстве вариантов алгоритма функция
В качестве критерия останова работы алгоритма авторами было предложено использовать одно из следующих правил. Каждая из составляющих векторов Вычисленная норма каждого из этих векторов в точке остановки меньше наперед заданной величины. На рис.6.6 приведена траектория движения по алгоритму Дэвидона–Флетчера–Пауэлла при начальной длине шага На практике оказалось, что в данном методе и в других методах переменной метрики могут иногда встречаться шаги в противоположном (относительно направления точки минимума) направлении, либо эти методы могут оканчиваться в нестационарной точке. Как выяснилось, это является следствием вырождения матрицы Если же эти операции выполнить нельзя, то матрицу
ДОКАЗАТЕЛЬСТВО
Проведем доказательство по индукции. При j = 1 матрица D1 симметрическая и положительно определенная по условию леммы. Кроме того,
Так как Dj – симметрическая положительно определенная матрица, то существует положительно определенная матрица Dj1/2, такая, что Dj = Dj1/2Dj1/2. Пусть a = Dj1/2x и b = Dj1/2qj. Тогда xTDjx = aTa, qjTDjqj = bTb и xTDjqj = aTb. Подставляя эти выражения в (4), получаем:
По неравенству Шварца имеем (aTa)(bTb) ³ (aTb)2. Таким образом, чтобы доказать, что xTDj+1x ³ 0, достаточно показать, что pjTqj > 0 и bTb > 0. Из (2) и (3) следует, что pjTqj = ljdjT[ По предположению Покажем теперь, что xTDj+1x > 0. Предположим, что xTDj+1x = 0. Это возможно только в том случае, если (aTa)(bTb) = (aTb)2 и pjTx = 0. Прежде всего заметим, что (aTa)(bTb) = (aTb)2 только при a = lb, т.е. Dj1/2x = lDj1/2qj. Таким образом, x = lqj. Так как x ¹ 0, то l ¹ 0. Далее, 0 = pjTx = l pjTqj противоречит тому, что pjTqj > 0 и l ¹ 0. Следовательно, xTDj+1x > 0, т.е. матрица Dj+1 положительно определена. Поскольку Лемма доказана. Квадратичный случай. В дальнейшем нам понадобиться: Теорема 2. Пусть f(x) = cTx + 1 xTHx, где Н - симметрическая матрица порядка n x n. Рассмотрим Н - сопряженные векторы d1, …, dn и произвольную точку x1. Пусть lk для k = 1, …, n - оптимальное решение задачи минимизации f(xk + ldk) при l О Е1 и xk+1 = xk + ldk. Тогда для k = 1, …, n справедливы следующие утверждения: 1. 2. 3. xk+1 является оптимальным решением задачи минимизации f(x) при условии В частности, xn+1 – точка минимума функции f на Еn. Если целевая функция f квадратичная, то в соответствии со сформулированной ниже теоремой 3 направления d1, …, dn, генерируемые методом Дэвидона - Флетчера - Пауэлла, являются сопряженными. Следовательно, в соответствии с утверждением 3 теоремы 2 метод останавливается после завершения одной итерации в оптимальной точке. Кроме того, матрица Dn+1, полученная в конце итерации, совпадает с обратной к матрице Гессе Н. Теорема 3. Пусть Н – симметричная положительно определенная матрица порядка n x n. Рассмотрим задачу минимизации f(x) = cTx + 1 xTHx при условии x О En. Предположим, что задача решена методом Дэвидона - Флетчера - Пауэлла при начальной точке y1 и начальной положительно определенной матрице D1. В частности, пусть lj, j = 1, …, n, – оптимальное решение задачи минимизации f(yj + ldj) при l ³ 0 и yj+1 = yj + ljdj, где dj = -Dj Доказательство. Прежде всего покажем, что для j, такого, что 1 £ j £ n, справедливы следующие утверждения: 1. d1, …, dj линейно независимы. 2. djTHdk = 0 для i ¹ k; i, k £ j. 3. Dj+1Hpk, или, что эквивалентно, Dj+1Hdk = dk для 1 £ k £ j, pk = lkdk. Проведем доказательство по индукции. Для j = 1 утверждения 1 и 2 очевидны. Чтобы доказать утверждение 3, заметим прежде всего, что для любого k справедливы равенства Hpk = H(lkdk) = H(yk+1 - yk) = В частности, Hp1 = q1. Таким образом, полагая j = 1 в (1), получаем т.е. утверждение 3 справедливо при j = 1. Теперь предположим, что утверждения 1, 2 и 3 справедливы для j £ n – 1. Покажем, что они также справедливы и для j + 1. Напомним, что по утверждению 1 теоремы 2 diT 0 = diT Ввиду предположения индукции это равенство показывает, что утверждение 2 также справедливо для j+1. Теперь покажем, что утверждение 3 справедливо для j+1. Полагая k £ j+1, имеем
Учитывая (7) и полагая k = j + 1 в (8), получим, что Dj+2Hpj+1 = pj+1. Теперь пусть k £ j. Так как утверждение 2 справедливо для j + 1, то pj+1THpk = lklj+1dj+1THdk = 0. (9) По предположению индукции из (7) и вследствие того, что утверждение 2 справедливо для j + 1, получаем
Подставляя (9) и (10) в (8) и учитывая предположение индукции, получаем Таким образом, утверждение 3 справедливо для j+1. Осталось показать, что утверждение 1 справедливо для j+1. Предположим, что Пусть теперь j = n в утверждении 3. Тогда Теорема доказана.
МЕТОД КУБИЧЕСКОЙ ИНТЕРПОЛЯЦИИ
Интерполяция – это способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Метод использует кусочную кубическую Эрмитову аппроксимацию и сохраняют монотонность и форму данных. Если какой-либо из элементов вектора xi находится вне интервала, заданного вектором x, то выбранный метод интерполяции используется также и для экстраполяции. Как альтернатива, функция yi = interp1(x, y, xi, method, extrapval) заменяет экстраполированные значения теми, которые заданы вектором extrapval. Для последнего часто используется нечисловое значение NaN. Все методы работают на неравномерной сетке значений вектора x. При решении реальных задач редко приходится иметь дело с функциями одной переменной. Однако методы одномерной оптимизации важны при многомерной оптимизации, которая выполняется в основном по следующему правилу: зафиксировать некоторую точку, выбрать подходящее направление, выполнить одномерную оптимизацию из выбранной точки в выбранном направлении. Поэтому методы интерполяции полезны для выполнения линейного поиска при оптимизации функций многих переменных. В этом случае обычно требуется найти минимум функции Рассмотрим метод Дэвидона, в котором функция аппроксимируется кубическим полиномом, и который обеспечивает большую точность определения точки минимума. Обсуждение метода проведем в виде, пригодном для многомерной оптимизации. Для интерполяции используются значения функции и ее производной, вычисленные в двух точках. Пусть минимизируется функция
Предполагаем, что известны следующие значения:
Эту информацию можно использовать для построения кубического полинома Если выбрать p=0 (для простоты), то уравнения, определяющие a, b, c, d, выглядят так: Эти уравнения имеют решение: Стационарные точки кубического полинома являются решением уравнения Точкой минимума кубического полинома является
Как уже отмечалось, это все выполняется при Если Остается задача определения начальной величины q. Значение q, которое было бы одинаково приемлемо для всех задач, выбрать весьма сложно. Дэвидон, Флетчер и Пауэлл предложили выбирать q следующим образом:
Алгоритм кубической интерполяции. 1. Найти 2. Проверить, выполняется ли условие 3. Вычислить 4. Если 5. Использовать выражение (*) для аппроксимации точки минимума на интервале (0, q) значением r. 6. Если 7. Вернуться на шаг 5, используя интервал (0, r), если Рассмотренный метод кубической интерполяции является одним из интерполяционных методов Эрмита, приспособленным специально для оптимизации. Этот метод требует знания производных функций и используется в основном в так называемых квазиньютоновских методах многомерной оптимизации, которые и сами по себе используют производные.
ЗАКЛЮЧЕНИЕ
Метод сопряженных градиентов формирует направления поиска, в большей мере соответствующие геометрии минимизируемой функции. Первоначально метод был предложен Дэвидоном и затем развит Флетчером и Пауэллом. Метод Дэвидона-Флетчера-Пауэлла называют также и методом переменной метрики. Он попадает в общий класс квазиньютоновских процедур, в которых направления поиска задаются в виде -Dj*grad(f(y)). Направление градиента является, таким образом, отклоненным в результате умножения на -Dj, где Dj - положительно определенная симметрическая матрица порядка n×n, аппроксимирующая обратную матрицу Гессе. На следующем шаге матрица Dj+1 представляется в виде суммы Dj и двух симметрических матриц ранга один каждая. В связи с этим схема иногда называется схемой коррекции ранга два. Интерполяция – это способ нахождения промежуточных значений величины по имеющемуся дискретному набору известных значений. Метод использует кусочную кубическую Эрмитову аппроксимацию и сохраняют монотонность и форму данных. При решении реальных задач редко приходится иметь дело с функциями одной переменной. Однако методы одномерной оптимизации важны при многомерной оптимизации, которая выполняется в основном по следующему правилу: зафиксировать некоторую точку, выбрать подходящее направление, выполнить одномерную оптимизацию из выбранной точки в выбранном направлении. Поэтому методы интерполяции полезны для выполнения линейного поиска при оптимизации функций многих переменных.
СПИСОК ЛИТЕРАТУРЫ
1. Кононюк А.Е. Основы теории оптимизации, 2011 Летова Т. А., Пантелеев А. В. Методы оптимизации. Практический курс, 2011 3. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах, 2005
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|