# Karush-Kuhn-Tucker condition - Lagrange multiplier

I was maths student but now I'm a software engineer and almost all my knowledge about maths formulas is perished.

One of my client wants to calculate optimal price for perishable products. He has come across an article named Optimal Pricing Policies for Perishable Products by Miguel F. Anjos¤ Russell C.H. Cheng Christine S.M. Currie.

It has a formula which is called Karush-Kuhn-Tucker condition. I'm completely baffled by looking at it, may be my basics are completely vanished that's why I became completely blank. I understood the basic requirement and has come up with a proper solution for that but I'm not sure whether my solution is completely addressing the condition given in this article.

Can anybody explain me in plain english about this condition so that I can convert it to algorithm written in a programming language. Or if there is any programming library available for this condition?

I'm sorry to ask without giving full information about this condition. I'm assuming someone will know about this condition, if not I'll have to post that entire formula which is of around 2-3 pages. :(

-
Here's a link to the "Perishable Products" article. optimization-online.org/DB_FILE/2004/03/832.pdf (I was surprised to see it originated at a university where I lectured for several years.) And here's a link to the KKT conditions. en.wikipedia.org/wiki/… – Derek Jennings Sep 26 '10 at 18:22
So you don't have to post the KKT conditions they are here: en.wikipedia.org/wiki/… – alext87 Sep 26 '10 at 18:24
@Derek: Thanks for posting the article – JPReddy Sep 27 '10 at 2:38

I've glanced at the paper you linked to. I have a few remarks:

• It looks the authors of the paper managed to derive explicit closed-form expressions for the stationarity conditions for a special class of functions. This is sometimes possible for very specific problems.

• If you remember your calculus, for a univariate function $f(x)$, the minimum or maximum is found when $f'(x) = 0$. You can think of the KKT as a generalization of this idea for an optimization problem with constraints.

• The reason I (and the authors) say "stationarity" conditions instead of "optimality" conditions is because KKT conditions are necessary but insufficient conditions for optimality. For a true guarantee of optimality, you need to test your solution against SSOCs (Sufficient Second Order Conditions). Again, the second order conditions are analogous to the Calculus-101 idea of determining whether $f''(x)$ is positive or negative, which tells you whether the solution of $f'(x) = 0$ is a minimum or maximum.

• Nevertheless in this case, under the assumptions in the paper, in the absence of saddle points, we may presume the solution to be optimal.

• This means you do not have to use any optimization algorithm/library in this particular case. For a given pricing function, all you have to do is evaluate a function based on the results given in the paper. This is a very nice property -- it means the optimization is implicitly done for you. See Example 1 in the paper for a worked example.

In general, the KKT does not provide an algorithm for finding an optimum; it's only a test for stationarity. However, in very specific cases (i.e. with regularity conditions assumed, convex, no inequalities, etc.), the KKT conditions can provide closed-form expressions for the optimal solution of a problem.

In fact... this is the idea behind the Method of Lagrange Multipliers. The Lagrange Multiplier method is simply a special case of the KKT conditions with no inequality constraints.

Side Note: one of the reasons behind the difficulty in using the KKT as a practical algorithm to find stationary/optimal points is due to the "complementarity conditions" in the KKT system (see Wikipedia article). when you have inequality constraints, you have to satisfy a set of constraints known as "complementarity constraints". There can be nasty, nonconvex, degenerate bilinear terms in these constraints, and special techniques are required to handle them -- enumerative methods are required for obtaining global optimality, and therefore the problem is NP-hard. There is a whole new field of research in burgeoning area of complementarity problems (and its related problem class, MPECs = mathematical programs with equilibrium constraints)... currently there's a lot of work being done on determining different types of stationarity conditions for this class of problems. It is outside the scope of the question, but I thought I'd just let you know what's out there.

-
That's a excellent explanation I got. Thanks for the detailed information. Somehow I managed to think about an algorithm to achieve this optimization but not sure whether I'm perfectly addressed KKT conditions as per the examples in this article. – JPReddy Sep 28 '10 at 18:39
@JPReddy: well, the point I was trying to make was that by satisfying conditions 9 & 11 given in the paper, you can get an explicit optimal solution (as per the 3 forms given section 4.1) without doing any optimization (there is no optimization to do! ;-). The KKT conditions (and the Euler-Lagrange equation, which gives stationary conditions for the differential equation) were used during the derivation, but do not appear in the final form at all. – Gilead Sep 29 '10 at 2:13
In a nutshell, check conditions 9 and 11. The work through Section 4.1 to pick the correct form of the optimal pricing function, depending on whether the full capacity is taken up. As far as I can tell, that's basically it. However, I would encourage you to seek local assistance -- it's hard for me to give very specific advice without knowing what your problem looks like. Good luck. – Gilead Sep 29 '10 at 2:33

The KKT conditions are necessary conditions for a constrainted optimization problem to have a local minimum. For complex problems these conditions normally motivate the development of minimization algorithms rather than trying to find the values that satisfy the KKT conditions.

There is black-boxed optimization software and it is advised to take advantages of these. Perhaps a SQP (Sequential quadratic programming) would be ideal for this problem.

The optimization toolbox in Matlab is a really easy to use. The function fmincon is likely to solve your problem. See: http://www.mathworks.com/products/optimization/

There are alternatives though I personally have never used them. See: http://wwwasdoc.web.cern.ch/wwwasdoc/minuit/minmain.html

-
@jpreddy I second alex's suggestion of using existing optimization libraries if possible. But if you must develop your own algorithm, knowing the KKT conditions is not enough. You must study the numerical aspects of optimization too. The standard texts are by Nocedal and Wright and Fletcher. – Jyotirmoy Bhattacharya Sep 27 '10 at 1:52
Shorter version: KKT is not an (practical) algorithm; it's what a solution to a constrained optimization problem has to satisfy. A probably simpler starting point than Nocedal/Wright or Fletcher would be the book by (Griva/)Nash/Sofer. – J. M. Sep 27 '10 at 16:20

I have used the KKT conditions numerous times, and am working on a project now that involves using the KKT conditions along with convexity in non-negative matrix factorization, but I'm having trouble finding a good, two-dimensional, image of why the KKT conditions work. Although I understand what is going on, I have never been one who is able to draw what makes sense. Does anyone know where I can find a good image to show why these conditions work with a convex function?

-
@victoria: I can not help you on that topic, but it might get more help if you put as a question :) – Bryan Yocks Dec 17 '10 at 21:24
@Victoria: I would recommend posting this as a new question. Your question is currently likely to be buried in the answers to this old one. If you do post this as a new question you should also delete this answer. – Mike Spivey Dec 17 '10 at 21:25

Maybe this site about Karush Kuhn Tucker conditions will help to give some insight why they work.

-