Welcome to MathOverflow

Question

1

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.

edited Nov 15 2010 at 15:24

asked Nov 15 2010 at 15:08

Eunsoo Oh
11●1

Keyword: linear programming. – Boris Bukh Nov 15 2010 at 15:17

2

Interior-point methods for linear programming give that automatically. – Warren Schudy Nov 15 2010 at 17:04

2

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 2010 at 17:06

the choice of word 'sampling' is unfortunate, although actually sampling from a polytope is an interesting question :). – Suresh Venkat Nov 17 2010 at 5:55

Gilead · Answer 1 · 2010-11-15 15:55:10Z UTC

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.

Sampling arbitrary point from system of linear inequalities

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

1 Answer

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.