Курс лекци Русакова по методам оптимизации (1083216), страница 9
Текст из файла (страница 9)
условие) тогда:[∇ 2 f ( x k )] −1 ≤ l −1 I[∇ 2 f ( x k )]−1 ≤ l −1Таким образом ∇f ( x k +1 ) ≤Ll −22∇f ( x k ) .2Ll −2Пусть q1=(обозначим). Выразим полученное неравенство через2∇f(x0)∇f ( x1 ) ≤ q1 ∇f ( x0 )22∇f ( x 2 ) ≤ q1 ∇f ( x1 ) ≤ q 31 ∇f ( x0 )4.........................................................................∇f ( x k ) ≤k1( q1 ∇f ( x 0 ) ) 2q1Для сильно выпуклых функций известно∇f ( x ) ≥ l x − x *2Тогда x k − x * ≤ (2l / L)q 276kТеорема доказана.Если начальные условия не удовлетворяют требованиям теоремы, тометод может не сходиться.Понятие о скорости сходимостиПусть метод обеспечивает выполнение следующего неравенстваdxk +1 − x * ≤ const xk − x *, где d- наибольшее из чисел, для которыхвыполняется это условие, тогда d- скорость сходимости метода.Если обозначить ∆k = x k − x * , тогда скорость сходимостиd = limln∆k +1, при ∆k→0 (k→ ∞).ln∆kПусть ∆k+1≈q ∆k, 0< q< 1.
Для этого случая d =1- геометрическаяскорость. Для метода Ньютона ∆k+1= const ∆k2 ⇒ d =2 - поэтому скоростьназывается квадратичной.2.07 Сравнениедостоинствинедостатковградиентного метода и метода НьютонаСравнительная таблица достоинств и недостатков градиентногометода и метода Ньютона:77МетодДостоинстваНедостаткиГрадиентный1. Глобальная сходимость, т.е.1. Медленная скорость сходимостиметодслабые требования на исходные(геометрическая сходимость,данные, точка х0 может бытьскорость сходимости d = 1).далека от х*.2.
Слабые требования к f(x),только f’(x) нужна3. Относительная простотавычисленийМетод1. Быстрая сходимостьЛокальная сходимость, т.е.Ньютона(квадратичная)начальное приближение должнобыть достаточно близко к х*)Жесткие требования на самуфункцию ( она должна быть дваждынепрерывно дифференциируема).Большой объем вычислений,связанный с необходимостьювычисления матрицы вторыхпроизводных и ее обращения.Полезен метод Ньютона в случае квадратичной функции (сходится заодин шаг).Число обусловленности локального min.Пусть Lδ = {x: f ( x ) = f ( x * ) + δ } — поверхности уровней f(x).Рассмотрим следующую величинуrδ = max x∈Lδ { x − x * } / min x∈Lδ { x − x * }Очевидно, что у окружности rδ=1, а у эллипса rδ>1 (увеличивается сувеличением растянутости).Определение:78Числом обусловленности точки локального min называется lim rδ .
Этоδ →0число дает основание для выбора метода.Определение:Говорят, что точка локального min плохо обусловлена, если числообусловленности велико, и хорошо обусловлена, если оно близко к 1.Пример.Пусть f(x) = 1/2 (Ax, x). А - диагональная матрица. Тогда числообусловленности есть отношение max диагонального элемента к minдиагональному элементу.Порядок применения методов.На первом этапе применяются методы первого порядка, так как ониобеспечивают глобальную сходимость (градиентные методы).На втором этапе ( xk − x * мало) - методы второго порядка (Ньютона).Перечисленныеметодыявляютсяклассическими,ониредкоприменяются в чистом виде, но служат базой для других методов.
Смыслмодификации метода в том, чтобы использовать достоинства обоих методов,обходя недостатки.Также известен метод Марквардта-Левенбергаx k + 1 = x k − γ k (∇ 2 f ( x k ) + α I ) −1 ∇f ( x k )Если α→ ∞ - градиентные методыα→ 0- метод Ньютона.792.08 Многошаговые ( двухшаговые ) методы. Методтяжелого шарикаОбщий вид метода тяжелого шарика:xk+1= xk - α∇f(xk)+β(xk-xk-1)Эторазностноеуравнение,полученноеиздифференциальногоуравнения, которое описывает движение шарика, катящегося по некоторойповерхностиспостояннымтрением.Введениеинерцииβ(xk-xk-1)увеличивает скорость сходимости.Теорема(о скорости сходимости метода тяжелого шарика):Если 0< l I ≤ ∇2f(x) ≤ L I и0 ≤ β ≤ 1, 0< α < 2(1+β)/L,тогда существует с=const такая, что || xk - x* || ≤ cqk , qmin =L− lL+ lБез доказательстваТакимпрогрессии,образом,какиметодсходитсяградиентныйнеметод;быстреегеометрическойпоказательгеометрическойпрогрессии тот же, только с корнями, т.е.
применение двухшагового методапри плохой обусловленности позволяет уменьшить эту обусловленность.Модификациядвухшаговогометода—градиентов.2.09 Метод сопряженных градиентовxk+1 = xk - αk ∇f(xk) + βk (xk-xk-1)80методсопряженныхОтличается тем, что αk и βk зависят от шага и выбираются следующимобразом:(αk , βk) = argmin f(xk - α∇f(xk)+β(xk-xk-1)){α,β}Для квадратичной функции f ( x )=( Ax, x )+ (b, x ), A > 021. Метод сходится за конечное число шагов, не превосходящее размерностипространства состояний.2. Градиенты в методе попарно ортогональны (∇f(xi), ∇f(xk))=0, ∀i≠kНо в Rn не может существовать более n ортогональных ненулевыхвекторов, поэтому для некоторого k ≤ n будет ∇f(xk)=0, то есть точка xkточка минимума.3.
Последовательныенаправлениядвиженияpk=xk-xk-1 удовлетворяютсоотношению (Api, pj ) =0 ∀i≠jОпределениеВекторы pi , связанные соотношением (Api, pj ) =0, называютсясопряженными или А-ортогональными.В методе сопряженных градиентов xk является точкой минимумаквадратичной функции f(x) на подпространстве, порожденном первыми kградиентами.Следовательно,никакойметод,использующийтолькоградиенты функции (точнее, в котором шаг делается по линейнойкомбинации предыдущих градиентов), не может сходиться быстрее, то естьметод сопряжённых градиентов является оптимальным по скоростисходимости в классе методов первого порядка.812.10 Модификация Полака-Ривьераxk+1= xk+ αkpk, где αk = argmin f(xk+ αpk ), α>0pk= -∇f(xk)+βkpk-1β k=((∇f ( x k ) − ∇f ( x k −1 )), ∇f ( x k ))∇f ( x k −1 )β0 = 0Для квадратичной функции последовательность точек xi, определённаяэтими формулами, совпадает с последовательностью, полученной методомсопряжённых градиентов.Этумодификациюудобнееприменятьдляпроизвольных(неквадратичных) функций.Рекомендуется применять процедуру обновления, т.е.
через каждые nшагов происходит сдвиг в направлении антиградиента.То есть β0 = 0, затем βn=0,..., βmn=0, следовательно,pk= -∇f(xk)+0*pk-1= -∇f(xk)(сдвиг в направлении антиградиента).По скорости сходимости n шагов методы сопряженного градиентаэквивалентны одному шагу метода Ньютона (для квадратичной функцииметод сходится за один шаг).2.11 Квазиньютоновские методыОбщая структура: xk+1 = xk - γkΗk∇f(xk)1. Если Hk =I , то это градиентный метод.2. Если Hk = (∇2f(xk))-1, то это метод Ньютона.823. Если Hk = Hk (∇f(xi), i=1..k) → (∇2f(xk))-1, т.е.
матрица Hk пересчитываетсярекурентным способом на основе информации, полученной на k-йитерации.Достоинство:Не надо вычислять обратную матрицу вторых производных.Обозначим pk = -Hk∇f(xk)yk= ∇f(xk+1) -∇f(xk),f ( x) =( Ax, x )+ (b, x ) , A>02Тогда для квадратичной функции имеемyk = A(xk+1-xk) = γkApkγk pk = ykA-1,поэтому матрицу Hk+1 (необязательно для квадратичной функции)выбирают так, чтобы выполнялось так называемое квазиньютоновскоеусловие:Hk+1yk= γkpk (Hk - должна стремиться к (∇2f(xk))-12.12Метод Давидона- Флетчера- Пауэлла (ДФП)TH k +1 = H k −H k yk ( H k yk )Tp pk+γ k k; Ho > 0(H k yk , yk )( pk , y k )Проверим выполнение квазиньютоновского условия:H k +1 y k = H k y k −83H k yk ( H k yk , yk )+γ( H k yk , yk )Для квадратичной функции метод сходится за n шагов, для n –размерность пространства состояний.
Скорость сходимости этого методасверхлинейная (быстрее любой геометрической прогрессии). Сходимостьглобальная. Объединяет достоинства градиентных методов и методаНьютона.Процедура применения:На очередном шаге, имея Hk, делаем шаг в направлении pk. Получаемγk (например, по методу наискорейшего спуска), получаем xk+1 , вычисляем ykи пересчитываем Hk+1 для следующего шага.Недостаток: (по сравнению с методом сопряженных градиентов).Надо хранить и пересчитывать Hk размерности m×n.Метод Бройдена-Флетчера –Шенно.H k +1ρ k p k ( pk ) T − p k ( y k ) T H k − H k y k ( p k ) T=H k +( y k , pk )где ρ k =γ k +( H k yk , y k )( yk , pk ),H 0 > 0.Примечание:Последовательностиxk,генерируемыекаждымвариантом,дляквадратичной функции совпадают.
Существует много других модификацийприведенных квазиньютоновских методов.842.13 Методы нулевого порядка (методы прямогопоиска). Методы аппроксимацииВ их основе лежит аппроксимация градиентаи матрицы вторыхпроизводных с помощью конечных разностей.Пусть ej - орт j-й оси.f (x + γej) ≈ f(x) + (∂f/∂x)jγ + O(γ2)∂f/∂xj ≈ ( f(x + γej) - f(x) )/ γ ≈ ( f(x + γej) - f(x - γej) )/ (2γ)Здесь под градиентом понимается конечная разность.
Если γ слишкоммала, то слишком велики погрешности при вычислении производных. Если γвелика, то из-за O(γ2) погрешности тоже велики. Таким образом, проблемаэтих методов - выбор γ.Метод покоординатного спускаНужны направления. Раньше их задавал градиент, теперь его нет.Возможен случайный выбор, а можно по координатным осям.Алгоритм:1) j :=12) min f(x’-γej)=f(x’’), x’’:= x’- γ*ej3) j:=j+1, x’= x’’4) if j ≤ n then goto 2)5) if not (условие окончания цикла) then goto 1Достоинство:Требуется min функции вдоль только одной прямой.Метод симплексов (Нелдера-Мида)85Алгоритм:1.Фиксируем xo…xn ( n+1- точка)Если n =2 , то выбираем равнобедренный треугольник.I2. x j =т∑ш=022x i − (1 + ) x jnnт.е. вычисляем отражённую точку.Если f(xj’) < f(xj), то xj := xj’; k:=0, иначе k:=k+1где k- количество идущих подряд неудачных отражений3. Если k<n, то (если j<n, то j:=j+1 , иначе j:=0) goto 2.4.Иначе сжатие: xl = argmin f(xj), 0≤ j ≤ n - ищем вершину, в которойфункция минимальна (то есть наименьшее значение из всех существующихвершин.5.
Cжатие: xj = xl + γ( xj - xl), ∀j (сжатие в γ раз).6. Если ||x0 – x1||≥ε, то j:=0, goto 2.7. Печать xl.Особенность: метод в ряде случаев позволяет найти глобальныйминимум, т.е. позволяет перескакивать через хребты.Существует много модификации метода.Метод Пауэлла (сопряженных направлений)Идея: Для двух точек x0,x1 делается шаг в произвольном направленииp0. Получаем точки x2,x3. Следующий шаг делаем в направлении p1.Находится x*.86p1= x3-x2x2x3p1x*p0p1x0x1Утверждается, что (Ap1,po)=0.Поэтому для квадратичной функции метод сойдется за n-шагов.
Этоодин из лучших методов прямого поиска.2.14 Методы прямого поиска в задачах одномернойминимизации. Метод квадратичной интерполяции.Схема метода: xk+1 = xk + tkSk , где Sk -направление.Необходимо определить tk.. Для этого надо найти минимум функцииодной переменной γ(t) = f(xk + tSk).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
