Stretch-Contract Operator in the Ellipsoidal Approximation of the Minkowski Sum of Convex Sets


  • Oleksii V. Sholokhov



stretch-contract operator, state space, attainability set, ellipsoidal approximation, linear control system, multidimensional volume of an ellipsoid, sum of positive degrees of ellipsoid semiaxes, criterion for minimizing an ellipsoid


The space expansion-contraction operator was originally developed to solve mathematical programming problems. However, it can be successfully applied to solve the problem of ellipsoidal approximation of the information set in the state space analytically specified. In this case, a main property of the operator - space compression is used to minimize the approximating ellipsoid by a multidimensional volume. The paper shows the use of the specified expansion-contraction operator to approximate a set of attainability of the linear control system as an example. The main goal of the paper is to give analytical and geometric representations of the specified operator in order to show its action in the approximation problem. For this purpose, the paper shows an analytical derivation of the operator and a geometric illustration of each parameter of the operator. The results of minimum approximation modeling by this operator compared with other known solutions have been also presented. The simulation results are given both numerically and graphically. Based on the results of comparison, conclusions are made and recommendations are given in the use of ellipsoidal approximation of information sets according to different criteria for minimizing the approximating ellipsoid. Typical examples of ellipsoidal approximation, which show when it is expedient to use the proposed of expansion-contraction operator, have been given.


F. L. Chernousko, “Ellipsoidal approximation of attainability sets of a linear system with indeterminate matrix,” Journal of Applied Mathematics and Mechanics, vol. 60, issue 6, pp. 921-931, 1996.

W. M. J. Firey, “p-Means of convex bodies,” Mathematica Scandinavica, vol. 10, pp. 17–24, 1962.

D. M. Mount, Computational Geometry. University of Maryland. 2002. 122 p.

K. Matsuura, A. Tsuchiya, “Matrix geometry for ellipsoids,” Progress of Theoretical and Experimental Physics, vol. 2020, issue 3, 033B05, 2020.

L. Rotem, “Support functions and mean width for -concave function,” Advances in Mathematics, vol. 243, pp. 168-186, 2013.

F. Dabbene, D. Henrion, “Set approximation via minimum-volume polynomial sublevel sets,” Proceedings of the European Control Conference, 2013, pp. 1114-1119,

N. Z. Shor, “The cut-off method with space stretching for solving convex programming problems,” Cybernetics, issue 1, pp. 94-95, 1977.

O. V. Sholokhov, “Investigation and simulating of algorithm of building of set of attainability of linear controlled system,” Proceedings of the 4th IEEE Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS 2007,” Dortmund, Germany, September 6-8, 2007, pp. 355-360.

O.V. Sholokhov, “Minimum-volume ellipsoidal approximation of the sum of two ellipsoids,” Cybernetics and Systems Analysis, vol. 47, pp. 954–960, 2011.

P. Brunovský, “A classification of linear controllable systems,” Kybernetika, vol. 6, issue 3, pp. 173-188, 1970. [Online]. Available at:

A. Sadegh et al., Marks Standard Handbook for Mechanical Engineers, 12th Edition. McGraw-Hill. 2017, 1536 p.

M. Runger, P. Tabuada, “Computing robust controlled invariant sets of linear systems,” IEEE Transaction Automatic Control, vol. 62, no. 7, pp. 3665-3670, 2017,

T. Anevlavis, P. Tabuada, “Computing controlled invariant sets in two moves,” Proceedings of the 2019 IEEE 58th Conference on Decision and Control, 2019, pp. 6248-6254,

A. Wintenberg, N. Ozay, “Implicit invariant sets for high-dimensional switched affine systems,” Proceedings of the 59th IEEE Conference on Decision and Control, 2020, pp. 3291-3297,

J. Zhang, M. Söpper, F. Holzapfel, “Attainable moment set optimization to support configuration design: a required moment set based approach,” Applied Sciences, vol. 11, issue 8, 3685, 2021,

E. Lutwak, “The Brunn-Minkowski-Firey theory I: Mixed volumes and the Minkowski problem,” Journal of Differential Geometry, vol. 38, no. 1, pp. 131–150, 1993.

E. Lutwak, “The Brunn-Minkowski-Firey theory II: Affine and geominimal surface areas,” Advances in Mathematics, vol. 118, no. 2, pp. 244–294, 1996.

H.-P. Shröcker, “Uniqueness results for minimal enclosing ellipsoids,” Computer Aided Geometric Design, vol 25, issue 9, 2008, pp. 756-762.

N.D. Pankratova, O.V. Sholokhov, “Development of the robust algorithm of guaranteed ellipsoidal estimation and its application for orientation of the artificial earth satellite,” Cybernetics and Systems Analysis, vol. 55, pp. 81–89, 2019.

V.A. Khonin, “Guaranteed estimates of the state of linear systems using ellipsoids,” Evolutionary Systems in Estimation Problems, Sverdlovsk: Ural Scientific Center of the Academy of Sciences of the USSR, pp. 104-123, 1985.

F. You, H. Zhang, F. Wang, “A new set-membership estimation method based on zonotopes and ellipsoids,” Transactions of the Institute of Measurement and Control, vol. 40, issue 7, pp. 2091-2099, 2018.

W. Tang, Q., Zhang, Z. Wang, Y. Shen, “Ellipsoid bundle and its application to set-membership estimation,” IFAC-Papers online, vol. 53, issue 2, pp. 13688-13693, 2020.

M. Althoff, G. Frehse, A. Girard, “Set propagation techniques for reachability analysis. annual review of control, robotics, and autonomous systems,” Annual Reviews, vol. 4, issue 1, 2021.

A. Halder, “Smallest ellipsoid containing p-sum of ellipsoids with application to reachability analysis,” IEEE Transaction on Automatic Control, vol. 66, issue 6, pp. 2512-2525, 2020.

Y. Becis-Aubry, N. Ramdani, “State-bounding estimation for nonlinear models with multiple measurements,” 2012 American Control Conference Fairmont Queen Elizabeth, Montreal, Canada, June 27-29, 2012.

L. Asselborn, D. Groß, O. Stursberg, “Control of uncertain nonlinear systems using ellipsoidal reachability calculus,” Proceedings of the 9th IFAC Symposium on Nonlinear Control Systems, Toulouse, France, September 4-6, 2013, pp. 50-55.




How to Cite

Sholokhov, O. V. (2022). Stretch-Contract Operator in the Ellipsoidal Approximation of the Minkowski Sum of Convex Sets. International Journal of Computing, 21(1), 52-60.