Abstract
For multiparametric convex nonlinear programming problems we propose a recursive algorithm for approximating, within a given suboptimality tolerance, the value function and an optimizer as functions of the parameters. The approximate solution is expressed as a piecewise affine function over a simplicial partition of a subset of the feasible parameters, and it is organized over a tree structure for efficiency of evaluation. Adaptations of the algorithm to deal with multiparametric semidefinite programming and multiparametric geometric programming are provided and exemplified. The approach is relevant for real-time implementation of several optimization-based feedback control strategies.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
C.B. Barber, D.P. Dobkin, and H. Huhdanpaa, “Qhull homepage,” The Geometry Center, University of Minnesota, 1993. http://www.geom.umn.edu/software/qhull/.
A. Bemporad, F. Borrelli, and M. Morari, “Model Predictive Control Based on Linear Programming—The Explicit Solution,” IEEE Trans. Automatic Control, vol. 47, no. 12, pp. 1974–1985, 2002a.
A. Bemporad and C. Filippi, “Approximate Multiparametric Convex Programming,” In Proc. 42th IEEE Conf. on Decision and Control, Maui, Hawaii, USA, pp. 3185–3190, 2003a.
A. Bemporad and C. Filippi, “Suboptimal explicit RHC via approximate multiparametric quadratic programming,” Journal of Optimization Theory and Applications, vol. 117, no. 1, pp. 9–38, 2003b.
A. Bemporad, M. Morari, V. Dua, and E.N. Pistikopoulos, “The Explicit Linear Quadratic Regulator for Constrained Systems,” Automatica, vol. 38, no. 1, pp. 3–20, 2002b.
H.Y. Benson and R.J. Vanderbei, “Solving Problems with Semidefinite and Related Constraints Using Interior-Point Methods for Nonlinear Programming,” Mathematical Programming, vol. 95, no. 2, pp. 279–302, 2003.
F. Borrelli, A. Bemporad, and M. Morari, “A Geometric Algorithm for Multi-Parametric Linear Programming,” Journal of Optimization Theory and Applications, vol. 118, no. 3, pp. 515–540, 2003.
S. Boyd and L. Vandenberghe, “Convex optimization,” Cambridge, MA: Cambridge University Press. http://www.stanford.edu/boyd/cvxbook.html, 2004.
E.F. Camacho and C. Bordons, “Model Predictive Control,” Advanced Textbooks in Control and Signal Processing, London: Springer-Verlag, 2nd edition, 2004.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest, Introduction to Algorithms, Chapt.5. New York: McGraw-Hill, 1990.
R.J. Duffin, E.L. Peterson, and C. Zener, “Geometric Programming — Theory and Applications,” New York: Wiley, 1967.
A.V. Fiacco, “Introduction to sensitivity and stability analysis in nonlinear programming,” London, U.K., Academic Press, 1983.
A.V. Fiacco and J. Kyparisis, “Computable bounds on parametric solutions of convex problems,” Mathematical Programming, vol. 40, pp. 213–221, 1988.
C. Filippi, “An Algorithm for Approximate Multiparametric Linear Programming,” Journal of Optimization Theory and Applications, vol. 120, no. 1, pp. 73–95, 2004.
T. Gal, Postoptimal Analyses, Parametric Programming, and Related Topics, Berlin: de Gruyter, 2nd edition, 1995.
D. Goldfarb and K. Scheinberg, “On Parametric Semidefinite Programming,” Applied Numerical Mathematics, vol. 29, pp. 361–377, 1999.
J.E. Goodman and J. O’Rourke (Eds.), “Handbook of Discrete and Computational Geometry,” Discrete Mathematics and Its Applications, New York: CRC Press, 1997.
E. Hansen, “Global optimization with data perturbation,” Computers and Operations Research, vol. 11, pp. 97–104, 1984.
R. Horst and N.V. Thoai, “DC Programming: Overview,” Journal of Optimization Theory and Applications, vol. 103, no. 1, pp. 1–43, 1999.
T.A. Johansen, “On Multi-parametric Nonlinear Programming and Explicit Nonlinear Model Predictive Control,” In Proc. 41th IEEE Conf. on Decision and Control, Las Vegas, Nevada, USA, pp. 2768–2773, 2002.
T.A. Johansen, “Approximate explicit receding horizon control of constrained nonlinear systems,” Automatica, vol. 40, no. 2, pp. 293–300, 2004.
T.A. Johansen and A. Grancharova, “Approximate explicit constrained linear model predictive control via orthogonal search tree,” IEEE Trans. Automatic Control, vol. 48, no. 5, pp. 810–815, 2003.
J. Maciejowski, Predictive Control with Constraints, Harlow, UK: Prentice Hall, 2002.
O.L. Mangasarian and J.B. Rosen, “Inequalities for stochastic nonlinear programming problems,” Operations Research, vol. 12, pp. 143–154, 1964.
D. Muñoz de la Peña, A. Bemporad, and C. Filippi, “Robust Explicit MPC Based on Approximate Multi-parametric Convex Programming,” In Proc. 43th IEEE Conf. on Decision and Control, Paradise Island, Bahamas, pp. 2491–2496, 2004.
K.G. Murty, “Computational complexity of parametric linear programming,” Mathematical Programming, vol. 19, pp. 213–219, 1980.
S.M. Robinson, “Computable error bounds for nonlinear programming,” Mathematical Programming, vol. 5, 235–242, 1973.
C. Rowe and J.M. Maciejowski, “An Algorithm for Multi-Parametric Mixed Integer Semidefinite Optimisation,” In Proc. 42th IEEE Conf. on Decision and Control, Maui, Hawaii, USA, pp. 3197–3202, 2003.
R. Seidel, “Exact upper bounds for the number of faces in d-dimensional Voronoi diagram,” In P. Gritzmann and B. Sturmfels (Eds.): Applied Geometry and Discrete Mathematics—The Victor Klee Festschrift, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Providence, RI: American Mathematical Society, pp. 517–529, 1991.
M. Seron, J. DeDoná, and G. Goodwin, “Global Analytical Model Predictive Control with Input Constraints,” In Proc. 39th IEEE Conf. on Decision and Control, Sydney, Australia, pp. 154–159, 2000.
P. Tøndel, T.A. Johansen, and A. Bemporad, “An Algorithm for Multi-parametric Quadratic Programming and Explicit MPC solutions,” Automatica, vol. 39, no. 3, 489–497, 2003.
L. Vandenberghe, S. Boyd, and B. Alkire, “SP — Software for Semidefinite Programming (Version 1.1),” http://www.ee.ucla.edu/vandenbe/sp.html, 1999.
L. Yepremyan and J. Falk, “Delaunay partitions in n applied to non-convex programs and vertex/facet enumeration problems,” Computers and Operations Research, vol. 32, 793–812, 2005.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bemporad, A., Filippi, C. An Algorithm for Approximate Multiparametric Convex Programming. Comput Optim Applic 35, 87–108 (2006). https://doi.org/10.1007/s10589-006-6447-z
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10589-006-6447-z