1
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – stochasticboy321 Aug 9 '16 at 6:29
  • $\begingroup$ There is a built in way to check this in the simplex algorithm. Just check the finish condition. $\endgroup$ – mathreadler Aug 9 '16 at 6:50
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – frogeyedpeas Aug 10 '16 at 2:34
  • $\begingroup$ Well, I am not much help here, but would suggest asking a separate question about how to recover dual variables from primal in a linear program. It is a well established thing and I I am sure people are able to guide you to a correct direction. In solvers, (i.e. softwares that optimiza) typically both primal and dual is returned, so that one can verify the correctness. $\endgroup$ – user25004 Aug 11 '16 at 3:42
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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