On polyhedral projection and parametric programming. (English) Zbl 1211.90119
Summary: This paper brings together two fundamental topics: polyhedral projection and parametric linear programming. First, it is shown that, given a parametric linear program (PLP), a polyhedron exists whose projection provides the solution to the PLP. Second, the converse is tackled and it is shown how to formulate a PLP whose solution is the projection of an appropriately defined polyhedron described as the intersection of a finite number of halfspaces. The input to one operation can be converted to an input of the other operation and the resulting output can be converted back to the desired form in polynomial time – this implies that algorithms for computing projections or methods for solving parametric linear programs can be applied to either problem class.
MSC:
| 90C05 | Linear programming |
References:
| [1] | Blanchini, F.: Set invariance in control–a survey. Automatica 35(11), 1747–1768 (1999) · Zbl 0935.93005 · doi:10.1016/S0005-1098(99)00113-2 |
| [2] | Vidal, R., Schaffert, S., Lygeros, J., Sastry, S.: Controlled invariance of discrete time systems. In: Hybrid Systems: Computation and Control. Lecture Notes in Computer Science, vol. 1790, pp. 437–450. Springer, Berlin (2000) · Zbl 0954.93022 |
| [3] | Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995) · Zbl 0823.52002 |
| [4] | Borrelli, F., Bemporad, A., Morari, M.: A geometric algorithm for multi-parametric linear programming. J. Optim. Theory Appl. 118(3), 515–540 (2003) · Zbl 1061.90086 · doi:10.1023/B:JOTA.0000004869.66331.5c |
| [5] | Bemporad, A., Borrelli, F., Morari, M.: Model predictive control based on linear programming–the explicit solution. IEEE Trans. Autom. Control 47(12), 1974–1985 (2002) · Zbl 1364.93697 · doi:10.1109/TAC.2002.805688 |
| [6] | Gal, T.: Postoptimal Analyses, Parametric Programming and Related Topics, 2nd edn. de Gruyter, Berlin (1995) |
| [7] | Schechter, M.: Polyhedral functions and multiparametric linear programming. J. Optim. Theory Appl. 53(2), 269–280 (1987) · Zbl 0595.90083 · doi:10.1007/BF00939219 |
| [8] | Baotić, M.: An efficient algorithm for multi-parametric quadratic programming. Technical report, ETH Zürich, Institut für Automatik, Physikstrasse 3, CH-8092, Switzerland (2002) |
| [9] | Grieder, P., Borrelli, F., Torrisi, F., Morari, M.: Computation of the constrained infinite time linear quadratic regulator. Automatica 40, 701–708 (2004) · Zbl 1168.93416 · doi:10.1016/j.automatica.2003.11.014 |
| [10] | Tøndel, P., Johansen, T.A., Bemporad, A.: An algorithm for multi-parametric quadratic programming and explicit MPC solutions. In: Proceedings of the 40th IEEE Conference on Decision and Control, Orlando, FL, USA (2001) · Zbl 1019.93019 |
| [11] | Jones, C.N., Kerrigan, E.C., Maciejowski, J.M.: Lexicographic perturbation for multiparametric linear programming with applications to control. Automatica 43(10), 1608–1816 (2007) · Zbl 1127.90068 · doi:10.1016/j.automatica.2007.03.008 |
| [12] | Jaffar, J., Maher, M.J., Stuckey, P.J., Yap, R.H.C.: Projecting clp() constraints. New Gener. Comput. 11(3,4), 449–469 (1993) · Zbl 0780.68013 · doi:10.1007/BF03037187 |
| [13] | Ponce, J., Sullivan, S., Sudsang, A., Boissonnat, J., Merlet, J.: On computing four-finger equilibrium and force-closure grasps of polyhedral objects. Int. J. Robot. Res. 16(1), 11–35 (1997) · doi:10.1177/027836499701600102 |
| [14] | Černikov, S.N.: Contraction of finite systems of linear inequalities. Dokl. Akad. Nauk SSSR 152(5), 1075–1078 (1963) (in Russian). (English translation in Soc. Math. Dokl. 4(5), 1520–1524 (1963)) |
| [15] | Balas, E., Pulleybank, W.R.: The perfectly matchable subgraph polytope of a bipartite graph. Networks 13, 495–516 (1983) · Zbl 0525.90069 · doi:10.1002/net.3230130405 |
| [16] | Fukuda, K., Prodon, A.: Double description method revisited. In: Deza, M., Euler, R., Manoussakis, I. (eds.) Combinatorics and Computer Science. Lecture Notes in Computer Science, vol. 1120, pp. 91–111. Springer, Berlin (1996). Postscript file available from ftp://ftp.ifor.math.ethz.ch/pub/fukuda/reports/ddrev960315.ps.gz |
| [17] | Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8, 295–313 (1992) · Zbl 0752.68082 · doi:10.1007/BF02293050 |
| [18] | Avis, D., Fukuda, K.: Reverse search for enumeration. Discrete Appl. Math. 65, 21–46 (1996) · Zbl 0854.68070 · doi:10.1016/0166-218X(95)00026-N |
| [19] | Amenta, N., Ziegler, G.M.: Shadows and slices of polytopes. In: Proceedings of the 12th Annual Symposium on Computational Geometry, pp. 10–19. ACM Press, New York (1996) |
| [20] | Jones, C.N., Kerrigan, E.C., Maciejowski, J.M.: Equality set projection: a new algorithm for the projection of polytopes in halfspace representation. Technical Report CUED/F-INFENG/TR. 463, Department of Engineering, University of Cambridge, 2004. http://www-control.eng.cam.ac.uk/\(\sim\)cnj22/docs/resp_mar_04_15.pdf |
| [21] | Klee, V., Kleinschmidt, P.: Geometry of the Gass-Saaty parametric cost LP algorithm. Discrete Comput. Geom. 5, 13–26 (1990) · Zbl 0683.90045 · doi:10.1007/BF02187776 |
| [22] | Murty, K.G.: Linear Programming. Wiley, New York (1983) |
| [23] | Tyrrell Rockafellar, R., Wets, R.J.-B.: Variational Analysis. A series of Comprehensive Studies in Mathematics, vol. 317. Springer, Berlin (1998) · Zbl 0888.49001 |
| [24] | Borrelli, F.: Constrained Optimal Control Of Linear And Hybrid Systems. Lecture Notes in Control and Information Sciences, vol. 290. Springer, Berlin (2003) · Zbl 1030.49036 |
| [25] | Spjøtvold, J., Tøndel, P., Johansen, T.A.: A method for obtaining continuous solutions to multiparametric linear programs. In: Proceedings of the 16th IFAC World Congress, Prague (2005) · Zbl 1145.90088 |
| [26] | Jones, C.N.: Polyhedral Tools for Control. PhD thesis, University of Cambridge, July 2005 |
| [27] | Cheng, M.C.: General criteria for redundant and nonredundant linear inequalities. J. Optim. Theory Appl. 53(1), 37–42 (1987) · Zbl 0593.90048 · doi:10.1007/BF00938815 |
| [28] | Padberg, M.: Linear Optimization and Extensions. Algorithms and Combinatorics. Springer, Berlin (1999) · Zbl 0926.90068 |
| [29] | Bemporad, A., Borrelli, F., Morari, M.: Min-max control of constrained uncertain discrete-time linear systems. IEEE Trans. Autom. Control 48(9), 1600–1606 (2003) · Zbl 1364.93181 · doi:10.1109/TAC.2003.816984 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
