0
$\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. (well so I think) 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."

Question: 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.

Improve this question
$\endgroup$
8
  • $\begingroup$ There is primal degeneracy and dual degeneracy. In primal degeneracy, there exist multiple active sets, all of which satisfy the optimality conditions. In dual degeneracy, the objective function is degenerate (i.e. linearly dependent) with respect to one of the constraints in the active set. So what is your question here? $\endgroup$
    – Richard
    Nov 5, 2020 at 9:11
  • $\begingroup$ @Richard 1 - Is optimal solution to dual not unique if optimal solution to the primal is degenerate? 2 - What is the additional assumption? $\endgroup$
    – BCLC
    Nov 12, 2020 at 2:35
  • 1
    $\begingroup$ I think this is something you should discuss with your professor. I do not specifically understand what is going on. $\endgroup$
    – Richard
    Nov 15, 2020 at 10:12
  • 1
    $\begingroup$ Hmm, I don't understand what this sentence means: "unique degenerate optimal solution to the primal". A unique solution is by definition non-degenerate (by solution I mean the solution values, not the objective function) $\endgroup$
    – Richard
    Sep 23, 2021 at 8:10
  • 1
    $\begingroup$ I agree with Paul, he's generally right about this kind of stuff :) $\endgroup$
    – Richard
    Sep 24, 2021 at 19:11

1 Answer 1

Reset to default
4
$\begingroup$

If I understand your question correctly, I think you can find your answer by considering the following two primal problems. The first is \begin{alignat*}{2} & \max & x_{1}\\ & \textrm{s.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0 \end{alignat*} and the second is \begin{alignat*}{2} & \max & 0\\ & \textrm{s.t.} & x_{1}+x_{2} & \le1\\ & & x_{1} & \le1\\ & & x & \ge0. \end{alignat*}

$x=(1,0)$ is a degenerate optimal solution for both problems. Inspecting their duals should prove informative.

Improve this answer
$\endgroup$
11
  • $\begingroup$ thanks prubin. yet to analyse, but what is the additional assumption please? $\endgroup$
    – BCLC
    Nov 11, 2020 at 3:50
  • $\begingroup$ I don't know. Ask OP. $\endgroup$
    – prubin ♦
    Nov 11, 2020 at 16:26
  • $\begingroup$ I am the OP. lol. so in your opinion is there no additional assumption? $\endgroup$
    – BCLC
    Nov 12, 2020 at 2:32
  • 1
    $\begingroup$ I'm not sure I do understand what you've said. The example I posted should tell you whether the degenerate primal solution -> multiple dual solutions implication requires uniqueness of the primal solution. That's all I have to offer. $\endgroup$
    – prubin ♦
    Nov 15, 2020 at 16:41
  • 1
    $\begingroup$ I don't see a difference. $\endgroup$
    – prubin ♦
    Nov 18, 2020 at 0:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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