If we are given a three-dimensional polyhedron $P \subset \mathbb{R}^3$ defined by $m$ linear inequalities: $$P = \{\textbf{x} \in \mathbb{R}^3\ |\ A\textbf{x} \leq \textbf{b}\}$$ where we let $\textbf{a}_i^T $ denote the $i^{th}$ row of $A$, then the $i^{th}$ linear inequality can be written as $\textbf{a}_i^T\textbf{x} \leq b_i$ or $$a_{i,1}x_1 + a_{i,2}x_2 + a_{i,3}x_3 \leq b_i$$ Given the task of finding the largest sphere $S$ that fits inside $P$, we must determine its radius $r$, and the coordinates of its center, $\textbf{c}^T = (c_1,c_2,c_3)$.
a. Formulate a linear program that could be used to solve this problem
Answer:
$ \begin{array}{l*{6}{r}lr} \mbox{Maximize}\hspace{10pt}\ & r \\ \mbox{Subject to}\hspace{10pt}\ & r & \leq & \dfrac{b_i - \textbf{a}_i^T\textbf{c}}{\lVert \textbf{a}_i \rVert} & (\mbox{for } i = 1,2,...,m)\\ ~ & r & \geq 0 \end{array}$
b. Form the dual
I have done part a, I am just having trouble forming the dual. Any help would be great, thanks!
