Quadratic Programming

Related to work in mixed-integer optimal control, we are interested in an efficient solution of optimal control problems of dynamic processes with many controls. Such problems arise, e.g., from the outer convexification of integer control decisions. We treat this optimal control problem class using the direct multiple shooting method to discretize the optimal control problem. The resulting nonlinear problems are solved using sequential quadratic programming methods. The classical condensing algorithm preprocesses the large but structured quadratic programs to obtain small but dense ones. It can be observed that this approach is not optimal when applied in conjunction with outer convexification.

We developed a new complementary condensing algorithm for quadratic programs with many controls. This algorithm is based on a hybrid null-space range-space approach to exploit the block structure of the quadratic programs that is due to direct multiple shooting. An assessment of the theoretical run time complexity reveals significant advantages of the proposed algorithm.

Selected publications

2019
article
Weber, T., Sager, S., Gleixner, A.
Solving Quadratic Programs to High Precision using Scaled Iterative Refinement
Mathematical Programming Computation
@article{Weber2019,
    author = {Weber, T. and Sager, S. and Gleixner, A.},
    title = {Solving Quadratic Programs to High Precision using Scaled Iterative Refinement},
    journal = {Mathematical Programming Computation},
    year = {2019},
    volume = {11},
    number = {3},
    pages = {421--455},
    doi = {10.1007/s12532-019-00154-6}
}
2016
article
Janka, D., Kirches, C., Sager, S., Wächter, A.
An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix
Mathematical Progamming Computation
@article{Janka2016,
    author = {Janka, D. and Kirches, C. and Sager, S. and W\"achter, A.},
    title = {An {SR1/BFGS SQP} algorithm for nonconvex nonlinear programs with block-diagonal {H}essian matrix},
    journal = {Mathematical {P}rogamming {C}omputation},
    year = {2016},
    volume = {8},
    number = {4},
    pages = {435--459},
    doi = {10.1007/s12532-016-0101-2}
}
2015
article
Frasch, J. V., Sager, S., Diehl, M.
A parallel quadratic programming method for dynamic optimization problems
Mathematical Programming Computation
@article{Frasch2015,
    author = {Frasch, J. V. and Sager, S. and Diehl, M.},
    title = {A parallel quadratic programming method for dynamic optimization problems},
    journal = {Mathematical {P}rogramming {C}omputation},
    year = {2015},
    volume = {7},
    number = {3},
    pages = {289--329}
}
2014
phdthesis
Frasch, J.
Parallel Algorithms for Optimization of Dynamic Systems in Real-Time
Otto von Guericke University Magdeburg
@phdthesis{Frasch2014,
    author = {Frasch, J.},
    title = {{P}arallel {A}lgorithms for {O}ptimization of {D}ynamic {S}ystems in {R}eal-{T}ime},
    school = {Otto von Guericke University Magdeburg},
    year = {2014},
    url = {https://mathopt.de/publications/Frasch2014.pdf}
}
2013
article
Frasch, J. V., Vukov, M., Ferreau, H., Diehl, M.
A dual Newton strategy for the efficient solution of sparse quadratic programs arising in SQP-based nonlinear MPC
Optimization Online
@article{Frasch2013c,
    author = {Frasch, J. V. and Vukov, M. and Ferreau, H.J. and Diehl, M.},
    title = {{A} dual {N}ewton strategy for the efficient solution of sparse quadratic programs arising in {SQP}-based nonlinear {MPC}},
    journal = {{O}ptimization {O}nline},
    year = {2013},
    note = {Optimization Online 3972},
    url = {http://www.optimization-online.org/DB_HTML/2013/07/3972.html}
}
2013
inproceedings
Kozma, A., Frasch, J. V., Diehl, M.
A Distributed Method for Convex Quadratic Programming Problems Arising in Optimal Control of Distributed Systems
Proceedings of the 52nd Conference on Decision and Control (CDC)
@inproceedings{Kozma2013a,
    author = {Kozma, A. and Frasch, J. V. and Diehl, M.},
    title = {{A} {D}istributed {M}ethod for {C}onvex {Q}uadratic {P}rogramming {P}roblems {A}rising in {O}ptimal {C}ontrol of {D}istributed {S}ystems},
    booktitle = {{P}roceedings of the 52nd {C}onference on {D}ecision and {C}ontrol ({CDC})},
    year = {2013}
}
2011
mastersthesis
Burgdörfer, H.
Strukturausnutzende Algorithmen der Quadratischen Programmierung für gemischt-ganzzahlige Optimalsteuerung
Universität Heidelberg
@mastersthesis{Burgdoerfer2011,
    author = {Burgd\"orfer, H.},
    title = {{S}trukturausnutzende {A}lgorithmen der {Q}uadratischen {P}rogrammierung f\"ur gemischt-ganzzahlige {O}ptimalsteuerung},
    school = {Universit\"at Heidelberg},
    year = {2011}
}
2011
article
Kirches, C., Bock, H., Schlöder, J., Sager, S.
Block Structured Quadratic Programming for the Direct Multiple Shooting Method for Optimal Control
Optimization Methods and Software
@article{Kirches2010b,
    author = {Kirches, C. and Bock, H.G. and Schl\"{o}der, J.P. and Sager, S.},
    title = {{B}lock {S}tructured {Q}uadratic {P}rogramming for the {D}irect {M}ultiple {S}hooting {M}ethod for {O}ptimal {C}ontrol},
    journal = {{O}ptimization {M}ethods and {S}oftware},
    year = {2011},
    volume = {26},
    number = {2},
    pages = {239--257},
    url = {http://www.informaworld.com/smpp/content~db=all~content=a919763304~frm=titlelink},
    doi = {10.1080/10556781003623891}
}

Prof. Dr. rer.nat. habil. Sebastian Sager
Head of MathOpt group
at the Institute of Mathematical Optimization
at the Faculty of Mathematics
at the Otto von Guericke University Magdeburg

Universitätsplatz 2, G02-224
39106 Magdeburg, Germany

: +49 391 67 58745
: +49 391 67 11171
:

Susanne Heß

Universitätsplatz 2, G02-206
39106 Magdeburg, Germany

: +49 391 67-58756
: +49 391 67-11171
:

Prof. Dr. rer.nat. habil. Sebastian Sager
Head of MathOpt group
at the Institute of Mathematical Optimization
at the Faculty of Mathematics
at the Otto von Guericke University Magdeburg

Universitätsplatz 2, G02-224
39106 Magdeburg, Germany

: +49 391 67 58745
: +49 391 67 11171
:

Susanne Heß

Universitätsplatz 2, G02-206
39106 Magdeburg, Germany

: +49 391 67-58756
: +49 391 67-11171
: