1
$\begingroup$

The idea of Sequential Quadratic Programming is to transform the nonlinear problem into many quadratic problems by:

1) Replacing the objective function with its quadratic approximation 2) Replacing non linear constraints with their linear approximation.

The idea looks interesting and I wish to apply it for solving a problem which has

  • Linear Objective Function
  • Nonlinear constraints

Step 1 is not needed in this case since the objective is already linear.

Is Sequential Quadratic Programming still a good algorithm for this kind of problems? Is it likely to be outperformed by other algorithms which are specific for nonlinear optimisation with linear objective function?

$\endgroup$
3
  • $\begingroup$ Many practical NLPs with linear objectives are solved with SQP methods. E.g. I use SNOPT quite often for such problems. $\endgroup$ Sep 21 '16 at 18:53
  • $\begingroup$ Out of curiosity, can you state your optimization problem? $\endgroup$
    – littleO
    Sep 24 '16 at 5:49
  • $\begingroup$ Jones, MOPTA08 is a nice test problem with linear objective, 124 variables, and 68 nonlinear constraints. Scipy SLSQP gets to f = 222.427 in 20 minutes or so on a mac, on a path feasible $\to$ infeasible $... \to$ feasible. See also NLopt SLSQP. $\endgroup$
    – denis
    Nov 8 '18 at 17:42
2
$\begingroup$

You've made an error in your assumptions. SQP doesn't replace the objective function with a quadratic approximation. Rather, it replaces the the objective function with a quadratic approximation to the Lagrangian. Since the Lagrangian has pieces of the constraints, the algorithm still pays off.

In order to see this, it's easiest to just derive things from Newton's method. Given a problem $$ \min\limits_{x\in X}\{f(x) : g(x)=0\} $$ the first order necessary conditions are $$\begin{array}{rl} \nabla f(x) + g^\prime(x)^*y &= 0\\ g(x)&=0 \end{array}$$ Here, $^*$ means adjoint, which is just the transpose when working in $\ell^2$. This gives a Newton's method system of $$ \begin{bmatrix} \nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y & g^\prime(x)^*\\ g^\prime(x) & 0 \end{bmatrix} \begin{bmatrix} \delta x\\ \delta y\\ \end{bmatrix} = -\begin{bmatrix} \nabla f(x) + g^\prime(x)^*y\\ g(x) \end{bmatrix} $$ Here, $(g^{\prime\prime}(x)\cdot)^*y=\sum\limits_{i=1}^m y_i\nabla^2 g_i(x)$ when working in $\mathbb{R}^m$ with the $\ell^2$ inner product. Anyway, it turns out that this is just the first order optimality conditions for the problem $$\begin{array}{rcl} \min\limits_{\delta x\in X}&&\frac{1}{2}\langle (\nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y)\delta x,\delta x\rangle + \langle \nabla f(x) + g^\prime(x)^*y, \delta x\rangle + (f(x) + \langle g(x),y\rangle\\ st&& g^\prime(x)\delta x + g(x) = 0 \end{array}$$ Here, $\langle x,y\rangle$ denotes the inner product, which, again, is just $x^Ty$ if we're in $\ell^2$. Anyway, note that the objective here is not a quadratic approximation of the objective. It's a quadratic approximation of the Lagrangian. This means it has bits of $g$ in it. Therefore, there's still a reason to the SQP methodology even though $f$ is linear.

Now, as to whether or not some other algorithm is faster, it's hard to tell and depends on the structure of the problem. SQP is a hammer and tends to work very well. Likely, it's the best place to start.


Edit 1

For a derivation and explanation of SQP algorithms, see Nocedal and Wright's Numerical Optimization, chapter 18. Here, you'll find the two forms of visualizing the SQP both from the Newton Method system point of view as well as the quadratic approximation.

As a final note, in that reference, you'll find the form of the quadratic approximation that the NEOS page uses, where there's no gradient of the Lagrangian, but just the gradient of the objective. The way we can obtain this is to take the Newton system:

$$ \begin{bmatrix} \nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y & g^\prime(x)^*\\ g^\prime(x) & 0 \end{bmatrix} \begin{bmatrix} \delta x\\ \delta y\\ \end{bmatrix} = -\begin{bmatrix} \nabla f(x) + g^\prime(x)^*y\\ g(x) \end{bmatrix} $$

Then, notice that $y_+ = y + \delta y$ since we're solving for a new Lagrange multiplier step. If we instead solve for that step directly and note, $\delta y = y_+ - y$ and plug that in, we get

$$ \begin{bmatrix} \nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y & g^\prime(x)^*\\ g^\prime(x) & 0 \end{bmatrix} \begin{bmatrix} \delta x\\ y_+ - y\\ \end{bmatrix} = -\begin{bmatrix} \nabla f(x) + g^\prime(x)^*y\\ g(x) \end{bmatrix} $$

