polyhedron

Steplength thresholds for invariance preserving of discretization methods of dynamical systems on a polyhedron

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Convex and Nonsmooth Optimization, Convex Optimization Tags , , , ,

    Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more

    Steplength Thresholds for Invariance Preserving of Discretization Methods of Dynamical Systems on a Polyhedron

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Control Applications, Convex and Nonsmooth Optimization, Polyhedra Tags , , ,

    Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more

    A Novel Unified Approach to Invariance in Control

  • Zoltán Horváth
  • Tamás Terlaky
  • Yunfei Song
    • Categories Control Applications, Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    In this paper, we propose a novel, unified, general approach to investigate sufficient and necessary conditions under which four types of convex sets, polyhedra, polyhedral cones, ellipsoids and Lorenz cones, are invariant sets for a linear continuous or discrete dynamical system. In proving invariance of ellipsoids and Lorenz cones for discrete systems, instead of the … Read more

    Containment problems for polytopes and spectrahedra

  • Kai Kellner
  • Thorsten Theobald
  • Christian Trabandt
    • Categories Polyhedra, Semi-definite Programming Tags , , , , ,

    We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more

    Facets for the Maximum Common Induced Subgraph Problem Polytope

  • Cid C. de Souza
  • Breno Piva
    • Categories Polyhedra Tags , , ,

    This paper presents some strong valid inequalities for the Maximum Common Induced Subgraph Problem (MCIS) and the proofs that the inequalities are facet-defining under certain conditions. The MCIS is an NP-hard problem and, therefore, no polynomial time algorithm is known to solve it. In this context, the study of its polytope can help in the … Read more

    A Polyhedral Study of Triplet Formulation for Single Row Facility Layout Problem

  • Kiavash Kianfar
  • Sujeevraja Sanjeevi
    • Categories Integer Programming Tags , , , ,

    The Single Row Facility Layout Problem (SRFLP) is the problem of arranging n departments with given lengths on a straight line so as to minimize the total weighted distance between all department pairs. We present a polyhedral study of the triplet formulation of the SRFLP introduced by Amaral [Discrete Applied Mathematics 157(1)(2009)183-190]. For any number … Read more