Article ID: | iaor20042315 |
Country: | Netherlands |
Volume: | 118 |
Issue: | 3 |
Start Page Number: | 515 |
End Page Number: | 540 |
Publication Date: | Sep 2003 |
Journal: | Journal of Optimization Theory and Applications |
Authors: | Bemporad A., Borrelli F., Morari M. |
Keywords: | control processes |
We propose a novel algorithm for solving multiparametric linear programming (LP) problems. Rather than visiting different bases of the associated LP tableau, we follow a geometric approach based on the direct exploration of the parameter space. The resulting algorithm has computational advantages, namely the simplicity of its implementation in a recursive form and an efficient handling of primal and dual degeneracy. Illustrative examples describe the approach throughout the paper. The algorithm is used to solve finite-time constrained optimal control problems for discrete-time linear dynamical systems.