40110

Методы наискорейшего и координатного спуска для минимизации выпуклой функции без ограничений. Их алгоритмы и геометрическая интерпретация

Доклад

Менеджмент, консалтинг и предпринимательство

Все методы спуска решения задачи безусловной минимизации различаются либо выбором направления спуска, либо способом движения вдоль направления спуска. Решается задача минимизации функции f(x) на всём пространстве Rn. Методы спуска состоят в следующей процедуре построения последовательност

Русский

2013-10-15

94.5 KB

45 чел.

25. Методы наискорейшего и координатного спуска для минимизации выпуклой функции без ограничений. Их алгоритмы и геометрическая интерпретация.

Выпуклой функцией на выпуклом множестве X называется функция: f(x1 + (1 – )x2)  f(x1)+ (1 – )f(x2)      x1, x2 X, [0,1]

Если в точке x0 у выпуклой функции f локальный min, то в этой точке grad f = 0.

У выпуклой функции локальный min совпадает с глобальным.

Общих методов решения нелинейной задачи не существует, однако для некоторых классов нелинейных задач разработаны общие методы, в частности, когда функция является выпуклой. Тогда задача заключается в минимизации выпуклой дифференцируемой  функции f(x), то есть

f(x)  min

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

Решается задача минимизации функции f(x) на всём пространстве Rn. Методы спуска состоят в следующей процедуре построения последовательности {Xk}. В качестве начального приближения выбирается любая точка X0Rn. Последовательные приближения X1, X2, … строятся по следующей схеме:

  1.  в точке Xk выбирают направление спуска –Sk n-мерный вектор;
  2.  находят (k+1)-е приближение по формуле Xk+1 = XkkSk.

Направление Sk и параметр k выбираются из условия сходимости последовательности решений к некоторому оптимальному решению X*, то есть необходимо обеспечить неравенство f(Xk+1) < f(Xk).

Вообще говоря, можно бесконечно долго приближаться к X*. В некоторых случаях мы можем попасть в точку  X*, в которой grad f = 0. Поэтому решение задачи часто находиться с точностью до некоторого  или .

| Xk+1Xk| <  

| f(Xk+1) – f(Xk)| < .

Метод наискорейшего спуска 

Если функция дифференцируема, то можно использовать градиентные методы. МНС является одним из вариантов градиентного спуска. Суть градиентного метода заключается в следующем: выбрать произвольную точку X0 и с помощью антиградиента -f(X0), вычисленного в этой точке, определить направление наискорейшего убывания функции и сместиться из точки X0 по этому направлению:

Таким образом, строится последовательность {Xk}.

Если величину k выбирать так, чтобы значение f = f(Xk+1) – f(Xk) было наименьшим, то градиентный метод называется МНС. В силу того, что f(Xk) известно и учитывая, что Xk+1=Xk kf(Xk), получаем, что приращение f является функцией одной переменной k, то есть f  = f (k).

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

Величину k , при которой достигается наименьшее значение f , можно определить одним из методов одномерной минимизации.

Поиск решения прекращается, когда | Xk+1Xk| < или | f(Xk+1) – f(Xk)| < .

Алгоритм метода наискорейшего спуска:

0 шаг. Выберем .

1 шаг. Находим . Если , то остановка и  Хk – решение.

2 шаг. Находится .

3 шаг. .

4 шаг. Если | Xk+1Xk| < или | f(Xk+1) – f(Xk)| < , то остановка и  Хk+1 – решение

5 шаг. k=k+1, переход к шагу 1.

С геометрической точки зрения градиент в очередной точке Xk+1 ортогонален градиенту в предыдущей точке Xk. Для случая функции двух переменных МНС имеет следующую геометрическую интерпретацию: для любого к луч, идущий от точки Xk к точке Xk+1, перпендикулярен к линии уровня функции, проходящей через точку  Xk, и касается линии уровня, проходящей через точку  Xk+1.


Метод покоординатного спуска

Одним из наиболее простых способов определения направления спуска является выбор в качестве Sk одного из координатных векторов e1, e2, …, en, вследствие чего у Xk на каждой итерации изменяется лишь одна из компонент. Существуют многочисленные варианты покоординатного спуска. Рассмотрим 2 из них.

Обозначим через ei =(0..0, 1, 0..0) – вектор, у которого на i-ой позиции находится 1.

Поиск решения прекращается, когда k < .

Метод ПС может применять (не всегда эффективно) и для не дифференцируемых функций, так как сам алгоритм покоординатного спуска не требует вычисления производной функции.

Теорема [о сходимости МПС]. Пусть функция f(x) является выпуклой в Rn и имеет непрерывную производную. Тогда последовательность точек МПС сходится к точке min.

Алгоритм метода покоординатного спуска:

0 шаг. Выберем .

1 шаг. Положим:

                (1)

Условие (1) обеспечивает перебор координатных векторов.

2 шаг. Вычисляют значение целевой функции f(X) в точке  и проверяют неравенство:

 (2)

Если (2) выполняется, то полагают:

Проверяется условие прекращения решения и при необходимости переход к шагу 1.

