Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол

Материал из MachineLearning.

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
== Постановка задачи одномерной оптимизации ==
== Постановка задачи одномерной оптимизации ==
Задача одномерной оптимизации определяется следующим образом:
Задача одномерной оптимизации определяется следующим образом:
-
# ''Допустимое множество'' — множество <tex>\mathbb{X} \subseteq \mathbb{R}</tex>;
+
# ''Допустимое множество'' — множество <tex>\texbb{X} \subseteq \texbb{R}</tex>;
-
# ''Целевую функцию'' — отображение <tex>f:\;\mathbb{X}\to\mathbb{R}</tex>;
+
# ''Целевую функцию'' — отображение <tex>f:\;\texbb{X}\to\texbb{R}</tex>;
# ''Критерий поиска'' (max или min).
# ''Критерий поиска'' (max или min).
-
Тогда решить задачу <tex>f(x)\to \min_{x\in\mathrm{X}}</tex> означает одно из:
+
Тогда решить задачу <tex>f(x)\to \min_{x\in\texrm{X}}</tex> означает одно из:
-
# Показать, что <tex>\mathbb{X}=\not\bigcirc</tex>.
+
# Показать, что <tex>\texbb{X}=\not\bigcirc</tex>.
# Показать, что целевая функция <tex>f(x)</tex> не ограничена.
# Показать, что целевая функция <tex>f(x)</tex> не ограничена.
-
# Найти <tex>x^*\in\mathbb{X}:\;f(x^*)=\min_{x\in\mathbb{X}}f(\vec{x})</tex>.
+
# Найти <tex>x^*\in\texbb{X}:\;f(x^*)=\min_{x\in\texbb{X}}f(\vec{x})</tex>.
-
# Если <tex>\not\exists x^* </tex>, то найти <tex>\inf_{x\in\mathbb{X}}f(x)</tex>.
+
# Если <tex>\not\exists x^* </tex>, то найти <tex>\inf_{x\in\texbb{X}}f(x)</tex>.
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <tex>x_0</tex> таких, что всюду в некоторой их окрестности <tex>f(x)\ge f(x_0)</tex> для минимума и <tex>f(x)\le f(x_0)</tex> для максимума.
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек <tex>x_0</tex> таких, что всюду в некоторой их окрестности <tex>f(x)\ge f(x_0)</tex> для минимума и <tex>f(x)\le f(x_0)</tex> для максимума.
-
Если допустимое множество <tex>\mathbb{X}=\mathbb{R}</tex>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''.
+
Если допустимое множество <tex>\texbb{X}=\texbb{R}</tex>, то такая задача называется ''задачей безусловной оптимизации'', в противном случае — ''задачей условной оптимизации''.
== Метод Ньютона ==
== Метод Ньютона ==
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция <tex>f(x)</tex> дважды непрерывно дифференцируема. Отыскание минимума функции <tex>f(x)</tex> производится при помощи отыскания стационарной точки, т.е. точки <tex>x^*</tex>, удовлетворяющей уравнению <tex>f'(x)=0</tex>, которое решается методом Ньютона.
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция <tex>f(x)</tex> дважды непрерывно дифференцируема. Отыскание минимума функции <tex>f(x)</tex> производится при помощи отыскания стационарной точки, т.е. точки <tex>x^*</tex>, удовлетворяющей уравнению <tex>f'(x)=0</tex>, которое решается методом Ньютона.
Строка 31: Строка 31:
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
 +
 +
=== Ограничения ===
 +
Пускай задано уравнение <tex>f(x)=0\!</tex>, где <tex>f(x):\;\texbb{X} \to \texbb{R}\!</tex> и надо найти его решение.
 +
 +
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского [[математик]]а и [[экономист]]а, лауреата [[Нобелевская премия|Нобелевской премии]] по экономике [[1975]] года «за вклад в теорию оптимального распределения ресурсов» [[Канторович, Леонид Витальевич|Леонида Витальевича Канторовича]] ([[1912]]—[[1986]]) и является одной из многочисленных [[Теоремы Канторовича|теорем]], ставших результатами его научных изысканий.
 +
 +
'''Теорема Канторовича.'''
 +
 +
''Если существуют такие константы <tex>A,B,C\!</tex>, что:''
 +
# ''<tex>\frac{1}{|f'(x)|}<A\!</tex> на <tex>[a,\;b]\!</tex>, то есть <tex>f'(x)\!</tex> существует и не равна нулю;''
 +
# ''<tex>\left|\frac{f(x)}{f'(x)}\right|<B\!</tex> на <tex>[a,\;b]\!</tex>, то есть <tex>f(x)\!</tex> ограничена;''
 +
# ''<tex>\exist f''(x)\!</tex> на <tex>[a,\;b]\!</tex>, и <tex>|f''(x)|\leq C \leq \frac{1}{2AB}\!</tex>;''
 +
''Причём длина рассматриваемого отрезка <tex>|a-b|<\frac{1}{AB}\left(1- \sqrt{1-2ABC}\right)\!</tex>. Тогда справедливы следующие утверждения:'' <br />
 +
# ''на <tex>[a,\;b]\!</tex> существует корень <tex>x^*</tex> уравнения <tex>f(x)=0:\quad\exist x^*\in[a,\;b]: f(x^*)=0\!</tex>;''
 +
