examples/chebyshevcenter.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Computes the [Chebyshev center](https://en.wikipedia.org/wiki/Chebyshev_center) of a polyhedron.\n",
    "The example is inspired from [here](http://web.cvxr.com/cvx/examples/cvxbook/Ch04_cvx_opt_probs/html/chebyshev_center_2D.html).\n",
    "The polyhedron is defined by the following inequalities:\n",
    "\\begin{align*}\n",
    "2x + y & \\leq 1\\\\\n",
    "2x - y & \\leq 1\\\\\n",
    "-x +2y & \\leq 1\\\\\n",
    "-x -2y & \\leq 1\n",
    "\\end{align*}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "H-representation Polyhedra.Intersection{Int64,Array{Int64,1},Int64}:\n",
       "4-element iterator of HalfSpace{Int64,Array{Int64,1}}:\n",
       " HalfSpace([2, 1], 1)\n",
       " HalfSpace([2, -1], 1)\n",
       " HalfSpace([-1, 2], 1)\n",
       " HalfSpace([-1, -2], 1)"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using Polyhedra\n",
    "h = HalfSpace([2, 1], 1) ∩ HalfSpace([2, -1], 1) ∩ HalfSpace([-1, 2], 1) ∩ HalfSpace([-1, -2], 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([0.0, 0.0], 0.4472135954999579)"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "using GLPK\n",
    "using JuMP\n",
    "cheby_center, cheby_radius = chebyshevcenter(h, with_optimizer(GLPK.Optimizer))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "using Plots"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/svg+xml": [
       "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n",
       "<svg xmlns=\"http://www.w3.org/2000/svg\" xmlns:xlink=\"http://www.w3.org/1999/xlink\" width=\"600\" height=\"400\" viewBox=\"0 0 2400 1600\">\n",
       "<defs>\n",
       "  <clipPath id=\"clip2800\">\n",
       "    <rect x=\"0\" y=\"0\" width=\"2400\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip2800)\" points=\"\n",
       "0,1600 2400,1600 2400,0 0,0 \n",
       "  \" fill=\"#ffffff\" fill-rule=\"evenodd\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip2801\">\n",
       "    <rect x=\"480\" y=\"0\" width=\"1681\" height=\"1600\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polygon clip-path=\"url(#clip2800)\" points=\"\n",
       "358.619,1503.47 2178.91,1503.47 2178.91,47.2441 358.619,47.2441 \n",
       "  \" fill=\"#ffffff\" fill-rule=\"evenodd\" fill-opacity=\"1\"/>\n",
       "<defs>\n",
       "  <clipPath id=\"clip2802\">\n",
       "    <rect x=\"358\" y=\"47\" width=\"1821\" height=\"1457\"/>\n",
       "  </clipPath>\n",
       "</defs>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  524.62,1503.47 524.62,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  868.071,1503.47 868.071,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1211.52,1503.47 1211.52,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1554.97,1503.47 1554.97,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  1898.42,1503.47 1898.42,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  358.619,1347.78 2178.91,1347.78 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  358.619,1061.57 2178.91,1061.57 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  358.619,775.359 2178.91,775.359 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  358.619,489.151 2178.91,489.151 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:2; stroke-opacity:0.1; fill:none\" points=\"\n",
       "  358.619,202.942 2178.91,202.942 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,1503.47 2178.91,1503.47 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,1503.47 358.619,47.2441 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  524.62,1503.47 524.62,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  868.071,1503.47 868.071,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1211.52,1503.47 1211.52,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1554.97,1503.47 1554.97,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  1898.42,1503.47 1898.42,1481.63 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,1347.78 385.923,1347.78 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,1061.57 385.923,1061.57 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,775.359 385.923,775.359 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,489.151 385.923,489.151 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2800)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  358.619,202.942 385.923,202.942 \n",
       "  \"/>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:middle;\" transform=\"rotate(0, 524.62, 1557.47)\" x=\"524.62\" y=\"1557.47\">-0.9</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:middle;\" transform=\"rotate(0, 868.071, 1557.47)\" x=\"868.071\" y=\"1557.47\">-0.6</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:middle;\" transform=\"rotate(0, 1211.52, 1557.47)\" x=\"1211.52\" y=\"1557.47\">-0.3</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:middle;\" transform=\"rotate(0, 1554.97, 1557.47)\" x=\"1554.97\" y=\"1557.47\">0.0</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:middle;\" transform=\"rotate(0, 1898.42, 1557.47)\" x=\"1898.42\" y=\"1557.47\">0.3</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:end;\" transform=\"rotate(0, 334.619, 1365.28)\" x=\"334.619\" y=\"1365.28\">-0.50</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:end;\" transform=\"rotate(0, 334.619, 1079.07)\" x=\"334.619\" y=\"1079.07\">-0.25</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:end;\" transform=\"rotate(0, 334.619, 792.859)\" x=\"334.619\" y=\"792.859\">0.00</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:end;\" transform=\"rotate(0, 334.619, 506.651)\" x=\"334.619\" y=\"506.651\">0.25</text>\n",
       "</g>\n",
       "<g clip-path=\"url(#clip2800)\">\n",
       "<text style=\"fill:#000000; fill-opacity:1; font-family:Arial,Helvetica Neue,Helvetica,sans-serif; font-size:48px; text-anchor:end;\" transform=\"rotate(0, 334.619, 220.442)\" x=\"334.619\" y=\"220.442\">0.50</text>\n",
       "</g>\n",
       "<polygon clip-path=\"url(#clip2802)\" points=\"\n",
       "410.137,775.359 1783.94,88.4582 2127.39,775.359 1783.94,1462.26 410.137,775.359 410.137,775.359 \n",
       "  \" fill=\"#009af9\" fill-rule=\"evenodd\" fill-opacity=\"1\"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#000000; stroke-width:4; stroke-opacity:1; fill:none\" points=\"\n",
       "  410.137,775.359 1783.94,88.4582 2127.39,775.359 1783.94,1462.26 410.137,775.359 \n",
       "  \"/>\n",
       "<polyline clip-path=\"url(#clip2802)\" style=\"stroke:#e26f46; stroke-width:16; stroke-opacity:1; fill:none\" points=\"\n",
       "  2066.96,775.359 2065.93,742.887 2062.84,710.546 2057.71,678.465 2050.55,646.775 2041.4,615.603 2030.28,585.073 2017.26,555.31 2002.37,526.434 1985.68,498.559 \n",
       "  1967.26,471.799 1947.18,446.261 1925.51,422.049 1902.36,399.259 1877.81,377.983 1851.95,358.308 1824.9,340.312 1796.77,324.068 1767.66,309.641 1737.69,297.089 \n",
       "  1706.99,286.463 1675.68,277.806 1643.88,271.152 1611.72,266.528 1579.33,263.953 1546.85,263.438 1514.4,264.984 1482.11,268.585 1450.11,274.226 1418.54,281.886 \n",
       "  1387.52,291.532 1357.17,303.127 1327.62,316.623 1298.98,331.967 1271.37,349.095 1244.91,367.941 1219.69,388.426 1195.83,410.47 1173.41,433.983 1152.52,458.871 \n",
       "  1133.26,485.033 1115.7,512.364 1099.9,540.754 1085.94,570.089 1073.86,600.25 1063.73,631.116 1055.57,662.564 1049.42,694.465 1045.3,726.692 1043.24,759.115 \n",
       "  1043.24,791.604 1045.3,824.027 1049.42,856.254 1055.57,888.155 1063.73,919.603 1073.86,950.469 1085.94,980.63 1099.9,1009.96 1115.7,1038.36 1133.26,1065.69 \n",
       "  1152.52,1091.85 1173.41,1116.74 1195.83,1140.25 1219.69,1162.29 1244.91,1182.78 1271.37,1201.62 1298.98,1218.75 1327.62,1234.1 1357.17,1247.59 1387.52,1259.19 \n",
       "  1418.54,1268.83 1450.11,1276.49 1482.11,1282.13 1514.4,1285.74 1546.85,1287.28 1579.33,1286.77 1611.72,1284.19 1643.88,1279.57 1675.68,1272.91 1706.99,1264.26 \n",
       "  1737.69,1253.63 1767.66,1241.08 1796.77,1226.65 1824.9,1210.41 1851.95,1192.41 1877.81,1172.74 1902.36,1151.46 1925.51,1128.67 1947.18,1104.46 1967.26,1078.92 \n",
       "  1985.68,1052.16 2002.37,1024.29 2017.26,995.408 2030.28,965.645 2041.4,935.116 2050.55,903.944 2057.71,872.253 2062.84,840.173 2065.93,807.832 2066.96,775.359 \n",
       "  \n",
       "  \"/>\n",
       "<circle clip-path=\"url(#clip2802)\" style=\"fill:#000000; stroke:none; fill-opacity:1\" cx=\"1554.97\" cy=\"775.359\" r=\"18\"/>\n",
       "<circle clip-path=\"url(#clip2802)\" style=\"fill:#3da44d; stroke:none; fill-opacity:1\" cx=\"1554.97\" cy=\"775.359\" r=\"14\"/>\n",
       "</svg>\n"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "plot(polyhedron(h), axis_ratio=:equal)\n",
    "α = range(0, stop=2π, length=100)\n",
    "x = cheby_center[1] .+ cheby_radius .* cos.(α)\n",
    "y = cheby_center[2] .+ cheby_radius .* sin.(α)\n",
    "plot!(x, y, linewidth=4)\n",
    "scatter!([cheby_center[1]], [cheby_center[2]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.0.3",
   "language": "julia",
   "name": "julia-1.0"
  },
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.0.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}