I have an optimization problem that at first sounds quite textbook. I have a convex objective function in $D$-dimensional space that is twice differentiable everywhere and has no local optima.
Ordinarily it would be a perfect candidate for numerical Newton-Raphson methods. However, Newton-Raphson requires solving a system of linear equations of size $D$. This takes $O(D^3)$ computations, at least with any reasonably implementable algorithm I'm aware of. In my case $D$ is on the order of several thousand. Can anyone suggest an optimization algorithm that is typically more efficient than Newton-Raphson for $D$ this large? I tried gradient descent, but empirically it seemed absurdly slow to converge.
Best Answer
Have you tried conjugate gradients? (http://en.wikipedia.org/wiki/Conjugate_gradient_method) I did a lot of work with that method some time ago; if you have questions about it feel free to ask.