2
$\begingroup$

How can one create a random bounded polytope in MATLAB, specified by the conditions $‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎$

$\endgroup$
2
  • $\begingroup$ I think this has been done and made public in the MATLOG toolbox using the Milp class and methods mp.addcstr( ), mp.addlb( ), mp.addub( ), and mp.addctype( ). Example included at link. Can add as answer if you find this helpful. Disclosure: I am not the author. $\endgroup$ Commented Jun 12 at 23:46
  • $\begingroup$ Why does this have a julia tag? Just curious. In julia, just use the JuMP package. $\endgroup$ Commented Jun 12 at 23:47

1 Answer 1

1
$\begingroup$

I don't use MATLAB, but the following should be straightforward to implement. I am going to assume that you start knowing the dimension $n$ of $x.$

The first step is to partition $n$ randomly into $n_1+n_2$ where $n_1$ will be the number of "natural" variables and $n_2$ the number of slack variables (and hence also the number of constraints). We will randomly generate the components of $\hat{A} \hat{x} \le b$ where $\hat{x}\in \mathbb{R}^{n_1}_+.$ Add slack variables to $\hat{x}$ to get $x$ and an identity matrix to $\hat{A}$ to get $A.$

Next, to ensure feasibility, randomly generate a vector $\hat{x}_0 \ge 0$ of dimension $n_1.$ We will ensure that $\hat{x}_0$ (extended by slack values) is contained in the polytope.

Now generate a random vector of dimension $n_1$ with strictly positive components. Call it $\hat{a}.$ Make it the first row of $\hat{A}.$ Compute $\hat{a}'\hat{x}_0$ and set $b_1$ to something larger than that. This will ensure boundedness. If the polynomial were unbounded, there would be a nonzero direction vector $d$ such that $\hat{x}_0 + \alpha d \ge 0$ and $\hat{a}'\left(\hat{x}_0 + \alpha d\right) \le b_1$ for all $\alpha > 0.$ The first inequality requires $d \ge 0.$ Given $d\ge 0$ and $d\neq 0,$ $\hat{a}'d > 0,$ and so the second inequality cannot hold for all $\alpha > 0.$

All that is left is to generate $n_2 - 1$ random vectors of dimension $n_1$ (with no conditions attached) and add them as rows of $\hat{A},$ randomly generate the remaining values of $b$ so that $\hat{A} \hat{x}_0 \le b,$ and then add in the slack columns.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.