Writing a linear program to calculate the maximum inscribed circle into a convex polytope defined by equations

Question

I need to find the Chebyshev center of a convex polytope defined by equations (lines) of type y = a_ix + b_i using a linear program. I know how I would do it with inequalities of type a_ix + y <= b_i, but I can't figure this out.

I tried using the distance from a point to a line formula but couldn't make a linear program from it.

Answer 1

Here is a way with R:

####### Chebyshev center
library(CVXR)
# Generate the input data
a1 <- c( 2,  1)
a2 <- c( 2, -1)
a3 <- c(-1,  2)
a4 <- c(-1, -2)
b  <- c(1, 1, 1, 1)

# variables: radius and center
r   <- Variable(1)
x_c <- Variable(2)
objective <- Maximize(r)

# constraints
constraints <- list(
  a1*x_c + r*norm2(a1) <= b[1],
  a2*x_c + r*norm2(a2) <= b[2],
  a3*x_c + r*norm2(a3) <= b[3],
  a4*x_c + r*norm2(a4) <= b[4]
)

# solve
program <- Problem(objective, constraints)
solution <- solve(program, solver = "SCS", FEASTOL = 1e-4, RELTOL = 1e-3, verbose = TRUE)

# get solutions
radius <- solution$getValue(r)
center <- solution$getValue(x_c)

---

Source:

Chebyshev center.