Timeline for Lagrangian duality
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 29, 2011 at 21:10 | comment | added | Jonathan | My question actually originated from a quite complicated problem. I do have a solution to the dual problem ($z^*_i$), and I want to recover the primal solution by using the KKT condition. But then I noticed the crack, because there is simply no x which satisfies: $h_i(x)=0$ and $\nabla f(x) + \sum_i z^*_i \nabla h_i(x) = 0$. Let me try to simplify my problem, but still keep the crack. Btw, my primal objective is $f(x) = ||x||_2$, not smooth only at $x=0$. | |
| Dec 29, 2011 at 20:53 | comment | added | Igor Rivin | I will ponder, but do you have an example for your $n-1$st comment? | |
| Dec 29, 2011 at 20:20 | comment | added | Jonathan | In other words, can one treat the dual problem as the "primal problem" in the theorem, and then apply the theorem in a reverse way? I think not, because in Lagrange dual, there is no "the dual of the dual is the primal", loosely speaking. | |
| Dec 29, 2011 at 20:13 | comment | added | Jonathan | Sorry for the confusion; it's tricky. The optimal solutions to the primal and dual problems are not unique. For any primal optimal $x^*$, there must exist a dual optimal solution $z^*_i$ such that they together satisfy the KKT condition. But it is possible that although a $z^*_i$ is a dual optimal solution, there does not exist any primal optimal $x^*$ which satisfies KKT condition together with $z^*_i$. | |
| Dec 29, 2011 at 20:03 | comment | added | Igor Rivin | I am probably still confused, but the book seems to say that if $x, z$ (in your notation) satisfy the KKT conditions, then $x, z$ are primal and dual optimal, with zero duality gap, which appears to be exactly what you are asking... | |
| Dec 29, 2011 at 19:55 | comment | added | Jonathan | Unfortunately no. The book only says $x^*$ is optimal if and only if there are $z_i$ that, together with $x^*$, satisfy the KKT conditions. However my question is given any $z^*_i$ which optimizes the dual problem, whether there exists a primal optimal solution $x^*$ which attains zero gradient together with $z^*_i$. | |
| Dec 29, 2011 at 19:45 | history | answered | Igor Rivin | CC BY-SA 3.0 |