# ''если <tex>x_0=\frac{a+b}{2}\!</tex>, то итерационная [[последовательность]] сходится к этому корню: <tex>\left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!</tex>;''
 +
# ''погрешность может быть оценена по формуле <tex>|x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!</tex>.''
 +
 +
Из последнего из утверждений теоремы в частности следует квадратичная [[скорость сходимости|сходимость]] метода: <br />
 +
:: <tex>|x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}=\frac{1}{2}\frac{B}{2^{n-2}}\left((2ABC)^{2^{n-2}}\right)^2=\alpha |x^*-x_{n-1}|^2\!</tex>
 +
 +
Тогда ограничения на исходную функцию <tex>f(x)\!</tex> будут выглядеть так:
 +
# функция должна быть ограничена;
 +
# функция должна быть [[гладкая функция|гладкой]], дважды [[дифференциал|дифференцируемой]];
 +
# её первая [[производная]] <tex>f'(x)</tex> равномерно отделена от нуля;
 +
# её вторая производная <tex>f''(x)\!</tex> должна быть равномерно ограничена.
 +
== Метод парабол ==
== Метод парабол ==

Версия 21:11, 16 ноября 2008

Содержание

Постановка задачи одномерной оптимизации

Задача одномерной оптимизации определяется следующим образом:

  1. Допустимое множество — множество \texbb{X} \subseteq \texbb{R};
  2. Целевую функцию — отображение f:\;\texbb{X}\to\texbb{R};
  3. Критерий поиска (max или min).

Тогда решить задачу f(x)\to \min_{x\in\texrm{X}} означает одно из:

  1. Показать, что \texbb{X}=\not\bigcirc.
  2. Показать, что целевая функция f(x) не ограничена.
  3. Найти x^*\in\texbb{X}:\;f(x^*)=\min_{x\in\texbb{X}}f(\vec{x}).
  4. Если \not\exists x^* , то найти \inf_{x\in\texbb{X}}f(x).

Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек x_0 таких, что всюду в некоторой их окрестности f(x)\ge f(x_0) для минимума и f(x)\le f(x_0) для максимума.

Если допустимое множество \texbb{X}=\texbb{R}, то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.

Метод Ньютона

Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция f(x) дважды непрерывно дифференцируема. Отыскание минимума функции f(x) производится при помощи отыскания стационарной точки, т.е. точки x^*, удовлетворяющей уравнению f'(x)=0, которое решается методом Ньютона.


Если x^k – точка, полученная на k-м шаге, то функция f'(x) аппроксимируется своим уравнением касательной:

y = f'(x^k) + (x - x^k)f''(x^k),

а точка x^{k+1} выбирается как пересечение этой прямой с осью Ох, т.е.

x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}.

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

Когда начальная точка итераций x_0 достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.

Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.

Ограничения

Пускай задано уравнение f(x)=0\!, где f(x):\;\texbb{X} \to \texbb{R}\! и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (19121986) и является одной из многочисленных теорем, ставших результатами его научных изысканий.

Теорема Канторовича.

Если существуют такие константы A,B,C\!, что:

  1. \frac{1}{|f'(x)|}<A\! на [a,\;b]\!, то есть f'(x)\! существует и не равна нулю;
  2. \left|\frac{f(x)}{f'(x)}\right|<B\! на [a,\;b]\!, то есть f(x)\! ограничена;
  3. \exist f''(x)\! на [a,\;b]\!, и |f''(x)|\leq C \leq \frac{1}{2AB}\!;

Причём длина рассматриваемого отрезка |a-b|<\frac{1}{AB}\left(1- \sqrt{1-2ABC}\right)\!. Тогда справедливы следующие утверждения:

  1. на [a,\;b]\! существует корень x^* уравнения f(x)=0:\quad\exist x^*\in[a,\;b]: f(x^*)=0\!;
  2. если x_0=\frac{a+b}{2}\!, то итерационная последовательность сходится к этому корню: \left\{ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\right\}\to x^*\!;
  3. погрешность может быть оценена по формуле |x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}\!.

Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:

|x^*-x_n|\leq\frac{B}{2^{n-1}}(2ABC)^{2^{n-1}}=\frac{1}{2}\frac{B}{2^{n-2}}\left((2ABC)^{2^{n-2}}\right)^2=\alpha |x^*-x_{n-1}|^2\!

Тогда ограничения на исходную функцию f(x)\! будут выглядеть так:

  1. функция должна быть ограничена;
  2. функция должна быть гладкой, дважды дифференцируемой;
  3. её первая производная f'(x) равномерно отделена от нуля;
  4. её вторая производная f''(x)\! должна быть равномерно ограничена.


Метод парабол

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

В этом методе вычисляется значение функции сразу в трех близлежащих точках x_0 - h, x_0, x_0 + h, где h – малое число. Через эти три точки проводится интерполяционная парабола:

y = ax^2 + bx + c.

Минимум параболы достигается при y = 2ax + b = 0, т.е. при x^* = /frac{-b}{2a}. Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:

x^{k+1} = x^k - 0.5h\frac{f(x^k + h) - f(x^k - h)}{f(x^k + h) - 2f(x^k) + f(x^k - h)}</.


Совмещение метода Ньютона и Парабол

Численный пример

Литература

Смотри также

Личные инструменты