Dense solution set
Can Gurobi encode this problem?
$Ax + B \leq 0$ and $\forall x'. |x' - x| \leq \delta \implies Ax' + B \leq 0$.
Basically I am trying to find a $\delta$-diameter dense region of the feasible set instead of a single solution point from the feasible set.
-
What do you mean by
|x' - x| \leq \delta ?
Are you comparing x and x' just component by component --meaning, you are looking for the largest L1-ball that can fit inside a polyhedron-- or are you comparing these with respect to Euclidean norm? The two problems are very different, and in the former case there is a very nice modelling approach.
-
With L1 norm in mind, I think one can give a nice compact formulation to this problem. But please take it with a grain of salt, so to speak, as I did not test it, and read and check things carefully. So, no guarantees, but I will give this a try:)
I will describe something a bit different first, from which move to your formulation.
1) Assume, in addition that 0\in \{x\in\Re^n: Ax \leq b\}.
Suppose you want to determine the largest volume of a centrally-symmetric rectangular box (with faces parallel to coordinate planes) that fits inside a polytope \{x: Ax \leq b\} (that contains the origin). Since the box has faces parallel to the coordinate planes, you can effectively describe it by a vector of numbers r_j --displacement from 0-- in each direction j, j = 1 through n.
Now, in principle you would have to check that every vertex of the box, with coordinates + or -r_j, is within the polytope, i.e., satisfies Ax \leq b; this is a lot of constraints (2^n, in fact).
Fortunately though, you only need to check "the worst case" scenario for each of the constraint, namely, noting that for each constraint i the worst case situation amounts to
(*) \sum_j abs( A_{i,j} ) r_j \leq b
as the vertex coordinates take on values plus or minus r_j as you go through all the vertices of the box.
S, to get the max-volume centrally symmetric box you need to maximize the product of r_j variables (equivalent to the sum of the logs, which is convex), subject to the set of constraints (*) above.
2) Note if you want just a max-volume cube in the above, all r_j are the same, i.e., you would use a single scalar variable r instead.
Now, lets drop the assumption that 0\in \{x\in\Re^n: Ax \leq b\}. We can "centre" the polytope around some feasible point c (assuming such point exists), i.e.,
(**) A c \leq b
and furthermore, drawing on the reasoning above, re-write the cube containment constraints (writing the box vertex coordinates x_j as c_j plus or minus r_j) as
(***) \sum_j abs( A_{i,j} ) r \leq b - A c
It remains to maximize r subject to (***).
I think this is it.
Hopefully, this helps (and I am not making major mistakes here :)).
-
ps: apparently I was thinking of L-\infintiy norm in
|x' - x| = max_j |x_j - x_j'| \leq \delta
in the above.
If you want the L1 norm, this should be easier, as you only need to check the containment of 2n vertices of the L1 ball of radius r (a "diamond", not a box), where each vertex has only one non-zero --either r or -r at some position j-- and zeros every place else. So, you should augment the sum in (***) accordingly.
Hope this helps.
-
Hey. Thanks for your answer. If I understand correctly, you convert the cube containment conditions to vertex satisfiability. But why only 2n vertices for n-dimension? Shouldn't it be 2^n, because 2 direction (+/-) for each dimensions.
As in if, upper and lower bounds of a box are [2, 2, 2] and [-2, -2, -2] respectively, then there are 2^3 vertices, not 2*3 vertices.
(-2, -2, -2),
(-2, -2, 2),
(-2, 2, -2),
(-2, 2, 2),
(2, -2, -2)
(2, -2, 2)
(2, 2, -2)
(2, 2, 2)
-
For L1 norm you have a unit ball defined by
|x| + |y| + |z| + ... <= 1
with respective vertices
(1;0;0;....), (-1;0;0;...), (0;1;0;0...) etc.giving you 2n vertices in dimension n,
whereas, the L-infinity ball is denied by
max{|x|,|y|,...} <= 1
so this is a standard unit "box" with 2^n vertices.
Depending on which norm you work with, (***) will be different.
Hope this helps.
-
This works for L-infinity norm:
maximize r
subject to
(***) \sum_j abs( A_{i,j} ) r \leq b - A c
Since it is could be a bit tricky to figure out how to avoid checking 2^n vertices, I made it explicit.
In case of L1 norm, you can substitute the vertices yourself as there are only 2n of those.
Hope this helps.
Please sign in to leave a comment.
Comments
7 comments