# 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.

-

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.

-
I thought of that (and read the article) as a way to solve the system of equations that Newton-Raphson gives me. However, it seems too slow to converge. If there is some other way I could be using it, please expand, as I'm not aware of it. –  dsimcha Feb 7 '11 at 3:57
You can use it as an optimization method in its own right -- this is described here: en.wikipedia.org/wiki/Nonlinear_conjugate_gradient_method. In my application, it was useless when used without preconditioning, but very effective with a well-chosen preconditioner; see en.wikipedia.org/wiki/…. Determining a suitable preconditioner is a bit of an art and will depend on the details of your objective function; basically you want to make the eigenvalues of the Hessian as similar as possible, ideally all the same. –  joriki Feb 7 '11 at 4:25

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.

-

How about the BFGS-method? I behaves asymptotically like Newton's method but builds the Hessian implicitely without solving any equations.

-