I am just beginning to read about the use of "Concave Programming" methods and use of the Karush-Kuhn-Tucker conditions to identify the maximum value of a non-linear objective function subject to inequality constraints.

The examples I have seen in the text I have at hand, all involve only linear constraints. Is this method equally applicable to situations where not only are there multiple constraints, but where one or more of those constraints are non-linear ?

  • $\begingroup$ Not a real question; vote to close. $\endgroup$ – Arturo Magidin Oct 24 '10 at 5:34
  • 5
    $\begingroup$ There is a mathematical question in there: "Are the Karush-Kuhn-Tucker conditions applicable to situations where one or more of the constraints are non-linear?" The answer is yes. Any book on nonlinear optimization should have the details. $\endgroup$ – user856 Oct 24 '10 at 5:36
  • $\begingroup$ @Rahul: fair enough; perhaps what the question needs is a massive edit to remove the last four, irrelevant, paragraphs. $\endgroup$ – Arturo Magidin Oct 24 '10 at 5:38
  • 1
    $\begingroup$ @Arturo: I agree. Dear @Michael Barkusky: You seem to have misunderstood the purpose of this site. It is designed specifically to answer questions about mathematics, and is not a general-purpose discussion forum. As such, the last four paragraphs of your post are out of place here, and your question may get a better reception if you edit them out. $\endgroup$ – user856 Oct 24 '10 at 5:46
  • 3
    $\begingroup$ I would just add to Rahul Narain's comment that not only can the KKT conditions be applied to problems with nonlinear constraints, part of the reason they were derived in the first place was to handle problems with nonlinear constraints. $\endgroup$ – Mike Spivey Oct 25 '10 at 3:32

The answers provided above are only partly valid. When there is at least one nonlinear constraint, the KKT conditions are necessary for optimality IF a constraint qualification holds! Consider for instance $$ \min_x \ x \quad \text{s.t.} \ x^2 = 0. $$ The KKT conditions are that $1 - 2 xy = 0$ and $x^2 = 0$. They have no solution. This is because no constraint qualification is satisfied at $x^* = 0$.


The KKT method is applicable to nonlinear constraints, but not equally applicable. Like Dominique said, you need a constraint qualification to be satisfied for the KKT conditions to be necessary.

For KKT conditions to be sufficient to characterize the solution of a maximization problem, your objective function needs to be concave, and you need the constraints to be convex, that is, you have to be able to write them as

$g(x) \leqslant 0$

where $g: \mathbb{R}^n \to \mathbb{R}$ is a convex function. For minimization problems, you want the objective function to be convex.

Boyd and Vandenberghe have a very good book on this that is freely available, accompanied by video lessons taught by Stephen Boyd. I have some short notes too that are a good complement or introduction to a more rigorous or extensive treatment. For the nonconvex case, I really like the treatment in the book "Numerical Optimization", by Nocedal and Wright.

Advice: make sure you understand the geometry of the case with inequality constraints. The continuously differentiable case will be easier. My notes have a picture and a very brief discussion on this if you want a quick treatment. You need to know a few things to make sense of it though: mainly that any direction that makes an obtuse (> 180 degrees) angle with the gradient of a continuously differentiable function is a direction of descent. The rest is linear algebra.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy