What's the motivation for choosing Direct Methods rather than Iterative Methods when solving Lifted-KKT or HyKKT systems? #365
-
|
Hi all, thanks for your great work. It's an amazing project. I'm quite new to topics about solving numerical optimization on GPUs. I'm wondering what's the main motivation for factorizing matrices using direct methods rather than using iterative methods (like Conjugate Gradient) after obtaining the sparse positive definite Lifted-KKT or HyKKT. I guess the reason is computing a good preconditioner is non-trivial for general settings. MadNLP is designed for solving general Nonlinear Programming so you cannot assume sparsity patterns of the KKT system (like the sparsity structure in optimal control problems). I'm wondering if my guess is correct and if there're other reasons. I would appreciate it if you can share more insights! Thanks a lot! |
Beta Was this translation helpful? Give feedback.
Replies: 1 comment 1 reply
-
|
Hey @FenglongSong thanks for the question. MadNLP is based on the interior point method and for the interior point method, iterative methods almost always don't work due to the extreme ill-conditioning that happens as we approach the solution. Even with a tailored preconditioner, iterative solvers tend to fail. When you don't have inequality constraints, it would be interesting to see if HybridKKT method works well, but because HybridKKT requires a large regularization paramter \gamma, I don't think iterative methods are likely to be effective. It is true that it is hard to design effective preconditioners without problem-specific structures. But I'd say ill-conditioning is the more important issue. |
Beta Was this translation helpful? Give feedback.
-
|
Thank you for your clear explanation! |
Beta Was this translation helpful? Give feedback.
Hey @FenglongSong thanks for the question.
MadNLP is based on the interior point method and for the interior point method, iterative methods almost always don't work due to the extreme ill-conditioning that happens as we approach the solution. Even with a tailored preconditioner, iterative solvers tend to fail. When you don't have inequality constraints, it would be interesting to see if HybridKKT method works well, but because HybridKKT requires a large regularization paramter \gamma, I don't think iterative methods are likely to be effective. It is true that it is hard to design effective preconditioners without problem-specific structures. But I'd say ill-conditioning is the more impor…