1
$\begingroup$

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.

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

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

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

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

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

$\endgroup$
5
  • $\begingroup$ Thank you! I should read your advice more carefully, but could you give additional comment if I could get computational benefits from exploiting the structure of my problem (i.e., quadratic constraints) compared to general nonlinear constraints, using these methods, either SQP, projection, or interior point? $\endgroup$
    – H.C.
    May 25, 2021 at 17:28
  • 1
    $\begingroup$ There's likely something really clever that can be done, but I'm not sure what. If anything, you have a really cheap way to compute the gradient and Hessian of the Lagrangian quickly, which should make the algorithm faster. Depending on the flavor of SQP you're using, the preconditioner for the linear systems should be easy to put together because all elements are immediately available and there's only a single equality constraint. Generally speaking, my bias is just to use the general algorithm and make the individual calculations fast and stable. This is not always the right approach. $\endgroup$
    – wyer33
    May 26, 2021 at 6:23
  • $\begingroup$ Thank you very much for all the detailed answers. I really appreciate it. One more flavor: could you recommend a specific SQP algorithm that you think is the best, and provide any papers that I can learn the details of the algorithm step by step? I would like to start with a standard algorithm, then try to see if I can modify to exploit quadratic structure of the problem. $\endgroup$
    – H.C.
    May 26, 2021 at 22:22
  • 1
    $\begingroup$ To be clear, everyone has their own opinion on this. Personally, I prefer composite step methods, which break the step into feasibility and optimality. Both of these papers are dense, but use this methodology: "A Matrix-Free Trust-Region SQP Method for Equality Constrained Optimization" by Heinkenschloss and Ridzal and "An Interior Point Algorithm for Large-Scale Nonlinear Programming" by Byrd et al. The book "Trust-Region Methods" by Conn et al will provide some context, but is also dense. "Numerical Optimization" by Nocedal and Wright also goes over the method on page 578. $\endgroup$
    – wyer33
    May 27, 2021 at 13:57
  • 1
    $\begingroup$ If you really want to investigate further, there's a long line of papers written at Rice University that puzzle through how to setup trust-region problems in different ways. I'll contend that El-Alem's thesis from 1988 started to expose an important methodology, but the papers from Richard Tapia, Yin Zhang, John Dennis, Matthias Heinkenschloss, and Denis Ridzal show a long line of improvement in SQP algorithms, which are published, but not collected into a book. This is not the only way to do things, but a good example of generational research at a singular institution. $\endgroup$
    – wyer33
    May 27, 2021 at 14:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .