半平面相交问题

计算科学 计算几何 r
2021-12-09 14:42:07

考虑半平面和 \{x+y \leqslant 3\}。这两个半平面使用 R 包 'rcdd' 进行编码，如下所示：{x⩽2}{x+y⩽3}

library(rcdd)
A <- rbind(
  c(1, 0), # x
  c(1, 1)  # x + y
)
b <- c(2, 3)
H <- makeH(A, b)

我们可以得到它们交集的表示如下：

V <- scdd(H)

这使：

> V$output
     [,1] [,2] [,3] [,4]
[1,]    0    1    2    1
[2,]    0    0   -1    1
[3,]    0    0    0   -1

第一列总是由 0 组成，没有用。第二个表示我们是否有相交区域的顶点（如果1在第二列）或射线（如果0）。所以这里我们有顶点和由和引导的两条光线。(2,1)(−1,1)(0,−1)

我们可以添加一个新的半平面，例如：{y⩽4}

H <- addHin(c(0, 1), 4, H)
scdd(H)$output
#       [,1] [,2] [,3] [,4]
# [1,]    0    0    0   -1
# [2,]    0    1    2    1
# [3,]    0    1   -1    4
# [4,]    0    0   -1    0

用表示获得的区域。我的问题是以下一个。给定一对 ，我想通过的最小值和最大值（可能是无穷大）。R(a,b)ax+by(x,y)∈R

3个回答

这是一个连续优化问题的教科书示例：

minxf(x)subject to gi(x)≤0i=1...m

在您的情况下，使用目标函数 和不等式约束、和。f=ax1+bx2 g1(x)=x1−2g2(x)=x1+x2−3g3(x)=x2−4

为了解决这样的问题，人们通常会计算拉格朗日 然后搜索满足Karush–Kuhn–Tucker 条件。

L(μ,x)=f(x)+∑i=1m=μigi(x)
(μ∗,x∗)

我不熟悉 R，但是应该有一个包可以解决这些问题（如果没有，任何其他语言都有一个；））如果你想自己解决它，请参阅任何关于持续优化的书。

无需求助于线性规划或优化。目标函数是线性的，因此它的极值要么是，要么是在上一步的顶点处获得的。±∞

V <- scdd(H)$output
vertices <- V[V[, 2L]==1, c(3L,4L), drop = FALSE]
rays <- V[V[, 2L]==0, c(3L,4L), drop = FALSE]
rays[rays < 0] <- -Inf 
rays[rays > 0] <- Inf 

x_infty <- c(any(rays[,1L] < 0), any(rays[,1L] > 0))
y_infty <- c(any(rays[,2L] < 0), any(rays[,2L] > 0))

Xt <- c(1, 5) # the new pair (a,b)
# min
if(
  any(x_infty | y_infty) && 
  (
    ((Xt[1L] > 0) && x_infty[1L]) || 
    ((Xt[2L] > 0) && y_infty[1L]) ||
    ((Xt[1L] < 0) && x_infty[2L]) || 
    ((Xt[2L] < 0) && y_infty[2L])
  )
){
  MIN <- -Inf
}else{
  MIN <- min(vertices %*% Xt)
}
# max 
if(
  any(x_infty | y_infty) && 
  (
    ((Xt[1L] > 0) && x_infty[2L]) || 
    ((Xt[2L] > 0) && y_infty[2L]) ||
    ((Xt[1L] < 0) && x_infty[1L]) || 
    ((Xt[2L] < 0) && y_infty[1L])
  )
){
  MAX <- Inf
}else{
  MAX <- max(vertices %*% Xt)
}

方程定义了通过坐标原点的平面。如果平面是水平的，即垂直于轴，则值的范围仅为。这对应于。对于所有其他平面相对于水平面倾斜，平面上点的值范围为。z=ax+by(x,y,z)zz[0,0]a=b=0a,bz[−∞,∞]

其它你可能感兴趣的问题
上一篇计算简单图形中的所有最短路径是否会产生遵循度量的完整图形？ 下一篇为什么我的 Lax Wendroff 代码中会出现此错误？