Finding the saddle points of $F(x_1,x_2,x_3,y_1,y_2,y_3)=(x_1-2x_2+x_3)y_1+(2x_1-2x_3)y_2$+$(-x_1+x_2)y_3$ subject to the constraints $x_1+x_2+x_3=1, y_1+y_2+y_3=1$. Show that the saddle point is $x=(\frac{1/3}{1/3},\frac{1/3}{1/3},\frac{1/3}{1/3}),y=(\frac{2}{7},\frac{1}{7},\frac{4}{7})$.
I know how to find the saddle point of a function with two variable by using $\Delta=(f_{12})^2-f_{11}f_{22}$, then when $\Delta>0$ the point is a saddle point.
But for this question, by using the constraints, we can reduce the variables from 6 to 4, but still can not use the $\Delta$ formula, and this question requires not to use lagrange multiplier. Thanks.


At a saddle point, all of the partial derivatives are 0. This leads to a system of equations: \begin{align} x_1 -2x_2 +x_3=0,\tag{1}\\ 2x_1 -2x_3=0,\tag{2}\\ x_2-x_1=0,\tag{3}\\ y_1+2y_2-y_3=0, \tag{4}\\ -2y_1 +y_3=0,\tag{5}\\ y_1-2y_2=0. \tag{6} \end{align} Adding 1 to both sides of equation (4) leads to \begin{equation} 2 y_1 = 1-3 y_2. \tag{7} \end{equation}

Solving for $y_1$ from equation (6) and substituting in (7) leads to $y_2= \frac{1}{7}$ and consequently $y_1=2y_2=\frac{2}{7}$ and $y_3=2y_1=\frac{4}{7}$.

Similarly, we can subtract 1 from both sides of equation (1) and use the constraint for x, which leads to $x_2=\frac{1}{3}$ and consequently from (3), $x_1=x_2=\frac{1}{3}$. Finally, from (3), we have $x_3=x_1=\frac{1}{3}$.

EDIT: Computing the Hessian matrix yields: \begin{equation} H = \begin{pmatrix} 0 & 0 & 0 & 1 & 2 & -1 \\ 0 & 0 & 0 & -2 & 0 & 1\\ 0 & 0 & 0 & 1 & 0 & 0\\ 1 & -2 & 1 & 0 & 0 & 0\\ 2 & 0 & 0 & 0 & 0 & 0\\ -1 & 1 & 0 & 0 & 0 & 0 \end{pmatrix}. \end{equation} Diagonalizing gives us the characteristic polynomial \begin{equation} \lambda^6-12\lambda^4 +27\lambda^2 -4=0. \end{equation}

This polynomial has a $\lambda \rightarrow -\lambda$ symmetry. So if we can find one non-zero real solution, we automatically show that the Hessian is indefinite (There are both positive and negative solutions). Therefore the critical point above is indeed a saddle point.


In case you find it difficult to actually find the roots of the polynomial, substitute $\rho=\lambda^2$, this gives \begin{equation} \rho^3-12\rho^2 +27\rho -4=0. \end{equation}

Now, using the fact that complex roots come in pairs and that we can see that zero is not a solution, we can deduce that there is at least one real solution of the cubic $\rho_0$ and therefore two opposing sign solutions $\lambda_{+/-} = \pm \sqrt{|\rho_0|}$.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks, but this only shows that the given point is a critical point, not proves it's a saddle point? $\endgroup$ – Cathy Jun 3 at 20:31
  • $\begingroup$ That's true. You can try the Hessian test after you have shown that it is a critical point? Seems like you should get an indefinte matrix - I haven't tried. $\endgroup$ – Stratiev Jun 3 at 20:44
  • $\begingroup$ I haven't learnt Hessian test yet, so there may exist some way to prove it's a saddle point without using Hessian test? $\endgroup$ – Cathy Jun 3 at 20:54
  • $\begingroup$ The expression that you defined as $\Delta$ is the determinant of the Hessian for a function of two variables. It's just that in this case you'd get a 6x6 matrix defined by the second order partial derivatives. It will be a sparse matrix with a few integer entries. $\endgroup$ – Stratiev Jun 3 at 21:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.