2
$\begingroup$

What is the quickest way to find a point inside a linear feasible space? (Defined by the intersection of several hyperplanes and halfspaces). I want to be able to choose an initial point in the original convex space, discover a certain neighborhood around it (not convex but can be written as the union of some convex spaces defined by by the intersection of several halfspaces) using a procedure that depends on the point I have, and then I need to choose another point in the original space but not in the neighborhood already explored. I need to keep doing that until the space is exhausted (It should be exhausted eventually). Basically, I have a convex space $S$, I need loop until $S=\phi$ while doing the following: Choose $x\in S$, Find $N$ around $x$, and then $S \leftarrow S - N$ Any help is appreciated.

$\endgroup$
4
$\begingroup$

Finding a single feasible point is traditionally done by phase 1 of the simplex algorithm.

http://en.wikipedia.org/wiki/Simplex_algorithm#Finding_an_initial_canonical_tableau

This means that you can do it by calling any routine for linear programming, just by putting the objective function to zero.

Covering the feasible domain by balls of fixed radius $r$ whose midpoints are feasible is much harder, though, as exccluding a ball constitutes a nonconvex domain. There are algorithms for enumerating all vertices of a bounded polyhedron given by equations and inequalities (their number typically grows exponentially with the dimension, though). After having all vertices, the feasible set consists just of their convex combinations, so this can be used to samle inside. But unless the polyhedron is a simplex, different convex combinations may give the same point, so one would need to add a reject facility when generating a minimal covering.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much for you reply. As for the first step, this seems to work fine and my LP solver (MOSEK) is working fast with zero objective function. For the second part, It is still confusing for me. The thing is, after choosing the first point, I discover a neighborhood around the point which can be described by a set of $n$ linear inequalities say $Ax \leq b$. As you said, the rest of the space is not convex anymore. One way would be to solve $n$ linear programs each of which have the initial space as a constraint and one of the inequalities of $Ax\leq b$ inverted. Is there a faster way? $\endgroup$ – Fawaz Jun 25 '12 at 15:54
  • 1
    $\begingroup$ @Fawaz: Your way for the second part is wrong. If you reverse one of your inequalities, you get a completely different problem. (Look at the simple set of inequalities $x\ge -1$ and $x\le 1$ to see that.) You'd need to add for each point $x_i$ discovered an inequality $\|x-x_i\|_2^2\ge \delta$. MOSEK will probably cope with the first few, but after a while it will be more and more difficult - and slower - to fill the gaps, and MOSEK will probably return infeasible apthough there are still feasible points not covered. The only reliable metyhod I know for covering is the one I described. $\endgroup$ – Arnold Neumaier Jun 25 '12 at 16:06
1
$\begingroup$

There is a software called PORTA that can enumerate all the points that are feasible in a set of linear inequalities and equalities.

http://www.iwr.uni-heidelberg.de/groups/comopt/software/PORTA/

enjoy it!

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Welcome to SciComp! Could you elaborate a bit on this? From the linked webpage, it looks like PORTA only enumerates the integral feasible points, of which there might be none even if the feasible set is nonempty. $\endgroup$ – Christian Clason Apr 8 '13 at 16:51

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.