Why is the cost increasing in the linear regression method?
The reason is your learning rate alpha is too large for this optimization problem. Start with a really small value (&lt; 0.000001) and you will observe a decrease in your cost function.

Keep in mind that when the learning rate is too large, the gradient descent algorithm will miss the global minimum (global because MSE cost function is convex) and will diverge. This is why you have observed still increasing cost function values with alpha = 0.001.