Сходимость BFGS для выпуклых перепараметрических задач

Question

Хорошо известно, что алгоритм оптимизации BFGS является суперлинейно сходящимся для строго выпуклых задач, но есть ли анализ для задач, которые не являются строго выпуклыми. Например, предположим, что f (x) выпукла для некоторого скаляра x. Тогда предположим, что мы оптимизируем по g (x1, x2) = f (x1 + x2). Будет ли это всегда суперлинейно сходящимся?

Answer 1

Сходится ли BFGS вообще по невыпуклым задачам, все еще остается открытой проблемой. Фактически, в 1984 году Пауэлл привел контрпример, который показывает, что BFGS с неточным поиском по строке может не сходятся. Что можно сделать, это локальные утверждения, такие как: Учитывая локальные минимумы x *, если вы в конечном итоге введете область пространства около x *, BFGS будет сходиться суперлинейно. Причина этого заключается в том, что вблизи x * целевая функция может быть точно смоделирована выпуклой квадратикой.

Что касается того, что известно для функции композиции, которую вы дали, я не уверен. Для подробного объяснения свойств BFGS см. Либо Деннис и Шнабель, либо Носедал и Райт.

Удачи.

Answer 2

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

Нужно быть осторожным с обновлениями BFGS, чтобы гарантировать, что получающийся приблизительный гессиан остается положительно определенным "достаточно", даже если теоретический гессиан - нет. Что я делаю, так это сохраняю и обновляю разложение Гессена по Холесскому, а не по Гессену как таковое или его обратное.

Answer 3

Поправьте меня, если я ошибаюсь, но разве «решение» в этом случае не будет линией, а не одной точкой? Если x 'является минимизатором для f (x), то лучшее, на что вы можете надеяться, применяя любой метод к g (x1, x2), это сходиться к линии x2 = x' - x1.