I am trying to solve a PDE-constrained optimization problem that can be written as:
subject to h(x)=0
As this problem is nonlinear, I try to find a local minimum by starting from a nearby initial condition and use Newton method locally to compute the direction. I achieve that by deriving the KKT condition locally for the linearized system and solve a quadratic problem locally. The aim is to converge to a point that satisfies dL(x)=0 , where L is the lagragian.
The problem that I face is that the real Hessian matrix is not always guaranteed to be a PD matrix, and therefore, obtaining a descent direction becomes not guaranteed. I wonder if there is a library that can obtain a descent direction for me while I provide the KKT system (Hessian and gradient).
You have two options: either you regularize the Hessian (that is, you add a multiple of the identity matrix until the resulting matrix becomes PD) or you use a trust region (this way, you bound negative curvature).
If you want to stick with a line search, check out Alg 3.3 (p51) from Numerical Optimization. It describes a regularization procedure (for Cholesky, but whatever). A linear solver such as Pardiso or MA57 will give you the rank/number of negative eigenvalues you need to determine if the matrix is PD.
Note: you can also use a readily available solver such as Ipopt or filterSQP.
Thanks a lot for your response. Would you suggest a certain way to do the line search in this case? I know that it involves a lot of heuristics such as merit functions … etc, that is why I was looking for a library to correct the Hessian that I provide and do the linesearch/trust region for me. I don’t know if there exist such a generic library?
I would suggest a backtracking LS coupled with a filter strategy. A filter forces one of two quantities (objective and constraint violation) to decrease and, together with the LS, enforces global convergence.
You can have a look at my latest slides about the NLP solver I’m developing: (PDF) Uno: An Open-Source Framework for Unifying Nonlinear Optimization Methods
However, I’m not aware of any libraries that provide these components (yet. My C++ framework will allow that but hasn’t been published yet).
Thanks once again for your prompt response and nice links.
Some related libraries with components of this functionality that may be of interest: