3

I have the following equation: $ \boldsymbol H = \sum\limits_{i=1}^{m} \left( \underbrace{\nabla r_i \nabla r_i^T }_{\boldsymbol J_i} + r_i \nabla^2 r_i \right) $ where $r_i: \mathbb{R}^n \rightarrow \mathbb{R}$. Now I want to know in which cases the approximation: $\boldsymbol H \approx \sum\limits_{i=1}^{m} \boldsymbol J_i = \boldsymbol{ \tilde{H} }\succeq 0$ is good and valid. I known that this is easy in the case when $r_i \rightarrow 0$ and/or $r_i$ are affine. $\boldsymbol H$ or its approximation is then used to solve a linear system of the form: $\boldsymbol H \boldsymbol x = \boldsymbol b$. Since $\boldsymbol{ \tilde{H} }$ is always positive semi-definite this approximations has also the advantage that $\boldsymbol H$ is not indefinite. Another reason for this approximation is the reduced computational complexity since the second order derivatives of $r_i$ are in general hard to compute.

To investigate whether this approximation is good or not I can also (analytically) compute the eigenvalues and eigenvectors of $r_i \nabla^2 r_i$ and $\boldsymbol J_i$.

My question is what are (besides the two trivial above mentioned ones) criteria to justify that the approximation is valid and good? Is it possible to make a statement on this by investigating $r_i \nabla^2 r_i$ ?

Thank you!

EDIT:

Sorry, I forgot to explain my notation. The gradient of $r_i$, $\nabla r_i$ is a column vector and therefore all $\boldsymbol J_i \in \mathbb{R}^{n \times n}$. Furthermore, $\nabla^2 r_i$ denotes the Hessian of $r_i$.

bonanza
  • 441
  • Can you clarify notation a bit? Is the gradient a column vector, so that $\nabla r_i \nabla r_i^T$ is a square matrix? And what is $\nabla^2$? – Giuseppe Negro Jul 09 '13 at 10:20
  • You can show that $|r_i \nabla^2r_i| \leq \epsilon$. This would imply that $|H - \tilde{H}| \leq \epsilon$. – TenaliRaman Jul 09 '13 at 10:22
  • @GiuseppeNegro your right, sorry for that, I made an edit of my question. – bonanza Jul 09 '13 at 10:26
  • @TenaliRaman thanks for you answer! Is it also possible to justify the approx. by looking at how the eigenvalues and eigenvectors may change by only considering the $J_i$ ? – bonanza Jul 09 '13 at 10:27

0 Answers0