1
$\begingroup$

I am civil engineering student , and I don't have any information about positive definite, rank, and conjugate . Please help me if you can.


I have an algorithm that finds the minimum.

I have a matrix $H$, and $H$ be an $n\times n$ symmetric matrix, and $$ f(x)= c^Tx+\frac12x^THx.$$ Suppose $D_1$ is a $n×n$ positive definite symmetric matrix, let $x_1$ be an initial point. For $j=1,..,n$ let $\lambda_j= \arg\min_{λ\ge0} f(x+ \lambda d_j)$, and $x_{j+1}=x_j+ \lambda_jd_j$ where $d_j=-D_j\nabla f(x_j) $ and $D_{j+1}= D_j+ a_j$

$$a_j=\frac{(p_j-D_jq_j)(p_j-D_jq_j)^T}{q_j^T(p_j-D_jq_j)}$$

$p_j=x_{j+1}-x_j$ and $q_j=Hp_j$.


  • In this algorithm, why is the matrix $a_j$ of rank $1$?

  • If $D_j$ be a positive definite, is necessarily $D_{j+1}$ positive definite too?

  • Are the direction $d_1,...,d_n$ necessarily conjugate?

Thanks

$\endgroup$
9
  • $\begingroup$ Did you already consult wikipedia for information about "posiive definite", "rank" etc.? $\endgroup$ Jun 4, 2018 at 11:01
  • $\begingroup$ Yes , but I can't proof $\endgroup$
    – ken kavaza
    Jun 4, 2018 at 11:03
  • $\begingroup$ It's very difficult for me, is it simple? $\endgroup$
    – ken kavaza
    Jun 4, 2018 at 11:03
  • $\begingroup$ How is $a_j$ a matrix? The denominator is of the form $u^Tv$, so it's a scalar, but the numerator is of the form $v^2$ for a vector $v$. Presumably it was meant as $vv^T$ which is a square matrix, with each column being a multiple of $v$, hence of rank $\le1$. $\endgroup$
    – Berci
    Jun 4, 2018 at 11:35
  • $\begingroup$ In my book $a_j= \frac{(p_j-D_jq_j)(p_j-D_jq_j)^T} {q_j^T(p_j-D_jq_j)}$ . $\endgroup$
    – ken kavaza
    Jun 4, 2018 at 11:48

1 Answer 1

2
$\begingroup$

The matrix $a_j$ is rank $1$ since it is a matrix of the form $uv^T$, where $u$ and $v$ are column vectors. Note that in such a matrix, every row will be a multiple of $v^T$.

The matrix $a_j$ is symmetric, and it will also be positive semidefinite since if the number on bottom is positive. In this case, we can say that $a_j$ is positive semidefinite since it can be written in the form $a_j = MM^T$. In particular, we have $$ a_j = \left[\frac{p_j - D_j q}{\sqrt{q_j^T(p_j - D_jq_j)}}\right]\left[\frac{p_j - D_j q}{\sqrt{q_j^T(p_j - D_jq_j)}}\right]^T $$

If both $D_j$ and $a_j$ are positive semidefinite, then their sum $a_j + D_j$ will also be positive semidefinite.

$\endgroup$
2
  • $\begingroup$ thanks a lot . if first iteration D1 is positive definite , and a1 is too , is it possible we don't have positive definite in next iteration? Why? $\endgroup$
    – ken kavaza
    Jun 4, 2018 at 12:43
  • $\begingroup$ to show $d_1,..,d_n$ are conjugate , must show $ d_iHd_j=0 , \forall i\neq j$ ?? $\endgroup$
    – ken kavaza
    Jun 4, 2018 at 13:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .