Is there a possibility to prove the strong duality (Lagrangian duality) if the primal problem is quasiconvex? Or is there a technique that proves that the primal problem is convex instead of quasiconvex?


I'm not sure I understand the question clearly enough to give a precise answer, but here is a kind of meta-answer about why you should not expect such a thing to be true.

Generally speaking duality results come from taking some given objective function and adding variable multiples of other functions (somehow connected to constraints) to it. Probably the simplest case is adding various linear functions.

Proving strong duality for a certain type of setup involves understanding the class of functions thus generated, usually using some sort of convexity property. For example, if our original objective function $f$ is convex and we think of adding arbitrary linear functions $L$ to it, the result $f+L$ will always be convex, so we have a good understanding of functions generated in this way, in particular what their optima look like.

Quasiconvexity does not behave nearly so will with respect to the operation of adding linear functions. One way to express this is the following. Let $f:\mathbb{R}^n\to\mathbb{R}$ be a function. Then $f+L$ is quasiconvex for all linear maps $L:\mathbb{R}^n\to\mathbb{R}$ if and only if $f$ is convex.

Therefore the class of functions for which the benefits of quasiconvexity (local minima are global, etc.) would help prove strong duality is in some sense just the convex functions. This is not to say strong duality will never hold for quasiconvex objectives, but just that some strong additional conditions are required beyond the usual constraint qualifications used for convex functions: quasiconvexity alone does not buy you much duality-wise.

  • $\begingroup$ yes it is not possible to prove strong duality if the problem is quasiconvex. But is there a some condition for the duality-gap? Some epsilon, that describes how close the dual problem is to the optimal solution? $\endgroup$ – Guido Aug 7 '11 at 10:42
  • $\begingroup$ @Guido, The way you originally posted the above text was as an answer; however, answers are only intended for things that provide an answer to the question. You intended your text to be a comment to Noah, so I have converted it to a comment. You can always comment on your own questions and answers, and on answers to your own questions, regardless of what your reputation score is. In the future, please use the "add comment" button on the bottom left of each question and answer on the site (it is light gray). $\endgroup$ – Zev Chonoles Aug 7 '11 at 11:00
  • $\begingroup$ @Zev: Do note the different account numbers on the comment and the original question. $\endgroup$ – Asaf Karagila Aug 7 '11 at 11:31
  • $\begingroup$ @Asaf: Thanks for catching that! $\endgroup$ – Zev Chonoles Aug 7 '11 at 12:11
  • $\begingroup$ @Guido: As Asaf points out, I now see that you were unable to make a comment because you accidentally created a different account. I've merged the duplicate account with your previous one; now there is only this one. It may help avoid this issue in the future if you register your account. $\endgroup$ – Zev Chonoles Aug 7 '11 at 12:13

Your Answer

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

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