Почему квазиньютоновские методы, такие как DFP и BFGS, имеют низкую производительность при плохо обусловленной проблеме, даже если квадратичная

Question

Я читал в литературе, что квазиньютоновские методы, такие как DFP и BFGS, плохо справляются с плохо обусловленными проблемами, но я не понимаю причину этого.Я пытался использовать эти методы в квадратичной задаче, которая плохо обусловлена ​​и не сходится в итерациях p + 1 (это одно из свойств квазиньютоновских методов для квадратичных задач), но немного больше.Это почему ?Спасибо за вашу помощь.

Answer 1

Плохое кондиционирование - общая проблема для алгоритмов оптимизации.Поскольку квазиньютоновские методы основаны на методе Ньютона, давайте сначала рассмотрим его свойства.По сути, есть два основных аспекта плохой обусловленности:

1. это приводит к численной нестабильности (например, ошибки округления), которые накапливаются алгоритмом
2. , это замедляет скорость сходимостииз-за растянутой формы результирующих контуров гессиана

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

Квазиньютоновские методы имеют те же проблемы.Однако из-за того, что они итеративно аппроксимируют обратный гессиан, они более надежны в обработке ошибок округления, а также могут быть немного быстрее в сходимости, но это не устраняет проблему полностью, поэтому у них низкая производительность.