probabilistic analysis

Trust-region algorithms: probabilistic complexity and intrinsic noise with applications to subsampling techniques

  • Stefania Bellavia
  • Gianmarco Gurioli
  • Benedetta Morini
  • Philippe L. Toint
    • Categories Nonlinear Systems and Least-Squares, Unconstrained Optimization Tags , , , , ,

    A trust-region algorithm is presented for finding approximate minimizers of smooth unconstrained functions whose values and derivatives are subject to random noise. It is shown that, under suitable probabilistic assumptions, the new method finds (in expectation) an epsilon-approximate minimizer of arbitrary order q > 0 in at most O(epsilon^{-(q+1)}) inexact evaluations of the function and … Read more

    A probabilistic analysis of the strength of the split and triangle closures

  • Amitabh Basu
  • Gérard Cornuéjols
  • Marco Molinaro
    • Categories (Mixed) Integer Linear Programming, Cutting Plane Approaches Tags , , ,

    In this paper we consider a relaxation of the corner polyhedron introduced by Andersen et al., which we denote by RCP. We study the relative strength of the split and triangle cuts of RCP’s. Basu et al. showed examples where the split closure can be arbitrarily worse than the triangle closure under a `worst-cost’ type … Read more

    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

    Projective Pre-Conditioners for Improving the Behavior of a Homogeneous Conic Linear System

  • Alexandre Belloni
  • Robert M. Freund
    • Categories Linear, Cone and Semidefinite Programming Tags , , , , ,

    We present a general theory for transforming a homogeneous conic system F: Ax = 0, x \in C, x \ne 0, to an equivalent system via projective transformation induced by the choice of a point in a related dual set. Such a projective transformation serves to pre-condition the conic system into a system that has … 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