3 шаг. Если (2) не выполняется, то вычисляют значение целевой функции f(X) в точке  и проверяют неравенство:

 (3)

Если (3) выполняется, то полагают:

Проверяется условие прекращения решения и при необходимости переход к шагу 1.

4 шаг. (k+1)-ая итерация называется удачной, если справедливо либо (2), либо (3), иначе она является неудачной и шаг k дробиться / увеличивается.

Существует другой вариант ПС, основанный на использовании градиента функции.

Поиск решения прекращается, когда | Xk+1-Xk| < или .

Алгоритм метода покоординатного спуска:

0 шаг. Выберем .

1 шаг. Находят максимальный по абсолютной величине из частных производных (элементов градиента), вычисленных в точке Xk, то есть

Обозначим через imax номер элемента, соответствующего S. Тогда координатный вектор

В качестве Sk выбирается

Sk = ekS, если частная производная отрицательна, и

Sk = -ekS, если частная производная положительна.

2 шаг. Находится

3 шаг. 

4 шаг. Проверяется условие прекращения решения.

X0

X1

X0

X1

X0

X0


 

А также другие работы, которые могут Вас заинтересовать

53598. УРОК КАК ОСНОВНАЯ ФОРМА ОРГАНИЗАЦИИ УЧЕБНОЙ РАБОТЫ В ШКОЛЕ План – конспект урока по изобразительному искусству 38 KB
  Виды изобразительного искусства графика живопись скульптура. Виды декоративноприкладного искусства одежда бижутерия ткани обои керамика ковроткачество и т. Виды конструктивного искусства архитектура и дизайн. Отличительные особенности жанров изобразительного искусства пейзаж натюрморт портрет бытовой жанр исторический жанр анималистический жанр.
53599. Геоинформационные системы в интернете 43.5 KB
  Цели урока: Образовательная знакомство с новейшим классом информационных систем освоение приемов поиска и средств навигации в ГИС 2GIS Тюмень и освоение приемов работы с инструментами в программе Google планета Земля. Что такое геоинформационная система ГИС географическая информационная система это современная...
53600. Правописание буквосочетаний жи, ши 785.5 KB
  Цель: Уточнение представлений учащихся о звуках ж, ш, ц как твёрдых; ознакомление учащихся с особенностями написания сочетания жи ши; развитие умение правильно писать сочетания жи ши; развитие познавательной активность детей; речи учащихся наблюдательности внимания мышления умения работать с книгой. Шишка жёлудь цветок Мягкий или твёрдый согласный звук слышится вначале каждого из этих слов Работа с учебником. У доски работают два ученика. Работа с учебником.
53601. Модель оценки капитальных активов 31 KB
  Одним из ключевых положений портфельной теории является обоснование того, что с каждым рисковым активом связаны два типа рисков – диверсифицируемый и недиверсифицируемый
53602. Работа в сети Интернет. Электронная почта 60 KB
  Электронная почта Этапы работы Содержание этапа заполняется педагогом Оценка эксперта по базовым педагогическим компетенциям и уровню владения учебным материалом 1. Методы: беседа Педагог здоровается отмечает отсутствующих в группе. Определение целей и задач которых педагог хочет достичь на данном этапе урока: повторение и закрепление теоретических знаний предыдущего занятия; закрепление практических навыков сохранения информации из интернета стимулирование обучающихся к быстрому выполнению работы воспитание эстетического...
53603. Конспект урока обучение грамоте: «Написание заглавной буквы «Т» 40.5 KB
  Детям предлагается игра Угадай букву по описанию Ставим ручку на верхнюю линию рабочей строки опускаемся по наклонной линии поднимаемся по наклонной до середины выполняем узелок уходим вправовверх и на 1 3 выписываем секрет по секрету наклонная вниз качалочка крючок до середины Ставим ручку на 1 3 сверху уходим влево вверх задерживаемся на строке опускаемся по наклонной вниз выполняем качалочку поднимаемся по крючку до середины две части соединяем секретом по секрету наклонная линия вниз качалочка крючок до середины...
53604. Введение в информатику. Правила техники безопасности 582.5 KB
  Дидактическая цель: дать общее представление об информатике как о науке ввести понятие информатика cформировать знания по технике безопасности работы в компьютерном классе. Знать: формулировку понятия информатика основные правила техники безопасности нормы работы в компьютерном классе основные упражнения физкультминутки. Информатика и ИКТ : учебник для 7 класса Н. Вначале мы узнаем что изучает предмет информатика а также поймем значимость этого предмета в современном мире.
53605. Оценка облигаций 23 KB
  Номинальная цена напечатана на бланке облигации и обозначает сумму, которая берется взаймы и подлежит возврату по истечении срока облигационного займа.
53606. Сантиметр 30 KB
  Сколько грибков у белочки Сколько грибков у ежика Как узнать сколько всего грибков Как записать это выражение Клик Прочитайте это выражение разными способами. Устное решение примеров слайд 4 кликаем Задания с окошками слайд 5 кликаем Восстановление числового ряда слайд 6 кликаем Задание от гнома Найти лишнюю фигуру слайд 7 почему...