BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-ORIGINAL-URL:https://optimisation.doc.ic.ac.uk
X-WR-CALDESC:Events for Computational Optimisation Group
REFRESH-INTERVAL;VALUE=DURATION:PT1H
X-Robots-Tag:noindex
X-PUBLISHED-TTL:PT1H
BEGIN:VTIMEZONE
TZID:UTC
BEGIN:STANDARD
TZOFFSETFROM:+0000
TZOFFSETTO:+0000
TZNAME:UTC
DTSTART:20140101T000000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=UTC:20151201T160000
DTEND;TZID=UTC:20151201T160000
DTSTAMP:20260404T051457
CREATED:20170124T102135Z
LAST-MODIFIED:20170124T102135Z
UID:548-1448985600-1448985600@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Rescaled coordinate descent methods for Linear Programming
DESCRIPTION:Title: Rescaled coordinate descent methods for Linear ProgrammingSpeaker: Dr. Giacomo ZambelliAffiliation: Department of Management – London School of Economics and Political ScienceLocation: SALC 10 Sherfield Building Time: 4:00pm \nAbstract. Simple coordinate descent methods such as von Neumann’s algorithm or Perceptron\, both developed in the 50s\, can be used to solve linear programming feasibility problems. Their convergence rate depends on the condition measure of the problem at hand\, and is typically not polynomial. Recent work of Chubanov (2012\, 2014)\, related to prior work of Betke (2004)\, has gathered renewed interest in the application of these methods in order to obtain polynomial time algorithms for linear programming. We present two algorithms that fit into this line of research. Both our algorithms alternate between coordinate descent steps and rescaling steps\, so that either the descent step leads to a substantial improvement in terms of the convergence\, or we can infer that the problem is ill conditioned and rescale in order to improve the condition measure. In particular\, both algorithms are based on the analysis of a geometrical invariant of the LP problem\,  used as a proxy for the condition measure\, that appears to be novel in the literature. This is joint work with Daniel Dadush (CWI) and László Végh (LSE) \nAbout the speaker. Dr Zambelli is an Associate Professor (Reader) in the Department of Mathematics at the London School of Economics and Political Science\, which he joined in September 2010. Previously he was  Assistant Professor at the University of Padova. He completed his PhD in Algorithms\, Combinatorics and Optimization at the Tepper School of Business\, Carnegie Mellon University. He is a co-recipient of the 2015 INFORMS Lanchester Prize.
URL:https://optimisation.doc.ic.ac.uk/event/seminar-rescaled-coordinate-descent-methods-for-linear-programming/
END:VEVENT
END:VCALENDAR