Suppose we have the following linear program (P):
max{$c^Tx: Ax \leq b, x\in R^n$ } where $A$ is an $m \times n$ matrix, $c\in R^n$ and $b\in R^m$.
A certificate of optimality for (P) consists of one or more vectors of dimension $m$ or $n$ satisfying certain linear constraints in terms of $A,b,c$ such that if such vectors exist, then LP (P) has an optimal solution.
Describe a certificate of optimality for (P) such that (P) has an optimal solution if and only if (P) has a certificate of optimality, and prove that the certificate has this property.
Can someone please help me with this problem? I don't quite understand what the question asks for.
If you can find a feasible solution to the primal problem and a feasible solution to the dual problem, and they share the same value, then it is optimal.
This is due to strong duality.