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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question

Have you tried conjugate gradients? ( I did a lot of work with that method some time ago; if you have questions about it feel free to ask.

share|cite|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
You can use it as an optimization method in its own right -- this is described here: In my application, it was useless when used without preconditioning, but very effective with a well-chosen preconditioner; see…. 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.

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer


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.