Questions tagged [quasi-newton]
The quasi-newton tag has no usage guidance.
20
questions
2
votes
1answer
79 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
1answer
34 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 ...
0
votes
0answers
101 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 ...
4
votes
1answer
155 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 (...
1
vote
0answers
68 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 ...
2
votes
0answers
82 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 ...
5
votes
1answer
154 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 ...
1
vote
0answers
149 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) ...
1
vote
1answer
78 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}\\...
3
votes
1answer
757 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 $...
2
votes
0answers
354 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, ...
3
votes
1answer
590 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 ...
5
votes
0answers
88 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 ...
3
votes
0answers
298 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 ...
3
votes
2answers
895 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
1answer
64 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 ...
2
votes
0answers
148 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 ...
2
votes
0answers
892 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|...
1
vote
0answers
150 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 ...
1
vote
1answer
115 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 ...