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

Question

Suppose we have an (not necessarily convex) optimization problem :

\begin{aligned} min_{x} f_{0} (x) \\ f_{1} (x) \leq 0. \end{aligned}

Let

L (x, λ) = f_{0} (x) + λ (f_{1} (x))

. Then the above problem can be equivalently written as:

min_{x} max_{λ \geq 0} L (x, λ) .

The dual of the above problem can be written as:

max_{λ \geq 0} min_{x} L (x, λ) .

We say that strong duality holds at a point when

min_{x} max_{λ \geq 0} L (x, λ) = max_{λ \geq 0} min_{x} L (x, λ) .

By weak duality, the inequality

min_{x} max_{λ \geq 0} L (x, λ) \geq max_{λ \geq 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_{λ \geq 0} (min_{x} L (x, λ)) = max_{λ \geq 0} L (x^{*}, λ) \geq min_{x} max_{λ \geq 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 1

No, because the last inequality,

max_{λ \geq 0} L (x^{*}, λ) \geq min_{x} max_{λ \geq 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^{*}

.

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

Answers (1)

Not exactly what you’re looking for?

You might be interested in

New questions