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

  • $\begingroup$ Obviously the second one is calculating something else not Chebyshev center. Your two models are not equivalent . What are some aplication of Chebyshev center? $\endgroup$ – Red shoes Apr 24 '19 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.