Suppose we have an (not necessarily convex) optimization problem : <mtable columnalign="right l

Carolyn Beck

Carolyn Beck

Answered question

2022-06-24

Suppose we have an (not necessarily convex) optimization problem :
min x f 0 ( x ) f 1 ( x ) 0.
Let L ( x , λ ) = f 0 ( x ) + λ ( f 1 ( x ) ). Then the above problem can be equivalently written as:
min x max λ 0 L ( x , λ ) .
The dual of the above problem can be written as:
max λ 0 min x L ( x , λ ) .
We say that strong duality holds at a point when
min x max λ 0 L ( x , λ ) = max λ 0 min x L ( x , λ ) .
By weak duality, the inequality
min x max λ 0 L ( x , λ ) max λ 0 min x L ( x , λ )
always holds true. My doubt is: suppose there exists an x that minimizes L ( x , λ ) for a fixed λ, can i say that the following inequality holds true:
max λ 0 ( min x L ( x , λ ) ) = max λ 0 L ( x , λ ) min x max λ 0 L ( x , λ ) .
If the above is true, then are we saying that if there is a primal variable that attains its minimum in the dual problem, then strong duality holds true? Somewhere this does not seem to add up.

Answer & Explanation

Harold Cantrell

Harold Cantrell

Beginner2022-06-25Added 21 answers

No, because the last inequality, max λ 0 L ( x , λ ) min x max λ 0 L ( x , λ ), does not hold in general. Note that x is a function of λ. It would have been clearer to write x∗(λ) instead of just x .

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Multivariable calculus

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?