An elementary proof of the Karush–Kuhn–Tucker theorem in normed linear spaces for problems with a finite number of inequality constraints

Abstract

We present an elementary proof of the Karush–Kuhn–Tucker theorem for the problem with a finite number of nonlinear inequality constraints in normed linear spaces under the linear independence constraint qualification. Most proofs in the literature rely on advanced concepts and results such as the convex separation theorem and Farkas, lemma. By contrast, the proofs given in this article, including a proof of the lemma, employ only basic results from linear algebra. The lemma derived in this article represents an independent theoretical result.

Keywords:

• Karush–Kuhn–Tucker theorem
• inequality-constrained optimization
• optimality conditions
• constraint qualifications
• linear independence

Acknowledgements

The authors thank Stephen E. Wright and the anonymous reviewers for the valuable comments and suggestions which helped us improve the content and presentation of this article. The work of the second author is partially supported by the Russian Foundation for Basic Research (project no. 08-01-00619), and by the Program of the State Support of Leading Scientific Schools (project no. NSh 5073.2008.1).