Coursera ML - Does the choice of optimization algorithm affect the accuracy of multiclass logistic regression?
Limits of numerical accuracy and stability are causing the optimisation routines to struggle.

You can see this most easily by changing the regularisation term to 0.0 - there is no reason why this should not work in principle, and you are not using any feature engineering that particularly needs it. With regularisation set to 0.0, then you will see limits of precision reached and attempts to take log of 0 when calculating the cost function. The two different optimisation routines are affected differently, due to taking different sample points on route to the minimum.

I think that with regularisation term set high, you remove the numerical instability, but at the expense of not seeing what is really going on with the calculations - in effect the regularisation terms become dominant for the difficult training examples.

You can offset some of the accuracy problems by modifying the cost function:

def compute_cost_regularized(theta, X, y, lda):
    reg =lda/(2*len(y)) * np.sum(theta[1:]**2) 
    return reg - 1/len(y) * np.sum(
      y @ np.log( np.maximum(sigmoid(X@theta), 1e-10) ) 
      + (1-y) @ np.log( np.maximum(1-sigmoid(X@theta), 1e-10) ) )


Also to get some feedback during the training, you can add

                       options = {
                           'disp': True
                       }


To the call to minimize.

With this change, you can try with regularisation term set to zero. When I do this, I get:

predict_one_vs_all(X_bias, theta_all_optimized_cg)
Out[156]:
94.760000000000005
In [157]:

predict_one_vs_all(X_bias, theta_all_optimized_bfgs)
/usr/local/lib/python3.6/site-packages/ipykernel/__main__.py:2: RuntimeWarning: overflow encountered in exp
  from ipykernel import kernelapp as app
Out[157]:
98.839999999999989


The CG value of 94.76 seems to match the expected result nicely - so I wonder if this was done without regularisation. The BFGS value is still "better" although I am not sure how much I trust it given the warning messages during training and evaluation. To tell if this apparently better training result really translates into better digit detection, you would need to measure results on a hold-out test set.