[Python] Python script for picking a randomly selected point that satisfies some linear...

I want to make a python script, which takes in a list of inequalities as input.

Each inequality is a list: [c0, c1, ..., cn] which represents the following: c0 + c1x1 + c2x2 + ...+ cnxn ≤ 0

I want it to output a randomly selected point that satisfies all the inequalities.

n is variable but it should normally be around 10. There should normally be about 60 inequalities.

I also know that the polytope formed by the inequalities is contained in the unit hypercube (i.e. we can assume all components of the random point are between 0 and 1 inclusive).

I tried sampling random points in the hypercube and checking them against the inequalities (see code below), but this is very inefficient as I'd have to sample so many points before the program would get one that satisfies all the inequalities.

def random_point_in_unit_cube(n):
return [random.random() for i in range(n)]

def satisfies_inequalities(point, inequalities):
for inequality in inequalities:
c0 = inequality[0]
coefficients = inequality[1:]
lhs = c0 + sum(c * x for c, x in zip(coefficients, point))
if lhs > 0:
return False
return True

def random_point_satisfying_inequalities(n, inequalities):
point = random_point_in_unit_cube(n)
print(point, inequalities)
while not satisfies_inequalities(point, inequalities):
point = random_point_in_unit_cube(n)


When I call the function random_point_satisfying_inequalities, it takes a long time to generate a point. Does anyone know a way I can make it faster?

Continue reading...