Метод Ньютона с доверительной областью

Конструктор принимает ключевые слова, определяющие начальный и максимальный размеры доверительной области, условия увеличения и уменьшения области, а также степень близости функции к квадратичной аппроксимации. Нотация соответствуют приведенной в четвертой главе работы Numerical Optimization («Численная оптимизация»). Ниже rho обозначает отношение фактического изменения функции к изменению квадратичной аппроксимации для данного шага.

Метод Ньютона с доверительной областью предназначен для использования информации второго порядка в гессиане функции, но обладает большей устойчивостью, чем метод Ньютона, когда функции не являются глобально вполне аппроксимируемыми квадратичным. Это достигается путем многократной минимизации квадратичных аппроксимаций в динамически изменяемой по размеру «доверительной области», в которой функция считается локально квадратичной [1].

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

Методы доверительной области используют информацию второго порядка, но ограничивают шаги так, чтобы они выполнялись в пределах «доверительной области», где функция считается приблизительно квадратичной. В итерации метод доверительной области выбирает шаг для минимизации квадратичной аппроксимации цели таким образом, чтобы размер шага не превышал заданного размера доверительной области .

Здесь  — это шаг, который нужно сделать в итерации , чтобы . В определении  — это значение в предыдущем расположении,  — градиент в предыдущем расположении,  — матрица Гессиана в предыдущей итерации, а  — евклидова норма.

Если размер доверительной области достаточно велик, чтобы минимизатор квадратичной аппроксимации имел , то шаг будет таким же, как и обычный шаг Ньютона. Однако если квадратичный минимизатор без ограничений находится вне доверительной области, минимизатор задачи с ограничениями будет находиться на границе, т. е. мы будем иметь . Оказывается, что если может быть вычислено разложение Холецкого для , оптимальное значение может быть относительно легко найдено численно. ([1], раздел 4.3) Именно этот метод в настоящее время используется в Optim.

Имеет смысл адаптировать размер доверительной области по мере перемещения в пространстве и оценки качества квадратичной аппроксимации. Эта адаптация управляется параметрами , и , которые являются параметрами метода оптимизации NewtonTrustRegion. Для каждого шага мы вычисляем

Интуитивно понятно, что измеряет качество квадратичной аппроксимации: если , квадратичная аппроксимация разумна. Если находился на границе и , то, возможно, следует использовать более крупные шаги. В этом случае для следующей итерации мы увеличиваем доверительную область в геометрической прогрессии до максимума :

И наоборот, если , мы уменьшаем доверительную область в геометрической прогрессии:

. Наконец, мы принимаем точку только в том случае, если ее уменьшение заметно по сравнению с квадратичной аппроксимацией. В частности, шаг принимается, только когда . Пока мы выбираем меньше , мы будем уменьшать доверительную область всякий раз, когда отклоняем шаг. В итоге, если целевая функция локально квадратична, значение станет достаточно малым, чтобы квадратичная аппроксимация была достаточно точной для дальнейшего продвижения.

[1] Nocedal, Jorge, and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.