quadprog 找不到解决方案
quadprog fails to find a solution
我正在尝试优化一组框的布局 w.r.t。他们的衣架位置 s.t。盒子与衣架最对齐,不会相互挤压。使用四元组。
给定:
1. box hanger x-locations (P). =710 850 990 1130
2. box-sizes (W). =690 550 690 130
3. usable x-spread tuple (S). =-150 2090
4. number of boxes (K). =4
5. minimum interbox spread (G). =50
6. box x-locations (X). =objective
我们可以看到所需的总 x 点差为 sum(W) + 3G = 2060 + 150 = 2210,而可用的 x 点差为 S[2] - S1 = 2240。所以,应该存在解决方案。
分钟:
sumof (P[i] – X[i])^2
s.t.:
(1) X[i+i] – X[i] >= G + ½ ( W[i+1] + W[i] ); i = 1..(K-1),即盒子不会相互排挤
-X[i] + X[i+1] >= -( -G – ½ (W[i+1] + W[i]) )
(2) X1 >= S[left] + ½ W1, (3) X[K] <= S[right] – ½ W[K],即盒子在给定的 x-spread
内
X[1] >= - ( S[left] + ½ W[1] )
-X[K] >= - ( S[right] – ½ W[K] )
总共有 5 个约束 - 3 个用于框间传播,2 个用于四肢。
在 R 中:
> Dmat = matrix(0,4,4)
> diag(Dmat) = 1
> dvec = P, the hanger locations
[1] 710 850 990 1130
> bvec
[1] -670 -670 -460 -195 2025
> t(Amat)
[,1] [,2] [,3] [,4]
[1,] -1 1 0 0
[2,] 0 -1 1 0
[3,] 0 0 -1 1
[4,] 1 0 0 0
[5,] 0 0 0 -1
> solve.QP(Dmat, dvec, Amat, bvec)
Error in solve.QP(Dmat, dvec, Amat, bvec) :
constraints are inconsistent, no solution!
很明显我错过了或错误指定了问题 (Package 'quadprog')!我正在使用 quadprog,因为我找到了它的 JavaScript 端口。
非常感谢。
问题在于 Amat
、bvec
或两者的设置。 solve.QP
试图找到受
约束的二次规划问题的解 b
t(Amat)*b >= bvec
在你的例子中扩展这个约束,我们想要找到一个满足条件的向量b := c(b[1], b[2], b[3], b[4])
:
-b[1] + b[2] >= -670
,
-b[2] + b[3] >= -670
,
-b[3] + b[4] >= -460
,
b[1] >= -195
和-b[4] >= 2025
(即b[4] <= -2025
)。
然而,通过将前四个不等式相加,我们得到 b[4] >= -670-670-460-195 = -1995
。换句话说,b[4]
必须大于 -1995
且小于 -2025
。这是一个矛盾,因此 solve.QP
无法找到解决方案。
使用约束 -b[4] >= -2025
尝试此示例,通过设置 bvec = c(-670, -670, -460, -195, -2025)
产生一个解决方案。无需过多考虑您的上述表述,也许这是有意为之(或者这些值中的另一个值应该是正数)?
我不确定这是否解决了您的物理问题,但下面的代码似乎解决了您所说的优化问题。我把它概括为
可变数量的框并包含一个图来检查解决方案。
library(quadprog)
p <- c(710, 850, 990, 1130) # hanger positions
w <- c(690, 550, 690, 130) # box widths
g <- 50 # min box separation
s <- c(-150, 2390) # min and max postions of box edges
k <- length(w) # number of boxes
Dmat <- 2*diag(nrow=k)
dvec <- p
# separation constraints
Amat <- -diag(nrow=k,ncol=(k-1))
Amat[lower.tri(Amat)] <- unlist(lapply((k-1):1, function(n) c(1,numeric(n-1))))
bvec <- sapply(1:(k-1), function(n) g + (w[n+1]+w[n])/2)
# x-spread constraints
Amat <- cbind(Amat, c(1,numeric(k-1)), c(numeric(k-1),-1))
bvec <- c(bvec, s[1] + w[1]/2, -(s[2] - w[k]/2))
sol <- solve.QP(Dmat, dvec, Amat, bvec)
plot(x=s, y=c(0,0), type="l", ylim=c(-2.5,0))
points(x=p, y=numeric(k), pch=19)
segments(x0=sol$solution, y0=-1, x1=p, y1=0)
rect(xleft=sol$solution-w/2, xright=sol$solution+w/2, ytop=-1.0, ybottom=-2, density=8)
我正在尝试优化一组框的布局 w.r.t。他们的衣架位置 s.t。盒子与衣架最对齐,不会相互挤压。使用四元组。
给定:
1. box hanger x-locations (P). =710 850 990 1130
2. box-sizes (W). =690 550 690 130
3. usable x-spread tuple (S). =-150 2090
4. number of boxes (K). =4
5. minimum interbox spread (G). =50
6. box x-locations (X). =objective
我们可以看到所需的总 x 点差为 sum(W) + 3G = 2060 + 150 = 2210,而可用的 x 点差为 S[2] - S1 = 2240。所以,应该存在解决方案。
分钟:
sumof (P[i] – X[i])^2
s.t.:
(1) X[i+i] – X[i] >= G + ½ ( W[i+1] + W[i] ); i = 1..(K-1),即盒子不会相互排挤
-X[i] + X[i+1] >= -( -G – ½ (W[i+1] + W[i]) )
(2) X1 >= S[left] + ½ W1, (3) X[K] <= S[right] – ½ W[K],即盒子在给定的 x-spread
内 X[1] >= - ( S[left] + ½ W[1] )
-X[K] >= - ( S[right] – ½ W[K] )
总共有 5 个约束 - 3 个用于框间传播,2 个用于四肢。
在 R 中:
> Dmat = matrix(0,4,4)
> diag(Dmat) = 1
> dvec = P, the hanger locations
[1] 710 850 990 1130
> bvec
[1] -670 -670 -460 -195 2025
> t(Amat)
[,1] [,2] [,3] [,4]
[1,] -1 1 0 0
[2,] 0 -1 1 0
[3,] 0 0 -1 1
[4,] 1 0 0 0
[5,] 0 0 0 -1
> solve.QP(Dmat, dvec, Amat, bvec)
Error in solve.QP(Dmat, dvec, Amat, bvec) :
constraints are inconsistent, no solution!
很明显我错过了或错误指定了问题 (Package 'quadprog')!我正在使用 quadprog,因为我找到了它的 JavaScript 端口。
非常感谢。
问题在于 Amat
、bvec
或两者的设置。 solve.QP
试图找到受
b
t(Amat)*b >= bvec
在你的例子中扩展这个约束,我们想要找到一个满足条件的向量b := c(b[1], b[2], b[3], b[4])
:
-b[1] + b[2] >= -670
,-b[2] + b[3] >= -670
,-b[3] + b[4] >= -460
,b[1] >= -195
和
-b[4] >= 2025
(即b[4] <= -2025
)。
然而,通过将前四个不等式相加,我们得到 b[4] >= -670-670-460-195 = -1995
。换句话说,b[4]
必须大于 -1995
且小于 -2025
。这是一个矛盾,因此 solve.QP
无法找到解决方案。
使用约束 -b[4] >= -2025
尝试此示例,通过设置 bvec = c(-670, -670, -460, -195, -2025)
产生一个解决方案。无需过多考虑您的上述表述,也许这是有意为之(或者这些值中的另一个值应该是正数)?
我不确定这是否解决了您的物理问题,但下面的代码似乎解决了您所说的优化问题。我把它概括为 可变数量的框并包含一个图来检查解决方案。
library(quadprog)
p <- c(710, 850, 990, 1130) # hanger positions
w <- c(690, 550, 690, 130) # box widths
g <- 50 # min box separation
s <- c(-150, 2390) # min and max postions of box edges
k <- length(w) # number of boxes
Dmat <- 2*diag(nrow=k)
dvec <- p
# separation constraints
Amat <- -diag(nrow=k,ncol=(k-1))
Amat[lower.tri(Amat)] <- unlist(lapply((k-1):1, function(n) c(1,numeric(n-1))))
bvec <- sapply(1:(k-1), function(n) g + (w[n+1]+w[n])/2)
# x-spread constraints
Amat <- cbind(Amat, c(1,numeric(k-1)), c(numeric(k-1),-1))
bvec <- c(bvec, s[1] + w[1]/2, -(s[2] - w[k]/2))
sol <- solve.QP(Dmat, dvec, Amat, bvec)
plot(x=s, y=c(0,0), type="l", ylim=c(-2.5,0))
points(x=p, y=numeric(k), pch=19)
segments(x0=sol$solution, y0=-1, x1=p, y1=0)
rect(xleft=sol$solution-w/2, xright=sol$solution+w/2, ytop=-1.0, ybottom=-2, density=8)