When Newton is good, it's very good; when it's bad, it's awful.

I remember both of us had a discussion here a few years back. And your analysis was spot on. The problem was NR had issues with humped yield curves and vol > 60%. So I tried NR for a few trials and then switched to a bracketing (bisection) method. But I decided to bracket the seed first to error ~ 10^-1 and then go into 5th gear to NR. 

I used Brent minimizer (not root finder version!) by converting f(x) = 0 to an optmization problem.

One open issue in this thread is to quantify what is meant by deep OTM, ITM. Most methods break when S = 100, K = 150.

dbl

I don't get this. What is the deal with implied volatility? It's just a numerical root solver away. End of story, no? 

Aren't all these approximations just a curiosity for unoccupied quants or am I missing something?

It's not a big issue, indeed. Just nice tie up some loose ends! There's a plethora of methods for iv. Why?
What's your own favourite methods?

You might be out of luckManaster & Koehler give a seed value such that, if there is a non-zero solution for the implied vol, then it will be found using their seed value' When other method fails, start from Manaster & Koehler seed valueIf sigmanow <= 0 Then sigmanow = Sqr(2 * Abs(Log(S / X) + (r - q) * tyr) / tyr)

A few tests show that M&K seed fails mainly for small sig, when ITM and OTM mostly. Take K = 150. S = 100., r = q = 0. T = 1, sig = 0.04. Bisection bracketing is a bit better.
So, K&M is probably not the 'elixir'. I'm a bit wary of magic formulae for all parameter ranges.

If you need reliable ultra-fast implied vols on all OPRA universe with proper modeling of early exercise, borrow and cash dividends, send me a message. 

Just read this thread today and got

Volatility = 0.04
Opt_Price=9.01002030921698e-25
Implied_Volatilty =0.0400000003783122

using a biscetion with a smart initial bounds guess.
It converged using a tol 1e-30 after 24 steps

Just read this thread today and got

Volatility = 0.04
Opt_Price=9.01002030921698e-25
Implied_Volatilty =0.0400000003783122

using a biscetion with a smart initial bounds guess.
It converged using a tol 1e-30 after 24 steps

The bisection method will converge in a finite number of steps. Of course, it breaks down if there is more than one root. Finding a good initial trust region is a wee job in itself.
Did you do bisection 'all the way'? How many iteration to reach a given tolerance? (edit: I see 24 iterations with 1.0e-30, double precision??) BTW your test case is not 1.0e-30 accurate(?)
One technique I found useful was 1) bisection until TOL = 1.0e-1, then 2) use quadratic Newton Raphson  with the midpoint of the found trust region in 1) as initial guess.

// In general, posing f(x) = 0 in least-squares form using Differential Evolution (DE) is very robust over a range of parameters.


BTW could you please post the complete data set T, K, etc.?

That`s the data set I`ve use. The first port I ran the code in Matlab and now I did it in C++

double Price = 100;
double Strike = 150;
double Volatility = 0.04;
double Risk_Free = 0.00;
double Dividends = 0;
double Time = 1;
double T_Vols = 1;
 
tol = 1.0e-29 ( used in the Bisection)

BS Price = 9.00331881509398404840189634861e-25
 BS Price Implied Volatility = 9.00341742270713667487757281468e-25
 Implied Volatility = 0.0399995456251887870902095301062
 Tol = 9.86076131526264756764660706603e-30
 Iterations = 21
 Time (ms)  = 0.0118969999999999995893285031912

Impressive!

Impressive!

how so?

Impressive!

how so?

I was paying you a compliment.
Your method seems to be very robust. 21 iterations for Bisection suggests some clever "pre-processing" is being done. Kind of surprising.
I tried a number of minimisation algos by writing f(x) = 0 as a least-squares problem. Good answer up to  K = 150, S = 115 but not S = 100.
This method needs about 70 iterations
https://en.wikipedia.org/wiki/Ternary_search

Oh Sorry I guess I was kind of rude . I figured you were been nice but I was wondering why the code had a good performance...

Oh Sorry I guess I was kind of rude . I figured you were been nice but I was wondering why the code had a good performance...

No problem. 
Your code must be very good because I tested about 6 different methods. But 21 iterations for Bisection is very good. As I mentioned, I reckon Bisection to 1..0e-1 and then Newton after that will be even faster.

r=0So, thinking out loud, here is a good test routine for your codes.Take [$]S=100, T=1[$] and [$]\sigma = 0.04[$].Now increment [$]K[$] in steps of 10 from [$]K =100[$],produce the BS call price [$]C[$], and produce the iv from [$]C[$].How high can you go with [$]K[$] before it fails to get [$]\sigma[$] correct to even 1 significant digit? I'd guess, with a little ingenuity, you could make this work, all in machine precision, to quite large [$]K[$],say [$]K > 1000[$]. Of course, trick will be to convert to logs at an appropriate point, and use the well-knownasymptotics of the cumulative normal.

'riverrun, past Brent and Newton, from swerve of shore to bend of bay, brings us by a commodious vicus of recirculation back to Simplicial Homology Castle and Environs.”
S = 100.0
K = 150 ... up to K = 290 OK
r = 0.0
b = r
x = 0.04 #sig/vol
T = 1
q = 0

With SHGO I get C = 9.0100203091698e-25

QED

All the other million methods I used are really no good.

With the same data above, SHGO algo fails to find a minimizer point when K > 290. Suggests infeasible region.

https://shgo.readthedocs.io/en/stable/docs/README.html