Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a student of Computer Science and currently learning about optimization. We've been introduced to the Fritz-John and Karush-Kuhn-Tucker conditions for convex optimizations.

I think I understand what they mean, in the sense that these conditions have to be fulfilled in order for a point to be an optimum.

However, I don't really understand the difference between both and my lecture notes are not very good at making a clear point of this difference. In fact, I am allergic to mathematical notation, so I would appreciate a concise and short answer in plain English, maybe with an example.

Thank you!

share|improve this question
    
Please try posing this question at stats.stackexchange.com –  anonymous Jan 30 '11 at 17:23
3  
@Chandru: I think this is the apt place for this question. I do not see how stats.stackexchange would help –  user17762 Jan 30 '11 at 18:02
1  
This isn't statistics. It's optimization, like the OP has tagged. –  Mike Spivey Jan 30 '11 at 18:47

4 Answers 4

up vote 5 down vote accepted

Both sets of conditions are necessary conditions for a point to be optimal, but they're not quite the same mathematically. The KKT conditions are more restrictive and thus shrink the class of points (from those satisfying the Fritz John conditions) that must be tested for optimality. The additional restriction with KKT is that the Lagrange multiplier on the gradient of the objective function cannot be zero. One of the most important resulting differences is that KKT points for linear programs must be optimal, whereas Fritz John points for linear programs don't have to be.

The section on KKT conditions in Bazarra, Sherali, and Shetty's Nonlinear Programming: Theory and Algorithms (second edition) has a nice discussion of the issues. There are several good examples, especially one in which a Fritz John point for a linear program is shown not to be optimal. That can't happen with KKT points for linear programs.

share|improve this answer

The conditions are mathematically the same, stated in different ways. The way KKT state the conditions makes it easier to find the a set of points which satisfy necessary optimality conditions and are potentially the local optimum points of the problem.

But if for a particular point one wants to see if it can be a local optimum then it is easy to verify Fritz-John conditions. The reason for that is that you know which constraints are active or inactive.

share|improve this answer

The crucial difference between the two sets of optimality conditions is that when there is at least one nonlinear constraint, a constraint qualification (CQ) condition must be satisfied for the KKT conditions to be necessary for optimality. The Fritz-John conditions hold at any local minimizer regardless of whether a CQ holds or not. Consider for instance $$ \min_x \ x \quad \text{s.t.} \ x^2 = 0. $$ The (only) solution is clearly $x^*=0$ (it is the only feasible point). Now write down the Fritz-John conditions and the KKT conditions side-by-side. The KKT conditions have no solution, i.e., it is impossible to find Lagrange multipliers so they are satisfied at $x^*=0$. But you can find Fritz-John multipliers (by setting the objective multiplier to zero)!

In fact, by setting all multipliers to zero in the Fritz-John conditions, you can see that any feasible point is a Fritz-John point! But it's not necessarily a local minimizer!!!

The Fritz-John conditions are useful to prove that a problem is degenerate (i.e., it doesn't satisfy a CQ). If you are forced to set the multiplier of the objective gradient to zero, you're left with something like $$ J_E(x)^T y_E + J_I(x)^T y_I = 0, \quad (c_I(x), y_I) \geq 0, \quad c_I(x) \cdot y_I = 0, \quad c_E(x) = 0 $$ where $J_E$ is the Jacobian of the equality constraints ($c_E(x)=0$), $J_I$ is the Jacobian of the inequality constraints ($c_I(x) \geq 0$), $y_E$ are the multipliers for the equality constraints and $y_I \geq 0$ are the multipliers for the inequality constraints. My notation $c_I(x) \cdot y_I = 0$ means that the product vanishes componentwise.

Now it's possible to show that, if at least one of the $y$'s is nonzero, this proves that the Magasarian and Fromovitz constraint qualification (MFCQ) doesn't hold at $x$. This is done using Farkas' lemma or Motzkin's theorem of the alternative (see for example the book "Nonlinear Programming" by Olvi Mangasarian, published by SIAM, for those theorems). Thus the stronger Linear Independence Constraint Qualification (LICQ) doesn't hold either.

share|improve this answer

The Fritz John conditions or the John conditions provide more information about the problem than the KKT conditions. Further the multiplier associated with the gradient of the objective function can be shown to be 1 in the John conditions from the conditions of the problem itself. This fact is true unless one has a very pathological situation where there is only one point in the feasible set. KKT conditions are an easy corollary of the John conditions.

Note that corresponding to a given local minimum there can be more than one set of John multipliers corresponding to it. Further note that if the Mangasarian-Fromovitz constraint qualification fails then we always have a vector of John multipliers with the multiplier corresponding to the objective function is zero. Thus any constraint qualification which is weaker than Mangasarian-Fromovitz like the Guignard or Abadie CQ can only show that there exists a set of John multipliers with the multiplier associated with the gradient of the objective to be one. They can never guarantee that all John multipliers are KKT multipliers. Thus the John conditions should play a more central role in optimization rather that the KKT. It is however hardly mentioned. Do have a look at the beautiful book OPTIMIZATION : INSIGHTS AND APPLICATIONS by Brinkhuis and Tihkomirov published by Princeton University Press. Once you read the book you will realize the true power of the John conditions. When start out on the subject beyond MFCQ one should not think much about constraint qualifications. Note that if MFCQ fails does not mean that there is no vector of John multipliers with the multipliers associated with the gradient of the objective as one. Typically you can get a John multiplier with the multiplier associated with the objective as 1 irrespective of satisfaction of any CQ or not. This is the central fact of optimization and the John conditions are the main stuff.

Joydeep Dutta IIT Kanpur, India

share|improve this answer
    
Please do not sign your nm in the end; see FAQ to know more. You already have a signature along with the question. Thanks. –  awllower Mar 31 '13 at 8:22

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.