This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of
mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join
the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics articles
The KKT theorem seems to refer to a different formulation of the problem that is actually there: The KKT theorem makes no reference to or , and the Lagrangian in the theorem is whereas in the problem statement it is . Also, the term "optimal vector" is not defined, but if it means "globally optimal" then the theorem is wrong since the saddle point condition at most gives local optimality (and no convexity or the like is assumed here). In short, this central element in the page seems to be a mixture of different formulations.
UffeHThygesen (
talk)
09:47, 9 December 2020 (UTC)reply
KKT in complex spaces
Could anyone please write on validity of the KKT for real-valued functions of complex vector variables? The current revision of the article covers the real case only. (
2andrewknyazev (
talk)
23:48, 22 July 2010 (UTC)).reply
This would be a nonstandard topic, better more of research literature than an encyclopedia. (A complex vector space with complex dimension D can be viewed as a real vector space of dimension 2D.)
Kiefer.Wolfowitz (
talk)
11:08, 25 July 2010 (UTC)reply
Is there a special reason for complex being "nonstandard"? Why, e.g., minimizing a real quadratic form over a complex space would be any less "standard" than over a real space? If it is true that the KKT holds without any changes for complex vector variables, that would be an encyclopedia-level statement. If there is a special reason, why it is not true, that would also be an encyclopedia-level statement, I guess. (
2andrewknyazev (
talk)
16:53, 26 July 2010 (UTC))reply
WP is not a forum for original research. An article on KKT conditions should respect WP guidelines, particularly wrt the weight of topics in standard, leading reliable references (e.g. textbooks and research monographs, or invited review articles).
In a constructive spirit, let me suggest some references. For the complex field, you may look at literature about Hilbert's 17th problem (sums of squares representations, e.g. J-B Lasserre), plurisubharmonic functions, etc. No reliable standard reference comes to mind for complex vector spaces: It may be worthswhile to look at Karlin's book from the 1950s, e.g. Sobyczyk (sic.).
Kiefer.Wolfowitz (
talk)
21:52, 29 July 2010 (UTC)reply
Complex optimization problems can be easliy transformed to real optimization problems mechanically. Thus I do not think it have any special properties. Before transformation you need define a order on complex space, to transform it to real one. If you mean real-valued function over complex field space, it is even simpler, just analyze a vector space with 2n dimensions (real and imaginary parts). --
91.213.255.7 (
talk)
03:44, 10 April 2012 (UTC)reply
a minus or a plus ?
In other sources, there is a minus (instead of a plus) sign in front the multiplier (or it is to the right of the equality sign). Is the English Wikipedia article wrong? See for instance the Swedish article. /Anton —Preceding
unsigned comment added by
83.249.20.170 (
talk)
20:00, 2 September 2009 (UTC)reply
There seems to be a typo here: should the complementarity condition be
$\sum_i \mu_i g_i(x^\ast) = 0$, not $\mu_i g_i(x^\ast) = 0$ for each $i$?
Tveldhui21:05, 17 March 2006 (UTC)reply
These are equivalent statements.
The introduction says "Allowing inequality constraints, the KKT approach to nonlinear programming generalizes the method of Lagrange multipliers, which had traditionally required linear constraints." Shouldn't "linear" (the second-to-last word) be replaced with "equality"? AFAIK, KKT and Langrange multipliers both do nonlinear programming quite naturally, and the first three words of the sentence also seem to support the idea that the shortcoming of Lagrange multipliers is that they require "equality constraints."
18.214.1.205 (
talk)
02:46, 31 March 2010 (UTC)reply
Does the $\lambda$ under "regularity" mean the $\mu$ and $\nu$ in the section before that? In this case this should be corrected, because the $\lambda$ for the dual multipliers doesn't appear anywhere else in the article. —Preceding
unsigned comment added by
84.75.149.134 (
talk)
22:17, 30 January 2008 (UTC)reply
Suggestions for article improvement
The article needs historical background.
It needs to show how the Lagrange Method can be an special case of KKT, when one uses two inequality constraints as an equivalent of one equality constraint.
From an economics student's point of view, the article should show more results related to the problem of cost minimization subject to constraints. Also, it would be a good idea to explain the different steps involved in applying the method to particular problems. For example, minimization problems imply a different set up of conditions than maximization problems. A reliable reference on this is Chiang and Wainwright's textbook of mathematical economics.
The article needs a graphical ilustration of an example of functions defined over a set of inequality constraints.--
Forich (
talk)
03:13, 6 May 2008 (UTC)reply
How about finding a max or min value of f(x) on an interval [a, b] or perhaps a two dimensional simplex? The inequalities would be constraints on the domain of x. You could have similar constraints on the range (say f has to be less than or equal to another function g). That should yield an interesting problem graphically. --
KarlHallowell (
talk)
13:04, 14 May 2013 (UTC)reply
The article refers to active constraints without defining what it means by "active". I suppose this refers to conditions with non-zero mu and lambda?
Janez Demsar (
talk)
19:41, 31 August 2009 (UTC)reply
I think the article should reference (and compare/contrast with) the well known Fritz John conditions as well (see
| Bertsekas' Fritz John paper for some background ). Also, more elaboration on the Slater condition would be great, since this is one of the most used conditions.
Lavaka (
talk)
16:47, 16 September 2009 (UTC)reply
Sufficient conditions
Someone correct me if I'm wrong, but shouldn't the sufficient conditions involve the Hessian? I think it's something like: the Hessian is positive definate with respect to feasible search directions? It appears the sufficient conditions are just copy/pasted necessary conditions...
Alec.N (
talk)
08:11, 27 October 2008 (UTC)reply
The only difference between the necessary/sufficient conditions is that in the sufficient case f, g are convex and h is affine.
I've tried different encodings, but all I see at the end of the article (regularity conditions) are little squares rather than math (evidently, with different encoding you get different gibberish). E.g. "It can be shown that LICQ⇒MFCQ" etc. I went to the source, hoping that it was some simple omission, but this wasn't the case.
the Hessian matrix determines whether the region is convex or not, H(x)> 0 means that it is stricly convex H(x)≥ 0 the region is convex. Strict convexity ensures that the solution found is a global minimum and thus optimum otherwise it might simply be a saddle point. —Preceding
unsigned comment added by
86.163.157.227 (
talk)
11:18, 18 April 2009 (UTC)reply
First Order Necessary Conditions (FONC)
In the book Applied Optimization (2006) from Ross Baldick, the author almost makes no mention of the KKT conditions, and instead uses terms such as First Order Necessary Conditions (FONC), and Second Order Sufficient Conditions (SOSC). Are these terms used regularly in optimization? Do they warrant a mention in this article? ---
201.127.248.133 (
talk)
01:34, 10 February 2010 (UTC)reply
In view of the confusion regarding the signs in the Lagrangian, it would be helpful with a short discussion of the maximization case also.
Isheden (
talk)
08:15, 14 December 2011 (UTC)reply
How about some examples? Lagrange multipliers article, have multiple examples of using them to solve some optimizations. Similar simple examples could be created for this article. Does anybody have some external resources, books or articles, with sensible examples? --
91.213.255.7 (
talk)
03:45, 10 April 2012 (UTC)reply
I am nore sure, but the following KKT conditions in the economic example doesn't sound correct to me :
I think it should be a "=".
The source, which I have now added, uses the inequality version along with a condition that either the inequality holds with equality or the choice variable equals zero.
Loraof (
talk)
17:51, 10 April 2017 (UTC)reply
Second order necessary conditions?
I do not know what they are called but the second order conditions should be discussed more. Second order necessary conditions:
Hessian matrix of the objective function is positive semidefinite
Second order sufficient conditions:
Hessian matrix of the objective function is positive definite
Problem in the Mangasarian-Fromovitz constraint qualification conditions?
If I want to minimize under the constraints and , there is only
one feasible point . The gradients of the constraints and are positive-linearly independent
(the Mangasarian-Fromovitz condition, as stated in the table)
and yet, the KKT conditions are not necessary to certify the optimality of .
They actually do not hold in because there is no linear combination of and
that is equal to .
Daniel.porumbel (
talk)
13:14, 16 July 2017 (UTC)reply
Yes, but I understand from the table that the Mangasarian-Fromovitz condition (positive linearly independence) would be enough to derive the necessity of the KKT conditions, see the table in Section "Regularity conditions (or constraint qualifications)". In my example, the Mangasarian-Fromovitz constraint qualification is satisfied, yet the KKT conditions do not hold.
Daniel.porumbel (
talk)
13:14, 16 July 2017 (UTC)reply
Positive linear INdependence is the statement for the Mangasarian-Fromovitz condition. Your example has positive linear dependence since , which means the condition does not hold.
Zfeinst (
talk)
23:15, 16 July 2017 (UTC)reply
Thanks for the reply, but sorry, I understand from the article that I do not have positive linear dependence for and . I repeat the given dependence definition: () is positive-linear dependent if there exists not all zero such that . If and , what are the positive values of and so that ?
Daniel.porumbel (
talk)
13:51, 18 July 2017 (UTC)reply
In fact, one can find an analogous counterexample even for this second definition of positive linear dependence. Minimize under the constraints and .There is only one feasible point: . The gradients of the constraints in this point are and . They are positive-linearly independent according to the new definition. The Mangasarian-Fromovitz condition should imply the necessity of the KKT conditions, but they do not hold in . I repeat the new positive dependence definition: () is positive-linear dependent if there exists and an element such that . With this definition, and are positive linearly independent. So either I missed something, or there is something missing in the Mangasarian-Fromovitz conditions as written in the article.
Daniel.porumbel (
talk)
10:23, 19 July 2017 (UTC)reply
You are yet again correct. In Bertsekas "Nonlinear Programming" (2nd edition) page 329-330 defines MFCQ as a necessary condition by: Let be a local minimum of the problem where are continuously differentiable functions. If the gradients are linearly independent and there exists a vector such that and for all equality constraints and all active inequality constraints, then the KKT conditions are necessary.
Since your example only has equality constraints, this will require linear independence of the gradients (plus an additional condition), which is not satisfied. The text in the article should be updated to reflect this actual definition.
Zfeinst (
talk)
12:13, 19 July 2017 (UTC)reply
Thanks for this quick response. Indeed, even if I replace by , these new Mangasarian-Fromovitz conditions are not satisfied. The article should be updated.
Daniel.porumbel (
talk)
13:27, 19 July 2017 (UTC)reply
Actually, I think I managed to figure out what was on the mind of the first person who wrote the Mangasarian-Fromovitz condition in the table. Let us first simplify and consider there is no equality constraints and we generalize afterwards. The existence of some such that for all active inequality constraints is equivalent to the fact that there exist no not all zero such that . This is a consequence of the hyperplane separation theorem. This formulation is equivalent to saying that the 's are positive linearly independent, using the initial (not accurate as far as I can see) definition of positive linearly dependence. If there are some equality constraints , we need to project the gradients on the null space (kernel) of . For these projected gradients , there must be no not all zero such that . Anyway, the article should be updated.
Daniel.porumbel (
talk)
14:07, 20 July 2017 (UTC)reply
I was the one writing the first definition of MFCQ. The current definition of positive-linear dependence was wrong. I've removed this definition. — Preceding
unsigned comment added by
143.107.45.1 (
talk)
13:56, 5 April 2018 (UTC)reply
Problem with second-order sufficient conditions?
I have the feeling, the sufficient conditions should involve a test about positivity of the hessian in more than just one direction.
That is, till now, the text states a test
"The solution found in the above section is a constrained local minimum if for the Lagrangian,
then,
"
My strong impression is that, grammatically, the word "then" is superfluous, and it confuses (me). Also, the text reads as if the first formula is merely an apposition to or an explanation of "the Lagrangian".
Now, I understand that two formulas separated by a mere comma may make for an ugly layout. Therefore, I propose:
"The solution found in the above section is a constrained local minimum for the Lagrangian,