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$
2
  • $\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$ Commented Aug 9, 2016 at 6:29
  • $\begingroup$ There is a built in way to check this in the simplex algorithm. Just check the finish condition. $\endgroup$ Commented Aug 9, 2016 at 6:50

2 Answers 2

2
$\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$
2
  • 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$ Commented Aug 10, 2016 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
    Commented Aug 11, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .