Fully Inverse Parametric Linear/Quadratic Programming Problems via Convex Liftings

详细信息    查看全文

• 关键词：Parametric convex programming problems ; Convex liftings ; Inverse parametric convex programming ; Continuous piecewise affine functions
• 刊名：Lecture Notes in Control and Information Sciences
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：464
• 期：1
• 页码：27-47
• 全文大小：711 KB
• 参考文献：1.G.Z. Angelis, System Analysis, Modelling and Control with Polytopic Linear Models (2001)
  2.F. Aurenhammer, Criterion for the affine equivalence of cell complexes in \(r^{d}\) and convex polyhedra in \(r^{d+1}\) . Discrete Comput. Geom. 2, 49–64 (1987)MATH MathSciNet CrossRef
  3.F. Aurenhammer, Power diagrams: properties, algorithms and applications. SIAM J. Comput. 16(1), 78–96 (1987)MATH MathSciNet CrossRef
  4.F. Aurenhammer, Recognising polytopical cell complexes and constructing projection polyhedra. J. Symb. Comput. 3, 249–255 (1987)MATH MathSciNet CrossRef
  5.F. Aurenhammer, Voronoi diagrams: a survey of a fundamental data structure. ACM Comput. Surv. 23, 345–405 (1991)CrossRef
  6.M. Baes, M. Diehl, I. Necoara, Every continuous nonlinear control system can be obtained by parametric convex programming. IEEE Trans. Autom. Control 53(8), 1963–1967 (2008)MathSciNet CrossRef
  7.A. Bemporad, C. Filippi, An algorithm for approximate multiparametric convex programming. Comput. Opt. Appl. 35(1), 87–108 (2006)MATH MathSciNet CrossRef
  8.A. Bemporad, M. Morari, V. Dua, E.N. Pistikopoulos, The explicit linear quadratic regulator for constrained systems. Automatica 38(1), 3–20 (2002)MATH MathSciNet CrossRef
  9.H. Crapo, W. Whiteley, Plane self stresses and projected polyhedra 1: the basic pattern. Struct. Topol. 19, 55–73 (1993)MathSciNet
  10.H. Crapo, W. Whiteley, Spaces of stresses, projections and parallel drawings for spherical polyhedra. Contrib. Algebra Geom. 35(So. 2), 259–281 (1994)MATH MathSciNet
  11.A.J. De Loera, J. Rambau, F. Santos, Triangulations: structures for algorithms and applications, Algorithms and Computation in Mathematics (Springer, Berlin, 2010)
  12.H. Edelsbrunner, R. Seidel, Voronoi diagrams and arrangements. Discrete Comput. Geom. 1, 25–44 (1986)MATH MathSciNet CrossRef
  13.A. Grancharova, T.A. Johansen, Explicit Nonlinear Model Predictive Control (Springer, Berlin, 2012)MATH CrossRef
  14.B. Grünbaum, Convex Polytopes (Wiley Interscience, New York, 1967)MATH
  15.M. Gulan, N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, B. Rohal’-Ilkiv, Implications of inverse parametric optimization in model predictive control, in Developments in Model-Based Optimization and Control, ed. by S. Olaru, A. Grancharova, F.L. Pereira (Springer, Berlin, 2015)
  16.D. Hartvigsen, Recognizing voronoi diagrams with linear programming. ORSA J. Comput. 4, 369–374 (1992)MATH MathSciNet CrossRef
  17.A.B. Hempel, P.J. Goulart, J. Lygeros, On inverse parametric optimization with an application to control of hybrid systems. IEEE Trans. Autom. Control 60(4), 1064–1069 (2015)MathSciNet CrossRef
  18.M. Herceg, M. Kvasnica, C.N. Jones, M. Morari, Multi-Parametric Toolbox 3.0, in Proceedings of the European Control Conference, Zürich, Switzerland, 17–19 July 2013, pp. 502–510, http://​control.​ee.​ethz.​ch/​~mpt
  19.T.A. Johansen, On multi-parametric nonlinear programming and explicit nonlinear model predictive control, in Proceedings of the 41st IEEE Conference on Decision and Control, vol. 3 (2002), pp. 2768–2773
  20.T.A. Johansen, Approximate explicit receding horizon control of constrained nonlinear systems. Automatica 40(2), 293–300 (2004)MATH MathSciNet CrossRef
  21.M. Kvasnica, M. Fikar, Clipping-based complexity reduction in explicit MPC. IEEE Trans. Autom. Control 57(7), 1878–1883 (2012)MathSciNet CrossRef
  22.M. Kvasnica, J. Hledík, I. Rauová, M. Fikar, Complexity reduction of explicit model predictive control via separation. Automatica 49(6), 1776–1781 (2013)MathSciNet CrossRef
  23.C.W. Lee, P.L.-spheres, convex polytopes, and stress. Discrete Comput. Geom. 15, 389–421 (1996)MATH MathSciNet CrossRef
  24.J.C. Maxwell, On reciprocal diagrams and diagrams of forces. Philos. Mag., ser. 4 27, 250–261 (1864)
  25.H.N. Nguyen, Constrained Control of Uncertain, Time-Varying Discrete-Time Systems. An Interpolation-Based Approach, Lecture Notes in Control and Information Sciences (Springer, Berlin, 2014)MATH CrossRef
  26.H.N. Nguyen, P.-O. Gutman, S. Olaru, M. Hovd, Explicit constraint control based on interpolation techniques for time-varying and uncertain linear discrete-time systems, in 18th IFAC World Congress, vol. 18(1) (2011)
  27.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, M. Hovd, I. Necoara, Inverse parametric convex programming problems via convex liftings, in 19th IFAC World Congress (Cape Town, South Africa, 2014)
  28.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, M. Hovd, I. Necoara, On the lifting problems and their connections with piecewise affine control law design, in European Control Conference (Strasbourg, France, 2014)
  29.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, On the complexity of the convex liftings-based solution to inverse parametric convex programming problems, in European Control Conference (Linz, Austria, 2015)
  30.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe. Recognition of additively weighted voronoi diagrams and weighted delaunay decompositions, in European Control Conference (Linz, Austria, 2015)
  31.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, Any discontinuous PWA function is optimal solution to a parametric linear programming problem, in 54th IEEE Conference on Decision and Control (Osaka, Japan, 2015)
  32.N.A. Nguyen, S. Olaru, P. Rodriguez-Ayerbe, M. Hovd, I. Necoara, Constructive solution to inverse parametric linear/quadratic programming problems via convex liftings, https://​hal-supelec.​archives-ouvertes.​fr/​hal-01207234/​file/​IPCP_​JOTA.​pdf
  33.S. Olaru, D. Dumur, A parameterized polyhedra approach for explicit constrained predictive control, in 43rd IEEE Conference on Decision and Control, vol. 2 (2004), pp. 1580–1585
  34.S. Olaru, D. Dumur, On the continuity and complexity of control laws based on multiparametric linear programs, in 45th Conference on Decision and Control (IEEE, 2006), pp. 5465–5470
  35.E.N. Pistikopoulos, M.C. Georgiadis, V. Dua, Multi-Parametric Programming (Wiley-VCH, Weinheim, 2007)CrossRef
  36.K. Rybnikov, Polyhedral partitions and stresses, Ph.D. thesis, Queen University, Kingston, Ontario, Canada (1999)
  37.A. Schrijver, Theory of Linear and Integer Programming (Wiley, New York, 1998)MATH
  38.A. Schulz, 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)
  39.M.M. Seron, G.C. Goodwin, J.A. Doná, Characterisation of receding horizon control for constrained linear systems. Asian J. Control 5(2), 271–286 (2003)CrossRef
  40.E.D. Sontag, Nonlinear regulation: the piecewise linear approach. IEEE Trans. Autom. Control 26(2), 346–358 (1981)MATH MathSciNet CrossRef
  41.J. Spjøtvold, E.C. Kerrigan, C.N. Jones, P. Tøndel, T.A. Johansen, On the facet-to-facet property of solutions to convex parametric quadratic programs. Automatica 42(12), 2209–2214 (2006)MathSciNet CrossRef
  42.J. Spjøtvold, P. Tøndel, T.A. Johansen, Continuous selection and unique polyhedral representation of solutions to convex parametric quadratic programs. J. Opt. Theory Appl. 134(2), 177–189 (2007)CrossRef
  43.P. Tøndel, T.A. Johansen, A. Bemporad, An algorithm for multi-parametric quadratic programming and explicit MPC solutions. Automatica 39(3), 489–497 (2003)MathSciNet CrossRef
  
