As you said, you are being stuck at a local minima mostly. Change the parameters as suggested above and try. A learning rate that is too large can hinder convergence and cause the loss function to fluctuate around the minimum or even to diverge actually.
To help with starting point and to be specific to quadratic and cross-entropy cost, according to Micheal A.Nielson, "neural Networks and Deep Learning,Determination Press,2015, 
This might not work as suggested. Randomizing is a good try. This is a good read.