Line-search SQP

Hi,

I am trying to solve a PDE-constrained optimization problem that can be written as:

minimize f(x)
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.

4 Likes

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).

2 Likes

Thanks once again for your prompt response and nice links.

1 Like

Some related libraries with components of this functionality that may be of interest:

2 Likes