Computing the Chebyshev center of a V-representation polyhedral cone

236 Views Asked by At

I'd like to compute the Chebyshev center of a convex polyhedral cone (restricting the center to be inside the unit hypercube).

Given a polyhedral cone in H-representation (linear inequalities $\mathbf{A}x\leq 0$), the Chebyshev center can be easily computed by a linear program.

However, I only have the V-representation of the cone:

$$ \{ x \ | \ x=\mathbf{C} \mathbf{\lambda}, \ \mathbf{\lambda}_i \geq 0 \ \ \forall i \} $$

The issue is that for my problem, $x\in \mathbb{R}^{84}$ and $\mathbf{C}$ has dimension $84 \times 162$. I think the facet enumeration problem of converting from V- to H- representation is too expensive because the cone is in a high dimensional space. Is there a way to compute the Chebyshev center directly from the V- representation?