Short Communication
A linear programming proof of the second order conditions of non-linear programming

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

Abstract

In this note we give a new, simple proof of the standard first and second order necessary conditions, under the Mangasarian–Fromovitz constraint qualification (MFCQ), for non-linear programming problems. We work under a mild constraint qualification, which is implied by MFCQ. This makes it possible to reduce the proof to the relatively easy case of inequality constraints only under MFCQ. This reduction makes use of relaxation of inequality constraints and it makes use of a penalty function. The new proof is based on the duality theorem for linear programming; the proofs in the literature are based on results of mathematical analysis. This paper completes the work in a recent note of Birbil et al. where a linear programming proof of the first order necessary conditions has been given, using relaxation of equality constraints.

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 x of an NLP problem that satisfies a mild constraint qualification (MCQ), which is slightly weaker than MFCQ. We assume that x 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 x. 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 x 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 formc,xmin,Ax=b,x0andb,ymax,ATyc.Here A is an m×n-matrix, c is an n-dimensional column vector, b is an m-dimensional column vector, x is a variable n-dimensional column vector, and ·,· denotes the standard inner product on Rk, with k equal to m or n, given by v,w=i=1kviwi.

Section snippets

The NLP problem with inequality constraints

We consider the non-linear programming (NLP) problem with inequality constraintsf(x)min,gj(x)0,j=1,,p,where f,gj:RnR,j=1,,p, are C2-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 h(x)=0 by two inequality constraints, h(x)0,-h(x)0.

The mild constraint qualification

Let x 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 ε>0 such that f(x)f(x) for all feasible points x of problem (P), (P) for which |x-x|ε; this is possible as x is a point of local minimum of (P), (P). Choose an infinite sequence of positive numbers (δk)k that converges to 0, and choose for each k a point of global minimum xk for the auxiliary problemf(x)+π(x)min,gj(x)δk,j=1,,p,|x-x|ε,where 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)

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

Cited by (0)

View full text