[bcmhtlmz] random convex polytope for linear programming

various tasks related to constructing a random D-dimensional linear programming problem:

we want a convex polyhedron (polytope) specified by a set of plane (hyperplane) inequalities (constraints).

for linear programming, sometimes it is OK for the polyhedron not to be closed, to have infinite volume.  but sometimes that will cause the solution to be infinite.  how can we detect an infinite polyhedron?  how can we determine if the solution is unbounded?

origin could be known to be an internal point (feasible).

are there any feasible points?

is a plane useless?  every point on the plane is infeasible.

all planes could be tangent to a sphere, or to an ellipsoid.

ellipsoid: start by constructing tangents to a sphere, then stretch and rotate.  probably need positive definite linear transformation.

hyperboloid and other quadrics could also work.  

plane equations could have all rational coefficients, so not all tangent to a sphere.  or could be: generalization of Pythagorean triples.

pick a random vertex.  might be tough in high dimensions.

given a subset of D plane equations (constraints), determine if their intersection is feasible.

start with a point at the intersection of D plane equations, then walk to an adjacent intersection, trying to move "inward" until reaching a feasible vertex.

pick a random vertex, project to sphere, and construct a tangent plane.  (previously.)

pick a random point on the sphere and construct tangent plane.  this is easy.

don't shave down all the way to tangency with the inscribed sphere, but a parallel plane only part of the way.  let the amount of material removed always be simple: just a pyramid.  is this always the case if maintaining convexity?  if starting from a random vertex, we probably need to know all its neighbor vertices.

pick a set of random points on a sphere and construct planes, but avoid tangent points from being too close to each other: Thomson problem.  does picking tangent points not close to each other tend to avoid vertices close to each other?  is there a better way to avoid vertices close to each other?

pick points from a spherical shell, construct planes perpendicular to the vector to the origin, then remove useless planes.  how thick should the shell be to avoid a lot of useless planes?  probably depends on number of dimensions.

rational points inside a spherical shell.  with rational planes close to being tangent.

if the polyhedron is nearly spherical, finding the maximum vertex might become easy.  if the feasible region is a sphere centered on the origin, the problem is likely very easy.  but in high dimensions, you probably don't have to worry about your polyhedron being too spherical: it probably takes an exponential number of planes to get nearly spherical.

convex hull.  worst case O(n^floor(d/2)) planes for n points, which is prohibitively huge in high dimensions.  should we, could we, avoid worst case?

limit to sparse plane equations: most coefficients are zero.

restrict to the positive (non-negative) quadrant (octant, etc.), i.e., all coordinates must be greater than or equal to zero.  restrict to a cube by requiring all coordinates to be less than or equal to some constant, or to a pyramid with x + y + z <= C.  more general pyramid: all positive coefficients.

we've ignored the objective function until now.  can we construct a random linear program whose solution is known in advance?

in quadratic programming, the maximum might not be at a vertex.  construct problems for which this is the case.  maximum could also be completely internal (probably makes the problem very easy), or on the boundary not at a vertex.

previous thoughts on generating random convex polytopes.