Julia：使用`Optim.jl`和`autodiff`優化整數的代價函數

Question

我喜歡用Optim.jl自動區分（autodiff=true）來優化（最小化）下列給定函數（quad_function）。

我的目標函數輪Real值整數，因此是步驟。

當我使用autodiff選項時，我的Real值得到dual numbers（ForwardDiff.Dual s）。但不幸的是沒有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 S和因此不能計算任何衍生物/梯度。一個更好的round函數怎麼可能是這樣的，哪些輪迴也可以嵌套雙重並且返回對偶？

Answer 1

As 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

由於Erwin Kalvelagen在原始問題上擊敗了我，我將以更多以雙號爲中心的答案迴應您的更新。

實際上，a round function implemented for ForwardDiff.Dual具有您在原始文章中提到的行爲 - 它會截斷偏微分組件，並僅將round應用於實際組件。這是一個大部分正確的定義，因爲round的導數幾乎爲零，並且在步驟出現的地方未定義（即間隔爲0.5）。

這個定義可以通過傳播NaN或在導數未定義的點上出錯來實現，但從實際AD的角度來看，這種策略沒有多大好處。在不連續的情況下，方法將「挑選一個方面」，所以當採用衍生時，我們有理由手動地「挑選一方」。這在round的情況下很容易，因爲不連續性兩邊的導數爲零。

您可以通過覆蓋當前定義的方法來使用任何定義，但正如您所指出的那樣，中間偏導數可能會產生不正確的整體導數。這基本上是由於你不再區分相同的目標函數。