quadprog無法找到一個解決方案

我想優化一組框w.r.t的佈局。他們的衣架地點s.t.箱子與衣架大部分對齊，不會互相擠出。使用quadprog。quadprog無法找到一個解決方案

吉文斯：

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傳播是總和（W）+ 3G = 2060 + 150 = 2210，而可用的x傳播是S [2] - S 1 = 2240.所以，應該存在一個解決方案。

敏：

sumof (P[i] – X[i])^2 

s.t.:

（1）X [I + 1] - X [I]> = G +½（W [I + 1] + W [1]）; I = 1 ..（K-1），即框不排擠彼此

 -X[i] + X[i+1] >= -(-G – ½ (W[i+1] + W[i]))

（2）X 1> = S [左] +½W¯¯1，和（3）X [K ] < = S [右] - ½W [K]，即，盒是內給定的x傳播

 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端口。

非常感謝。

來源

2015-07-12 Dinesh

你的聲明，S [2] - S1 = 2240不是S的給定值正確[1]和S [2]。然而，如果你改變了S [1]的符號，那麼S [1] = -150，那麼你的數學運作並求解。QP返回一個解。 – WaltS

你是對的，應該是-150。 – Dinesh

我不確定這是否解決了您的物理問題，但下面的代碼似乎解決了您所述的優化問題。我已將它推廣到可變數量的盒子，幷包含一個圖表來檢查解決方案。

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)

enter image description here

來源

2015-07-13 12:43:00 WaltS

++爲可視化，謝謝 – Dinesh

問題出在設置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)產生一個解決方案。不要過多地考慮上面的表達式，也許這是有意的（或者這些值中的另一個應該是正的）？

來源

2015-07-12 20:48:16

謝謝，我做了更正。我得到的結果是（710 850 990 1130），但是導致框重疊，所以我想我需要回到繪圖板 - 可能需要更多約束 – Dinesh

順便說一句，quadprog文檔聲明它正在解決't （Amat）* b> = -bvec'這不是你寫的。澄清，請嗎？ – Dinesh

這並不是說。它表明它正在尋找使'-t（dvec）* b + 0.5 * t（b）* Dmat * b'最小化的矢量'b'，換句話說就是'solve.QP''解決了二次規劃問題的形式min（-d^T b + 1/2 b^TD b）「，但」具有約束A^T b> = b_0「。也就是說，找到的任何'b'都必須滿足't（Amat）* b> = bvec'，這就是我原來寫的。 –

quadprog無法找到一個解決方案

回答

相關問題