I am currently dealing with a problem where I need to detect all redundant constraints of a convex polytope defined by $\mathcal{P} = \{x\in\mathcal{R}^n: Ax\leq b \wedge Cx = d \}$, basically your standard convex polytope with equality constraints.
I already know the solutions for removing strongly redundant constraints. To check the strong redundancy of the $i^{th}$ constraint, we need to check the following linear program's feasibility. If it is infeasible, then it is strongly redundant.
$$ \min_{x} 0\\ \begin{align*} \text{s.t. } Ax &\leq b\\ A_ix&=b_i\\ Cx &= d \end{align*}$$
However, I am unsure how to identify weakly redundant constraints correctly. My first thought was to check the dimensionality of the polytope defined by $\mathcal{P_i} = \{x\in\mathcal{R}^n: Ax\leq b\wedge C x= d\wedge A_i x = b_i\}$ for each $i^{th}$ constraint.
I am not sure how to proceed. I know for polytopes defined by inequalities only, there is a procedure for eliminating weakly redundant constraints via a Chebyshev ball approach. One method I have thought of was enumerating all vertices of the polytope and checking each facet ( relating to a constraint) intersects at least $n$ vertices. Still, this method suffers from the curse of dimensionality and becomes computationally intractable quickly.
I suspect there is a linear programming formulation that will be much faster.
Any help would be greatly appreciated!
I have figured it out. I am using a Chebychev ball approach. This is fairly performant.
Given a convex polytope defined as above, and assuming that we have already culled all strongly redundant constraints via the method above. we can use the following LP to check for weak degeneracy in the inequality constraints.
$$ \begin{align*} R_i = \max_{x\in\mathcal{R}^n,r\in\mathcal{R}_+}& \quad r\\ \text{s.t. } A_jx & + ||A_j||_2r\leq b_j, \forall j \neq i\\ Cx &= d\\ A_i x &= b_i \end{align*} $$
For each inequality constraint $i$, if $R_i> 0$ then it is not weakly degenerate. This optimization problem is equivalent to the question "What is the largest euclidean ball I can fit inside of my feasible space?". The feasible space will be lower dimensional with a weakly redundant constraint active (a vertex, edge, ect), so the above optimization problem should identify weak redundancy.
I suspect that this can also cull strongly degenerate inequality constraints as it will just be infeasible.