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:
- 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.
- 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..
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.