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$.

Yann · Answer

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.

Stéphane Laurent · Answer

There's no need to resort to linear programming or optimization. The objective function is linear, hence its extreme values are either $pminfty$ 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)
}

Answered by Stéphane Laurent on April 6, 2021

Problem of half-planes intersection

2 Answers

Add your own answers!

Ask a Question