Timeline for Stopping criteria for damped Newton iterations with backtracking line search
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 31, 2024 at 17:56 | comment | added | Sébastien Loisel | I've definitely had the $\epsilon$ vs $\sqrt{\epsilon}$ issue. I can run my code in BigFloat, it's in Julia. The code is here. That being said, you can probably find the behavior with this barrier function: $f(t,x) = tx-\log(x)$. The central path is $x^*(t) = 1/t$ but $f(t,1/t) = 1+\log t$ while $f(t,c/t) = c+\log t-\log c$ so the difference is $c-1-\log c \approx 0.5(c-1)^2$, so put $c = 1+\sqrt{\epsilon}$ I guess? Hopefully this example works, my wife wants me to go to dinner, I'll double check later. | |
| May 31, 2024 at 17:34 | comment | added | Daniel Shapero | I mentioned the fixed vs floating point thing because I've definitely chased my own tail on multiple occasions only to remember how floating-point arithmetic actually works. I don't have a great answer for that part of your question and it would be interesting to manufacture a case to test whether you get $\|x_k - x_\infty\|$ to order $\epsilon$ or $\sqrt\epsilon$. It might be as simple as running the code you already have written in single- and then double-precision arithmetic. If you can do it in quad-precision even better but that can be annoying to code. | |
| May 31, 2024 at 17:30 | comment | added | Sébastien Loisel | Also, I'm aware of the difference between floating point and fixed point, I'm just following the fashion of glossing over it. If you look at Boyd and Vanderberghe, they just do Newton iterations until the absolute error is less than $\epsilon$ and they don't care about relative vs absolute. | |
| May 31, 2024 at 17:25 | comment | added | Sébastien Loisel | I've also tried other tests. In the line search, with $\phi(s) = F(x_k-sn_k)$, I tried things like: use $s=1$ if $\phi'(1) \leq 0$, else backtrack until $\phi'(s)\phi'(0.5s)<0$ or maybe $\phi'(s)\phi'(2s)<0$. I'm just not sure what any of these do to the convergence analysis for self-concordant functions. | |
| May 31, 2024 at 17:19 | comment | added | Sébastien Loisel | Thanks Daniel for all this information. I'm indeed working on solvers for p-Laplacians, but using the barrier method so the objective isn't directly your F(u). My objective doesn't have this type of decomposition. The reason why I've asked this question here is that I've done lots of numerical experiments and observed the Armijo rule flaking out on me. I've also tried using the Newton decrement, I know it's in principle the right thing in self-concordant calculus, but I've also had floating point issues with that quantity. You are right, I'm trying to get rid of the "tol", it's undesirable. | |
| May 31, 2024 at 17:06 | history | answered | Daniel Shapero | CC BY-SA 4.0 |