Largest Ball in a Polyhedron in 2D

Problem

The following is a problem from Boyd and Vandenberghe (2004), section 4.3.1.

Find the largest Euclidean ball (i.e. its center and radius) that lies in a polyhedron described by affine inequalites:

\[ P = {x : a_i'*x <= b_i, i=1,...,m} \]

where x is in \({\mathbf R}^2\).

We define variables that determine the polyhedron.

a1 <- matrix(c(2,1))
a2 <- matrix(c(2,-1))
a3 <- matrix(c(-1,2))
a4 <- matrix(c(-1,-2))
b <- rep(1,4)

Next, we formulate the CVXR problem.

r <- Variable(name = "radius")
x_c <- Variable(2, name = "center")
obj <- Maximize(r)
constraints <- list(
    t(a1) %*% x_c + p_norm(a1, 2) * r <= b[1],
    t(a2) %*% x_c + p_norm(a2, 2) * r <= b[2],
    t(a3) %*% x_c + p_norm(a3, 2) * r <= b[3],
    t(a4) %*% x_c + p_norm(a4, 2) * r <= b[4]
)
p <- Problem(obj, constraints)

All that remains is to solve the problem and read off the solution.

result <- solve(p)
radius <- result$getValue(r)
center <- result$getValue(x_c)
cat(sprintf("The radius is %0.5f for an area %0.5f\n", radius, pi * radius^2))    

## The radius is 0.44721 for an area 0.62832

A Plot

ggplot() +
    geom_abline(slope = -a1[1] / a1[2], intercept = b[1] / a1[2]) +
    geom_abline(slope = -a2[1] / a2[2], intercept = b[2] / a2[2]) +
    geom_abline(slope = -a3[1] / a3[2], intercept = b[3] / a3[2]) +
    geom_abline(slope = -a4[1] / a4[2], intercept = b[4] / a4[2]) +
    geom_circle(mapping = aes(x0 = center[1], y0 = center[2], r = radius), color = "blue") +
    geom_point(mapping = aes(x = center[1], y = center[2]), color = "red", size = 2) +
    geom_line(mapping = aes(x = c(center[1], center[1] - radius), y = c(center[2], center[2])),
              arrow = arrow(length = unit(0.03, "npc"), ends = "first", type = "closed"),
              color = "brown") +
    annotate("text", x = -0.2, y = 0.04, label = sprintf("r = %0.5f", radius)) +
    labs(x = "x", y = "y") +
    xlim(-1, 1) + ylim(-1, 1)

Session Info

sessionInfo()

## R version 4.0.2 (2020-06-22)
## Platform: x86_64-apple-darwin19.5.0 (64-bit)
## Running under: macOS Catalina 10.15.7
## 
## Matrix products: default
## BLAS/LAPACK: /usr/local/Cellar/openblas/0.3.10_1/lib/libopenblasp-r0.3.10.dylib
## 
## locale:
## [1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
## 
## attached base packages:
## [1] stats     graphics  grDevices datasets  utils     methods   base     
## 
## other attached packages:
## [1] ggforce_0.3.2 ggplot2_3.3.2 CVXR_1.0-9   
## 
## loaded via a namespace (and not attached):
##  [1] tidyselect_1.1.0 xfun_0.15        slam_0.1-47      purrr_0.3.4     
##  [5] lattice_0.20-41  Rmosek_9.2.3     colorspace_1.4-1 vctrs_0.3.2     
##  [9] generics_0.0.2   htmltools_0.5.0  yaml_2.2.1       gmp_0.6-0       
## [13] rlang_0.4.7      pillar_1.4.6     glue_1.4.1       Rmpfr_0.8-1     
## [17] withr_2.2.0      Rcplex_0.3-3     tweenr_1.0.1     bit64_0.9-7     
## [21] lifecycle_0.2.0  stringr_1.4.0    munsell_0.5.0    blogdown_0.19   
## [25] gtable_0.3.0     gurobi_9.0.3.1   codetools_0.2-16 evaluate_0.14   
## [29] labeling_0.3     knitr_1.28       cccp_0.2-4       Rcpp_1.0.5      
## [33] scales_1.1.1     osqp_0.6.0.3     farver_2.0.3     bit_1.1-15.2    
## [37] digest_0.6.25    stringi_1.4.6    bookdown_0.19    dplyr_1.0.0     
## [41] polyclip_1.10-0  grid_4.0.2       Rglpk_0.6-4      tools_4.0.2     
## [45] magrittr_1.5     tibble_3.0.3     crayon_1.3.4     pkgconfig_2.0.3 
## [49] ellipsis_0.3.1   MASS_7.3-51.6    rcbc_0.1.0.9001  Matrix_1.2-18   
## [53] assertthat_0.2.1 rmarkdown_2.3    R6_2.4.1         compiler_4.0.2

Source

R Markdown