# Chebyshev center of a polyhedron: nonnegativity issue

Let us have a polyhedron, defined by the inequalities of the form: $$\mathcal{P} = \{ x \ | \ a_i^T x \leq b_i, \ i=1,\ldots,m \}$$

Here on page 19, the way to calculate Chebyshev center is given by the following linear optimization problem: $$\max \ r \\ s.t. \ a_i^Tx + r||a_i||_2 \leq b_i \quad \forall i \in [m]$$

This is very intuitive and easy to understand. What I don't understand is, when we have $$x \in \mathbb{R}^n_{+}$$, i.e., nonnegative optimization variables. There are two different ways:

1. adding new constraints $$a_j^Tx \leq 0$$ for $$j = 1,\ldots,n$$ to the original inequalities where $$a_j$$ is the minus $$j$$-th basis vector.
2. keeping the optimization problem above, adding $$x \geq \mathbf{0}$$ as a new constraint

These ways end up different radii. The second one has a bigger one. When you go for the first option, instead of $$x_j \geq 0$$, you add $$x_j \geq r$$ and force each variable to be at least as big as the radius.

Does this imply the first one is a better option? Am I doing something wrong in the second step? If I am doing right, why aren't these equivalents?

Edit: I think the correct one should be option 1. The second one does not make a full sphere. So, we should include $$x \geq 0$$ hyperplanes as constraints since that's the only option to have an inscribed ball..

• Obviously the second one is calculating something else not Chebyshev center. Your two models are not equivalent . What are some aplication of Chebyshev center? – Red shoes Apr 24 at 17:57

If you have non-negativity constraints on $$x$$, you simply include those among all other constraints, as in (1). They are constraints like any other constraint.