6.Bordered Hessian matrix

Bordered Hessian Matrix

Hessian matrix of   $f(x_1, x_2, \cdots , x_n)$ :

Bordered Hessian Matrix(경계 헤시안 행렬) of  the Lagrange- function(2013.12.02)  $L$ :

$L=f(x_1,x_2,\cdots , x_n)+\lambda_{1}g^{1}(x_1,x_2,\cdots , x_n)+\lambda_{2}g^{2}(x_1,x_2,\cdots , x_n)+\cdots$ $+\lambda_{m}g^{m}(x_1,x_2,\cdots , x_n)$ :

$\large Hb=\begin{pmatrix} L_{\lambda_{1}\lambda_{1}} & \cdots &L_{\lambda_{1}\lambda_{m}} & L_{\lambda_{1}x_{1}} & \cdots &L_{\lambda_{1}x_{n}} \\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\ L_{\lambda_{m}\lambda_{1}} &\cdots &L_{\lambda_{m}\lambda_{m}} & L_{\lambda_{m}x_{1}} & \cdots &L_{\lambda_{m}x_{n}} \\ L_{x_{1}\lambda_{1}} & \cdots &L_{x_{1}\lambda_{m}} &L_{x_{1}x_{1}} &\cdots &L_{x_{1}x_{n}} \\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\ L_{x_{n}\lambda_{1}}& \cdots& L_{x_{n}\lambda_{m}}&L_{x_{n}x_{1}}&\cdots&L_{x_{n}x_{n}} \end{pmatrix}$

$\large =\begin{pmatrix} 0 &\cdots &0 &g_1^1 & \cdots &g_n^1 \\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\ 0 & \cdots &0 &g_1^m &\cdots &g_n^m \\ g_1^1 &\cdots &g_1^m &f_{11}+\sum^m_{i=1}\lambda_{i}g_{11}^i & \cdots & f_{1n}+\sum^m_{i=1}\lambda_{i}g_{1n}^i\\ \cdots & \cdots &\cdots &\cdots &\cdots &\cdots \\ g_n^1 &\cdots &g_n^m &f_{n1}+\sum^m_{i=1}\lambda_{i}g_{n1}^i &\cdots &f_{nn}+\sum^m_{i=1}\lambda_{i}g_{nn}^i \end{pmatrix}$

If the constraints are linear(제한함수가 선형일 경우) -- as  $g_{ij}=0 ,i=1,\cdots ,n , j=1,\cdots,n$  the bordered Hessian becomes :

$\large Hb=\begin{pmatrix} 0 &\cdots &0 &g_1^1 & \cdots &g_n^1 \\ \cdots &\cdots &\cdots &\cdots &\cdots &\cdots \\ 0 & \cdots &0 &g_1^m &\cdots &g_n^m \\ g_1^1 &\cdots &g_1^m &f_{11} & \cdots & f_{1n}\\ \cdots & \cdots &\cdots &\cdots &\cdots &\cdots \\ g_n^1 &\cdots &g_n^m &f_{n1} &\cdots &f_{nn} \end{pmatrix}$

In particular, given the  function as before:  adding a constraint (linear)(하나의 선형제한함수일 경우) function such that:    the bordered Hessian appears as (참고: http://en.wikipedia.org/wiki/Hessian_matrix 2013.12.03)

Theorem6 (Bordered Hessian Test)

For the bordered Hessian matrix of lagrage function with $f(x_1, x_2, \cdots , x_n)$ and m constraints $g^1(x_1 , x_2, \cdots, x_n),g^2(x_1 , x_2, \cdots, x_n),\cdots,g^m(x_1 , x_2, \cdots, x_n)$ :

1) The Hessian matrix of $f(x_1, x_2, \cdots , x_n)$  at critical points is negative definite (i. e. $f$ has local maximum(극대)) under the constraints

iff its Leading principal minor of bordered Hessian alternative in signs and  $(-1)^{n}\rm det(\it Hb)>\rm0$

2) The Hessian matrix of $f(x_1, x_2, \cdots , x_n)$  at critical points is positive definite (i. e. $f$ has local minimum(극소)) under the constraints

iff its Leading principal minor of bordered Hessian are all negative and also  $\rm det(\it Hb)<\rm0$.

The proof of bordered Hessian Test : artaci, http://goo.gl/IIkp5m 2013.12.02
Information of bordered Hessian Matrix : Ronald wendner, http://goo.gl/PK6Fgu 2013. 12.02
Application Example of Bordered Hessian matrix : Tianxi Wang, http://goo.gl/E8OeIJ 2013.12.02

Example) Find the local maximum and local minimum points of

$f(x,y)=100-x^2y^2$

subject to the constraint  $g(x,y)=x+y-4=0$. (The same example of HOME application)

Sol)

Find the critical points of  $f(x,y)$ under the constraint  $g(x,y)$ using the Lagrange multiplier.

Then,  $L(f,g)=f(x,y)+tg(x,y)=100-x^2y^2+t(x+y-4)$.

Then, the critical points are  $(x,y,t)=(2,2,16) ,(4,0,0),(0,4,0)$.

The Bordered Hessian matrix of $f$ under $g$ is  $BH=\begin{bmatrix} 0 &1 &1 \\ 1 &-2y^2 &-4xy \\ 1 & -4xy & -2x^2 \end{bmatrix}$ .

At  $(x,y)=(4,0)$ ,  $\rm det(\it BH)=\rm 32>0$  and  $\rm det(\it SBH)=\rm -1<0$

Thus $f$ has local maximum (i.e. negative definite) at $(x,y)=(4,0)$ by Bordered Hessian Test.

At  $(x,y)=(0,4)$ ,  $\rm det(\it BH)=\rm 32>0$  and  $\rm det(\it SBH)=\rm -1<0$

Thus $f$ has local maximum (i.e. negative definite) at $(x,y)=(0,4)$ by Bordered Hessian Test.

At  $(x,y)=(2,2)$ ,  $\rm det(\it BH)=\rm -16<0$ and  $\rm det(\it SBH)=\rm -1<0$

Thus $f$ has local minimum (i.e. positive definite) at $(x,y)=(2,2)$ by Bordered Hessian Test.

http://goo.gl/vxcrD3 2013.12.03

Example)

Find the local maximum and local minimum point of

$\small f(x,y)=x^2+y^2$

subject to the constraint  $\small g(x,y)=2x+y=1$ .

Example)

Find the local maximum and local minimum point of

$\small f(x,y,z)=x^2+y^2+z^2$

subject to the constraint  $\small g(x,y,z)=2x+y+z=1$ .

일반적인 경우)

http://goo.gl/74YCl8 .2013.12.03

다음은  제한하는 함수가 2개 있을 경우에 이변수함수의 극소값과 극대값을 판단해주는 interact입니다.

다음은 제한함수가 2개 있을 경우 삼변수 함수의 극대값과 극소값을 판단해주는 interact입니다.