# Is optimal solution to dual not unique if optimal solution to the primal is degenerate?

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?

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

"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).

"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.

"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.

• 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? – Richard Nov 5 '20 at 9:11
• @Richard 1 - Is optimal solution to dual not unique if optimal solution to the primal is degenerate? 2 - What is the additional assumption? – BCLC Nov 12 '20 at 2:35
• I think this is something you should discuss with your professor. I do not specifically understand what is going on. – Richard Nov 15 '20 at 10:12
• @Richard it was 6 years ago but eh i guess i'll give it a shot. – BCLC Nov 15 '20 at 11:28
• @Richard But just from your reading of what's going, is there an additional assumption? – BCLC Nov 15 '20 at 11:28

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.