Constructive solution of inverse parametric linear/quadratic programming problems. (English) Zbl 1372.90105
Summary: Parametric convex programming has received a lot of attention, since it has many applications in chemical engineering, control engineering, signal processing, etc. Further, inverse optimality plays an important role in many contexts, e.g., image processing, motion planning. This paper introduces a constructive solution of the inverse optimality problem for the class of continuous piecewise affine functions. The main idea is based on the convex lifting concept. Accordingly, an algorithm to construct convex liftings of a given convexly liftable partition will be put forward. Following this idea, an important result will be presented in this article: Any continuous piecewise affine function defined over a polytopic partition is the solution of a parametric linear/quadratic programming problem. Regarding linear optimal control, it will be shown that any continuous piecewise affine control law can be obtained via a linear optimal control problem with the control horizon at most equal to 2 prediction steps.
Keywords:
convex liftings; parametric convex programming; inverse optimality; piecewise affine functionsReferences:
| [1] | Johansen, T.A.: On multi-parametric nonlinear programming and explicit nonlinear model predictive control. In: Proceedings of the 41st IEEE Conference on Decision and Control, vol. 3, pp. 2768-2773 (2002) |
| [2] | Johansen, T.A.: Approximate explicit receding horizon control of constrained nonlinear systems. Automatica 40(2), 293-300 (2004) · Zbl 1051.49018 · doi:10.1016/j.automatica.2003.09.021 |
| [3] | Grancharova, A., Johansen, T. A.: Explicit Nonlinear Model Predictive Control: Theory and Applications, vol. 429. Springer Science & Business Media (2012) · Zbl 1401.93004 |
| [4] | Bemporad, A., Morari, M., Dua, V., Pistikopoulos, E.N.: The explicit linear quadratic regulator for constrained systems. Automatica 38(1), 3-20 (2002) · Zbl 0999.93018 · doi:10.1016/S0005-1098(01)00174-1 |
| [5] | Tøndel, P., Johansen, T.A., Bemporad, A.: An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica 39(3), 489-497 (2003) · Zbl 1019.93019 · doi:10.1016/S0005-1098(02)00250-9 |
| [6] | Seron, M.M., Goodwin, G.C., Doná, J.A.: Characterisation of receding horizon control for constrained linear systems. Asian J. Control 5(2), 271-286 (2003) · doi:10.1111/j.1934-6093.2003.tb00118.x |
| [7] | Olaru, S., Dumur, D.: A parameterized polyhedra approach for explicit constrained predictive control. In: 43rd IEEE Conference on Decision and Control, vol. 2, pp. 1580-1585 (2004) · Zbl 1367.90103 |
| [8] | Pistikopoulos, E.N., Georgiadis, M.C., Dua, V.: Multi-parametric Programming. Wiley, London (2007) · doi:10.1002/9783527631216 |
| [9] | Feller, C., Johansen, T.A., Olaru, S.: An improved algorithm for combinatorial multi-parametric quadratic programming. Automatica 49(5), 1370-1376 (2013) · Zbl 1319.90048 · doi:10.1016/j.automatica.2013.02.022 |
| [10] | Baes, M., Diehl, M., Necoara, I.: Every continuous nonlinear control system can be obtained by parametric convex programming. IEEE Trans. Autom. Control 53(8), 1963-1967 (2008) · Zbl 1367.90103 · doi:10.1109/TAC.2008.928131 |
| [11] | Hempel, A., Goulart, P., Lygeros, J.: On inverse parametric optimization with an application to hybrid scontrol. IEEE Trans. Autom. Control 60(4), 1064-1069 (2015) · Zbl 1360.90241 · doi:10.1109/TAC.2014.2336992 |
| [12] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P., Hovd, M., Necoara, I.: Inverse parametric convex programming problems via convex liftings. In: 19th IFAC World Congress, Cape Town, South Africa (2014) · Zbl 1334.49111 |
| [13] | Maxwell, J.C.: On reciprocal diagrams and diagrams of forces. Philos. Mag. (4) 27, 250-261 (1864) |
| [14] | Crapo, H., Whiteley, W.: Plane self stresses and projected polyhedra. 1: The basic pattern. Struct. Topol. 19, 55-73 (1993) · Zbl 0793.52006 |
| [15] | Crapo, H., Whiteley, W.: Spaces of stresses, projections and parallel drawings for spherical polyhedra. Contrib. Algebra Geom. 35(2), 259-281 (1994) · Zbl 0819.52018 |
| [16] | Aurenhammer, F.: Recognising polytopical cell complexes and constructing projection polyhedra. J. Symb. Comput. 3, 249-255 (1987) · Zbl 0633.68086 · doi:10.1016/S0747-7171(87)80003-2 |
| [17] | Aurenhammer, F.: Criterion for the affine equivalence of cell complexes in \[r^d\] rd and convex polyhedra in \[r^{d+1}\] rd+1. Discrete Comput. Geom. 2, 49-64 (1987) · Zbl 0608.52006 · doi:10.1007/BF02187870 |
| [18] | Rybnikov, K.: Polyhedral partitions and stresses. Ph.D. thesis, Queen University, Kingston(1999) · Zbl 0941.52008 |
| [19] | Schulz, A.: Lifting planar graphs to realize integral 3-polytopes and topics in pseudo-triangulations. Ph.D. thesis, Fachbereich Mathematik und Informatik der Freien Universitat Berlin (2008) |
| [20] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P., Hovd, M., Necoara, I.: On the lifting problems and their connections with piecewise affine control law design. In: European Control Conference, Strasbourg, France (2014) · Zbl 0999.93018 |
| [21] | Grüunbaum, B.: Convex Polytopes. Wiley, London (1967) · Zbl 0163.16603 |
| [22] | Aubin, J.P., Cellina, A.: Differential Inclusions: Set-Valued Maps and Viability Theory, vol. 264. Springer, Berlin (2012) · Zbl 0538.34007 |
| [23] | Aurenhammer, F.: Voronoi diagrams: a survey of a fundamental data structure. ACM Comput. Surv. 23, 345-405 (1991) · doi:10.1145/116873.116880 |
| [24] | Aurenhammer, F.: Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78-96 (1987) · Zbl 0616.52007 · doi:10.1137/0216006 |
| [25] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P.: Recognition of additively weighted Voronoi diagrams and weighted Delaunay decompositions. In: European Control Conference, Linz, Austria (2015) · Zbl 0621.93032 |
| [26] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P.: Inverse parametric linear/quadratic programming problem for continuous PWA functions defined on polyhedral partitions of polyhedra. In: 54th IEEE Conference on Decision and Control, Osaka, Japan (2015) |
| [27] | Avis, D., Fukuda, K.: A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8(1), 295-313 (1992) · Zbl 0752.68082 · doi:10.1007/BF02293050 |
| [28] | Nguyen, N.A.: Explicit robust constrained control for linear systems: analysis, implementation and design based on optimization. Ph.D. thesis, CentraleSupélec, Université Paris-Saclay, France (11/2015) · Zbl 1360.90241 |
| [29] | Gulan, M.; Nguyen, NA; Olaru, S.; Rodriguez-Ayerbe, P.; Rohal’-Ilkiv, B.; Olaru, S. (ed.); Grancharova, A. (ed.); Pereira, FL (ed.), Implications of inverse parametric optimization in model predictive control (2015), Berlin · Zbl 1336.49043 |
| [30] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P.: Any discontinuous PWA function is optimal solution to a parametric linear programming problem. In: 54th IEEE Conference on Decision and Control, Osaka, Japan (2015) · Zbl 0633.68086 |
| [31] | Clarke, D.W., Mohtadi, C., Tuffs, P.S.: Generalized predictive controlpart i. The basic algorithm. Automatica 23(2), 137-148 (1987) · Zbl 0621.93032 · doi:10.1016/0005-1098(87)90087-2 |
| [32] | Nguyen, N.A., Olaru, S., Rodriguez-Ayerbe, P.: On the complexity of the convex liftings-based solution to inverse parametric convex programming problems. In: European Control Conference, Linz, Austria (2015) · Zbl 1334.49111 |
| [33] | Nguyen, N.A., Gulan, M., Olaru, S., Rodriguez-Ayerbe, P.: Convex liftings: theory and control applications. Research report (2016). https://hal-centralesupelec.archives-ouvertes.fr/hal-01326804/document · Zbl 1395.93350 |
| [34] | Gilbert, E.G., Tan, K.T.: Linear systems with state and control constraints: the theory and application of maximal output admissible sets. IEEE Transactions on Automatic Control 36(9), 1008-1020 (1991) · Zbl 0754.93030 · doi:10.1109/9.83532 |
| [35] | Boucher, P., Dumur, D.: La commande prédictive, vol. 8. Editions Technip, Paris (1996) · Zbl 0889.93002 |
| [36] | Maciejowski, J.M.: Predictive Control: With Constraints. Pearson Education, New York (2002) · Zbl 0978.93002 |
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.
