# How to find an extreme feasible point in a linear polytope (set $\{x : Ax \leq b\}$ defined by halfspaces)?

The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $$H$$-polytope) and is defined as the intersection of a finite number of halfspaces.

The simplex method for the linear program optimizes over a polytope

$$\begin{array}{ll} \min_{x\in \mathbb R^n} &c^Tx\\ \mathrm{s.t.} & Ax \leq b \end{array}$$

and initializes by finding an extreme point, e.g $$\bar x$$ where $$A\bar x \leq b$$, and $$A_I\bar x = b_I$$ for a set of row indices $$I$$ of length $$n$$, and $$A_I$$ is invertible.

Suppose that such an $$A_I$$ exists. Are there any systematic or commonly accepted ways of finding an extreme feasible point? Even if it's a crappy way, are there any ways that are used in practice? I found many references on how to proceed once the feasible point is found, but not how to pick it to begin with.

Thank you!

• I updated the title to include the definition, but a linear polytope is just the set of vectors $x$ satisfying the constraint $Ax \leq b$. – Y. S. Mar 2 at 17:47
• I would call that an $\mathcal H$-polytope, since it's defined by the intersection of half-spaces. This is standard terminology. – Rodrigo de Azevedo Mar 2 at 18:40
• Ok, I added a clarification in the question description. – Y. S. Mar 2 at 21:19

A common approach is to introduce slack variables $$s$$, i.e., $$Ax + s = b$$. Define $$s = s^+ - s^-$$ with $$s^+ \geq 0$$ and $$s^- \geq 0.$$ And consider for objective function $$\min_{s,x} 1^Ts^-$$. In other words, solve
$$\begin{array}{ll} \min_{s, x} & 1^T s^-\\ \mathrm{s.t.} & Ax + s= b\\ & s = s^+ - s^-\\ & s^+, s^- \geq 0\\ \end{array}$$
Then, $$s = b$$ with $$x = 0$$ is a solution for that particular problem. Now, if the optimal value is $$0$$, then $$s^- = 0$$, hence the corresponding $$x$$ verifies $$Ax \leq b$$, and therefore is a solution to your original problem. If the optimal value is not $$0$$, then your original problem is not feasible.