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


 

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

20832. Повышение производительности коксовой батареи и повышение качества конечного продукта коксовая батарея № 14 ОАО «ММК» 794.02 KB
  Рассмотрены причины необходимости реконструкции коксовой батареи, различные виды конструкций коксовых печей. Предложено использование многощелевой насадки в качестве нового типа насадки регенератора, за счет чего увеличено количество рядов корнюрной зоны с 9 до 12.
20833. Анализ показателей, характеризующих состояние и использование основных фондов ООО «Инжстрой» 296.38 KB
  Анализ эффективности деятельности организации раскрывает возможные риски, которые могут быть устранены, или проблемы, с которыми можно бороться, или резервы повышения эффективности деятельности в целом, и отдельных показателей в частности. То есть, показывает по каким направлениям следует вести работу.
20834. Автоматизация процесса абонентского учета и биллинга с помощью единой информационной системы на примере ОАО «Челябэнергосбыт» 4.04 MB
  В дипломном проекте был проведён анализ внешней и внутренней среды ОАО «Челябэнергосбыт», проанализирована бизнес - архитектура и ИТ-архитектура предприятия, были выявлены и проранжированы существующие проблемы компании. Был проанализирован рынок информационных продуктов для решения выявленных проблем.
20835. Методи проектування (метод комбінування). Планування роботи з проектування та виготовлення виробу 158.5 KB
  Разработка сайтов для компаний является актуальной и востребованной сферой деятельности, т.к. сайт фирмы в сети Интернет представляет собой достаточно дешевый и массовый способ рекламы, дает возможность потенциальным и существующим клиентам легко получать информацию о товарах и услугах компании, ее деловых интересах.
20836. Учет и анализ стипендиального фонда и расчетов со стипендиатами 438 KB
  Изучение, систематизация и обобщение практического материала и теоретических знаний по вопросов учёта расчётов со стипендиатами и анализа стипендиального фонда.
20837. РЕКОМЕНДАЦИИ ПО СОВЕРШЕНСТВОВАНИЮ УЧЕТА ЗАРАБОТНОЙ ПЛАТЫ ООО «ЭДЕМ» 348.5 KB
  Для решения поставленных задач выпускная квалификационная работа разделена на три главы. Первая глава содержит теоретические основы бухгалтерского учета расчетов по оплате труда, формы, виды системы оплаты труда, Вторая глава рассматривает применяемые на практике способы учета оплаты труда порядок начисления и удержания из заработной платы в анализируемой организации.
20838. Мотивация персонала 96.5 KB
  Работник перестает понимать, что ему нужно делать и почему работа у него не ладится, связано ли это с ним самим, с начальником, с работой. Усилия работника пока не сказываются на производительности. Он легко контактирует с сослуживцами
20839. Ррезонансні частоти та форми власних коливань 1.09 MB
  В конструкціях машинобудівної, авіаційної, приладобудівної та суднобудівної промисловості широко використовуються конструктивні елементи, що представляють собою циліндричні оболонки. Ці елементи складають по вазі порівняно невелику частину конструкції, але суттєво впливають на її міцність і жорсткість.
20840. ПЕРСПЕКТИВЫ РАЗВИТИЯ АГРОЭКОТУРИЗМА В РОССОНСКОМ РАЙОНЕ 1.03 MB
  Провести мониторинг посещаемости агроэкоусадеб района за 2006-2011 гг. Провести анализ экономической среды агроусадеб. Обосновать рекомендации по развитию туризма в районе.