2
$\begingroup$

I was reading a paper about BFGS and met the following problem:

$\min_B \|B-B_k\|$, s.t. $B=B^{\top}, Bs_k=y_k, s_k^{\top}y_k>0$ and $B$ is positive definite. Here $B_k$ is a symmetric positive definite $n\times n$ matrix, $y_k,s_k$ are all $n\times 1$ vectors. $B_k, y_k,s_k$ are all known.

The norm used to measure the closeness between matrices is defined to be the weighted Frobenius norm, $\|A\|=\|W^{\frac{1}{2}}AW^{\frac{1}{2}}\|_F$.

The paper then gives the solution of this minimization problem as $B^* = (I-\rho_ky_ks_k^{\top})B_k(I-\rho_ks_ky_k^{\top})+\rho_ky_ky_k^{\top}$, where $\rho_k=\frac{1}{y_k^{\top}s_k}$, and calls it the Davidon-Fletcher-Powell formula.

I didn't have any clues about how to solve this optimization in closed form. Also, materials explaining the DFP formula seems to be ridiculously difficult to find. Could any one help?

Even any hints on solving matrix norm optimization problem would help, thanks!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

This seems to be covered by the wikipedia.

Improve this answer
$\endgroup$
2
  • $\begingroup$ seems not. Wikipedia directly gives the solution and didn't derive it. Now I can somehow see this could follow from solving a Lagrange multiplier problem. But the form of the equation is crazy... $\endgroup$
    – todpole3
    Oct 17, 2012 at 2:15
  • 1
    $\begingroup$ Actually, the Wikipedia has references to the original papers AND a book by Nocedal, so I would say that it IS covered. $\endgroup$
    – Igor Rivin
    Oct 17, 2012 at 3:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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