Exercise 1.12 (Chebychev center)

Practically, we are looking at the following optimization problem

(This may look weird at first glance, as we are optimizing over variables $r$ and $x$, and the latter has the coefficient equal to zero in the cost function.) This formulation is not quite linear; we try to formulate $B(x,r)\subseteq P$ using the language of linear constraints.

• First, we consider a simpler problem of reformulating $B(x,r)\subseteq \{a^{\prime }y\le b\}$ - i.e., our polyhedron only has one restriction and is thus a hyperplane. Notice that we can write

  $$B\left(x,r\right)=\left\{x+v\mid \parallel v\parallel =r\right\}.$$

  Using this, we obtain

  $$\begin{array}{cc}\hfill & B\left(x,r\right)\subseteq \{x\in {\Re }^n\mid y\in {\Re }^n\mid a^{\prime }y\le b\}\hfill \\ \\ \hfill & ⟺\forall <!--\; FUNCTION\; APPLICATION\; -->y\in B\left(x,r\right):a^{\prime }y\le b\hfill \\ \\ \hfill & ⟺\forall <!--\; FUNCTION\; APPLICATION\; -->v\in {\Re }^n,\parallel v\parallel =r:a^{\prime }\left(x+v\right)\le b\hfill \\ \\ \hfill & ⟺\underset{\{v\in {\Re }^n,\parallel v\parallel =r\}}{\sup <!--\; FUNCTION\; APPLICATION\; -->}{a}^{\prime }\left(x+v\right)\le b\hfill \\ \\ \hfill & ⟺a^{\prime }x+\underset{\{v\in {\Re }^n,\parallel v\parallel =r\}}{\sup <!--\; FUNCTION\; APPLICATION\; -->}{a}^{\prime }v\le b\hfill \\ \\ \hfill & ⟺a^{\prime }x+\parallel a\parallel r\le b\hfill \end{array}$$

  where in the last step we have used the Cauchy-Schwarz inequality.

• Now consider the constraint $B(x,r)\subseteq \left\{y\in {\Re }^n\mid a_i^{\prime }y\le b_i,i=1,\dots ,m\right\}$. Repeating the steps above, we obtain an equivalent formulation

  $$a_i^{\prime }x+\parallel a_i\parallel r\le b_{i}i=1,\dots ,m.$$

Rewriting the constraints as explained above, we obtain a linear optimization problem