r - 目标函数中双线性项的松弛 - 使用 CVXR 和 McCormick 包络
问题描述
我有一个目标函数
有一些限制
我想最小化。
我想使用 R 包CVXR和McCormick 信封。
让我们检查一下代码：
library(CVXR) # if necessary
x <- Variable(1)
y <- Variable(1)
w <- Variable(1)
objective <- Minimize(5*x^2 + 14*w + 10*y^2 -76*x -108*y +292)
constraints <- list(x >= 0, x <= 100,
y >= 0, y <= 100,
x+2*y <= 10,
x+y <= 6,
w >= 0, w >= 100*x + 100*y - 10000, # constraints according to McCormick envelopes
w <= 100*y, w <= 100*x) # constraints according to McCormick envelopes
prob_OF <- Problem(objective, constraints)
solution_OF <- solve(prob_OF)
solution_OF$value
## -125.0667
solution_OF$getValue(x)
## 2.933333
solution_OF$getValue(y)
## 3.066667
solution_OF$getValue(w)
## 1.000135e-30
但遗憾的是，这是一个缺点：
和的值
只是近似值，因为 McCormick 是约束的松弛。
- 这些是真正的价值观：
为了克服这个缺点，您可以使用这种方法（请参阅 josliber 的答案），在其中将间隔拆分为一个变量。就像josliber我在 x 变量上分开了......
在以下部分中，我的问题出现了 - 但首先看看我的代码：
library(CVXR) # if necessary
# the two variables for the objective function
x <- Variable(1)
y <- Variable(1)
# five variables for w - substitute of the bilinear part
w1 <- Variable(1)
w2 <- Variable(1)
w3 <- Variable(1)
w4 <- Variable(1)
w5 <- Variable(1)
# five boolean variables to know which range of the x-axis is used
z1 <- Variable(1, boolean=TRUE)
z2 <- Variable(1, boolean=TRUE)
z3 <- Variable(1, boolean=TRUE)
z4 <- Variable(1, boolean=TRUE)
z5 <- Variable(1, boolean=TRUE)
# objective function with the five linear substitutes for xy
objective <- Minimize(5*x^2 + 14*w1 + 14*w2 + 14*w3 + 14*w4 + 14*w5 + 10*y^2 -76*x -108*y +292)
# for convenience - to build up the constraints easier
x_Range=matrix(rep(seq(from=0,to=100,by=20),each=2)[-c(1,12)],nrow=2,byrow=FALSE)
## [,1] [,2] [,3] [,4] [,5]
##[1,] 0 20 40 60 80
##[2,] 20 40 60 80 100
y_Range=matrix(c(0,100),nrow=2,byrow=FALSE)
## [,1]
##[1,] 0
##[2,] 100
# FIRST alternative of the constraints
constraints <- list(x >= 0, x <= 100,
y >= 0, y <= 100,
x+2*y <= 10,
x+y <= 6,
## w1
w1 <= x_Range[2,1]*y + x1*y_Range[1,1] - x_Range[2,1]*y_Range[1,1]*z1, #w1 <= xU1*y + x1*yL - xU1*yL*z1,
w1 <= x1*y_Range[2,1] + x_Range[1,1]*y - x_Range[1,1]*y_Range[2,1]*z1, #w1 <= x1*yU + xL1*y - xL1*yU*z1,
x1 >= x_Range[1,1]*z1, x1 <= x_Range[2,1]*z1, #xL1*z1 <= x1 <= xU1*z1,
## w2
w2 <= x_Range[2,2]*y + x2*y_Range[1,1] - x_Range[2,2]*y_Range[1,1]*z2, #w2 <= xU2*y + x2*yL - xU2*yL*z2,
w2 <= x2*y_Range[2,1] + x_Range[1,2]*y - x_Range[1,2]*y_Range[2,1]*z2, #w2 <= x2*yU + xL2*y - xL2*yU*z2,
x2 >= x_Range[1,2]*z2, x2 <= x_Range[2,2]*z2, #xL2*z2 <= x2 <= xU2*z2,
## w3
w3 <= x_Range[2,3]*y + x3*y_Range[1,1] - x_Range[2,3]*y_Range[1,1]*z3, #w3 <= xU3*y + x3*yL - xU3*yL*z3,
w3 <= x3*y_Range[2,1] + x_Range[1,3]*y - x_Range[1,3]*y_Range[2,1]*z3, #w3 <= x3*yU + xL3*y - xL3*yU*z3,
x3 >= x_Range[1,3]*z3, x3 <= x_Range[2,3]*z3, #xL3*z3 <= x3 <= xU3*z3,
## w4
w4 <= x_Range[2,4]*y + x4*y_Range[1,1] - x_Range[2,4]*y_Range[1,1]*z4, #w4 <= xU4*y + x4*yL - xU4*yL*z4,
w4 <= x4*y_Range[2,1] + x_Range[1,4]*y - x_Range[1,4]*y_Range[2,1]*z4, #w4 <= x4*yU + xL4*y - xL4*yU*z4,
x4 >= x_Range[1,4]*z4, x4 <= x_Range[2,4]*z4, #xL4*z4 <= x4 <= xU4*z4,
## w5
w5 <= x_Range[2,5]*y + x5*y_Range[1,1] - x_Range[2,5]*y_Range[1,1]*z5, #w5 <= xU5*y + x5*yL - xU5*yL*z5,
w5 <= x5*y_Range[2,1] + x_Range[1,5]*y - x_Range[1,5]*y_Range[2,1]*z5, #w5 <= x5*yU + xL5*y - xL5*yU*z5,
x5 >= x_Range[1,5]*z5, x5 <= x_Range[2,5]*z5 #xL5*z5 <= x5 <= xU5*z5
)
# SECOND alternative of the constraints
constraints <- list(x >= 0, x <= 100,
y >= 0, y <= 100,
x+2*y <= 10,
x+y <= 6,
## w1
w1 >= x_Range[1,1]*y + x1*y_Range[1,1] - x_Range[1,1]*y_Range[1,1]*z1, #w1 >= xL1*y + x1*yL - xL1*yL*z1,
w1 >= x_Range[2,1]*y + x1*y_Range[2,1] - x_Range[2,1]*y_Range[2,1]*z1, #w1 >= xU1*y + x1*yU - xU1*yU*z1,
w1 <= x_Range[2,1]*y + x1*y_Range[1,1] - x_Range[2,1]*y_Range[1,1]*z1, #w1 <= xU1*y + x1*yL - xU1*yL*z1,
w1 <= x1*y_Range[2,1] + x_Range[1,1]*y - x_Range[1,1]*y_Range[2,1]*z1, #w1 <= x1*yU + xL1*y - xL1*yU*z1,
x1 >= x_Range[1,1]*z1, x1 <= x_Range[2,1]*z1, #xL1*z1 <= x1 <= xU1*z1,
## w2
w2 >= x_Range[1,2]*y + x2*y_Range[1,1] - x_Range[1,2]*y_Range[1,1]*z2, #w2 >= xL2*y + x2*yL - xL2*yL*z2,
w2 >= x_Range[2,2]*y + x2*y_Range[2,1] - x_Range[2,2]*y_Range[2,1]*z2, #w2 >= xU2*y + x2*yU - xU2*yU*z2,
w2 <= x_Range[2,2]*y + x2*y_Range[1,1] - x_Range[2,2]*y_Range[1,1]*z2, #w2 <= xU2*y + x2*yL - xU2*yL*z2,
w2 <= x2*y_Range[2,1] + x_Range[1,2]*y - x_Range[1,2]*y_Range[2,1]*z2, #w2 <= x2*yU + xL2*y - xL2*yU*z2,
x2 >= x_Range[1,2]*z2, x2 <= x_Range[2,2]*z2, #xL2*z2 <= x2 <= xU2*z2,
## w3
w3 >= x_Range[1,3]*y + x3*y_Range[1,1] - x_Range[1,3]*y_Range[1,1]*z3, #w3 >= xL3*y + x3*yL - xL3*yL*z3,
w3 >= x_Range[2,3]*y + x3*y_Range[2,1] - x_Range[2,3]*y_Range[2,1]*z3, #w3 >= xU3*y + x3*yU - xU3*yU*z3,
w3 <= x_Range[2,3]*y + x3*y_Range[1,1] - x_Range[2,3]*y_Range[1,1]*z3, #w3 <= xU3*y + x3*yL - xU3*yL*z3,
w3 <= x3*y_Range[2,1] + x_Range[1,3]*y - x_Range[1,3]*y_Range[2,1]*z3, #w3 <= x3*yU + xL3*y - xL3*yU*z3,
x3 >= x_Range[1,3]*z3, x3 <= x_Range[2,3]*z3, #xL3*z3 <= x3 <= xU3*z3,
## w4
w4 >= x_Range[1,4]*y + x4*y_Range[1,1] - x_Range[1,4]*y_Range[1,1]*z4, #w4 >= xL4*y + x4*yL - xL4*yL*z4,
w4 >= x_Range[2,4]*y + x4*y_Range[2,1] - x_Range[2,4]*y_Range[2,1]*z4, #w4 >= xU4*y + x4*yU - xU4*yU*z4,
w4 <= x_Range[2,4]*y + x4*y_Range[1,1] - x_Range[2,4]*y_Range[1,1]*z4, #w4 <= xU4*y + x4*yL - xU4*yL*z4,
w4 <= x4*y_Range[2,1] + x_Range[1,4]*y - x_Range[1,4]*y_Range[2,1]*z4, #w4 <= x4*yU + xL4*y - xL4*yU*z4,
x4 >= x_Range[1,4]*z4, x4 <= x_Range[2,4]*z4, #xL4*z4 <= x4 <= xU4*z4,
## w5
w5 >= x_Range[1,5]*y + x5*y_Range[1,1] - x_Range[1,5]*y_Range[1,1]*z5, #w5 >= xL5*y + x5*yL - xL5*yL*z5,
w5 >= x_Range[2,5]*y + x5*y_Range[2,1] - x_Range[2,5]*y_Range[2,1]*z5, #w5 >= xU5*y + x5*yU - xU5*yU*z5,
w5 <= x_Range[2,5]*y + x5*y_Range[1,1] - x_Range[2,5]*y_Range[1,1]*z5, #w5 <= xU5*y + x5*yL - xU5*yL*z5,
w5 <= x5*y_Range[2,1] + x_Range[1,5]*y - x_Range[1,5]*y_Range[2,1]*z5, #w5 <= x5*yU + xL5*y - xL5*yU*z5,
x5 >= x_Range[1,5]*z5, x5 <= x_Range[2,5]*z5 #xL5*z5 <= x5 <= xU5*z5
)
# Now the final calculations
prob_OF <- Problem(objective, constraints)
solution_OF <- solve(prob_OF)
# results
### of FIRST constraint alternative
solution_OF$value
## NA
solution_OF$getValue(x1)
## NA
solution_OF$getValue(x2)
## NA
solution_OF$getValue(x3)
## NA
solution_OF$getValue(x4)
## NA
solution_OF$getValue(x5)
## NA
# results
### of SECOND constraint alternative
solution_OF$value
## 15.99776
solution_OF$getValue(x1)
## 4.206985
solution_OF$getValue(x2)
## 28.49989
solution_OF$getValue(x3)
## 49.34965
solution_OF$getValue(x4)
## 69.59733
solution_OF$getValue(x5)
## 89.71508
问题：
- 为什么josliber只使用四个不等式中的两个？
- 因此，我也在代码中尝试了第二个约束替代方案
- 你能帮我解决我的问题吗？！
- 我想我必须使用第二个约束替代方案，但这里的值
solution_OF$getValue(x'ses)是如此之高，以至于像josliber提到的那样总结它们不会让我得到预期的结果x=2。 - 在这两种选择中，都有两个约束
x+2*y <= 10和x+y <= 6。由于我将 x 范围分成五个子部分，我必须转换它们吗？
- 我想我必须使用第二个约束替代方案，但这里的值
- 是否也可以拆分多个变量？参考josliber的回答。
解决方案
我们可以使问题凸出：
min 5z^2+(1/5)y^2-76x-108*y+292
z = x+(7/5)y
x+2y <= 10
x+y <= 6
这可以输入 CVXR 并使用任何 QP 求解器求解。（当然，检查我的数学）。
推荐阅读
- sql-server - 尝试编写动态 sql 并将结果导出到文本文件
- c++ - MRISegmentation.exe 中 0x0435A072 (mfc110d.dll) 的第一次机会异常：0xC0000005：访问冲突读取位置 0x00000000
- android - 如何使用带有 Firestore onSnapshotListener 的任务来链接实时更新？
- php - 根据变量的值更改颜色
- mysql - 从 sparklyr 和/或 pyspark 连接到 mysql
- javascript - 请在此处查找错误。单击按钮后，单词会在框中出现并消失
- reactjs - 仅当道具更新（而不是状态）时才反应组件挂钩
- windows - 如何在 Powershell 中的 System.String 类型的字符串中添加值
- python - 使用 pd.to_datetime 将字符串日期转换为日期时间格式时出错
- android - 将片段添加到片段中