Questions tagged [quasi-newton]
Use for questions involving quasi-Newton method, which in contrast to [tag:newton-method] uses an approximation of the Hessian during the root-finding or optimization process.
22
questions
8
votes
2
answers
2k
views
Are Quasi-Newton methods computationally impractical?
I was reading a book by Simon Haykin on neural networks when I came across the following strong statement (on the pdf's page 188):
"However, we still have a computational complexity that is
$\...
- 195
1
vote
0
answers
48
views
Hessian-free preconditioner for non linear least squares
I am solving a nonlinear least squares problem using Gauss Newton method. Due to the large dimension of the problem, I use the Hessian-free approach. As a linear solver I use either MINRES or CG. To ...
2
votes
1
answer
590
views
Difference between asymptotic and non-asymptotic convergence in optimization?
I am reading some optimization methods and I am facing some issues with two terms "asymptotic and non-asymptotic convergence". What is the difference between them?
-1
votes
1
answer
47
views
Interpretation of error between Hessian approximation and real Hessian - Quasi-Newton Method
$$ ||I- H_{k}^{BFGS}\nabla^{2}f(x_{k})||_{2}$$
, where $H_{k}$ is the inverse of hessian approximation at each iteration.
I am given this expression to assess the error in Hessian approximation in ...
- 1
0
votes
0
answers
168
views
General question related to BFGS
Based on my basic understanding of the BFGS method, the algorithm will iterate until the gradient norm is less than or equal to a set value called "gtol" in the case of Python.
However, when ...
- 11
4
votes
1
answer
286
views
When does L-BFGS outperform GD?
In practice, L-BFGS is frequently held comparably to other inexact QN methods, and it provides a middle ground of sorts between Hestenes–Stiefel CG and BFGS as memory goes from zero to infinity (...
- 211
1
vote
0
answers
71
views
Solution predictors for accelerating convergence in nonlinear FEM
I am looking for the details of commonly-used predictors for accelerating the convergence of iterations using Newton-Raphson scheme for nonlinear problems in FEM. I am looking specifically for static ...
- 810
2
votes
0
answers
113
views
Does BFGS preserve the bandedness of the inverse hessian?
In the BFGS method we perform iterations by calculating an approximation $\boldsymbol{H}_k$ to the inverse Hessian $\boldsymbol{H}$ of the objective function. This method belongs to a family of ...
- 472
5
votes
1
answer
221
views
Sensitivity of BFGS to the accuracy of the gradient
I am studying how to speed-up the BFGS method using quantum computing techniques.
I have used a method of speeding up the gradient of the function, but it sacrifices the precision value of the ...
- 151
1
vote
0
answers
331
views
How to use Wolfe-Powell step-size control in quasi-Newton method?
I'm trying to find the minimum of a function using the quasi-Newton method with the Broyden-Fletcher-Goldfarb-Shanno (BFGS) algorithm.
But I want to change the following implementation, so that:
1) ...
- 131
1
vote
1
answer
102
views
Product of rank one updates as a low rank update for quasi newton/BFGS
I'm trying to improve the speed of the following iteration to calculate $s_k$:
$$B_k^{-1} = \Bigg( I + \frac{s_{k}s_{k-1}^T}{||s_{k-1}||^2}\Bigg)...\Bigg(I+ \frac{s_1s_0^T}{||s_0||^2}\Bigg) B_0^{-1}\\...
- 11
3
votes
1
answer
2k
views
Computational complexity of Newton's method
the classical Newton's method for non-linear systems of equations is $x_{k+1} =x_k-J_F(x_n)^{-1} F(x_n)$. In pratice, rather than compute the inverse of the Jacobian matrix, one solves the systems $...
- 540
2
votes
0
answers
548
views
How to prevent BFGS from getting stuck on astronomically large gradient?
I have implemented BFGS myself from scratch in order to solve minimization problems. Part of BFGS, as I understand it, is that the approximation to the Hessian is supposed to be positive definite, ...
- 141
3
votes
1
answer
890
views
Linear constraints for L-BFGS-B
I know L-BFGS-B only supports simple box constrains of the form: $l_i \leq x_i \leq u_i$, where $l_i$ and $u_i$ are constants. For my specific optimization problem, I need to specify some simple ...
- 1,310
5
votes
0
answers
94
views
Minimize interesting objective function with knowledge of gradient nonlinearity?
I plan on using a Quasi-Newton method (L-BFGS) to minimize a non-linear objective function.
$$ f: \mathbb{R}^n \rightarrow \mathbb{R}$$
The gradient is kind of interesting: as the values of the ...
- 163
3
votes
0
answers
339
views
How to avoid the Broyden's jacobian approximation becoming poorer with the number of iterations?
I have to solve many times a nonlinear system of the form
$$f(x) = b^{(n)}$$
inside a loop.
The function $f$ is expensive to compute and I do not have its jacobian, so I have tried the good Broyden's ...
- 439
3
votes
2
answers
1k
views
Low-rank updates in BFGS
I have read this and other threads on this site on BFGS, but I still don't have a clear understanding of what it's meant by low-rank updates.
For example, I read the following in this book:
The ...
2
votes
1
answer
66
views
Doubt regarding principled approach towards approximating the Hessian
In my optimization problem, the hessian has a structure such that it can be written as the sum of two matrices. Populating the first of the matrices is efficient. Populating the second one is ...
- 656
2
votes
0
answers
155
views
Quasi-Newton Optimization with parallel function evaluation
I have a function of many variables (~200-2000) which I am optimizing with some success using L-BFGS. While the function is expensive to evaluate, the gradient can be computed with not much additional ...
- 121
2
votes
0
answers
973
views
Weighted Frobenius norm in BFGS
In what sense is the weighted Frobenius norm "adimensional"/"scale-invariant" for any symmetric positive definite weight matrix $W$? If we plug in a positive diagonal matrix into $W$ wee see that $||A|...
- 121
1
vote
0
answers
177
views
Quasi Newton taking very small steps
I have implemented a Quasi-Newton method based on the Hessian approximation. I am noticing that the algorithm takes too many iterations to converge, even though it does converge. What I am not able to ...
- 656
1
vote
1
answer
145
views
The linear system in Quasi Newton method
I have implemented a Quasi Newton method for my problem, where I use the Hessian matrix approximation based approach. Hence, there is a linear system solve in every iteration. I solve the linear ...
- 656