Tamás Terlaky

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

    Invariance conditions for nonlinear dynamical systems

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

    Recently, Horv\’ath, Song, and Terlaky [\emph{A novel unified approach to invariance condition of dynamical system, submitted to Applied Mathematics and Computation}] proposed a novel unified approach to study, i.e., invariance conditions, sufficient and necessary conditions, under which some convex sets are invariant sets for linear dynamical systems. In this paper, by utilizing analogous methodology, we … Read more

    Examples with Decreasing Largest Inscribed Ball for Deterministic Rescaling Algorithms

  • Dan Li
  • Tamás Terlaky
    • Categories Linear Programming, Linear, Cone and Semidefinite Programming Tags , , ,

    Recently, Pena and Soheili presented a deterministic rescaling perceptron algorithm and proved that it solves a feasible perceptron problem in $O(m^2n^2\log(\rho^{-1}))$ perceptron update steps, where $\rho$ is the radius of the largest inscribed ball. The original stochastic rescaling perceptron algorithm of Dunagan and Vempala is based on systematic increase of $\rho$, while the proof of … Read more

    A polynomial primal-dual affine scaling algorithm for symmetric conic optimization

  • Ali Mohammad-Nezhad
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    The primal-dual Dikin-type affine scaling method was originally proposed for linear optimization and then extended to semidefinite optimization. Here, the method is generalized to symmetric conic optimization using the notion of Euclidean Jordan algebras. The method starts with an interior feasible but not necessarily centered primal-dual solution, and it features both centering and reducing the … Read more

    A Polynomial Column-wise Rescaling von Neumann Algorithm

  • Dan Li
  • Cornelis Roos
  • Tamás Terlaky
    • Categories Linear, Cone and Semidefinite Programming Tags , , , ,

    Recently Chubanov proposed a method which solves homogeneous linear equality systems with positive variables in polynomial time. Chubanov’s method can be considered as a column-wise rescaling procedure. We adapt Chubanov’s method to the von Neumann problem, and so we design a polynomial time column-wise rescaling von Neumann algorithm. This algorithm is the first variant of … Read more

    A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , ,

    It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant … 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

    On Families of Quadratic Surfaces Having Fixed Intersections with Two Hyperplanes

  • Pietro Belotti
  • Julio C. Góez
  • Imre Pólik
  • Ted K. Ralphs
  • Tamás Terlaky
    • Categories Second-Order Cone Programming Tags , , ,

    We investigate families of quadrics that have fixed intersections with two given hyper-planes. The cases when the two hyperplanes are parallel and when they are nonparallel are discussed. We show that these families can be described with only one parameter. In particular we show how the quadrics are transformed as the parameter changes. This research … Read more