BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Computational Optimisation Group - ECPv6.15.11//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Computational Optimisation Group
X-ORIGINAL-URL:http://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:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:20180325T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:20181028T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:20190331T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:20191027T010000
END:STANDARD
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:20200329T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:20201025T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/London:20190702T140000
DTEND;TZID=Europe/London:20190702T150000
DTSTAMP:20260507T011045
CREATED:20190425T090204Z
LAST-MODIFIED:20190425T090204Z
UID:1229-1562076000-1562079600@optimisation.doc.ic.ac.uk
SUMMARY:Seminar: Chordal Completions - Semidefinite Programming and Minimum Completions
DESCRIPTION:Title: Chordal Completions – Semidefinite Programming and Minimum Completions\nSpeaker: Dr Arvind Raghunathan\nAffiliation: Mitsubishi Electric Research Laboratories (MERL)\nLocation: 217 Huxley Building\nTime: 14:00 – 15:00 \nAbstract. A graph is chordal if every cycle of length at least four contains a chord\, that is\, an edge connecting two nonconsecutive vertices of the cycle. Chordal completion of a given undirected graph G is a chordal graph\, on the same vertex set\, that has G as a subgraph. Several classical applications in sparse linear systems\, database management\, computer vision\, and SemiDefinite Programming (SDP) utilize chordal completions. The computation workload that results can be related to the number of edges that are added. Hence\, finding the minimum number of edges that makes a graph chordal is important. We refer to this as the Minimum Chordal Completion Problem (MCCP). In this talk\, we will present results on an application of completions in SDPs and the solution of MCCP. \nConversion approach\, a decomposition based on chordal completions\, is routinely used for solving large-scale SDPs. We show that the SDP resulting from the conversion approach is numerically degenerate under very mild assumptions. Numerical experiments on SDPLIB are provided to demonstrate the impact on solvers such as SDPT3 and SeDuMi. \nWe propose a new formulation for the MCCP which does not rely on finding perfect elimination orderings of the graph\, as has been considered in previous work. We introduce several families of facet-defining inequalities for cycle subgraphs. Numerical studies combining heuristic separation methods based on a threshold rounding and lazy-constraint generation indicate that our approach substantially outperforms existing methods for the MCCP\, solving many benchmark graphs to optimality for the first time. \nBiography. Arvind Raghunathan is a Senior Principal Scientist at Mitsubishi Electric Research Laboratories (MERL). His research interests are in the development of algorithms for the solution of nonlinear and mixed integer programming problems with applications in electric grid operations\, model predictive control\, and transportation. Arvind’s research has found business impact in Mitsubishi’s products and has won top technical honors within MERL and Mitsubishi Electric Corporation. Arvind currently serves as an associate editor for Optimization & Engineering journal and as an expert of ANSI on the ISO Working Group on Smart Transportation. He obtained a Ph.D. from Carnegie Mellon University and a B.Tech from Indian Institute of Technology (Madras) both in Chemical Engineering. He worked for United Technologies Research Center for 7 years prior to joining MERL.
URL:http://optimisation.doc.ic.ac.uk/event/seminar-chordal-completions-semidefinite-programming-and-minimum-completions/
END:VEVENT
END:VCALENDAR