Next, if we multiply this out, we get

$$ \begin{bmatrix} \nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y & g^\prime(x)^*\\ g^\prime(x) & 0 \end{bmatrix} \begin{bmatrix} \delta x\\ y_+\\ \end{bmatrix} = -\begin{bmatrix} \nabla f(x)\\ g(x) \end{bmatrix} $$

which corresponds to the quadratic approximation

$$\begin{array}{rcl} \min\limits_{\delta x\in X}&&\frac{1}{2}\langle (\nabla^2 f(x) + (g^{\prime\prime}(x)\cdot)^*y)\delta x,\delta x\rangle + \langle \nabla f(x), \delta x\rangle + (f(x) + \langle g(x),y\rangle\\ st&& g^\prime(x)\delta x + g(x) = 0 \end{array}$$

This is what the page you linked to uses. I was in error when I said it was incorrect. It is correct. So is the one that I posted above originally. The difference between the two is how we interpret the Lagrange multiplier for the quadratic subproblem. In one, we view the Lagrange multiplier as the step. In the other, we view it as the new Lagrange multiplier directly.

I'll still contend that, most of the time, we're better off just using the Newton's method form directly, which is the linear system above. There, we have all of the information directly and don't need to remember any implicit information such as what the Lagrange multiplier for the quadratic approximation really means. Really, most of the game in these algorithms is how we attack that system and the implication of it. Remember, Newton's method is not guaranteed to converge to a solution unless we'll sufficiently close to the optimum, so the algorithm needs to be globalized with either a line-search or trust-region method. Line-search methods generally need a positive definite Hessian approximation, so they'll replace the Hessian with a quasi-Newton approximation or use a Hessian modification. Trust-region methods needs something that looks like a quadratic model, but is positive definite near optimality, so they'll actually break this up into two steps and use a composite step SQP method in order to meet this requirement. All of that game is generally worked from the linear system point of view and not from the quadratic approximation point of view. It's sort of cute to view an algorithm for optimization as a sequence of optimization problems since we're closing the loop. At the end of the day, the only thing we can really solve are linear systems, so most of the game is generating a linear system that's easy to work with. Quadratic problems have linear systems as their optimality conditions, which is how we end up here.

$\endgroup$
8
  • $\begingroup$ I followed this tutorial for the SQP: neos-guide.org/content/sequential-quadratic-programming . It states that SQP replaces the objective function with a quadratic approximation. My understanding was that the Lagrangian comes into play when making such approximation. Do you confirm this is incorrect? $\endgroup$
    – Vit Ill
    Sep 25 '16 at 9:14
  • $\begingroup$ Yes. That is incorrect. I mean, it's almost correct, but the error is in the definition of q. They correctly use the Hessian of the Lagrangian for the second-order term, that's the L piece. However, rather than have the gradient of f in the expression for q, it should be the gradient of L. Anyway, the Lagrangian has pieces of the constraints in them, so even if you don't believe me, the fact that they have the Hessian of L in there indicates that the constraints are important to the SQP objective. $\endgroup$
    – wyer33
    Sep 26 '16 at 3:07
  • $\begingroup$ Technically, I should be a little bit careful. It may be possible to make that form work if you use an appropriate merit function to fix convergence. However, if you look at the merit functions, it'll be something like the Augmented Lagrangian, which ends up getting you back to the form I discussed above. $\endgroup$
    – wyer33
    Sep 26 '16 at 3:23
  • $\begingroup$ As a final note, personally, I don't like this explanation of SQP because I believe it emphasizes the wrong things. Very specifically, write out the first order optimality conditions. Then, apply Newton's method to this nonlinear system of equations. The game in SQP is how creative we are solving this system. It's symmetric indefinite system, which can be solved directly and has certain properties. Alternatively, there are composite step SQP methods, which solve the linear system in two steps. That has a different behavior. Point being, the Newton form is the easiest to see these tricks. $\endgroup$
    – wyer33
    Sep 26 '16 at 3:25
  • 1
    $\begingroup$ @H.C. The second-order necessary conditions guarantee that the Hessian of the Lagrangian is positive semi-definite on the nullspace of the (active) constraints near optimality. This property is important for rapid convergence near the optimal solution. As far as the Hessian approximations, I'll contend most people don't know how to do it well, so they pick an easy approximation. A full Hessian requires a lot of memory, but the full Hessian is not required if matrix-free methods are used. Further, if an analytic gradient is known, forward mode AD can efficiently produce a hess-vec product. $\endgroup$
    – wyer33
    May 23 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.