2
$\begingroup$

I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop as soon as the system becomes infeasible. Basically this:

class LPSolver {
    // add constraint ax + by + cz + d < 0 (plane equation), and return false if infeasible
    bool add_constraint(int a, int b, int c, int d);
};

Coefficients a, b, c, d happen to be integers and x, y, z are true reals (computing x, y, z is not required and even undesirable to avoid numerical error).

From thinking about the problem, I have figured out that at most 3 constraints are required to show infeasibility. This seems to point to a solution where the class should keep track of 3 constraints or planes, whose intersection point is in the feasible space. When a new constraint is added, the fast path is that this point (intersection of 3 planes) satisfies the new constraint, in which case nothing needs to be done and we keep track of the same 3 constraints. Otherwise, we need to recompute the constraints. The new constraint just added is definitely one of the 3 constraints to track, and we need to search for the other two, but this seems to require quite a bit of cleverness to avoid exhaustive search.

This seems to be an interesting problem and I would like to implement a solution myself rather than using a library, but I don't have formal training in convex optimization so I'm looking for a reference implementation, pseudo code or a research paper.

Improve this question
$\endgroup$
4
  • $\begingroup$ There's a lot of material out there on linear programming and specifically the simplex algorithm. $\endgroup$ – Yuval Filmus Sep 25 '18 at 21:05
  • $\begingroup$ What exactly is your question? I don't see a question, just a series of declarative sentences. Guessing at what your idea seems to be, you seem to think it's sufficient to track only three of the constraints seen so far. It's easy to come up with examples where it seems necessary to remember all the constraints. $\endgroup$ – D.W.♦ Sep 26 '18 at 8:49
  • $\begingroup$ I think tracking three constraints enables a fast path (if the point defined by the intersection of three past constraints is still feasible when you add a new constraint, then you can return true immediately). I don't think it's enough for the slow path as you pointed out. $\endgroup$ – Giovanni Funchal Sep 26 '18 at 9:43
  • $\begingroup$ My question is asking for a reference to an implementation or a paper which discusses this problem in detail. The literature in convex optimisation is very vast and hard to navigate for someone new to the domain. $\endgroup$ – Giovanni Funchal Sep 26 '18 at 9:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.