# Characterizing optimal points in a linear program

Suppose I have a linear program of the form

$$\max c^T x$$

$$Ax \le b$$

And some mystical oracle gives me a point $x'$ claiming it is an optimal solution.

How could I determine if this is true, without solving the linear program from scratch.

Now perhaps it is easier if we know ahead of time there is a unique max. Then we can test if $x'$ is an extreme point, and perhaps try to compute all its adjacent vertices and verify it has maximal objective value over them. But this leads to three questions:

1. I said that algorithm at a high level, how do I actually do that?
2. What if we relax the condition to perhaps a non unique max, then we lose out on the extreme point tests etc...

3. Is there an algebraic characterization we can do instead? If I wanted to state all optimal $x'$ satisfy some $f(x',A,c^T,b) = 0$ what would that property be?

The last point (#3) I'm most interested in. I'm curious if we can do an approach involving lagrange multipliers with the inequalities that are tight for the value $x'$ to reason, that there is no direction one can walk that is better. This would be useful for example in proofs where we say

Given $x'$ is optimal prove some statement $\phi(x',A,b,c^T)$.

Then knowing this property of $x'$ gives you an equation to work with to manipulate to conclude $\phi$

• The statement "without solving the linear program from scratch" is a little ambiguous. For instance, a characterisation is possible through the complimentary slackness condition - check if the polyhedron $A^Tp = c , b^Tp = c^Tx', p \ge 0$ is non-empty. Does this fit your bill? – stochasticboy321 Aug 9 '16 at 6:29
• There is a built in way to check this in the simplex algorithm. Just check the finish condition. – mathreadler Aug 9 '16 at 6:50

Theorem 4.2.2. (Certificate of Optimality) If $x$ and $y$ are feasible solutions of the primal and dual and $c^\top x = b^\top y$, then $x$ and $y$ must be optimal solutions to the primal and dual.
• The certificate is exactly what i'm looking for. The one catch is that it requires 2 points to be used, how can one modify the certification to a single point certificate? Does there exist a procedure for taking a point $x$ in the primal and mapping it to some "natural" point in the dual? – frogeyedpeas Aug 10 '16 at 2:34
First check if this point $x'$ is a vertex. Then do perturbation by adjusting x about that point and check to see if it is the optimal point.