# Tag Info

Accepted

### Are Quasi-Newton methods computationally impractical?

I'm guessing you're referring to the discussion on pages 188-189 of that book. The author doesn't give much detail on quasi-Newton methods or substantiate the $\mathscr O(W^2)$ complexity estimate. To ...

### Are Quasi-Newton methods computationally impractical?

Traditional quasi-newton methods like BFGS require $O(n^{2})$ storage for a potentially fully dense quasi-Hessian matrix and $O(n^{2})$ work in each iteration to update the factorized quasi-Hessian ...
Accepted

Accepted

### Computational complexity of Newton's method

If you take $m$ steps, and update the Jacobian every $t$ steps, the time complexity will be $O(m N^2 + (m/t)N^3)$. So the time taken per step is $O(N^2+N^3/t)$. You're reducing the amount of work you ...
Accepted

### The linear system in Quasi Newton method

It is a well-known theorem that conjugate gradients is guaranteed to converge (in exact arithmetic) within $r+1$ steps for an identity-plus-rank-$r$ matrix, regardless of its size. In finite precision,...

### Linear constraints for L-BFGS-B

One approach to this problem is to reparameterize your problem in terms of $x_{1}$ and $z_{i}=x_{i}-x_{i-1}$, $i=2, \ldots, n-1$. You can then rewrite your objective function in terms of the the ...

To add on Brian's answer. The idea behind the low rank update is to find what an approximation that is "good enough", thus saving on computation resources. The BFGS method approximates the hessian ...
Accepted

### Interpretation of error between Hessian approximation and real Hessian - Quasi-Newton Method

Either I am not understanding the issue, or you're making it out to be more difficult than it really is. You have a thing $A$ that should ideally be equal to $I$. The norm $\|I-A\|_2$ measures its ...
1 vote

### When does L-BFGS outperform GD?

(Not exactly an answer to my question, but some empirical experiments which might give guidance to what a worst-case analysis of the L-BFGS iteration of a quadratic function should result in). I ...
1 vote

### Sensitivity of BFGS to the accuracy of the gradient

From a pure convergence point of view, I believe the only thing that's necessary is to satisfy the convergence criteria from a globalization method such as a line-search or trust-region. This is ...
1 vote

### Product of rank one updates as a low rank update for quasi newton/BFGS

You can do this using the Sherman-Morrison Formula and some other tricks, detailed starting on page 124 of Kelley, Iterative Methods for Linear and Nonlinear Equations
1 vote
Accepted

### Doubt regarding principled approach towards approximating the Hessian

You may find this paper relevant. They give some BFGS-inspired methods and convergence proofs for cases where the Hessian is the sum of a part you can compute easily and a part you can't ("structured ...

Only top scored, non community-wiki answers of a minimum length are eligible