6
$\begingroup$

My question is about a Linear Program (LP) of the form $\bf Ax\ge b$ with $\bf x\ge0$.

From a theoretical standpoint: Given a feasible solution $\mathbf{x^{(0)}}$, how can we check (verify) whether it is an extreme point?

I found this on the web, but I don't know if this is correct.

Can anyone please comment on the above method? Or aware of other methods to check whether a point $\mathbf{x^{(0)}}$ is an extreme point of the LP feasible space?

$\endgroup$

2 Answers 2

4
$\begingroup$

The page you linked is correct. Note that $Ax\ge b$ there includes any nonnegativity constraints, so their $A$ combines your $A$ and an identity matrix.

For a feasible solution $x\in\mathbb{R}^n$ to be an extreme point, there must be at least $n$ bounding hyperplanes of the feasible region that pass through $x$ (meaning at least $n$ constraints, including sign constraints, that are binding at $x$), and $n$ of those hyperplanes must have linearly independent normals. The constraints corresponding to those $n$ hyperplanes are satisfied as equalities (since they are binding) and have rank $n$ (since the constraints intersect only at one point, namely $x$).

$\endgroup$
3
  • $\begingroup$ Thanks.. Yes, my thoughts were similar. At extreme points, for the $n$ bounding constraints, slack variables are 0.. But at non-extreme points, one or more of these slacks kick in (become non-zero), so we need $t$ equations to find the point (since we now need to find the values of $t$ variables) where $t \ge n+1$. $\endgroup$ Oct 30, 2022 at 20:03
  • $\begingroup$ Some relevant publications: (1) Complexity of Linear Programming (Page 6), and (2) Algorithms in Combinatorial Geometry by Edelsbrunner (Ch. 10) where he says "the problem is equivalent to one of determining whether a given half-space of an LP is redundant". $\endgroup$ Oct 31, 2022 at 7:34
  • $\begingroup$ Another thought - Show that there is a vector $D \in \mathbb{R}^n$ such that the objective function $DX = \sum_{j=1}^n d_jx_j$ achieves either a unique maximum or unique minimum at the given point $X^{(0)}$ (among all points in the original LP feasible region). $\endgroup$ Oct 31, 2022 at 10:01
3
$\begingroup$

In

https://scholar.google.com/citations?view_op=view_citation&hl=da&user=kEOeI2gAAAAJ&cstart=20&pagesize=80&citation_for_view=kEOeI2gAAAAJ:KlAtU1dfN6UC

Nimrod Megiddo proves that if you have a primal dual optimal solution you can find an optimal basis solution in strongly polynomial time. A basis solution specifies a vertex solution.

Moreover, unless there is a strongly polynomial algorithm for LP then you really need both a primal and dual optimal solution for that to be true.

Hence, you can use the idea of Megiddo and I doubt that can be improved much since it is strongly polynomial.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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