NLopt SLSQP 舍弃好的解决方案，取而代之的是旧的、更差的解决方案

Question

我正在解决金融领域的标准优化问题 - 投资组合优化。绝大多数时候，NLopt return 是一个明智的解决方案。然而，在极少数情况下，SLSQP 算法似乎迭代到正确的解决方案，然后没有明显的原因它选择 return 迭代过程中大约三分之一的解决方案，这显然是次优的。有趣的是，通过非常少量更改初始参数向量可以解决问题。

我已经设法分离出一个相对简单的工作示例来说明我正在谈论的行为。抱歉数字有点乱。这是我能做的最好的。以下代码可以剪切并粘贴到 Julia REPL 中，每次 NLopt 调用 objective 函数时，将运行和打印 objective 函数和参数的值。我两次调用优化例程。如果您向后滚动浏览下面代码打印的输出，您会注意到在第一次调用时，优化例程迭代到一个很好的解决方案，objective 函数值为 0.0022 但随后没有明显的原因可以追溯到更早的解决方案，其中 objective 函数是 0.0007，而 return 是它。第二次调用优化函数时，我使用了稍微不同的参数起始向量。同样，优化例程迭代到同一个好的解决方案，但这次它 return 是 objective 函数值为 0.0022 的好的解决方案。

所以，问题是：有人知道为什么在第一种情况下 SLSQP 在迭代过程中仅进行了大约三分之一就放弃了好的解决方案而选择了一个更差的解决方案吗？如果是这样，我有什么办法可以解决这个问题吗？

#-------------------------------------------
#Load NLopt package
using NLopt
#Define objective function for the portfolio optimisation problem (maximise expected return subject to variance constraint)
function obj_func!(param::Vector{Float64}, grad::Vector{Float64}, meanVec::Vector{Float64}, covMat::Matrix{Float64})
    if length(grad) > 0
        tempGrad = meanVec - covMat * param
        for j = 1:length(grad)
            grad[j] = tempGrad[j]
        end
        println("Gradient vector = " * string(grad))
    end
    println("Parameter vector = " * string(param))
    fOut = dot(param, meanVec) - (1/2)*dot(param, covMat*param)
    println("Objective function value = " * string(fOut))
    return(fOut)
end
#Define standard equality constraint for the portfolio optimisation problem
function eq_con!(param::Vector{Float64}, grad::Vector{Float64})
    if length(grad) > 0
        for j = 1:length(grad)
            grad[j] = 1.0
        end
    end
    return(sum(param) - 1.0)
end
#Function to call the optimisation process with appropriate input parameters
function do_opt(meanVec::Vector{Float64}, covMat::Matrix{Float64}, paramInit::Vector{Float64})
    opt1 = Opt(:LD_SLSQP, length(meanVec))
    lower_bounds!(opt1, [0.0, 0.0, 0.05, 0.0, 0.0, 0.0])
    upper_bounds!(opt1, [1.0, 1.0, 1.0, 1.0, 1.0, 1.0])
    equality_constraint!(opt1, eq_con!)
    ftol_rel!(opt1, 0.000001)
    fObj = ((param, grad) -> obj_func!(param, grad, meanVec, covMat))
    max_objective!(opt1, fObj)
    (fObjOpt, paramOpt, flag) = optimize(opt1, paramInit)
    println("Returned parameter vector = " * string(paramOpt))
    println("Return objective function = " * string(fObjOpt))
end
#-------------------------------------------
#Inputs to optimisation
meanVec = [0.00238374894628471,0.0006879970888824095,0.00015027322404371585,0.0008440624572209092,-0.004949409024535505,-0.0011493778903180567]
covMat = [8.448145928621056e-5 1.9555283947528615e-5 0.0 1.7716366331331983e-5 1.5054664977783003e-5 2.1496436765051825e-6;
          1.9555283947528615e-5 0.00017068536691928327 0.0 1.4272576023325365e-5 4.2993023110905543e-5 1.047156519965148e-5;
          0.0 0.0 0.0 0.0 0.0 0.0;
          1.7716366331331983e-5 1.4272576023325365e-5 0.0 6.577888700124854e-5 3.957059294420261e-6 7.365234067319808e-6
          1.5054664977783003e-5 4.2993023110905543e-5 0.0 3.957059294420261e-6 0.0001288060347757139 6.457128839875466e-6
          2.1496436765051825e-6 1.047156519965148e-5 0.0 7.365234067319808e-6 6.457128839875466e-6 0.00010385067478418426]
paramInit = [0.0,0.9496114216578236,0.050388578342176464,0.0,0.0,0.0]

#Call the optimisation function
do_opt(meanVec, covMat, paramInit)

#Re-define initial parameters to very similar numbers
paramInit = [0.0,0.95,0.05,0.0,0.0,0.0]

#Call the optimisation function again
do_opt(meanVec, covMat, paramInit)

注意：我知道我的协方差矩阵是半正定的，而不是正定的。这不是问题的根源。我已经通过将零行的对角线元素更改为一个小但明显非零的值来确认这一点。上面的示例以及我可以随机生成的其他示例中仍然存在该问题。

Answer 1

SLSQP 是一种约束优化算法。每一轮它都必须检查是否具有最佳 objective 值并满足约束条件。最终输出是满足约束条件下的最优值。

通过将 eq_con! 更改为：

来打印约束值

function eq_con!(param::Vector{Float64}, grad::Vector{Float64})
    if length(grad) > 0
        for j = 1:length(grad)
            grad[j] = 1.0
        end
    end
    @show sum(param)-1.0
    return(sum(param) - 1.0)
end

显示第一个运行中的最后一个有效评价点有：

Objective function value = 0.0007628202546187453
sum(param) - 1.0 = 0.0

而在第二个运行中，所有的评估点都满足约束条件。这解释了行为并表明它是合理的。

附录：

导致参数不稳定的根本问题是等式约束的确切性质。引自 NLopt 参考 (http://ab-initio.mit.edu/wiki/index.php/NLopt_Reference#Nonlinear_constraints):

For equality constraints, a small positive tolerance is strongly advised in order to allow NLopt to converge even if the equality constraint is slightly nonzero.

确实，将 do_opt 中的 equality_constraint! 调用切换为

    equality_constraint!(opt1, eq_con!,0.00000001)

给出两个初始参数的 0.0022 解。

NLopt SLSQP 舍弃好的解决方案，取而代之的是旧的、更差的解决方案

NLopt SLSQP discards good solution in favour of older, worse solution

julia

mathematical-optimization

nonlinear-optimization

nlopt