2
$\begingroup$

If optimal solution to the primal is degenerate, does it necessarily follow that optimal solution to dual not unique? That is, is uniqueness an unnecessary assumption?

Spin-off from here.

In my Operations Research problem set, our professor required us to prove

"If an optimal solution to the primal is degenerate, then there is at least one alternative optimal solution to the dual."

I found, however, that if we do not assume uniqueness, the statement is false?

I asked by e-mail:

"In the problem set, does the optimal solution to the primal really need not be unique?"

The reply I got:

"Yes. Some LP problems have alternative optimal solutions."

I asked if uniqueness was not needed to conclude an alternative optimal solution to dual and showed the counterexample I linked above (again here).

Reply I got:

"I only said thet in LP, alternative optimal solutions may exist. I am not referring to the problem in the exercise specifically. Please read the statement of the problem again."

I then asked if the OP was equivalent to

"If there are several optimal solutions to the primal with at least one of them being degenerate or there is a unique degenerate optimal solution to the primal, then the optimal solution to the dual is not unique?" i.e. uniqueness of degenerate optimal solution to primal is irrelevant?

The reply I got: "There is an additional assumption in your statement which is not in the problem."

What is the additional assumption?

In the end, we just copied the "proof" of one of our other classmates. Apparently, e was able to prove the statement even though it looks to be false. I don't have the proof with me though.

One of my classmates asked our professor on the day of submission that someone (me) pointed out that if we don't assume uniqueness, the statement doesn't hold. I was kind of sleepy, but iirc, our prof said something that began with

"But that's not what you're trying to show"

or something like that. My classmate didn't respond, and we just moved on. Well, they did.

$\endgroup$
  • $\begingroup$ What exactly do you mean by "assume uniqueness"? Unique what? $\endgroup$ – Michael Grant Apr 27 '15 at 3:01
  • $\begingroup$ @MichaelGrant I mean that the statement should be revised to "If there is a unique degenerate optimal solution to the primal, then there is at least one alternative optimal solution to the dual" if we assume uniqueness. I found a counterexample to the original statement (linked above). I found a proof for the revised statement math.stackexchange.com/questions/1049796/… $\endgroup$ – BCLC Apr 29 '15 at 12:51
  • $\begingroup$ Isn't "a unique degenerate optimal" kind of a contradiction? The property of degeneracy implies that there are multiple solutions (that is, variable value assignments) resulting in the same optimal (i.e. the optimal is an overdetermined point in solution space). The point of the exercise is probably to show that if this holds for the primal optimal, it'll also hold for the dual. Your concept of uniqueness is vague here and will probably have resulted in the described language confusion, which your professor dismissed as not pertaining to the question. $\endgroup$ – Fasermaler Apr 30 '15 at 9:40
  • 1
    $\begingroup$ @Fasermaler Um, do you know what the additional assumption is? $\endgroup$ – BCLC May 2 '15 at 12:05
  • 1
    $\begingroup$ @BCLC At this point I can also only speculate what your instructor meant. I could imagine he is blissfully unaware of this somewhat exotic uniqueness consideration you seem to be well versed in, so he just wanted the textbook solution to the textbook question and no corrections to the question, however valid. If you're looking for more insightful replies than my guesses though, it might help to post the proof he did accept. $\endgroup$ – Fasermaler May 2 '15 at 21:57

Your Answer

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

Browse other questions tagged or ask your own question.