TY - JOUR

T1 - An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix

AU - Janka, Dennis

AU - Kirches, Christian

AU - Sager, Sebastian

AU - Wächter, Andreas

N1 - Publisher Copyright:
© 2016, Springer-Verlag Berlin Heidelberg and The Mathematical Programming Society.

PY - 2016/12/1

Y1 - 2016/12/1

N2 - We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.

AB - We present a quasi-Newton sequential quadratic programming (SQP) algorithm for nonlinear programs in which the Hessian of the Lagrangian function is block-diagonal. Problems with this characteristic frequently arise in the context of optimal control; for example, when a direct multiple shooting parametrization is used. In this article, we describe an implementation of a filter line-search SQP method that computes search directions using an active-set quadratic programming (QP) solver. To take advantage of the block-diagonal structure of the Hessian matrix, each block is approximated separately by quasi-Newton updates. For nonconvex instances, that arise, for example, in optimum experimental design control problems, these blocks are often found to be indefinite. In that case, the block-BFGS quasi-Newton update can lead to poor convergence. The novel aspect in this work is the use of SR1 updates in place of BFGS approximations whenever possible. The resulting indefinite QPs necessitate an inertia control mechanism within the sparse Schur-complement factorization that is carried out by the active-set QP solver. This permits an adaptive selection of the Hessian approximation that guarantees sufficient progress towards a stationary point of the problem. Numerical results demonstrate that the proposed approach reduces the number of SQP iterations and CPU time required for the solution of a set of optimal control problems.

KW - Direct methods for optimal control

KW - Optimum experimental design

KW - Quasi-Newton

KW - Sequential quadratic programming

UR - http://www.scopus.com/inward/record.url?scp=84994050050&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84994050050&partnerID=8YFLogxK

U2 - 10.1007/s12532-016-0101-2

DO - 10.1007/s12532-016-0101-2

M3 - Article

AN - SCOPUS:84994050050

VL - 8

SP - 435

EP - 459

JO - Mathematical Programming Computation

JF - Mathematical Programming Computation

SN - 1867-2949

IS - 4

ER -