I have a question regarding the big-picture in the field: Lagrangian, Duality, KKT, sufficient, necessary conditions.

1) Duality is a concept: “The solution to the dual problem provides a lower bound to the solution of the primal”

2) The concept of Lagrangian is a strategy to find local maxima, minima with equality constraints.

3) KKT concept: Is the generalized idea of the Lagrangian – includes inequality constraints.

4) Lagrange Duality: Transfers any problem into a convace (the dual) problem --> uses the idea/proves of 1.

Question 1: The KKT and the Lagrange-Dualty concept use both the Lagrangian right? The Lagrange-Dualty: $ g = inf(x)> L(x,u,v)$

Question2: KKT: Regarding necessary and sofficient conditions: If I can prove, that the problem is convex - a KKT point = global optimum right? If the problem is not convex, i have to compare all KKT points and the lowest (in a min. problem) is the local, not a global minimum? Or do I have to prove if Hessian is positiv(semi) definit?

Thank you very much for your help!


Question 1: Yes you can sort of see KKT as an extension of Langrange multipliers if that helps.

Question 2: Nope. A point can be a KKT point without being optimal. We say that the KKT conditions are necessary but not always sufficient. You need some additional constraint qualifications to hold here, which are kind of boring and technical in nature and usually highly overkill. Convexity and the existance of some interior point is usually fine.

  • $\begingroup$ Regarding Q2, I think @lars111 is right. If the problem is known to be convex, the KKT conditions are necessary and sufficient for global optimality. $\endgroup$ – Dunkel Nov 30 at 8:33
  • $\begingroup$ Opinion doesn't add much. Back it up with something $\endgroup$ – Benjamin Lindqvist Dec 1 at 8:30

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.