4
$\begingroup$

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, and 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.

$\endgroup$
2
10
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – JPReddy Sep 28 '10 at 18:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Gilead Sep 29 '10 at 2:13
  • 1
    $\begingroup$ 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. $\endgroup$ – Gilead Sep 29 '10 at 2:33
3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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. $\endgroup$ – Jyotirmoy Bhattacharya Sep 27 '10 at 1:52
  • $\begingroup$ 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. $\endgroup$ – J. M. isn't a mathematician Sep 27 '10 at 16:20
1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ can both the inequality constraint and associated multiplier be zero , or does one zero excludes the other? $\endgroup$ – Hass Feb 28 '18 at 12:38

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.