Какие численные оптимизаторы могут работать только с градиентами и без явного значения цели?

У меня есть проблема оптимизации, которая включает в себя минимизацию функции, градиент которой я знаю, но фактическое значение целевой функции в любой точке неизвестно.

Я хотел бы оптимизировать функцию с помощью BFGS, но все реализации BFGS, которые я нашел, похоже, требуют знания значения цели, особенно на этапе поиска строки. Я просмотрел реализацию BFGS как на Python (scipy), так и на C++.

Очевидно, я могу использовать градиентный спуск, но я бы предпочел не изобретать велосипед здесь.

Любые идеи?

Подробнее: я хочу минимизировать h. Но мне не дано h. Мне дали h = f(g) и явную формулу для g(x). f в основном преобразует градиенты g каким-то хитрым геометрическим способом, который не слишком сложно вычислить, но невозможно проинтегрировать. Таким образом, довольно просто вычислить градиент h(x), но трудно получить явные значения для h(x).


r numpy optimization numerical-methods numerics
person Robert T. McGibbon    schedule 01.02.2013    source источник
comment
Еще немного деталей: я хочу минимизировать $h$. Но мне не дают $h$. Мне дали $\del h = f(\del g)$ и явную формулу для $g(x)$. $f$ в основном преобразует градиенты $g$ каким-то хитрым геометрическим способом, который не слишком сложно вычислить, но невозможно проинтегрировать. Таким образом, довольно просто вычислить градиент $h(x)$, но трудно получить явные значения для $h(x)$.   -  person Robert T. McGibbon    schedule 01.02.2013
comment
Можете ли вы дать определения для f и g? Если нет, можете ли вы предоставить больше информации о h, например, является ли он выпуклым? n раз непрерывно дифференцируема?   -  person orizon    schedule 01.02.2013

Ответы (4)


arrow_upward
3
arrow_downward

Я полагаю, что вы свели проблему к поиску корней. Вы можете использовать один из искателей корня в scipy, то вам просто нужно проверить, является ли эта точка минимумом, максимумом или точкой перегиба.

person Bi Rico    schedule 01.02.2013
comment
Я думал, что это был ответ, но, если подумать, я на самом деле думаю, что это не совсем так. Это чрезвычайно специализированная задача поиска корня, потому что в целом мы знаем, что хотим двигаться в направлении, противоположном градиенту. Если мы просто находим корень, и все, что мы знаем, это то, что мы хотим найти, где градиент равен нулю, мы действительно можем получить направление поиска только из обратного якобиана/гессеана. - person Robert T. McGibbon; 08.02.2013

arrow_upward
2
arrow_downward

В этом случае попробуйте минимизировать h(x) до степени два. Это потому, что вы, по сути, ищете точки, в которых h(x) близок к нулю. Вы можете округлить его, возведя его в квадрат и выполнив поиск по параметрам.

РЕДАКТИРОВАТЬ: извините, я имел в виду, что h(x) - это градиент..

person Aditya Sihag    schedule 01.02.2013
comment
Значит, ваше решение проблемы отсутствия h состоит в том, чтобы возвести h в квадрат? - person Dason; 01.02.2013
comment
Более того, квадрат невыпуклой функции обычно также не является выпуклым. Например, f(x) = sin(x). - person orizon; 01.02.2013
comment
может быть, он имел в виду минимизировать квадрат градиента? - person flodel; 01.02.2013
comment
Я думаю, что этот ответ вполне хорош: вместо того, чтобы минимизировать функционал h, просто попытайтесь найти такое x, что некоторая норма градиента равна нулю. - person Dr_Sam; 01.02.2013
comment
это может работать, но на самом деле может работать не очень хорошо - см., например. соответствующую главу Numerical Recipes (глава 10, я думаю), в которой указывается, что поиск корня намного сложнее и хуже обусловлен, чем минимизация. Но если у тебя нет выбора... - person Ben Bolker; 02.02.2013

arrow_upward
1
arrow_downward

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

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

Я реализовал его для BFGS на python и C++: https://gist.github.com/rmcgibbo/4735287. Однако на втором этапе, я думаю, вы могли бы получить тот же результат, предоставив подпрограмме BFGS функцию, которая всегда уменьшается (например, она содержит счетчик, отслеживающий количество вызовов, и всегда возвращает меньшее число, чем было) последний раз, когда вы звонили ему). Снижение должно быть достаточно большим, чтобы вы всегда выполняли правило Армихо (http://en.wikipedia.org/wiki/Wolfe_conditions).

person Robert T. McGibbon    schedule 08.02.2013

arrow_upward
0
arrow_downward

Может быть, разговор о более простом примере поможет. Возьмем некоторый скаляр y=f(x). Градиент y равен df/dx . Если вы везде знаете производную, вы можете легко (!!) определить значение f (x) либо аналитически, либо с помощью численного интегрирования, но с неопределимой глобальной константой. Старый трюк с интегралом (f(x)dx) = F(x) + C. Таким образом, если вы не можете закрепить свою функцию h хотя бы в одной точке, вы не сможете решить проблему. Вы можете отследить расположение минимума x, чтобы h(x) было минимумом), но не значение h(x)

person Carl Witthoft    schedule 01.02.2013