Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I'm learning about optimization of quadratic forms and this textbook goes through definiteness of matrices and principle minors etc. and then goes straight onto optimizing with constraints but never mentions how to solve the general problem of finding stationary points on $f(x)$ where $$f(x)=x^TAx + \mathbf b^Tx+c$$

$A$ being an n x n matrix and b an n x 1

Any help is appreciated

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

Let $\vec\nabla f$ be a $n \times 1$ vector, we will call this $\dfrac{\partial f}{\partial x}$. Then we get that $$\dfrac{\partial f}{\partial x} = Ax + A^Tx + b.$$ The differentiation with respect to a vector is obtained by recalling the following vector differentiation identities.

If $y \in \mathbb{R}^{m \times 1}$, $x \in \mathbb{R}^{n \times 1}$, then $\dfrac{\partial y^T}{\partial x}$ is a $n \times m$ matrix $A$ with $A(i,j) = \dfrac{\partial y_j}{\partial x_i}$.

Also, the chain rule goes as follows. $$\dfrac{\partial (\cdot)}{\partial x} = \sum_k \dfrac{\partial y_k^T}{\partial x}\dfrac{\partial (\cdot)}{\partial y_k}$$ Hence, we have the following relations $$\dfrac{\partial x^T}{\partial x }= I_{n \times n}$$ $$\dfrac{\partial (c^Tx)}{\partial x} = \dfrac{\partial (x^Tc)}{\partial x} = c$$

Hence, $$\dfrac{\partial b^Tx}{\partial x} = b$$ and \begin{align} \dfrac{\partial \left(y_1(x)^TAy_2(x) \right)}{\partial x} & = \dfrac{\partial y_1^T}{\partial x}\dfrac{\partial \left(y_1(x)^TAy_2(x) \right)}{\partial y_1} + \dfrac{\partial y_2^T}{\partial x}\dfrac{\partial \left(y_1(x)^TAy_2(x) \right)}{\partial y_2}\\ & = \dfrac{\partial y_1^T}{\partial x} \dfrac{\partial \left(y_2(x)^TA^Ty_1(x) \right)}{\partial y_1} + \dfrac{\partial y_2^T}{\partial x} \dfrac{\partial \left(y_1(x)^TAy_2(x) \right)}{\partial y_2}\\ & = \dfrac{\partial y_1^T}{\partial x} \dfrac{\partial \left((Ay_2(x))^Ty_1(x) \right)}{\partial y_1} + \dfrac{\partial y_2^T}{\partial x} \dfrac{\partial \left((A^Ty_1(x))^Ty_2(x) \right)}{\partial y_2}\\ & = \dfrac{\partial y_1^T}{\partial x} Ay_2(x) + \dfrac{\partial y_2^T}{\partial x} A^Ty_1(x) \end{align} In our case, $y_1(x) = y_2(x) = x$ and hence $\dfrac{\partial y_1^T}{\partial x} = \dfrac{\partial y_2^T}{\partial x} = I_{n \times n}$. Hence, $$\dfrac{\partial (x^TAx)}{\partial x} = I A x + I A^T x = \left(A+A^T \right)x$$ Setting the gradient to zero, we get the equation $$(A+A^T)x = -b$$ Solve this linear system to get the stationary points.

share|improve this answer
    
Thanks, Very good! would the $(A+A^T)$ then be the Hessian that we evaluate to find the nature of the st. point? –  Ronald Jun 17 '12 at 20:33
1  
@Ronald Yes. $A+A^T$ would be the Hessian. –  user17762 Jun 17 '12 at 22:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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