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.

Let's say we have a smooth function $f:\mathbb{R}^{1000000} \rightarrow \mathbb{R}$, which we want to minimize using a method from numerical optimization. which method would we choose? Is the conjugate gradient method the best choice? What methods are better than others in the minimization process of high-dimensional problems?

Thank you very much for your time!

share|improve this question
2  
The answer is "it depends". The basic conjugate gradient algorithm only works when the function $f$ is a quadratic form, and it works best when the problem is sparse. Is that the case here? There are also nonlinear conjugate gradient methods that work with numerical derivatives, that may work well for you. Randomization algorithms like simulated annealing can also work well in high dimensions. Can you give any more information about the problem? –  Chris Taylor Jul 21 '12 at 19:16
2  
I would echo @ChrisTaylor's remarks. The form of $f$ matters too. Do you have an explicit derivative? Is $f$ separable in some way, is it convex, etc... –  copper.hat Jul 21 '12 at 21:40
    
I don't have any details on the form of $f$. I was just wondering if there are some preferred algorithms when you have functions of high dimensions. It's not a specific question about something particular, I was just wondering. –  Chris Jul 22 '12 at 15:02
add comment

1 Answer

I don't know much about it, but what people do in the case Support Vector Machine kind of problems is to use the KKT conditions to dualize the problem and make it dimension independent. You could try to read about it and see if similar ideas can be applied in your case, for example http://en.wikipedia.org/wiki/Support_vector_machine

share|improve this answer
    
Just to make clear dimension independent means that the solution time does not depend of the dimension in some sense, but you still have to compute the dot products or the chosen kernel –  Nivan Jul 21 '12 at 21:34
    
The asker didn't say anything about constraints, so neither the KKT conditions nor duality apply. –  Rahul Jul 22 '12 at 1:02
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.