Помогите выбрать между кубической и квадратичной интерполяцией в поиске строк

9

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

Позволять f:RR,fC1быть функцией интереса. Я хочу найтиx такой, что f(x)0,

Позволять f(xk), f(xk), f(xk+1) а также f(xk+1)быть известным. Также предположим,0xК<Икс*<ИксК+1, Я подгоняю кубический полиномQ(Икс)знак равноaИкс3+бИкс2+сИкс+d так что Q(0)знак равное(ИксК), Q'(0)знак равное'(ИксК), Q(ИксК+1-ИксК)знак равное(ИксК+1) а также Q'(ИксК+1-ИксК)знак равное'(ИксК+1),

Я решаю квадратное уравнение: (1):Q'(Икс*-ИксК)знак равно0 для моего разыскиваемого Икс* используя решение в закрытой форме.

Вышеуказанное работает хорошо в большинстве случаев, кроме случаев, когда е(Икс)знак равноО(Икс2) как решение в закрытой форме для (1) делится на a который становится очень близко или точно 0,

Мое решение состоит в том, чтобы посмотреть на a и если оно «слишком мало», просто примите решение в замкнутой форме для минимизатора квадратичного полинома Q2(Икс)знак равнобИкс2+сИкс+d для которого у меня уже есть коэффициенты б,с,d от более раннего Q(Икс),

Мой вопрос: как мне разработать хороший тест для того, когда брать квадратичную интерполяцию по кубике? Наивный подход к тестированию наa0 плохо по численным причинам, поэтому я смотрю на |a|<ετ где ε это точность машины, но я не могу определиться с хорошим τ это масштабный инвариант е,

Бонусный вопрос: есть ли какие-либо проблемы с использованием коэффициентов,б,с,dиз неудачной кубической подгонки или я должен выполнить новую квадратичную подгонку с подходящим способом вычисления коэффициентов?

Изменить для уточнения: По моему вопросуе на самом деле то, что обычно называют ϕ(α)=f(x¯k+αpk¯)в литературе. Я просто упростил формулировку вопроса. Задача оптимизации, которую я решаю, нелинейна в 6 измерениях. И я хорошо знаю, что условий Вульфа достаточно для поиска линии BFGS, следовательно, заявляя, что я был заинтересован вf(x)0; Я ищу что-то, что удовлетворит сильные условия Вольфа, и использование минимизатора кубического приближения - хороший шаг на этом пути.

Вопрос был не о BFGS, а о том, как определить, когда кубический коэффициент достаточно мал, чтобы квадратичное приближение было более подходящим.

Редактировать 2: обновить обозначения, уравнения без изменений.

Эмили Л.
источник

Ответы:

4

Хм ... кубическая интерполяция не является неслыханной задачей для поиска строк, но обычно излишняя.

Если я правильно читаю вашу проблему, xэто просто скаляр? В этом случае BFGS, вероятно, не самый эффективный способ решения вашей проблемы. Алгоритмы скалярной оптимизации, такие как метод Брента, могут решить вашу проблему быстрее.

Для BFGS существует ряд алгоритмов поиска строк. Для моих собственных приложений, использующих BFGS с ограниченным объемом памяти (L-BFGS), этот поиск строки работает очень хорошо. Помните, что вам нужно только выполнить условия Вулфа, и вы, вероятно, не получите много, найдя точный минимизатор.

В любом случае, чтобы ответить на ваш вопрос: я бы рассмотрел простой переход к квадратичному полиному, если при решении кубического получаются «плохие» значения, такие как NaN или Inf (как это делается здесь ).

Я не совсем уверен, что вы имеете в виду, используя b,c,d? Эти коэффициенты для кубической подгонки не будут такими же, как для квадратичной подгонки, поэтому их нельзя использовать повторно.

Наконец, вы можете использовать f(xk1) , скорее, чем f(x0), поскольку ваша функция (вероятно) будет только приблизительно кубической или квадратичной локально, и xk а также xk1 должны быть ближе друг к другу (и решение), чем x0,

Надеюсь это поможет.

LKlevin
источник
Отредактировано для наглядности. Используяb,c,d«Я имею в виду, что я сделал кубическую посадку Q(x)=ax3+bx2+cx+d и обнаружил, что a0 таким образом у меня есть Q(x)=bx2+cx+dкоторый уже является квадратичным полиномом. И вопрос был, если коэффициентыb,c,dполученные для этой подгонки целесообразно использовать для интерполяции или, если мне нужно пересчитать новые коэффициенты для типичной квадратичной подгонки.
Эмили Л.
Ааа, конечно. Я не вижу никаких проблем в использовании коэффициентов с числовой точки зрения. Единственная точка, где я думаю, что это имеет значение, это очень близко к решению, где вы все равно прекратите.
Л.Клевин
Можете ли вы мотивировать свой ответ вычислением кубических значений и проверкой на «плохие» значения? Почему это безопасно делать, когдаa<<b или a0?
Эмили Л.
когда a0, b,c а также dбудет примерно те, для квадратичного случая. Поскольку линейный поиск BFGS достаточно надежен, вы должны использовать его, даже если они не совсем точны. Если вы будете подчиняться условиям Вулфа, вы получите конвергенцию. Что касается «плохих» значений, то, пока компьютер может точно выполнять вычисления с необходимой точностью, все хорошо. Когда это невозможно, вы начнете видеть инф и NaN.
Л.Клевин
4

Есть статья Море, выполненная Nocedal, о которой:

Хорхе Х. Море и Дэвид Дж. Туенте. 1994. Алгоритмы линейного поиска с гарантированным достаточным уменьшением. ACM Trans. Математика Softw. 20, 3 (сентябрь 1994 г.), 286-307. DOI http://dx.doi.org/10.1145/192115.192132 ( препринт ).

Хуан Пабло Фриас
источник
Добро пожаловать в SciComp.SE! Я отформатировал твой пост, чтобы легче было найти бумагу. Если вы можете найти ссылку на реализацию Nocedal, это было бы полезно.
Кристиан Клэйсон