Метод Ньютона. Проблема области сходимости. Метод парабол. Совмещение методов Ньютона и парабол
Материал из MachineLearning.
Строка 1: | Строка 1: | ||
== Постановка задачи одномерной оптимизации == | == Постановка задачи одномерной оптимизации == | ||
Задача одномерной оптимизации определяется следующим образом: | Задача одномерной оптимизации определяется следующим образом: | ||
- | # ''Допустимое множество'' — множество <tex>\ | + | # ''Допустимое множество'' — множество <tex>\texbb{X} \subseteq \texbb{R}</tex>; |
- | # ''Целевую функцию'' — отображение <tex>f:\;\ | + | # ''Целевую функцию'' — отображение <tex>f:\;\texbb{X}\to\texbb{R}</tex>; |
# ''Критерий поиска'' (max или min). | # ''Критерий поиска'' (max или min). | ||
- | Тогда решить задачу <tex>f(x)\to \min_{x\in\ | + | Тогда решить задачу <tex>f(x)\to \min_{x\in\texrm{X}}</tex> означает одно из: |
- | # Показать, что <tex>\ | + | # Показать, что <tex>\texbb{X}=\not\bigcirc</tex>. |
# Показать, что целевая функция <tex>f(x)</tex> не ограничена. | # Показать, что целевая функция <tex>f(x)</tex> не ограничена. | ||
- | # Найти <tex>x^*\in\ | + | # Найти <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\ | + | # Если <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>\ | + | Если допустимое множество <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
Содержание |
Постановка задачи одномерной оптимизации
Задача одномерной оптимизации определяется следующим образом:
- Допустимое множество — множество ;
- Целевую функцию — отображение ;
- Критерий поиска (max или min).
Тогда решить задачу означает одно из:
- Показать, что .
- Показать, что целевая функция не ограничена.
- Найти .
- Если , то найти .
Если минимизируемая функция не является выпуклой, то часто ограничиваются поиском локальных минимумов и максимумов: точек таких, что всюду в некоторой их окрестности для минимума и для максимума.
Если допустимое множество , то такая задача называется задачей безусловной оптимизации, в противном случае — задачей условной оптимизации.
Метод Ньютона
Это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727), под именем которого и обрёл свою известность. Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. В случае решения задач оптимизации предполагается, что функция дважды непрерывно дифференцируема. Отыскание минимума функции производится при помощи отыскания стационарной точки, т.е. точки , удовлетворяющей уравнению , которое решается методом Ньютона.
Если – точка, полученная на k-м шаге, то функция аппроксимируется своим уравнением касательной:
,
а точка выбирается как пересечение этой прямой с осью , т.е.
.
Неудобство этого метода состоит в необходимости вычисления в каждой точке первой и второй производных. Значит, он применим лишь тогда, когда функция имеет достаточно простую аналитическую форму, чтобы производные могли быть вычислены в явном виде вручную. Действительно, всякий раз, когда решается новая задача, необходимо выбрать две специфические подпрограммы (функции) вычисления производных и , что не позволяет построить общие алгоритмы, т.е. применимые к функции любого типа.
Когда начальная точка итераций достаточно близка к искомому минимуму, скорость сходимости метода Ньютона в общем случае квадратическая. Однако, глобальная сходимость метода Ньютона, вообще говоря, не гарантируется.
Хороший способ гарантировать глобальную сходимость этого метода состоит в комбинировании его с другим методом для быстрого получения хорошей аппроксимации искомого оптимума. Тогда несколько итераций метода Ньютона, с этой точкой в качестве исходной, достаточны для получения превосходной точности.
Ограничения
Пускай задано уравнение , где и надо найти его решение.
Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Она носит имя советского математика и экономиста, лауреата Нобелевской премии по экономике 1975 года «за вклад в теорию оптимального распределения ресурсов» Леонида Витальевича Канторовича (1912—1986) и является одной из многочисленных теорем, ставших результатами его научных изысканий.
Теорема Канторовича.
Если существуют такие константы , что:
- на , то есть существует и не равна нулю;
- на , то есть ограничена;
- на , и ;
Причём длина рассматриваемого отрезка . Тогда справедливы следующие утверждения:
- на существует корень уравнения ;
- если , то итерационная последовательность сходится к этому корню: ;
- погрешность может быть оценена по формуле .
Из последнего из утверждений теоремы в частности следует квадратичная сходимость метода:
Тогда ограничения на исходную функцию будут выглядеть так:
- функция должна быть ограничена;
- функция должна быть гладкой, дважды дифференцируемой;
- её первая производная равномерно отделена от нуля;
- её вторая производная должна быть равномерно ограничена.
Метод парабол
Относительно метода Ньютона этот метод обладает тем преимуществом, что он не требует вычисления производных функции . Однако, его сходимость может быть гарантирована лишь для достаточно регулярных функций (непрерывных и много раз дифференцируемых).
В этом методе вычисляется значение функции сразу в трех близлежащих точках , , , где h – малое число. Через эти три точки проводится интерполяционная парабола:
.
Минимум параболы достигается при , т.е. при . Для трех точек получаем систему трех линейных уравнений для коэффициентов a, b, c. Находим a и b и тогда:
.