Julia: Оптимизируйте функцию стоимости с помощью `Optim.jl` и` autodiff` для целых чисел

Question

Мне нравится оптимизировать (минимизировать) следующую заданную функцию (quad_function) с помощью Optim.jl с автоматической дифференциацией (autodiff=true).

Мои целевые функции раундовReal значения целыми числами и поэтому являются ступенчатыми.

Как я использую опцию autodiff, значения Real получают dual numbers (ForwardDiff.Dual). Но, к сожалению, нет функции round, реализованной для типа ForwardDiff.Dual. Таким образом, я написал функцию roundtoint64, которая извлекает реальную часть. Такой подход вызывает проблемы при оптимизации.

using Plots 
plotlyjs() 

function roundtoint64(x) 
    if typeof(x) <: ForwardDiff.Dual 
    roundtoint64(x.value) 
    else 
    Int64(round(x)) 
    end 
end 

function quad_function(xs::Vector) 
    roundtoint64(xs[1])^2 + roundtoint64(xs[2])^2 
end 

x, y = linspace(-5, 5, 100), linspace(-5, 5, 100) 
z = Surface((x,y)->quad_function([x,y]), x, y) 
surface(x,y,z, linealpha = 0.3) 

Это как мой quad_function выглядит следующим образом:

Проблема в том, что optimize функции сходится сразу и не происходит.

using Optim 

res = Optim.optimize(
    quad_function, 
    [5.0,5.0], 
    Newton(), 
    OptimizationOptions(
    autodiff = true, 
    # show_trace = true 
)) 

результат:

Results of Optimization Algorithm 
* Algorithm: Newton's Method 
* Starting Point: [5.0,5.0] 
* Minimizer: [5.0,5.0] 
* Minimum: 5.000000e+01 
* Iterations: 0 
* Convergence: true 
    * |x - x'| < 1.0e-32: false 
    * |f(x) - f(x')|/|f(x)| < 1.0e-32: false 
    * |g(x)| < 1.0e-08: true 
    * Reached Maximum Number of Iterations: false 
* Objective Function Calls: 1 
* Gradient Calls: 1 


optimal_values = Optim.minimizer(res) # [5.0, 5.0] 
optimum   = Optim.minimum(res) # 50.0 

Я также попытался инициализировать optimize функции с вектором целых [5,5], чтобы избежать округления вещей, но это вызывает также проблемы с поиском начального размера шага в:

ERROR: InexactError() 
in alphainit(::Int64, ::Array{Int64,1}, ::Array{Int64,1}, ::Int64) at /home/sebastian/.julia/v0.5/Optim/src/linesearch/hz_linesearch.jl:63 
in optimize(::Optim.TwiceDifferentiableFunction, ::Array{Int64,1}, ::Optim.Newton, ::Optim.OptimizationOptions{Void}) at /home/sebastian/.julia/v0.5/Optim/src/newton.jl:69 
in optimize(::Function, ::Array{Int64,1}, ::Optim.Newton, ::Optim.OptimizationOptions{Void}) at /home/sebastian/.julia/v0.5/Optim/src/optimize.jl:169 

Вопрос: Есть ли способ рассказать optimize только e xplore целое пространство?

Обновление: Я считаю, что проблема с конвертерным подходом к Int64 является то, что я больше не имею ForwardDiff.Dual с и, таким образом, не могу вычислить любые производные/градиентов. Как могла бы выглядеть лучшая функция round, в которой раунды также вложенные дуэли и дают двойные дуги?

Answer 1

Как Erwin Kalvelagen указал в комментариях к моему вопросу: решения данного типа с данным алгоритмом и решателем нет.

Таким образом, я изменил мои функции затрат немного, чтобы иметь по крайней мере, некоторые градиенты, но до сих пор не гладко:

function quad_function_with_gradient(xs::Vector) 
    round(xs[1])*xs[1] + round(xs)[2]*xs[2] 
end 

, который выглядит следующим образом:

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

using Optim 

roundpartials{T<:ForwardDiff.Partials}(partials::T) = (round(v) for v in partials.values) 

Base.round{T<:ForwardDiff.Dual}(dual::T) = ForwardDiff.Dual(
    round(dual.value), 
    roundpartials(dual.partials)...) 

Это дает мне решение, но немного различный проблема:

res = Optim.optimize(
    quad_function, 
    [5.0,5.0], 
    Newton(), 
    OptimizationOptions(
    autodiff = true 
)) 

Results of Optimization Algorithm 
* Algorithm: Newton's Method 
* Starting Point: [5.0,5.0] 
* Minimizer: [0.0,0.0] 
* Minimum: 0.000000e+00 
* Iterations: 1 
* Convergence: true 
    * |x - x'| < 1.0e-32: false 
    * |f(x) - f(x')|/|f(x)| < 1.0e-32: false 
    * |g(x)| < 1.0e-08: true 
    * Reached Maximum Number of Iterations: false 
* Objective Function Calls: 5 
* Gradient Calls: 5 

Это до вас, ребята решить, является ли это приемлемым решением.

Answer 2

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

Существует, по сути, a round function implemented for ForwardDiff.Dual, у которого есть поведение, о котором вы упоминали в своем исходном сообщении, - оно обрезает частичные производные компоненты и применимо только к round к реальному компоненту. Это в основном правильное определение, потому что производная от round равна нулю почти всюду и не определена, где происходит шаг (то есть с интервалами 0.5).

Это определение может быть сделано «более правильным» путем распространения NaN или с ошибкой в ​​точках, где производная не определена, но с этой точки зрения не имеет большого преимущества с точки зрения практического AD. Метод round будет «выбирать сторону» в случае разрыва, поэтому имеет смысл для нас, чтобы «разглядеть сторону» при принятии производной. Это легко сделать в случае round, так как производная по обе стороны от разрыва равна нулю.

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