Raphael Hauser

Algebraic Tail Decay of Condition Numbers for Random Conic Systems under a General Family of Input Distributions

  • Raphael Hauser
  • Tobias Muller
    • Categories Linear, Cone and Semidefinite Programming Tags , , ,

    We consider the conic feasibility problem associated with linear homogeneous systems of inequalities. The complexity of iterative algorithms for solving this problem depends on a condition number. When studying the typical behaviour of algorithms under stochastic input one is therefore naturally led to investigate the fatness of the distribution tails of the random condition number … Read more

    On the Relationship Between Convergence Rates of Discrete and Continuous Dynamical Systems

  • Raphael Hauser
  • Jelena Nedic
    • Categories Unconstrained Optimization Tags ,

    Considering iterative sequences that arise when the approximate solution $x_k$ to a numerical problem is updated by $x_{k+1} = x_k+v(x_k)$, where $v$ is a vector field, we derive necessary and sufficient conditions for such discrete methods to converge to a stationary point of $v$ at different Q-rates in terms of the differential properties of $v$ … Read more

    Boundedness Theorems for the Relaxation Method

  • Edoardo Amaldi
  • Raphael Hauser
    • Categories Linear Programming, Polyhedra Tags , , ,

    A classical theorem by Block and Levin says that certain variants of the relaxation method for solving systems of linear inequalities produce bounded sequences of intermediate solutions even when running on inconsistent input data. Using a new approach, we prove a more general version of this result and answer an old open problem of quantifying … Read more

    On Tail Decay and Moment Estimates of a Condition Number for Random Linear Conic Systems

  • Dennis Cheung
  • Raphael Hauser
  • Felipe Cucker
    • Categories Linear Programming Tags , , , ,

    In this paper we study the distribution tails and the moments of a condition number which arises in the study of homogeneous systems of linear inequalities. We consider the case where this system is defined by a Gaussian random matrix and characterise the exact decay rates of the distribution tails, improve the existing moment estimates, … Read more

    The continuous Newton-Raphson method can look ahead

  • Raphael Hauser
  • Jelena Nedic
    • Categories Unconstrained Optimization Tags , , ,

    This paper is about an intriguing property of the continuous Newton-Raphson method for the minimization of a continuous objective function f: if x is a point in the domain of attraction of a strict local minimizer x* then the flux line of the Newton-Raphson flow that starts in x approaches x* from a direction that … Read more

    Self-scaled barriers for irreducible symmetric cones

  • Raphael Hauser
  • Yongdo Lim
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags , , , ,

    Self-scaled barrier functions are fundamental objects in the theory of interior-point methods for linear optimization over symmetric cones, of which linear and semidefinite programming are special cases. We are classifying all self-scaled barriers over irreducible symmetric cones and show that these functions are merely homothetic transformations of the universal barrier function. Together with a decomposition … Read more

    Self-scaled barrier functions on symmetric cones and their classification

  • Osman Guler
  • Raphael Hauser
    • Categories Convex Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

    Self-scaled barrier functions on self-scaled cones were introduced through a set of axioms in 1994 by Y.E. Nesterov and M.J. Todd as a tool for the construction of long-step interior point algorithms. This paper provides firm foundation for these objects by exhibiting their symmetry properties, their intimate ties with the symmetry groups of their domains … Read more