Consider the problem $$ \text{ Find } y \text{ s.t. } \\ \exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx $$ where $y$ is a $2\times 1$ vector of unknowns, $x$ is a $10\times 1$ vector of unknowns, $A,D,b,c,e$ are matrices and vectors of known values with appropriate dimensions.

My objective is to find (plot) the region of values of $y$ such that $$ \exists \text{ } x \text{ solving} \text{ }Ax\leq b, Dx=e, \text{ and } y=cx $$

Let us call this region $\mathcal{R}$. I would like your help to investigate whether there is a way (with relative algorithm in any language) to reach my objective.

Let me also add that the region $\mathcal{P}\equiv \{x: Ax\leq b, Dx=e\}$ is bounded.

A naive way to go is to:

(1) rewrite the problem as a unique linear programming problem $$ Ax\leq b\\ Dx=e\\ y=cx, $$

(2) find the feasibility region, and

(3) report only the feasible values of $y$.

The problem is that there is no algorithm that allows me to find (plot) the feasibility region of a $12$-dimensional linear programming. The available algorithms (for example, in Matlab) allows me to plot feasibility regions of 3 dimensions at most.

Hence, the question is: is there a simpler way to rewrite my problem in order to reach my objective?

  • $\begingroup$ Let $P = \left\lbrace x \: : \: Ax \leq b \right\rbrace$ denote the polyhedron in your setup. One option is to calculate the set of all extreme points and extreme rays of $P$ (you can maybe hope to do this since $P$ is only ten-dimensional in your case), and then transform them using the matrix $c$ to get a description of the extreme points and extreme rays of the polyhedral region that corresponds to the set of possible $y$ $\endgroup$ – madnessweasley Aug 13 '19 at 18:28
  • $\begingroup$ Thanks. Regarding $P$, do you know any algorithm that calculates the set of all extreme points and extreme rays? I found this in Matlab uk.mathworks.com/matlabcentral/fileexchange/… but it gives me lots of errors and the explanations contained in the code do not help. $\endgroup$ – TEX Aug 13 '19 at 18:48
  • $\begingroup$ I've heard some folks talk about PORTA, but I haven't used it myself. Another option appears to be cddlib $\endgroup$ – madnessweasley Aug 13 '19 at 18:50
  • $\begingroup$ This does not seem to have anything to do with coding-theory. $\endgroup$ – Jyrki Lahtonen Aug 14 '19 at 17:11

As you have noted, this (implicit) feasibility region on $y$ can be formulated as the projection (via $y=cx$) of an explicit feasibility region in $x$. I had to deal with this problem myself recently. One method, as people have commented, is to obtain the vertices from your half-space representation and then project these down; the convex hull of these projected points is the desired feasibility region. For your problem’s size, that’s probably the best way. I suggest using either SageMath’s polyhedral commands or the program ’polymake’ (both accessible online via the CoCalc cloud computation site).

In my case, this route was ultimately impractical for dimensionality reasons. A nice alternative for me, since my projection was to a low-dimensional space, was the convex hull algorithm of Lassez & Lassez (1992): https://www2.cs.duke.edu/donaldlab/Books/SymbolicNumericalComputation/103-119.pdf. For some notes on both vertex enumeration and the convex hull method, see J. Apte’s slides at https://faculty.coe.drexel.edu/jwalsh/JayantCHM.pdf.


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.