Short CommunicationA linear programming proof of the second order conditions of non-linear programming
Introduction
In a recent note [1], Birbil, Frenk and Still have given an elementary proof of the first order conditions of non-linear programming problems with equality and inequality constraints, which is based on the duality theorem for linear programming. Initially, there seemed to be an obstacle to give such a proof of the second order conditions.
However, here we show how to give a proof of the second order conditions that is based on the duality theorem for linear programming. There are various versions of this result: here we consider the second order conditions with non-fixed multipliers under the Mangasarian–Fromovitz constraint qualification (MFCQ). In fact, we work under a slightly weaker constraint qualification, the mild constraint qualification (MCQ): this allows to reduce to the case of inequality constraints only, by the naive approach of rewriting each equality constraint as two inequality constraints. This technical point is of interest, as earlier it was considered that this naive approach is useless as far as necessary conditions are concerned (cf. [1]). Compared to [2], the method of proof is simplified further by means of the following device: in the present note the inequality constraints are relaxed, rather than the equality constraints. As these simplifications are of interest, the proof of the first order conditions is included.
The Mangasarian–Fromovitz constraint qualification was introduced in [5]; the second order conditions under MFCQ are for example given in Ref. [3]. In the extensive literature on the second order conditions several variants of the second order conditions and the constraint qualifications are given; there is a trade-off between the strength of the second order conditions and of the constraint qualifications. Proofs are based on results from mathematical analysis such as the implicit function theorem or properties of metric regularity. Recent accounts of second order optimality conditions for NLP problems are given in Refs. [4], [6].
The strategy of the proof given in the present paper is as follows. We consider a point of local minimum of an NLP problem that satisfies a mild constraint qualification (MCQ), which is slightly weaker than MFCQ. We assume that is a point of global minimum, as we may without restriction of generality to the argument: by restriction to a sufficiently small ball. Then, by replacing each equality constraint by two inequality constraints, we rewrite the problem as an NLP problem (P), (P) with inequalities only. MCQ still holds after this reformulation. Thus a reduction of the proof to the case of inequalities only has been established. Then an infinite sequence of auxiliary NLP problems with inequalities only is constructed. A choice of a point of global minimum for each one of these problems is made. This sequence of problems and points has the following properties. MFCQ holds at the points of global minimum, and the points of global minimum tend to . The auxiliary problems are defined as follows: all (inequality) constraints of (P), (P) are relaxed, and a penalty function is added. As the NLP problems have inequalities only and, moreover, satisfy MFCQ, a straightforward variational argument gives the second order necessary conditions for these problems in primal form. These are then formulated in terms of a linear programming (LP) problem. Then the duality theorem for LP is applied. This gives the second order necessary conditions in dual form, in terms of multipliers. Taking the limit of these necessary conditions turns out to lead to the required second order conditions for the point of minimum of the problem (P), (P).
Finally, we recall the duality theorem for LP: for a pair of dual LP problems, both have the same optimal value, provided not both are infeasible, and moreover, if this value is finite, then both have an optimal solution. In standard form, a pair of dual LP problems has the following formandHere is an -matrix, is an n-dimensional column vector, is an m-dimensional column vector, is a variable n-dimensional column vector, and denotes the standard inner product on , with k equal to m or n, given by .
Section snippets
The NLP problem with inequality constraints
We consider the non-linear programming (NLP) problem with inequality constraintswhere , are -functions. This will not restrict the generality of the treatment of optimality conditions, as the main result will be strong enough to be applicable to NLP problems that have equality constraints as well, by means of the replacement of each equality constraint by two inequality constraints, .
The mild constraint qualification
Let be a feasible point of (P), (P). We
Proof of Theorem 1 in the special case that MFCQ holds
In this section we prove Theorem 1 under MFCQ.
Proof of Theorem 1 in the general case
The aim of this section is to prove Theorem 1 in the general case, that is, under the assumption of MCQ. Proof Choose such that for all feasible points of problem (P), (P) for which ; this is possible as is a point of local minimum of (P), (P). Choose an infinite sequence of positive numbers that converges to 0, and choose for each k a point of global minimum for the auxiliary problemwhere the ‘penalty function’ is defined
Acknowledgement
I would like to thank Hans Frenk for drawing my attention to the unsolved problem of finding an LP proof for the second order conditions of non-linear programming.
References (6)
- et al.
An elementary proof of the Fritz–John and Karush–Kuhn–Tucker conditions in nonlinear programming
European J. Oper. Res.
(2007) - et al.
The Fritz John necessary optimality conditions in the presence of equality and inequality constraints
Journal of Mathematical Analysis and Applications
(1967) Second-order and related extremality conditions in nonlinear programming
JOTA
(1980)