2

I am having difficulties understanding the graphical interpretation as well as why the two following KKT conditions is necessary for a point x* being a minimum.

image

It is my understanding that the (d) conditions is also known as complementary slackness variables, meaning that at most one of the conditions are slack (I.e. not an equality).

The (e) condition does not make any sense to me.

Can anyone help with the derivation of these two conditions, or provide a better understanding of the graphical interpretation?

Gerry Myerson
  • 179,216
  • Hello ! Are you sure the question is related to the Mathematica computer system ? – Sektor Aug 23 '13 at 09:55
  • Your question is not mathematica related. It is about optimization theory. To answer your question briefly: (e) is the positivity constraint for lagrange multipliers with respect to inequality constraints. This inequality follows directly from hyperplane separableness of certain convex sets related to a convex optimization problem. Please refer to books that derive the KKT-Conditions for details. – Wizard Aug 23 '13 at 10:12
  • @Wizard do you recommend any particular books that explain the viewpoint you alluded to? I know a proof of a strong duality theorem along those lines is given in Boyd and Vandenberghe, but I'm curious about other references as well. Also, I'd be interested in hearing you explain this point in more detail. – littleO Aug 25 '13 at 01:12
  • Guilherme Freitas wrote some good notes about the KKT conditions here. – littleO Aug 25 '13 at 01:15

1 Answers1

1

I'd ususally put this in a comment, but I do not have enough reputation (my comment above is from the mathematica.stackexchange forums). There is actually not much good literature on optimization, that I can really recommend. Most of my knowledge comes from German literature, which I will not mention here. One book I can recommend though is the well known book "Convex Analysis and Optimization" from Bertsekas. It's not perfect and no quick introduction either, but it is well written and does a good job explaining things (which unfortunately is pretty rare in math literature). Another good book seems to be convex optimization from Boyd. If anybody knows other good literature on (convex) optimization, I'd like to hear about it.

Wizard
  • 249
  • I think that if you have a nonlinear equality constraint, then your problem might not be convex anymore, since the feasible set might not be convex. – JLagana Dec 08 '16 at 18:28
  • @JLagana: You are right about that. As Boyd's book is called "convex optimization" it makes sense that he focuses only on linear equality constraints. Honestly I do not know why I wrote that back then. I guess I edit the answer. – Wizard Dec 09 '16 at 19:53