# Line-search SQP

**URL:** <https://discourse.julialang.org/t/line-search-sqp/75547>\
**Category:** Optimization (Mathematical)\
**Tags:** optim, optimization\
**Created:** [January 31, 2022, 10:12pm UTC](https://discourse.julialang.org/t/line-search-sqp/75547 "2022-01-31T22:12:35Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![AhmedAlreweny](https://avatars.discourse-cdn.com/v4/letter/a/db5fbb/32.png) [@AhmedAlreweny](https://discourse.julialang.org/u/AhmedAlreweny)\
**Post date:** [January 31, 2022, 10:12pm UTC](https://discourse.julialang.org/t/line-search-sqp/75547/1 "2022-01-31T22:12:35Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [January 31, 2022, 11:27pm UTC](https://discourse.julialang.org/t/line-search-sqp/75547/2 "2022-01-31T23:27:50Z")

</div>

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](http://www.apmath.spbu.ru/cnsa/pdf/monograf/Numerical_Optimization2006.pdf). 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.

---

<div class="post-metadata">

**Author:** ![AhmedAlreweny](https://avatars.discourse-cdn.com/v4/letter/a/db5fbb/32.png) [@AhmedAlreweny](https://discourse.julialang.org/u/AhmedAlreweny)\
**Post date:** [February 1, 2022, 8:50am UTC](https://discourse.julialang.org/t/line-search-sqp/75547/3 "2022-02-01T08:50:31Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![cvanaret](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/cvanaret/32/11594_2.png) [@cvanaret](https://discourse.julialang.org/u/cvanaret)\
**Post date:** [February 1, 2022, 9:16am UTC](https://discourse.julialang.org/t/line-search-sqp/75547/4 "2022-02-01T09:16:58Z")

</div>

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: [https://www.researchgate.net/publication/354921761](https://www.researchgate.net/publication/354921761)

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

---

<div class="post-metadata">

**Author:** ![AhmedAlreweny](https://avatars.discourse-cdn.com/v4/letter/a/db5fbb/32.png) [@AhmedAlreweny](https://discourse.julialang.org/u/AhmedAlreweny)\
**Post date:** [February 1, 2022, 9:24am UTC](https://discourse.julialang.org/t/line-search-sqp/75547/5 "2022-02-01T09:24:24Z")

</div>

Thanks once again for your prompt response and nice links.

---

<div class="post-metadata">

**Author:** ![jd-foster](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jd-foster/32/35824_2.png) [@jd-foster](https://discourse.julialang.org/u/jd-foster)\
**Post date:** [February 3, 2022, 2:32am UTC](https://discourse.julialang.org/t/line-search-sqp/75547/6 "2022-02-03T02:32:04Z")

</div>

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

- The [JuliaSmoothOptimizers](https://juliasmoothoptimizers.github.io/) ecosystem:
  - [https://github.com/JuliaSmoothOptimizers](https://github.com/JuliaSmoothOptimizers)
  - For PDE-specifically (optimization problem with partial differential equation in the constraints) see [https://github.com/JuliaSmoothOptimizers/PDENLPModels.jl](https://github.com/JuliaSmoothOptimizers/PDENLPModels.jl)

- NLSolve.jl with LineSearches.jl: [https://github.com/JuliaNLSolvers/NLsolve.jl#newton-method-with-linesearch](https://github.com/JuliaNLSolvers/NLsolve.jl#newton-method-with-linesearch)