17
votes
Difference between Gauss-Newton method and quasi-Newton method for optimization
Quasi-Newton methods construct an approximate Hessian for an arbitrary smooth objective function $f(x)$ using values of $\nabla f$ evaluated at the current and previous points. At each iteration of ...
- 18.2k
17
votes
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 ...
- 9,168
11
votes
Accepted
How to calculate/derive analytic FEM Newton Jacobian
Your example is a pretty good indication that the two derivatives (with respect to $x$ and with respect to $u$) do not commute :) (In fact, they're very different beasts -- one is a Fréchet derivative,...
- 12.1k
11
votes
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 ...
- 18.2k
10
votes
Positive root of $x^q + bx - b$
According to Wolfram Alpha, $x^5+3(x-1)=0$ has no closed-form solution, so you can forget about a nice closed-form expression. :)
I see nothing wrong with Newton's method; it should be quick and ...
- 10.1k
8
votes
Accepted
Lack of quadratic convergence in Newton's method
Yes: See Higham's book "Accuracy And Stability of Numerical Algorithms", second edition, chapter 25: Nonlinear Systems and Newton's Method.
In particular, see the section on the "limiting residual" ...
- 2,085
7
votes
Accepted
Newton iteration applied to nonlinear PDE
It's a bit easier to see if you write your equation in the a semi-discretised system of the form $u^{\prime}(t) = F(u(t))$ and with the application of the $\theta$-method and approximating $u^{\prime}(...
- 5,369
7
votes
Accepted
Eigenvalues of $ab^T$
This is sometimes known as Buzano's inequality (http://www.jstor.org/stable/2159168). In general, if $\|x\|=1$, $P=xx^{\top}$ is a projection operator, so a simple application of Cauchy-Schwarz leads ...
- 11.4k
7
votes
Accepted
Low-rank updates in BFGS
A low rank update to an $n$ by $n$ matrix $A$ is an update of the form
$A=A+UU^{T}$
where $U$ is matrix with $n$ rows but very few columns (typically just one or two.) If the matrix $UU^{T}$ has $...
- 18.2k
7
votes
Which absolute and/or relative stopping criteria do use for Newton's method?
Some of the confusion comes about because mathematicians often consider artificial functions that happen to have size $O(1)$ whereas practitioners use functions and variables that just happen to be ...
6
votes
How does one calculate reaction force in FEA?
To calculate the reaction forces at a node, Abaqus (or any structural FE code) simply sums the internal forces for all elements attached to that node. The reaction forces are the negative of that sum.
...
- 5,864
6
votes
Implementation of the Jacobian-free Newton method
Not sure where you get your equation for $\epsilon$, but ultimately your approximation for the Jacobian matvec operation is a finite difference approximation to the directed derivative of $F(\cdot)$. ...
- 3,818
6
votes
Accepted
GMRES vs Newton-GMRES for Solving nonlinear PDE's
The reason is that GMRES can only be used for solving linear equations, i.e. equations of the form $Ax=b$, where $A$ is some matrix and $x,b$ are vectors. What GMRES does, essentially, is it ...
- 106
5
votes
Accepted
What would be a good approach to solving this large data non-linear least squares optimisation
I don't know much about tracking implicit surfaces, so I'm just going to start with the optimization problem and go from there.
The optimization problem is, at the core, nonlinear least squares, and ...
- 3,063
5
votes
Accepted
Roots of a function for eigensystem
I suspect the main problem is the magnitude of the values. If you divide through by $\cosh$ to make all the numbers smaller, then ApproxFun doesn't seem to have a problem finding all the roots.
...
- 11.4k
5
votes
Why do Newton-Krylov iterations stagnate in this problem?
I'm not sure if this is the answer, but consider the case as $\alpha \rightarrow \infty$. In this case you're trying to solve
$\iint_{\Omega} \cosh(P) dxdy = 0$
And since cosh looks like this:
You ...
- 609
5
votes
Accepted
Newton's method problem
The Netwon(-Raphson) method helps you finding the root(s) of a function $f(x)$, that is, those values of $x_0$ for which $f(x_0) = 0$. In your case, the unknown value is $c$, so we start by writing ...
- 677
5
votes
Accepted
Solving system of nonlinear vector functions
If you have a single vector equation $\vec{F}(\vec{x})=0$ then you solve it by representing that state vector $\vec{x}$ as a set of amplitudes $[x_0,x_1,...,x_{n-1}]$ after discretization by your ...
- 2,240
4
votes
Accepted
Hessian-free and Truncated Newton methods
It looks like this paper is combining Hessian-free with truncated Newton method.
Yes, it is.
...the approach is referred to as Hessian-free method. That is because the Hessian is never computed ...
- 30.1k
4
votes
Accepted
Methods of solving non-linear advection-diffusion systems beyond Newton-Raphson?
I'm assuming the limitation in 2D and 3D is storing the Jacobian.
One option is to retain the time derivatives and use an explicit "pseudo" time-stepping to iterate to steady state. Normally the CFL ...
- 181
4
votes
Accepted
Can redundant variables be beneficial for root-finding convergence
In terms of computational effort, it is useless. I mean, you are still having a nonlinear problem with a bigger Jacobian (which is the worst part to be computed quickly).
For next thoughts: dense ...
- 1,628
4
votes
How does one calculate reaction force in FEA?
Once the solution of the problem is known, i.e. you know displacement vector, to calculate reaction/internal forces an integral is evaluated
\begin{equation}
\mathbf{f}^\textrm{int} = \sum_{e=1}^{...
- 906
4
votes
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 ...
- 11.4k
4
votes
How to use Newton-Raphson method to handle nonlinear terms in coupled system of PDEs?
The Nonlinear Schroedinger Equation is special. Instead of applying a Newton-Raphson method, it is easier to use an operator splitting scheme that uses the particular form of the nonlinearity because ...
4
votes
Accepted
Which absolute and/or relative stopping criteria do use for Newton's method?
This is not a definite answer, but I highly recommend the work of Deuflhard on Newton methods (e.g. this report, this book, and another report I cannot find just yet).
The basic idea is the following: ...
- 1,669
4
votes
Accepted
Backward Euler + Quasi Newton(Broyden) method fails to solve Van der Pol's equation(Stiff ODE)
This is not surprising. For one, Broyden is not very stable for highly ill-conditioned nonlinear systems, and having a stiff ODE means that the nonlinear system will be ill-conditioned. This is why ...
- 12.1k
3
votes
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,...
- 2,435
3
votes
Are there special methods for solving $f'(z)=0$ for analytic $f$?
While it's especially well-suited for polynomial systems, Smale's $\alpha$-theory gives a way to be certain that the Newton iterates for a nonlinear analytic system will converge, and also gives a ...
- 9,168
3
votes
Accepted
Efficient and stable computation of inverse CDF
The assumptions you have are no more specific than what you need to assume to make something like Newton's method work. In fact, you don't even assume enough to make the problem unique: you only ...
3
votes
Accepted
Newton's method goes to zero determinant Jacobian
From what you describe, you have an ill-posed problem: The solution is not unique (not even locally). A standard way of dealing with this is the following: Instead of trying to solve $F(x)=y$, where $...
- 12.1k
Only top scored, non community-wiki answers of a minimum length are eligible