Short CommunicationAn elementary proof of the Fritz-John and Karush–Kuhn–Tucker conditions in nonlinear programming
Introduction
Let A be an m × n matrix with rows , 1 ⩽ k ⩽ m, an m-dimensional vector, and , 0 ⩽ i ⩽ q some non-affine, continuously differentiable functions. We consider the optimization problemand the program including equalitieswhere the functions , 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 by , 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 and satisfyingFor 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 , with (λ, μ) ≠ 0 satisfyingIf λ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 , let denote a δ-neighborhood of given byA vector xP is called a local minimizer of optimization problem (P) (respectively, for optimization problem (Q) if (respectively, ) and there exists some δ > 0 such that f0(xP) ⩽ f0(x) for every (respectively, .
We introduce the active index sets I(x): = {1 ⩽ i ⩽ q : fi(x) = 0} and , and denote by B(x), the matrix consisting of the corresponding active rows
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)
- et al.
Generalized Concavity
(1988) - et al.
Nonlinear Programming: Theory and Algorithms
(1993) Nonlinear Programming
(1995)Linear Programming
(1999)- et al.
Algorithmic Principles to Mathematical Programming
(2002)