{ "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, 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": [ "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", " \n", " \n", " \n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "\n", "-0.9\n", "\n", "\n", "-0.6\n", "\n", "\n", "-0.3\n", "\n", "\n", "0.0\n", "\n", "\n", "0.3\n", "\n", "\n", "-0.50\n", "\n", "\n", "-0.25\n", "\n", "\n", "0.00\n", "\n", "\n", "0.25\n", "\n", "\n", "0.50\n", "\n", "\n", "\n", "\n", "\n", "\n", "\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 }