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


 

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

85992. ГЕОПОЛИТИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 82.92 KB
  Например в России прошел II Всероссийский конгресс политологов а в Беларуси ряд международных конференций и семинаров. Распад СССР как геополитическая катастрофа Афганистан Косово и Средняя Азия как плацдармы контроля две войны России в Чечне с целью сохранения целостности страны и контроля за добычей нефти в Каспии. В данном случае он просто повторил опыт царской России. Замятин приводит в этой связи интересный пример: Так политическое и военное соперничество России и Великобритании в Средней Азии во второй половине XIX в.
85993. ОСНОВНЫЕ ТЕОРИИ, МЕТОДИКИ И СТРУКТУРЫ ПРИНЯТИЯ РЕШЕНИЙ ВО ВНЕШНЕЙ ПОЛИТИКЕ 59.97 KB
  Теории и анализ принятия решений в области внешней политики обозначились еще в 1950е гг. Объектом теорий принятия решений во внешней политике являются не общие проблемы касающиеся например предмета и сущности международных отношений конфликта или другие а конкретные вопросы связанные с действиями государства. Некоторые исследователи справедливо отмечают что изучение детерминант внешней политики без учета процесса принятия решений может оказаться или напрасной потерей времени поскольку результаты не будут иметь практического значения...
85994. ВНЕШНЕПОЛИТИЧЕСКИЙ ПРОЦЕСС 60.01 KB
  Ответы на этот вопрос призваны дать социологический и политический анализы внешней политики. Втретьих существует четкое осознание противоречия между с одной стороны требованиями максимально высокого профессионализма во внешней патетике а с другой императивами сохранения и укрепления и в этой сфере демократических начал. Оно ведет к поиску путей и средств оптимального преодоления названного противоречия какими оказываются многочисленные общественные организации по проблемам внешней политики как внутри социальной и политической элит так...
85995. МЕСТО И РОЛЬ КОНФЛИКТОВ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 123.4 KB
  Понятие конфликта Проблема конфликта является одной из сложнейших в теории международных отношений. Оставаясь важнейшим элементом международных отношений она переходит в качественно иное состояние наполняя внутреннюю жизнь любого субъекта напряженностью и возможной взрывоопасностью. Хотя среди аналитиков нет единого мнения в вопросе определения конфликта они в общем соглашаются что под конфликтом в международных отношениях понимается особый вид внешнеполитического взаимодействия субъектов прежде всего государств который выражается в...
85996. ПОНЯТИЕ И СУЩНОСТЬ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 155.5 KB
  В русском языке понятие «международные отношения» существенно расходится с вроде бы родственным ему «international relations» в английском языке, на котором почти исключительно создавалась эта наука. В нашем понимании «международные отношения» в изначальном и прямом...
85997. ОСОБЕННОСТИ СОВРЕМЕННОГО МИРА И ИХ ВЛИЯНИЕ НА МЕЖДУНАРОДНЫЕ ОТНОШЕНИЯ И ВНЕШНЮЮ ПОЛИТИКУ РЕСПУБЛИКИ БЕЛАРУСЬ 56.64 KB
  В современных условиях глобализация как важнейшая особенность международных отношений вызывает неоднозначную оценку. Сущность глобализации Сам термин глобализация по своей внутренней определенности предполагает формирование подлинного мира в котором по мнению некоторых аналитиков стираются географические границы социальных и культурных систем и сами люди во все большей степени осознают исчезновение подобных границ. Тем не менее глобализация имеет объективные источники и следовательно является естественным ходом истории. Таким образом...
85998. МЕТОДОЛОГИЧЕСКИЕ ПРИНЦИПЫ И ОСНОВНЫЕ КАТЕГОРИИ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 72.11 KB
  Поскольку в нашем пособии рассматривается интеллектуальная карта дисциплины международных отношений ни одно представление в этой академической области не будет приниматься само по себе. Кукулка выработать же объективистский взгляд на проблему международных отношений очень и очень трудно если вообще возможно. Так в основе историкоописательного метода лежат представления о дипломатических отношениях между государствами в тот или иной период развития истории; Он только описывает взаимодействие между основными субъектами международных...
85999. ОСНОВНЫЕ НАУЧНЫЕ НАПРАВЛЕНИЯ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 193.5 KB
  Поэтому в современной науке о международных отношениях все чаще обнаруживается стремление к переходу от теоретического к методологическому и нормативному модусу рассмотрения этих отношений, в границах которых она нередко воспринимается как форма делегитимизации
86000. ИНТЕГРАЦИОННЫЕ И ДЕЗИНТЕГРАЦИОННЫЕ ФАКТОРЫ В ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 76.4 KB
  Развитие интеграционных процессов стало закономерным результатом роста производительных сил что потребовало создания более надежных связей и отношений между странами и устранения многочисленных препятствий на пути сотрудничества. В интеграции необходимо выделить несколько элементов: Первый предпосылки к которым необходимо отнести близость уровней развития и степень зрелости интегрирующихся стран; наличие исторических связей общность проблем стоящих перед странами в области развития и сотрудничества; демонстративный эффект когда в...