Abstract. In the algorithmic trade-off between generality and efficiency, sometimes the only way out is to accept approximate methods. If all else fails, we can always fall back on heuristic methods. But some form of approximation guarantee is usually preferable. In this talk we shall discuss a set of approximating reformulations to various classes of mathematical programming problems involving matrices. Random projections are a dimensionality reduction methodology which projects a set of vectors into a much lower dimensional space, so that the projected vector set is approximately congruent to the original one with high probability. The probability of failure falls exponentially fast as the dimension increases, making this a truly “big data” methodology. We shall show how to apply this methodology to Linear and Conic Programming, as well as (bounded) Quadratic Programming. We shall discuss applications to Quantile Regression and Error-Correcting Codes.
Biography. Dr Leo Liberti is CNRS Research Director (and part-time professor) at CNRS LIX (the Computer Science Laboratory) of École Polytechnique, France. Dr Liberti did his undergraduate studies in mathematics at Imperial College London and the University of Turin. He received his Ph.D. from Imperial College London in 2004 and HDR (French professorship diploma) from Paris-Dauphine University, Paris, France in 2007. His main research interests are in (i) reformulations in mathematical programming, (i) mixed-integer nonlinear programming (MINLP), global and combinatorial optimization, (iii) distance geometry and bioinformatics, and (iv) complex industrial systems and sustainable development.