Теорема о линейной сходимости градиентного метода с постоянным шагом

    Дисциплина: Разное
    Тип работы: Доклад
    Тема: Теорема о линейной сходимости градиентного метода с постоянным шагом

    Доклад по математическим методам в экономике
    “Теорема о линейной сходимости градиентного метода с постоянным шагом”
    ДВГУ
    Теорема о линейной сходимости градиентного метода с постоянным шагом.
    Пусть выполнены условия: функция
    ограничена снизу, непрерывно дифференцируема и
    ’ удовлетворяет условию Липшица и, кроме того,
    f дважды непрерывно дифференцируема и
    сильно выпукла с константой
    Тогда при
    (0, 2/
    градиентный метод с шагом
    сходится со скоростью геометрической прогрессии
    со знаменателем
    max{|1
    |, |1
    x*||
    x*||.
    Д о к а
    з а т е л
    ь с т в о.
    Решение
    x* =
    argmin
    x) существует и единственно в силу
    теорем 1)
    . Для функции F(
    x) =
    x) воспользуемся аналогом формулы Ньютона— Лейбница
    y) = F(
    x) +
    x)](
    или, для
    x* и
    n, учитывая, что
    x*) =
    n) =
    cc
    [x* + s(
    *)](
    (здесь
    воспользовались
    ). Далее, в силу утверждения 4)
    cc
    при всех
    . Кроме того (в силу 5)
    ), по условию
    cc
    при тех же
    x. Поэтому, так как
    ||h||
    cc
    x* +
    ||h||
    выполнено неравенство
    ||h||
    cc
    x* +
    ||h||
    (10)
    Интеграл, стоящий в этом неравенстве, определяет линейный (
    симметричный
    в силу симметричности
    f) оператор на
    , обозначим его
    . Неравенство
    (10)
    означает, что
    . В силу
    градиентный метод
    записывается в виде
    x*).
    Но тогда
    n|| = ||
    x*)|| =
    = ||(I
    x*)||
    x*||.
    Спектр
    ) оператора I
    состоит из чисел вида
    , где
    ). В силу
    (10)
    и неравенства
    и следовательно
    max{|1
    |, |1
    |} =
    Таким образом,
    q||x
    x*||.
    Из этого неравенства вытекает утверждение
    данной
    теоремы
    Оптимальный выбор шага
    Константа
    q, характеризующая скорость сходимости метода, зависит от шага
    . Нетрудно видеть, что величина
    max{|1
    |, |1
    минимальна, если шаг
    выбирается из условия |1
    | = |1
    | (см.
    рис. 1
    ), т.е. если
    * = 2/(
    ). При таком выборе шага оценка сходимости будет наилучшей и будет характеризоваться величиной
    q* =
    Рис. 1.
    В качестве
    могут выступать равномерные по
    x оценки сверху и снизу собственных значений оператора
    cc
    x). Если
    , то
    1 и метод сходится очень медленно. Геометрически случай
    соответствует функциям с сильно вытянутыми линиями уровня (см.
    рис. 2
    ). Простейшим примером такой функции может служить функция на
    , задаваемая формулой
    1, x
    2) =
    Рис. 2.
    Поведение итераций градиентного метода для этой функции изображено на
    рис. 2
    — они, быстро спустившись на \"дно оврага\", затем медленно \"зигзагообразно\" приближаются к точке минимума. Число
    (характеризующее разброс собственных значений оператора
    cc
    x)) называют
    числом обусловленности функции
    . Если
    1, то функции называют
    плохо обусловленными или
    овражными. Для таких функций градиентный метод сходится медленно.
    Но даже для хорошо обусловленных функций проблема выбора шага нетривиальна в силу отсутствия априорной информации о
    минимизируемой функции. Если шаг выбирается малым (чтобы гарантировать сходимость), то метод сходится медленно. Увеличение же шага (с целью ускорения сходимости) может
    привести к
    расходимости метода.
    Теорема единственности для строго выпуклой функции.
    Задача
    min ,
    со
    строго выпуклой функцией
    не может иметь более одного решения.
    2) Теорема о разрешимости для сильно выпуклой функции.
    Задача
    min,
    дифференцируемой
    сильно выпуклой
    функцией разрешима.
    cc
    x). Поясним: здесь [
    — производная функции
    x), действующей из
    m в
    m, а
    cc
    x) — вторая производная функции
    Пусть F:
    дифференцируема
    . Тогда F удовлетворяет условию Липшица с константой
    , в том и только том случае, если ||F
    x)||
    при всех
    ( существует и обратное утверждение).
    2 сильно выпукла с константой
    c в том и только том случае, если
    cc
    c при всех
    Язык: Русский
    Скачиваний: 259
    Формат: Microsoft Office
    Размер файла: 28 Кб
    Автор:
    Скачать работу...

    Забрать файл

    Похожие материалы:


ПИШЕМ УНИКАЛЬНЫЕ РАБОТЫ
Заказывайте напрямую у исполнителя!


© 2006-2016 Все права защищены