Problem of half-planes intersection

Question

Consider the half-planes $\{x \leqslant 2\}$ and $\{x+y \leqslant 3\}$. These two half-planes are coded with the R package 'rcdd' as follows:

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

And we can get a representation of their intersection as follows:

V <- scdd(H)

which gives:

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

The first column is always made of 0s, it is useless. The second one indicates whether we have a vertex of the intersection region (if 1 in the second column) or a ray (if 0). So here we have the vertex $(2,1)$ and two rays directed by $(-1,1)$ and $(0,-1)$.

We can add a new half-plane, e.g. $\{y \leqslant 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

Denote by $R$ the obtained region. My problem is the following one. Given a pair $(a,b)$, I want to get the minimum value and the maximal value (possibly infinites) of $ax + by$ with $(x,y) \in R$.

Answer 1

This is a textbook example of a continuous optimization problem: \begin{align} \min_{x} \quad &f(x)\\ \text{subject to }& g_i(x) \leq 0 \qquad i=1\,...\,m \end{align}

With the objective function $f=ax_1+bx_2$ and the inequality constraints $g_1(x)=x_1-2$, $g_2(x) =x_1+x_2-3$ and $g_3(x)=x_2-4$ in your case.

To solve such a problem, one usually computes the Lagrangian \begin{equation} L(\mu,x) = f(x)+ \sum_{i=1}^m=\mu_i g_i(x) \end{equation} and then searches for points $(\mu^*,x^*)$ that satisfy the Karush–Kuhn–Tucker conditions.

I'm not familiar with R, but there should be a package available to solve such problems (if not, any other language has one;) ) If you want to solve it on your own, refer to any book on continuous optimization.

Answer 2

There's no need to resort to linear programming or optimization. The objective function is linear, hence its extreme values are either $\pm\infty$ or they are attained at the vertices of the previous step.

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)
}

Answer 3

The equation $z=a x + b y$ defines a plane passing through the origin of coordinates $(x,y,z)$. If the plane is horizontal, i.e., perpendicular to the $z$ axis, the range of $z$ values is just $[0,0]$. That corresponds to $a=b=0$. For all other $a,b$ the plane is tilted with respect to the horizontal plane, and the range of $z$ values for points on the plane is $[-\infty,\infty]$.