Mathematical Algorithmic Optimization - Otto-von-Guericke-University Magdeburg

 
 
 
 
 
 
 
 

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



AuthorTitleYearJournal/ProceedingsReftypeLink
Burgdörfer, H. Strukturausnutzende Algorithmen der Quadratischen Programmierung für gemischt-ganzzahlige Optimalsteuerung 2011 School: Universität Heidelberg   mastersthesis
 
BibTeX:
@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}
}
Frasch, J. Parallel Algorithms for Optimization of Dynamic Systems in Real-Time 2014 School: Otto-von-Guericke University Magdeburg   phdthesis
preprint  
BibTeX:
@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://www.mathopt.de/PUBLICATIONS/Frasch2014.pdf}
}
Frasch, J. V., Sager, S. & Diehl, M. A parallel quadratic programming method for dynamic optimization problems 2015 Mathematical Programming Computation   article
 
BibTeX:
@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}
}
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 2013 Optimization Online   article
preprint  
BibTeX:
@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}
}
Janka, D., Kirches, C., Sager, S. & Wächter, A. An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix 2016 Mathematical Progamming Computation   article DOI
 
BibTeX:
@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 = {http://dx.doi.org/10.1007/s12532-016-0101-2}
}
Kirches, C., Bock, H., Schlöder, J. & Sager, S. Block Structured Quadratic Programming for the Direct Multiple Shooting Method for Optimal Control 2011 Optimization Methods and Software   article DOI
preprint  
BibTeX:
@article{Kirches2010b,
  author = {C. Kirches and H.G. Bock and J.P. Schl\"{o}der and S. Sager},
  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 = {http://dx.doi.org/10.1080/10556781003623891}
}
Kozma, A., Frasch, J. V. & Diehl, M. A Distributed Method for Convex Quadratic Programming Problems Arising in Optimal Control of Distributed Systems 2013 Proceedings of the 52nd Conference on Decision and Control (CDC)   inproceedings
 
BibTeX:
@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}
}

Further references of the MathOpt group can be found on this page.

Last Modification: 2016-05-12 - Contact Person: Sebastian Sager - Impressum