3
$\begingroup$

I am wondering if there is a simple example application of the Karush-Kuhn-Tucker conditions to show that a minimum exists for a multivariate minimization/optimization problem. Could anyone suggest a good reference textbook or monograph with an example?

Moreover, I am wondering if there is a computer algebra system (CAS) program or function that can be used to experiment with multivariate equations. The input to the program would be a multivariate equation, whereas the output would be some sort of analytic check for convergence (i.e. that a minimum exists). Perhaps such a program would quickly help to check equations for convergence.

$\endgroup$
  • 1
    $\begingroup$ The KKT conditions are necessary conditions, just like Lagrange multipliers. Generally they cannot be used to show that a minimum exists unless you know something more about the problem (convexity, for example). $\endgroup$ – copper.hat Aug 1 '12 at 18:55
  • $\begingroup$ @copper.hat: Thanks, copper.hat. Is there a good expository reference that deals with the KKT conditions, and perhaps demonstrates how to use them? How do I show convexity? $\endgroup$ – Nicholas Kinar Aug 1 '12 at 19:15
  • 2
    $\begingroup$ This is a tough one for me. Frankly, it took me a long time to grasp the KKT conditions (and similar), and it wasn't until I acquired some familiarity with nonsmooth analysis (Frank Clarke, "Optimization and Nonsmooth Analysis") in the context of minimax problems ($\min_x \max_i f_i(x)$) that I began to get a grip on understanding. However, that is a tough route to follow, if understanding KKT is your goal. I have only glanced at the book, but Boyd & Vandenberghe's "Convex Optimization" has a section on KKT for convex problems, which might be good to develop intuition. $\endgroup$ – copper.hat Aug 1 '12 at 20:23
  • $\begingroup$ Oh, these references are just lovely, and the Boyd & Vandenberghe book is available online as well: stanford.edu/~boyd/cvxbook, so I can read it immediately. Please write this up as an answer. $\endgroup$ – Nicholas Kinar Aug 1 '12 at 20:34
  • $\begingroup$ You are welcome, hope it helps you. $\endgroup$ – copper.hat Aug 1 '12 at 20:54
1
$\begingroup$

I guess the answer is late, but maybe it can help others with the same problem.

When I needed to understand the KKT conditions, this explanation helped me a lot, with a very simple and complete step by step example. If it is still complicated, I recommend reading this chapter from Mathematial Optimization and Economic Analysis (Luptácik, M.; Springer) on the subject carefully. When you master the basics concepts, you can already go to practically any book or handbook on nonlinear optimization.

$\endgroup$

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.