# Maximising with multiple constraints

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?

• 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. – Han de Bruijn Jan 5 '14 at 12:55
• I am interesting on like this uni-graz.at/ronald.wendner/SOC_Hessian.pdf – Huseyin Jan 5 '14 at 14:58
• Is there any reply to me? – Huseyin Jan 22 '14 at 23:18
• @Huseyin please consider revising your question if you want to get nice answers. The question in its current for is not concrete.. – Seyhmus Güngören Jan 30 '14 at 12:29
• I had changed it. – Huseyin Jan 30 '14 at 15:32

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

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

$$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]$$ 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.

• I think a numeric example should explore it. For example in the case of 7 variable and 3 constrain. – Huseyin Jan 30 '14 at 20:22
• @Huseyin Do you need further clarification on how to do that, or is my answer sufficient for you to keep going? – yoknapatawpha Jan 31 '14 at 21:45
• Yes. Please your answer is useful but any example may help me for better understanding and avoiding from misunderstanding. – Huseyin Jan 31 '14 at 23:47
• @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? – kaka May 18 '16 at 7:49