From: "R.G. Vickson" <rvickson@engmail.uwaterloo.ca>
Subject: Re: Lagrange multiplier 2nd Der test
Date: Tue, 28 Sep 1999 18:07:21 -0400
Newsgroups: sci.math
Keywords: What is the 2nd derivative test for Lagrange multipliers?

James Park wrote:

> Does anyone know what the 2nd derivative test is for a lagrange multiplier
> problem where there are multiple constraints.  For the single constraint,
> the test is based on the hessian of h(X,k)=f(X)-k(g(X)-c) where f(X) is
> the function to optimize,k is the multiplier and g(X)=c is the constraint.
> I assume that for multiple constraints it would be based on the hessian of
> h(X,k1,...kn)=f(X)-k1(g1(X)-c1)...-kn(gn(X)-cn) but it is not clear to me
> what the test would be, since I don't really understand the criteria for
> the single test either.

Some things are complicated and just have to be learned. Anyway, here goes:

Suppose X*=(x1*, ..., xn*) is optimal in the problem min f(X), subject to
g1(X)-c1=0, ..., gm(X)-cm=0, and that the gradient vectors
grad [g1(X)], ..., grad[gm(X)]  are linearly independent at X=X*. Then, there
exist
k1, ..., km such grad [L(X)] = 0 at X=X*, where L=f-k1*(g1-c1)-...-km*(gm-cm).

So far, so good; the above are the necessary first-order conditions.

Now suppose twice-continuously differentiable f, c1, ..., cm, etc. Define a
subspace
D = { p in E^n : p^T grad[c1(X*)]=0, ..., p^T grad[cm(X*)]=0} = set of
feasible directions at X*. D is a linear subspace of E^n.

A 2nd order necessary condition for X* to be a constrained minimum is that
H = the Hessian of L at X=X* be positive semi-definite on the subspace D (that

is, that p^T H p be >= 0 for all p in D). This can be tested by appropriate
projections into lower dimensions.

A second order for X* to be a strict local minimum is that H be positive
definite in D.

[That should be: "A second order sufficient condition for X* to be ..." --djr]

Some numerical optimization codes implement tests of this type within their
basic workings.





>
> Thanks,
> J.D. Park