0

quad_function我喜欢通过使用Optim.jl自动微分（ ）来优化（最小化）以下给定函数（autodiff=true）。

我的目标函数将值四舍五入 Real为整数，因此是阶梯式的。

当我使用该autodiff选项时，我的Real值得到双数（ForwardDiff.Duals）。但不幸的是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只探索整数空间？

更新： 我认为转换方法的问题Int64是我不再有ForwardDiff.Duals ，因此无法计算任何导数/梯度。一个更好的round函数会是什么样子，哪些回合还嵌套了对偶并返回对偶？

4

2 回答 2

2

我会以更以双数为中心的答案来回应您的更新，因为 Erwin Kalvelagen 在最初的问题上击败了我。

事实上，有一个round实现的函数ForwardDiff.Dual具有您在原始帖子中提到的行为 - 它截断了偏导数分量并且仅适用round于实际分量。这是一个最正确的定义，因为 的导数round几乎在所有地方都为零，而在步骤发生的地方（即在 的间隔处0.5）未定义。

NaN通过在导数未定义的点传播 s 或错误，可以使该定义“更正确” ，但从实际 AD 的角度来看，该策略并没有太多好处。在不连续的情况下，该round方法将“选边”，因此我们在求导时手动“选边”是有意义的。这在 的情况下很容易round，因为不连续点两侧的导数为零。

您可以通过覆盖当前定义的方法来使用您想要的任何定义，但正如您所指出的，round中间偏导数可能会产生不正确的整体导数。这本质上是由于您不再区分相同的目标函数。

于 2016-11-25T20:04:37.560 回答
0

正如Erwin Kalvelagen在我的问题的评论中指出的那样：给定的算法和求解器无法解决此类问题。

因此，我稍微改变了我的成本函数，使其至少具有一些渐变，但仍然不平滑：

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

看起来像这样：

quad_function_with_gradient

但后来我仍然必须解决双数舍入问题。因此我写了一个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

由你们决定这是否是一个可行的解决方案。

于 2016-11-25T18:57:01.413 回答