0
$\begingroup$

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

$\endgroup$
1
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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". $\endgroup$ – Wolfgang Bangerth Dec 8 '20 at 19:25
  • $\begingroup$ well spotted. I guess that gives you even more options on which libraries to use ;) $\endgroup$ – Yann Dec 9 '20 at 0:08
0
$\begingroup$

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)
}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.