ASL: Hessian-vector products in trust-region SQP method

Support
1

Hi all,
I’m using the ASL library in a trust-region SQP method and I encountered a major issue. Here’s what basically happens:

  • we start from a primal-dual iterate at which we evaluate the functions.
  • we define the QP approximation with an \ell_\infty trust-region constraint (= bound constraints). The Hessian is not formed explicitly because the QP solver works with Hessian-vector products.
  • we solve the QP and get a direction.
  • we form the trial iterate (the current point + the direction) and evaluate the objective and the constraints at this point.
  • if the trial iterate makes enough progress wrt objective and constraint violation, we replace the current iterate with the trial iterate.
  • otherwise, we reduce the trust-region radius and update the bounds of the QP (apart from the bounds, the QP definition should stay the same).
  • we resolve the QP.
  • and so on.

You probably noticed the issue: if the trial iterate was rejected, the Hessian definition changed from one trust-region iteration to the next because we evaluated the objective and constraints at the trial iterate. According to the ASL manual, there’s no workaround here. Should I just use the explicit Hessian?
Thanks,

Charlie

2

Our expert on ASL replies as follows:

Hessian-vector products are computed at the last place where the objective and constraints were evaluated. (Those evaluations compute partial derivatives used in Hessian-vector products.)

For the algorithm that you have sketched, when backtracking (trying a smaller trust radius) you could recompute the relevant functions again before doing Hessian-vector products and changed bounds. More efficient is to maintain two copies of the place where the partials are stored. That is easiest with ASL2 (source solvers2.tgz), where you just need to pass the desired workspace to the function evaluation routines. If you have two workspaces, say w1 and w2, declared by

EvalWorkspace *w1, *w2;

and obtained by

w1 = ewalloc();
w2 = ewalloc();

you might call opjval_ew(w1,np,x,ne) for an objective (np = 0 for the first objective — most of the time there is just one objective) when computing the objective at a point x where you want to compute Hessian-vector product, and opjval_ew(w2,np,x,ne) at trial points. When you find a trial point where you want to compute new Hessian-vector products, just interchange w1 and w2 (by w3 = w1; w1 = w2; w2 = w3;).

You could alternatively use two ASL pointers, but that would require calling the reader twice — duplicate effort best avoided. However, if you insist on using ASL1 (solvers.tgz, the original ASL), then you will need to follow this latter course.

1 Like
3

Hi @4er,
Thanks for your feedback! Upgrading to solvers2 seems like a great idea, I’ll give it a try. I’m also hoping it will make its way into the Julia ecosystem (see my request here).