R中二次规划的错误解决方案

Question

我正在尝试使用包 osqp 解决 R 中的二次规划。然而，结果看起来错得离谱。

重现此处所附示例的代码：（objective函数是最小化

library(osqp)
library(Matrix)
P <- Matrix(c(1., 0.,0,
              0., 1.,0, 0,0,1), 3, 3, sparse = TRUE)
q <- c(0, 1,1)
A <- Matrix(c(1., 1., 0.,
              1., 0., 1.,1,0,1), 3, 3, sparse = TRUE)
l <- c(1.2, 0., 0.7)
u <- c(2., 0.8, 0.7)
settings <- osqpSettings(alpha = 1.0,eps_abs = 1.0e-05, eps_rel = 1.0e-05,)
model <- osqp(P, q, A, l, u, settings)
res <- model$Solve()

这是模型的输出，显示最优值为0.7

但是，如果使用最优解插入 objective 函数，它会给出 1.018556

#this should be the final objective value after solving
0.5*t(res<span class="math-container">$x)%*%P%*%res$</span>x+t(c(0,1,1))%*%res$x

#the solution
res$x
#0.6261887 0.3500000 0.3500000

更重要的是，这不是最优解。如果我仔细观察这个解决方案，我可以找到另一个答案，它的 objective 函数更小，值为 0.5,0.1,0.6 我不确定我做错了什么。

感谢您提前提出任何建议！

Answer 1

我试图欺骗 OQSP（在 python）给出你的结果。

我一开始怀疑是alpha不过好像没什么区别。另一件事是迭代次数，它可能在 25 次迭代后没有收敛，但在那种情况下我不希望 objective 为 0.70000.

import osqp
from scipy.sparse import csr_matrix
P = np.array([[1., 0.,0],
            [0., 1.,0], 
            [0,0,1]]).T
q = np.array([0, 1,1])[None, :];
A = np.array([[1., 1., 0.],
              [1., 0., 1.],
              [1,0,1]]).T
l = np.array([1.2, 0., 0.7])[:, None]
u = np.array([2., 0.8, 0.7])[:, None]

m = osqp.OSQP()
m.setup(P=csr_matrix(P), A=csr_matrix(A), l=l, u=u, q=q.T,
        alpha=1.0, eps_abs = 1.0e-05, eps_rel = 1.0e-05, max_iter=25)
results = m.solve()

这给出了

x = [0.45492868, 0.35002252, 0.35002252]

已经接近[0.5, 0.35, 0.35]的最优解。我注意到的一件事是 q%*%x=0.7.

仔细看，我看到你的 A 的最后一行是 q，相应的约束指定 0.7 <= x(1) + x(2) <= 0.7。也就是说，您的问题的任何有效解决方案都有 q'x = 0.7 因此我们得出结论，内部 x' P x = 0。

如果我将 P 矩阵设置为零

，您显示的解决方案非常接近我获得的解决方案

m.setup(P=csr_matrix(P)*0, A=csr_matrix(A), l=l, u=u, q=q.T,
        alpha=1.0, eps_abs = 1.0e-05, eps_rel = 1.0e-05, max_iter=100)
results = m.solve()
results.x

-----------------------------------------------------------------
           OSQP v0.6.2  -  Operator Splitting QP Solver
              (c) Bartolomeo Stellato,  Goran Banjac
        University of Oxford  -  Stanford University 2021
-----------------------------------------------------------------
problem:  variables n = 3, constraints m = 3
          nnz(P) + nnz(A) = 9
settings: linear system solver = qdldl,
          eps_abs = 1.0e-05, eps_rel = 1.0e-05,
          eps_prim_inf = 1.0e-04, eps_dual_inf = 1.0e-04,
          rho = 1.00e-01 (adaptive),
          sigma = 1.00e-06, alpha = 1.00, max_iter = 25
          check_termination: on (interval 25),
          scaling: on, scaled_termination: off
          warm start: on, polish: off, time_limit: off

iter   objective    pri res    dua res    rho        time
   1  -9.9950e-03   1.20e+00   7.01e+01   1.00e-01   5.74e-05s
  25   7.0000e-01   2.66e-15   6.94e-18   1.00e-01   1.07e-03s

status:               solved
number of iterations: 25
optimal objective:    0.7000
run time:             1.79e-03s
optimal rho estimate: 1.70e+00

array([0.62618873, 0.35      , 0.35      ])

R中二次规划的错误解决方案

Wrong solution of quadratic programming in R

optimization

modeling

r