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

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

Перейти к: навигация, поиск

Содержание

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

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

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

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

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

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

Если допустимое множество \texbb{X}=\mathbb{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):\;\mathbb{X} \to \mathbb{R}\! и надо найти его решение.

Ниже приведена формулировка основной теоремы, которая позволяет дать чёткие условия применимости. Теорема Канторовича.

Если существуют такие константы 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)}.


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

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

Литература

Смотри также

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