Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

3 Answers 3

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.

share|improve this answer
    
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
2  
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
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.