# Constrained Optimization: Is the condition for definiteness of a matrix different for a bordered hessian matrix?

I am asked to find the definiteness of the bordered Hessian matrix obtained while optimizing the following problem: $$U(x,y) = xy + x$$ subject to the constraint $$6x + 2y = 110$$

The Bordered Hessian takes the form:

$$\begin{pmatrix} 0 & g_x & g_y \\ g_x & f_{xx} & f_{xy} \\ g_y & f_{yx} & f_{yy} \\ \end{pmatrix}$$

Where $$g$$ is the constraint function and $$f$$ is the objective function. $$g_x$$ is the constraint function differentiated with respect to $$x$$ and other notation is similarily defined. The matrix I get is:

$$\begin{pmatrix} 0 & -6 & -2 \\ -6 & 0 & 1 \\ -2 & 1 & 0 \\ \end{pmatrix}$$

The Leading Principal Minors of this matrix are: 0, -36, 24. So we have nothing from the leading principal minors test (for positive definite, they should all be positive. For negative definite they should alternate in sign with the first one being negative).

So we will have to go on and check for semi-definiteness. But the solution I have actually stops right here and concludes that the matrix is negative definite, and therefore there is a maximum.

Upon proceeding with the semi definiteness test, we have:

The First Order Principal Minors are: 0, 0, 0. The Second Order Principal Minors are: -1, -2, -36 The Third Order Principal Minor is: 24

They're not all positive or equal to 0 (which'd make them positive semidefinite), nor are they negative for odd orders and positive for even orders (which would make them negative semidefinite).

So the matrix is indefinite, and any critical point we find is a saddle point.

Plugging this problem in at Wolfram shows that there is a maximum point, and that there are no saddle points. Where am I going wrong?

• You’re not going wrong—the matrix you give is indefinite (can be quickly checked by computing the eigenvalues) Commented May 11, 2019 at 4:31
• For the bordered Hessian the condition is the opposite of the normal characterization. If $\det(H) > 0$ then there is a local maximum and if $\det(H) < 0$ is a local minimum. In our case $\det(H) = 24$ so there is a local maximum. In time. All this can be demonstrated but is a bit long... Commented May 11, 2019 at 10:42

Focusing our attention in this two dimensional problem, we can formulate it as

Stationary points of

$$L(x,y,\lambda) = f(x,y)+\lambda(y-g(x))$$

or

$$\max_{x} f(x,g(x))$$

In the first case we have the bordered Hessian

$$H_g = \left(\begin{array}{ccc}0 & -g' & 1\\ -g' & f_{xx}& f_{xy}\\ 1& f_{yx} & f_{yy}\end{array}\right)$$

and for qualification

$$\det(H_g) = -(f_{xx}+2g'f_{xy}+g'^2f_{yy})$$

in the second case we have

$$\frac{d^2}{dx^2}f(x,g(x)) = g''f_y + f_{xx}+2g'f_{xy}+g'^2f_{yy}$$

but $$g'' = 0$$ because $$g(x)$$ is linear so the qualification from $$\frac{d^2}{dx^2}f(x,g(x))$$ and from $$\det(H_g)$$ have opposite signs, according to my previous comment.

In our case $$f(x,y) = x(y+1)$$ and $$y = g(x) = \frac{110-6x}{2}$$ giving

$$g' = -3, f_{xx} = f_{yy} = 0, f_{xy} = 1$$

hence

$$\det(H_g) = 6,\ \ \frac{d^2}{dx^2}f(x,g(x)) =-6$$

characterizing a local maximum.