Short Communication
An elementary proof of the Fritz-John and Karush–Kuhn–Tucker conditions in nonlinear programming

https://doi.org/10.1016/j.ejor.2006.04.012Get rights and content

Abstract

In this note we give an elementary proof of the Fritz-John and Karush–Kuhn–Tucker conditions for nonlinear finite dimensional programming problems with equality and/or inequality constraints. The proof avoids the implicit function theorem usually applied when dealing with equality constraints and uses a generalization of Farkas lemma and the Bolzano-Weierstrass property for compact sets.

Introduction

Let A be an m × n matrix with rows ak, 1  k  m, bRm an m-dimensional vector, and fi:RnR, 0  i  q some non-affine, continuously differentiable functions. We consider the optimization problemmin{f0(x):xFP},FP{xRn:akxbk,1km,fi(x)0,1iq},and the program including equalitiesmin{f0(x):xFQ},FQFP{xRn:hj(x)=0,1jr},where the functions hj:RnR, 1  j  r, are non-affine and continuously differentiable.

Two basic results covered in every course on nonlinear programming are the Fritz-John (FJ) and Karush–Kuhn–Tucker (KKT) necessary conditions for the local minimizers of optimization problems (P), (Q) [7], [8], [9]. Denoting the nonnegative orthant of Rl by R+l, the FJ necessary conditions for problem (P) are given by the following: If xP is a local minimizer of problem (P), then there exist (see for example [2], [5]) vectors 0λR+q+1 and νR+m satisfyingi=0qλifi(xP)+k=1mνkak=0,λifi(xP)=0,1iqandνk(akxP-bk)=0,1km.For optimization problem (Q) the resulting FJ conditions are as follows: If xQ is a local minimizer of problem (Q), then there exist (see for example [2], [5]) vectors (λ,ν)R+q+1+m, μRr with (λ, μ)  0 satisfyingi=0qλifi(xQ)+j=1rμjhj(xQ)+k=1mνkak=0,λifi(xQ)=0,1iqandνk(akxQ-bk)=0,1km.If λ0 given in conditions (FJP), (FJQ) can be chosen positive, then the resulting necessary conditions are called the KKT conditions for problems (P), (Q), respectively. A sufficient condition for λ0 to be positive is given by a so-called first-order constraint qualification. In Section 2 we first give an elementary proof of the FJ and KKT conditions for problem (P). Then the same proof is given for optimization problem (Q) by using a perturbation argument but avoiding the implicit function theorem.

Section snippets

The FJ and KKT conditions for problems (P) and (Q)

For δ > 0 and x¯Rn, let N(x¯,δ) denote a δ-neighborhood of x¯ given byN(x¯,δ){xRn:x-x¯δ}.A vector xP is called a local minimizer of optimization problem (P) (respectively, for optimization problem (Q) if xPFP (respectively, xPFQ) and there exists some δ > 0 such that f0(xP)  f0(x) for every xFPN(xP,δ) (respectively, xFQN(xP,δ)).

We introduce the active index sets I(x): = {1  i  q : fi(x) = 0} and K(x)={1km:akx=bk}, and denote by B(x), the matrix consisting of the corresponding active rows ak,k

Conclusion

In this note we have shown that the basic results in nonlinear programming are a natural and direct consequence of basic results in linear programming and analysis. In our proof we could avoid the implicit function theorem usually applied in the proof of the FJ conditions for problem (Q) (see for example [2], [5]). The proof of the implicit function theorem [11] and its understanding is in general difficult for undergraduate/graduate students in the applied computational sciences. This concern

References (11)

  • M. Avriel et al.

    Generalized Concavity

    (1988)
  • M.S. Bazaraa et al.

    Nonlinear Programming: Theory and Algorithms

    (1993)
  • D.P. Bertsekas

    Nonlinear Programming

    (1995)
  • V. Chvátal

    Linear Programming

    (1999)
  • U. Faigle et al.

    Algorithmic Principles to Mathematical Programming

    (2002)
There are more references available in the full text version of this article.

Cited by (0)

View full text