Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

How to choose an arbitrary point from a polytope defined by system of linear inequalities, Ax < b ? (Here A is an m-by-n matrix, x is n-by-1 and b is m-by-1.) I just want to find one ARBITRARY point that satisfies Ax < b and NOT satisfies Ax = b.

share|improve this question
Keyword: linear programming. –  Boris Bukh Nov 15 '10 at 15:17
Interior-point methods for linear programming give that automatically. –  Warren Schudy Nov 15 '10 at 17:04
Interior-point methods will find the so-called analytic center of the polytope. Or solve the LP "max s such that $Ax + s \le b$" to maximize the slack. –  Warren Schudy Nov 15 '10 at 17:06
the choice of word 'sampling' is unfortunate, although actually sampling from a polytope is an interesting question :). –  Suresh Venkat Nov 17 '10 at 5:55

1 Answer 1

I agree with Boris -- you want to solve an LP. If you would like to solve it numerically, just pose it like this: $$ \begin{align} & \min 0 \\ s.t. \quad & Ax + e\leq b \end{align} $$ where $e \in \mathbb{R}^m$ is a vector containing $\epsilon$'s, which is some numerical tolerance.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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