# Problem of half-planes intersection

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

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 $$$$L(\mu,x) = f(x)+ \sum_{i=1}^m=\mu_i g_i(x)$$$$ 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.

• It is true that this is an optimization problem, but it has a very specific structure: Objective function and all constraints are linear. Such problems are called "linear programs" and the approach to solving them is generally not based on the Karush-Kuhn-Tucker conditions but on (variations of) Dantzig's "simplex algorithm". – Wolfgang Bangerth Dec 8 '20 at 19:25
• well spotted. I guess that gives you even more options on which libraries to use ;) – Yann Dec 9 '20 at 0:08

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