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.2.1 (2022-06-23)
## Platform: x86_64-apple-darwin21.6.0 (64-bit)
## Running under: macOS Ventura 13.0
##
## Matrix products: default
## BLAS: /usr/local/Cellar/openblas/0.3.21/lib/libopenblasp-r0.3.21.dylib
## LAPACK: /usr/local/Cellar/r/4.2.1_4/lib/R/lib/libRlapack.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.4.1 ggplot2_3.3.6 CVXR_1.0-11
##
## loaded via a namespace (and not attached):
## [1] tidyselect_1.2.0 xfun_0.34 bslib_0.4.0 slam_0.1-50
## [5] lattice_0.20-45 Rmosek_10.0.25 colorspace_2.0-3 vctrs_0.5.0
## [9] generics_0.1.3 htmltools_0.5.3 yaml_2.3.6 gmp_0.6-6
## [13] utf8_1.2.2 rlang_1.0.6 jquerylib_0.1.4 pillar_1.8.1
## [17] glue_1.6.2 Rmpfr_0.8-9 withr_2.5.0 DBI_1.1.3
## [21] Rcplex_0.3-5 tweenr_2.0.2 bit64_4.0.5 lifecycle_1.0.3
## [25] stringr_1.4.1 munsell_0.5.0 blogdown_1.13 gtable_0.3.1
## [29] gurobi_9.5-2 codetools_0.2-18 evaluate_0.17 labeling_0.4.2
## [33] knitr_1.40 fastmap_1.1.0 cccp_0.2-9 fansi_1.0.3
## [37] highr_0.9 Rcpp_1.0.9 scales_1.2.1 cachem_1.0.6
## [41] osqp_0.6.0.5 jsonlite_1.8.3 farver_2.1.1 bit_4.0.4
## [45] digest_0.6.30 stringi_1.7.8 bookdown_0.29 dplyr_1.0.10
## [49] Rglpk_0.6-4 polyclip_1.10-4 grid_4.2.1 cli_3.4.1
## [53] tools_4.2.1 magrittr_2.0.3 sass_0.4.2 tibble_3.1.8
## [57] pkgconfig_2.0.3 rcbc_0.1.0.9001 MASS_7.3-58.1 Matrix_1.5-1
## [61] assertthat_0.2.1 rmarkdown_2.17 R6_2.5.1 compiler_4.2.1
Source
References
Boyd, S., and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.