# High Dimensional Optimization Algorithm?

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.

Even if your matrix is of order several thousand, a linear solve should still be pretty fast, and Newton methods should not require many iterations. If your matrix is sparse or has special structure, it will be even faster. My Matlab solves a rank 2000 system in 3 seconds. If you need even more speed, you can try to solve the system only approximately using an iterative method with some fixed number of steps (so then it becomes $O(D^2)$, and see if the Newton iteration still converges.