3
$\begingroup$

I have $$Z=f(x_1 ,x_2 ,x_3 ,... ,x_n)$$ function and $$\left[\begin{array}{r}c_1=g_1(x_1 ,x_2 ,x_3 ,... ,x_n) \\c_2=g_2(x_1 ,x_2 ,x_3 ,... ,x_n)\\c_3=g_3(x_1 ,x_2 ,x_3 ,... ,x_n) \\...\\c_m=g_m(x_1 ,x_2 ,x_3 ,... ,x_n) \end{array}\right]$$ constraints. How can I know critical points are maximized or minimized with Hessian Matrix(bordered matrix)? I need to know it for use to solve numeric problems only not for prove. In other word, how can I know that critical points (that had sound by first order condition. Setting derivatives of Lagrange function to zero ) are Maximum, Minimum or inflection points via Hessian Matrix?

$\endgroup$
  • $\begingroup$ As far as I can see this is pretty standard optimization. But maybe the above formulation is too general for people to say something interesting about it. $\endgroup$ – Han de Bruijn Jan 5 '14 at 12:55
  • $\begingroup$ I am interesting on like this uni-graz.at/ronald.wendner/SOC_Hessian.pdf $\endgroup$ – Huseyin Jan 5 '14 at 14:58
  • $\begingroup$ Is there any reply to me? $\endgroup$ – Huseyin Jan 22 '14 at 23:18
  • $\begingroup$ @Huseyin please consider revising your question if you want to get nice answers. The question in its current for is not concrete.. $\endgroup$ – Seyhmus Güngören Jan 30 '14 at 12:29
  • $\begingroup$ I had changed it. $\endgroup$ – Huseyin Jan 30 '14 at 15:32
1
+50
$\begingroup$

I'm going to use the notation \begin{equation} f(x) := f(x_1, x_2, \ldots, x_n) \end{equation} and \begin{equation} g(x) = \left[\begin{array}{c} g_1(x) \\ \vdots \\ g_m(x) \end{array}\right] \end{equation} along with \begin{equation} c = \left[\begin{array}{c} c_1 \\ \vdots \\ c_m\end{array}\right] \end{equation} to represent all of your constraints compactly as \begin{equation} g(x) = c. \end{equation}

You are correct in forming the bordered Hessian matrix because this is a constrained problem. Note that the bordered Hessian differs from the Hessian used for unconstrained problems and takes the form

\begin{equation} H = \left[\begin{array}{ccccc} 0 & \frac{\partial g}{\partial x_1} & \frac{\partial g}{\partial x_2} & \cdots & \frac{\partial g}{\partial x_n} \\ \frac{\partial g}{\partial x_1} & \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1 \partial x_2} & \cdots & \frac{\partial^2}{\partial x_1 \partial x_n} \\ \frac{\partial g}{\partial x_2} & \frac{\partial^2 f}{\partial x_2 \partial x_1} & \frac{\partial^2 f}{\partial x_2^2} & \cdots & \frac{\partial^2 f}{\partial x_2 \partial x_n} \\ \frac{\partial g}{\partial x_3} & \frac{\partial^2 f}{\partial x_3 \partial x_1} & \frac{\partial^2 f}{\partial x_3 \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_3 \partial x_n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ \frac{\partial g}{\partial x_n} & \frac{\partial^2 f}{\partial x_n \partial x_1} & \frac{\partial^2 f}{\partial x_n \partial x_2} & \cdots & \frac{\partial^2 f}{\partial x_n^2} \end{array}\right] \end{equation} where the $0$ in the upper-left represents an $m\times m$ sub-matrix of zeros and we've added $m$ columns on the left and $m$ rows on top.

To determine if a point is a minimum or a maximum, we look at $n - m$ of the bordered Hessian's principal minors. First we examine the minor made up of the first $2m+1$ rows and columns of $H$ and compute its determinant. Then we look at the minor made up of the first $2m + 2$ rows and columns and compute its determinant. We do the same for the first $2m+3$ rows and columns, and we continue doing this until we compute the determinant of the bordered Hessian itself.

A sufficient condition for a local minimum of $f$ is to have all of the determinants we computed above have the same sign as $(-1)^m$. A sufficient condition for a local maximum of $f$ is that the determinant of the smallest minor have the same sign as $(-1)^{m-1}$ and that the determinants of the principal minors (in the order you computed them) alternate in sign.

$\endgroup$
  • $\begingroup$ I think a numeric example should explore it. For example in the case of 7 variable and 3 constrain. $\endgroup$ – Huseyin Jan 30 '14 at 20:22
  • $\begingroup$ @Huseyin Do you need further clarification on how to do that, or is my answer sufficient for you to keep going? $\endgroup$ – yoknapatawpha Jan 31 '14 at 21:45
  • $\begingroup$ Yes. Please your answer is useful but any example may help me for better understanding and avoiding from misunderstanding. $\endgroup$ – Huseyin Jan 31 '14 at 23:47
  • $\begingroup$ @yoknapatawpha what if there are some non-equalities constraints i-e $h(x) \le 0$? How the bordered Hessian get modified and the sufficient condition? $\endgroup$ – kaka May 18 '16 at 7:49

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.