• 作者单位：Ngoc Anh Nguyen (6)
  Sorin Olaru (6)
  Pedro Rodriguez-Ayerbe (6)
  Morten Hovd (7)
  Ion Necoara (8)
  
  6. Laboratory of Signals and Systems, CentraleSupélec-CNRS-Université Paris-Sud, Université Paris-Saclay, 3 Rue Joliot Curie, 91192, Paris, Gif-sur-Yvette, France
  7. Department of Engineering Cybernetics, Norwegian University of Science and Technology, 7491, Trondheim, Norway
  8. Automatic Control and Systems Engineering Department, Politehnica University of Bucharest, Splaiul Independentei, 313, Bucharest, Romania
  
• 丛书名：Developments in Model-Based Optimization and Control
• ISBN：978-3-319-26687-9
• 刊物类别：Engineering
• 刊物主题：Control Engineering
  Vibration, Dynamical Systems and Control
  
• 出版者：Springer Berlin / Heidelberg

文摘

In this chapter, we present in an unified manner the latest developments on inverse optimality problem for continuous piecewise affine (PWA) functions. A particular attention is given to convex liftings as a cornerstone for the constructive solution we advocate in this framework. Subsequently, an algorithm based on convex lifting is presented for recovering a continuous PWA function defined over a polyhedral partition of a polyhedron. We also prove that any continuous PWA function can be equivalently obtained by a parametric linear programming problem with at most one auxiliary one-dimensional variable.