**Open Journal of Optimization**

Vol.04 No.02(2015), Article ID:56417,3 pages

10.4236/ojop.2015.42006

A Short Derivation of the Kuhn-Tucker Conditions

Yoshihiro Tanaka

Graduate School of Economics and Business Administration, Hokkaido University, Sapporo, Japan

Email: tanaka@econ.hokudai.ac.jp

Copyright © 2015 by author and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

Received 3 April 2015; accepted 16 May 2015; published 19 May 2015

ABSTRACT

The Kuhn-Tucker conditions have been used to derive many significant results in economics. However, thus far, their derivation has been a little bit troublesome. The author directly derives the Kuhn-Tucker conditions by applying a corollary of Farkas’s lemma under the Mangasarian- Fromovitz constraint qualification and shows the boundedness of Lagrange multipliers.

**Keywords:**

Farkas’s Lemma, Kuhn-Tucker Conditions, The Method of Lagrange Multipliers, Economics

1. Introduction

The Kuhn-Tucker conditions have been used to derive many significant results in economics, particularly in decision problems that occur in static situations, for instance, to show the existence of an equilibrium for a competitive economy (Negishi [1] ), to carry out the first-order approach to principal-agent problems (Rogerson [2] ), and to examine the need for land reform (Grossman [3] ). Also, the Kuhn-Tucker conditions and/or the method of Lagrange multipliers are usually contained in standard microeconomics textbooks, for instance, Mas-Colell, Whinston and Green [4] , where the Kuhn-Tucker conditions for the problem with both inequality and equality constraints are discussed.

The Kuhn-Tucker conditions for the optimization problem with inequality and equality constraints have a comprehensive form that incorporates the method of Lagrange multipliers (introduced by Lagrange in 1788) in a natural way; therefore, the simple derivation of the Kuhn-Tucker conditions would shed light on the problem’s true nature.

In this paper, the Kuhn-Tucker conditions under the Mangasarian-Fromovitz constraint qualification are derived directly by applying a corollary of Farkas’s lemma without resorting to the Fritz John conditions and the boundedness of Lagrange multipliers is also shown.

2. Preliminaries

The problem to be addressed is as follows:

where, , and are continuously Fréchet differentiable functions, and, (). If there are no inequality (equality) constraints, we think that ().

Here, we should pay attention to the fact that the problem (P) naturally includes the optimization problem with equality constraints considered by Lagrange in the 18th century.

We postulate the following Mangasarian-Fromovitz constraint qualification (MF) (Mangasarian and Fromovitz [5] ) in association with (P). We define.

(MF) For, , are linearly independent, and there exists an s.t. and.

Remarks

The linearly independent constraint qualification, which is usually assumed in practice, implies (MF) (see Nocedal and Wright [6] ).

(MF) is equal to the Cottle constraint qualification without the presence of equality constraints, and if the problem (P) is a concave program without equality constraints, the Slater constraint qualification implies the Cottle constraint qualification (Bazaraa and Shetty [7] ).

Finally, we recall the following result to the linear system including equalities for the sake of convenience.

Lemma 1. ([7] , Corollary 2 to Theorem 2.3.5) For, , and, either

(a), , ,

or

(b), and,

but never both.

3. Result

We now establish the main result, which differs from [7] Theorem 5.3.1 in that our result includes complementarity conditions and the boundedness of Lagrange multipliers under (MF).

Theorem 1. Suppose that is a local solution for (P), and that the constraint qualification (MF) holds at. Then, it holds that for and,

(1)

and, are bounded.

Proof. At a local solution, if we choose in the feasible region such that,

which shows that satisfies, and,.

Then, for a local solution, it follows that

(2)

does not hold, since, if so, as for, which con-

tradicts the local optimality of at.

Note that (MF) guarantees the existence of such from the implicit function theorem ([8] , Appendix D-3 with and) if; otherwise (2) does not hold for. By applying Lemma 1 to (2) and (MF), even if the active constraints are empty, we obtain

(3)

or, equivalently,

for,.

The rest part of the proof is as follows. From (3) we obtain

So, if,

and if, vanishes. In any case, (3) reduced to

Since, are linearly independent by (MF), is determined to a single bounded vector.

Example 1.

Consider the problem

with an optimal solution. At, the linearly independent constraint qualification does not hold, whereas (MF) holds for.

Indeed, (MF) is valid for problems with a number of inequality constraints and admits feasible directions around in the orthogonal complementary space of,.

4. Concluding Remarks

In this paper, the Kuhn-Tucker conditions under the Mangasarian-Fromovitz constraint qualification were derived directly by applying a corollary of Farkas’s lemma without resorting to the Fritz John conditions, or without introducing the Bouligand tangent cone, and the boundedness of Lagrange multipliers was also shown.

Considerable effort has been devoted to the generalization of Farkas’s lemma. However, what seems to be lacking is a discrete version of Farkas’s lemma under a mild condition; such a version would be theoretically meaningful and would be help solve the discrete optimization problems that emerge in the economics studying indivisible goods.

References

- Negishi, T. (1960) Welfare Economics and Existence of an Equilibrium for a Competitive Economy. Metroeconomica, 12, 92-97. http://dx.doi.org/10.1111/j.1467-999X.1960.tb00275.x
- Rogerson, W.P. (1985) The First-Order Approach to Principal-Agent Problems. Econometrica, 53, 1357-1367. http://dx.doi.org/10.2307/1913212
- Grossman, H.I. (1994) Production, Appropriation, and Land Reform. American Economic Review, 84, 705-712.
- Mas-Colell, A., Whinston, M.D. and Green, J.R. (1995) Microeconomic Theory. Oxford University Press, New York.
- Mangasarian, O.L. and Fromovitz, S. (1967) The Fritz John Necessary Optimality Conditions in the Presence of Equality and Inequality Constraints. Journal of Mathematical Analysis and Applications, 17, 37-47. http://dx.doi.org/10.1016/0022-247X(67)90163-1
- Nocedal, J. and Wright, S.J. (2006) Numerical Optimization. 2nd Edition, Springer, Berlin.
- Bazaraa, M.S. and Shetty, C.M. (1979) Nonlinear Programming: Theory and Algorithms. 2nd Edition, Wiley, New York.
- Mangasarian, O.L. (1994) Nonlinear Programming. SIAM, Philadelphia. http://dx.doi.org/10.1137/1.9781611971255