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:
- I said that algorithm at a high level, how do I actually do that?
What if we relax the condition to perhaps a non unique max, then we lose out on the extreme point tests etc...
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$
Look for KKT conditions for a linear program.
The terminology used for such conditions is certificate of optimality. I would suggest to check one of main references about optimality certificate, such as in Boyd and vandenberghe book.
See also theorem 4.2.2 of Introduction to optimization lecture notes 4 on LP, where it states:
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.