given a set of linear inequalities (and equalities) I want to find a bounding fox for it. There is an obvious straightforward solution, but I hope it is possible to convert the whole problem to one linear programming problem. I'd like to give you an example so you could understand what I need. Consider this triangle: {-y + x - 3 >= 0, y - 2 x + 8 >= 0, y + 3 x - 7 >= 0}:
I've drawn red box, indicating solution of the problem, two circles are coordinates of the solution ((x1,y1),(x2,y2)).
Straightforward way would be solving linear programming problem for each dimension, X and Y in this case, twice to find minimum and maximum, like this (you can see that it has found left X bound, 2.5, correctly):
However when there are N dimensions, it will be expensive to run N calculations in my case. My hope is that it possible to reformulate this problem as maximisation of volume of the bounding rectangle, i.e. x2-x1+y2-y1 in this case, and converting inequalities to linear equalities with the bounds for the new variables:
So I can still correctly find left bound in this slightly reformulated problem, but now, I need somehow to reformulate it as maximisation of the bounding box and not really know how to do it, also I don't know if it is possible to do it like that. In this case I have 10 variables for the new linear programming problem: x1,x2,y1,y2,p1,p2,q1,q2,r1,r2, but I don't know how to rewrite these equations for x,y,p,q,r as (in)equations for (x1,x2,y1,y2,p1,p2,q1,q2,r1,r2), since as, for example, point (x1,y1,p1,q1,r1) does not necessarily lies on this linear hyperspace.
In this approach I need essentially to intersect a rectangle ((-∞,∞),(-∞,∞),(0,∞),(0,∞),(0,∞)) with a linear subspace {-3-p+x-y=0,y-2x+8-q=0,y+3x-7-r=0}, so my question is how to do it, and if its even possible by solving just one LP problem?
I don't think your proposed approach works, and I don't understand why you think it will be more efficient than the naive algorithm.
I am not aware of any algorithm that is more efficient than running linear programming $2N$ times.