Convergence of Sequential Quadratic Programming (SQP) My question is regarding Sequential Quadratic Programming (SQP) for nonlinear programming problem. I am new to SQP algorithm, but I hope to get some advice and learn more about SQP. I am investigating the problem with linear objective function, quadratic equality constraints, and box constraints, given as below:
\begin{align}
    \underset{x,u}{\mathrm{min}} &\,\,\, q^\top x\\
    \mathrm{s.t.} &\,\,\, x^\top P x + p^\top x - b = 0,\\
                  &\,\,\, x \geq 0,
\end{align}
where $P$ is not necessarily positive (semi)definite. To solve the above problem, I am trying to apply sequential quadratic programming (SQP). But, from my studying, it requires a certain assumptions for convergence, including the following statement:
The Hessian of the Lagrangian with respect to $x$ is positive definite on the null space of $G(x^∗)^\top$, i.e. $d^\top H \mathcal{L}^* d > 0$ for all $d \neq 0$ such that $G(x^∗)^\top d = 0$ where $\mathcal{L}$ is the Lagrangian function, $H\mathcal{L}$ denotes Hessian of the Lagrangian function, $\mathcal{L}^* = \mathcal{L}(x^*,\lambda^*)$, and $G(x) := [\nabla h_1(x), \ldots, \nabla h_m(x)]$.
Regarding the problem, I have two questions.

*

*Will SQP converge for the above problem even if the Hessian of the Lagrangian function is not positive definite?


*The second question is more fundamental question regarding the SQP algorithm itself. In SQP algorithm, $H \mathcal{L}$ is approximated using some methods, e.g., Broyden-Fletcher-Goldfarb-Shanno (BFGS). Why do we need to approximate Hessian of the Lagrangian function? For example, in the above problem, I think we can get an explicit expression for the Lagrangian function as well as Hessian of the Lagrangian function.
 A: There's a couple of things going, so we need to disambiguate them.  First, it's important to realize that SQP isn't exactly a singular algorithm, but a general idea that can be implemented in multiple ways.  For example, one version of SQP is to simply take a quadratic approximation of the Lagrangian and a linear approximation of the constraints and to iteratively solve the optimality conditions.  Another version can splits each optimization step into two pieces, a step to feasibilty (quasi-normal step), and a step to optimality (tangential step.)  Both of these are SQP, but they are also different algorithms.  In addition, there are different globalization strategies that can be considered such as trust-region versus line-search.  Each one of these choices results in different algorithms.  Alternatively, there's a choice of which merit function to use such as differentiable versus non-differentiable.  Maybe we want to use a filter method.  Also, layered on this decision is whether something like a second-order correction step is or is not taken.  Each one of these decisions leads to a slightly different algorithm.  This is important because it takes us to the first question.

*

*Generally speaking, it's not exactly right to ask whether or not SQP converges.  We could be a little more precise and ask does a particular variety of SQP converge, but this isn't really the right question either.  It's really more proper to ask whether the particular globalization scheme chosen for a particular SQP algorithm guarantees convergence from an arbitrary starting point. For the most part, the choice boils down to trust-region vs line-search and merit functions vs filter method.  It's not entirely that simply, but it's mostly that.  For example, IPOPT uses a line-search with a filter method.  NITRO uses trust-region with a non-differentiable merit function.  Both are SQP and both converge.


*As for whether not not to use BFGS, a lot of this in my opinion is historical.  BFGS can be implemented with very little memory and it gives a positive definite approximation to the Hessian.  Before computers had much memory and the use of Krylov methods with optimization algorithms became common, being able to get some kind of approximation to the Hessian was valuable because the full-Hessian requires a large amount of memory.  Second, having a positive definite approximation was valuable because it meant that the inverse of the BFGS hessian times the gradient guaranteed a descent direction, which is useful for globalization (convergence from a starting point.)  That said, I'll argue that neither one of these benefits is really that important given modern technology.  As far as memory goes, just solve the optimality system using truncated-CG (Steihaug-Toint), which guarantees a descent direction and doesn't require a full-Hessian.  Rather, only Hessian-vector products are required and these can be computed efficient with little memory.  Specifically, as long as a code is available to generate the gradient, a forward-mode AD algorithm can be layered on top of this and it can be computed in twice the memory and twice the computational time.  If you can't spare enough memory for two gradients, you're already in a huge amount of trouble.  Now, that said, it's far easily to just implement a BFGS Hessian that it is to develop and maintain infrastructure to support a more complicated linear solver and AD tool set.  It's not cleanly written down in half a page like BFGS can be.  As such, I'll contend the ease of understanding and it's historical use is why it tends to be used to this day.  As to whether or not it works just as well, it depends, but I'll contend the answer most of the time is no.  It really depends on how complicated the spectrum of the Hessian is and how quickly it changes.  BFGS sort of, but not exactly, captures one eigenvector/value pair for each vector that it adds to the approximation (SR1 captures exactly one, but is not positive definite.)  That means that if the the objective was strictly quadratic and contained m variables and the eigenvalues are spread apart, it takes about m iterations or so to find the exact Hessian.  Or, you could just use the actual Hessian with a Krylov method like CG and every iteration there would capture an eigenvalue.  Now, it depends on how far apart the eigenvalues are spread for things actually work, but, frankly, Krylov methods do a better job than BFGS.  This is also assuming that the Hessian is quadratic and doesn't change iteration by iteration.  If it changes, BFGS will have stale information.  At the end of the day, it doesn't really matter if the true Hessian is captured or not; it only matters if we find an optimal solution quickly and efficiently.  That said, it generally helps to have a good Hessian approximation because it means that we have a better quadratic approximation, which assists in fast convergence near an optimal solution as well as more accurately determining step lengths when far from the optimal solution.
By the way, for your problem, you have an additional choice not discussed above.  You also need to choose how you want to deal with the box constraint.  There are projection methods, interior point methods (reflective or primal-dual), and active set methods.  Each choice will also impact your algorithm and convergence.  Generally speaking, projection is probably the easiest to implement, but interior-point tends to work the best when properly implemented and tuned.
