Events
Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-2-phd-talks-1
- Seminar: Jasper van Doornmalen (TU Eindhoven) + Daniel Brosch (Tilburg University), 2 PhD talks
- 2022-05-24T16:00:00+02:00
- 2022-05-24T17:00:00+02:00
- When May 24, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Jasper van Doornmalen (TU/e) and Daniel Brosch (Tilburg University)
Title:
Jasper van Doornmalen: Symmetry handling in binary programs through propagation
Daniel Brosch : The Symmetries of Flag-Algebras
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Symmetry handling in binary programs through propagation" (Jasper van Doornmalen):
Symmetries of binary programs are known to dramatically slow down branch-and-bound procedures. A classical approach to handle permutation symmetries is to enforce that only one representative of equivalent (symmetric) solutions can be computed. In classical integer programming literature, among others, this is established by introducing symmetry handling constraints. This way, solutions that are not lexicographically maximal among the permuted solutions are cut off.
We present a propagation-based symmetry handling technique. Given a set of fixed variables (e.g., due to branching decisions), this technique identifies further variables that can be fixed to ensure that only lexicographically maximal solutions are computed. We present efficient algorithms to find such additional symmetry-based variable fixings for arbitrary sets of permutations and cyclic groups. In particular, for cyclic groups, we show that all possible fixings can be found in polynomial time even if the cyclic group has exponential order.
Our methods are implemented as a plugin in the academic integer programming solver SCIP, and we discuss the effectiveness of these methods on various symmetrical instances.
Video of the talk of Jasper van Doornmalen:
Slides of the talk of Jasper van Doornmalen:
Slides
Abstract of "The Symmetries of Flag-Algebras" (Daniel Brosch):
Flag-Algebras, first introduced by Razborov in 2007, remain one of the most powerful tools in extremal combinatorics. Recently a connection to polynomial optimization was discovered: We can recover Flag-Sums-of-Squares hierarchies by partially exploiting the symmetries of a polynomial optimization hierarchy. We continue from there and fully exploit the symmetries in this polynomial setting for two different hierarchies, one focusing on a low number of edges, and another focusing on a low number of vertices of appearing Flags. For the first, due to the high initial dimension of the hierarchy, a novel algorithm was needed to decompose modules of the symmetric group into irreducible submodules. We apply the reduced hierarchies to obtain outer approximations of graph-profiles, which model various open problems from extremal combinatorics.
Video of the talk of Daniel Brosch:
Slides of the talk of Daniel Brosch:
Link to Daniel's slides on his webpage
Seminar: Krzysztof Postek (TU Delft)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-krzysztof-postek-tu-delft
- Seminar: Krzysztof Postek (TU Delft)
- 2022-04-28T16:00:00+02:00
- 2022-04-28T17:00:00+02:00
- When Apr 28, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Where Online seminar
- Contact Name Daniel Dadush and Sven Polak
- Add event to calendar iCal
Speaker: Krzysztof Postek (TU Delft)
Title:
An Adaptive Robust Optimization Model for Parallel Machine Scheduling
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
We develop an approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted, allowing an arbitrary set of scenarios for the task lengths' realizations. We demonstrate that this can lead to better here-and-now decisions. In a recent work, we develop an exact MILP formulation of this problem for discrete sets of scenarios, which, to best of our knowledge, is the first one in which so-called nonanticipativity constraints are formulated exactly.
Joint work with Shimrit Shtern (Technion), Izack Cohen (Bar Ilan University), Izak de Heer (TU Delft).
Video:
Slides:
Slides
Seminar: Esteban Gabory (CWI) + Donato Maragno (UvA), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-2-phd-talks
- Seminar: Esteban Gabory (CWI) + Donato Maragno (UvA), 2 PhD talks
- 2022-03-31T16:00:00+02:00
- 2022-03-31T17:00:00+02:00
- When Mar 31, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Esteban Gabory (CWI) + Donato Maragno (UvA)
Title:
Esteban Gabory: On Strings Having the Same Length-k Substrings
Donato Maragno : Mixed-Integer Optimization with Constraint Learning
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "On Strings Having the Same Length-k Substrings" (Esteban Gabory):
Video of the talk of Esteban Gabory:
Slides of the talk of Esteban Gabory:
Slides
Abstract of "Mixed-Integer Optimization with Constraint Learning" (Donato Maragno):
Joint work with: Holly Wiberg, Dimitris Bertsimas, S. Ilker Birbil, Dick den Hertog, Adejuyigbe Fajemisin
Paper:
https://arxiv.org/abs/2111.04469
Code:
https://github.com/hwiberg/OptiCL
Video of the talk of Donato Maragno:
Slides of the talk of Donato Maragno:
Slides
Seminar: Friedrich Eisenbrand (EPFL Lausanne), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-friedrich-eisenbrand-epfl-lausanne-international-speaker
- Seminar: Friedrich Eisenbrand (EPFL Lausanne), International speaker
- 2022-03-03T16:00:00+01:00
- 2022-03-03T17:00:00+01:00
- When Mar 03, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Friedrich Eisenbrand (EPFL Lausanne)
Title:
Algorithms for Integer Programming
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Slides
Seminar: Lightning Talks (several speakers), 2022-1
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-lightning-talks-several-speakers-1
- Seminar: Lightning Talks (several speakers), 2022-1
- 2022-02-10T16:00:00+01:00
- 2022-02-10T17:00:00+01:00
- When Feb 10, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Several speakers (hopefully 12-15)
Title: Lightning Talks
Our first lightning talk was very successful, so we will now have 2 per year, in between the first two regular seminars of each semester. Lightning talks are 1 to 5 min talks meant to foster interaction in the community. This can include:
1. Introducing yourself & what you do
2. Announcing a recent result & why its cool
3. Posing an open problem / advertising a research area (or an open position)
4. Anything awesome you want to tell us about :)
If you'd like to sign up for a talk, please sign up here with your name and the subject of your talk (can be TBD) by *Friday February 4th*:
https://docs.google.com/spreadsheets/d/1KH6_dL7yz4I5cXH8udlXAyZrbTwUAjEgQLoslxt-yz4/edit?usp=sharing
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Our goal is to include as many people as possible, so we'll try and fit everyone.
Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-andreas-wiese-vrije-universiteit
- Seminar: Andreas Wiese (Vrije Universiteit Amsterdam)
- 2022-01-27T16:00:00+01:00
- 2022-01-27T17:00:00+01:00
- When Jan 27, 2022 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Andreas Wiese (VU Amsterdam)
Title:
A PTAS for the Unsplittable Flow on a Path problem
(joint work with Fabrizio Grandoni and Tobias Mömke)
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
In this talk, we present a polynomial time $(1+\eps)$-approximation algorithm for UFP.
Video:
Slides:
Slides
Seminar: Hadi Abbaszadehpeivasti (Tilburg) + Utku Karaca (Erasmus University), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-hadi-abbaszadehpeivasti-tilburg-utku-karaca-erasmus-university-2-phd-talks
- Seminar: Hadi Abbaszadehpeivasti (Tilburg) + Utku Karaca (Erasmus University), 2 PhD talks
- 2021-12-09T16:00:00+01:00
- 2021-12-09T17:00:00+01:00
- When Dec 09, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Hadi Abbaszadehpeivasti (Tilburg University) + Utku Karaca (Erasmus University)
Title:
Hadi Abbaszadehpeivasti: On the convergence rate of DCA
Utku Karaca : Differentially Private Resource Sharing
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "On the convergence rate of DCA" (Hadi Abbaszadehpeivasti):
https://arxiv.org/abs/2109.13566
Video of the talk of Hadi Abbaszadehpeivasti:
Slides of the talk of Hadi Abbaszadehpeivasti:
Abstract of "Differentially Private Resource Sharing" (Utku Karaca):
This study examines a resource-sharing problem involving multiple parties that agree to use a set of capacities together. We start with modeling the whole problem as a mathematical program, where all parties are required to exchange information to obtain the optimal objective function value. This information bears private data from each party in terms of coefficients used in the mathematical program. Moreover, the parties also consider the individual optimal solutions as private. In this setting, the great concern for the parties is the privacy of their data and their optimal allocations. Methodology and results: We propose a two-step approach to meet the privacy requirements of the parties. In the first step, we obtain a reformulated model that is amenable to a decomposition scheme. Although this scheme eliminates almost all data exchange, it does not provide a formal privacy guarantee. In the second step, we provide this guarantee with a differentially private algorithm at the expense of deviating slightly from the optimality. We provide bounds on this deviation and discuss the consequences of these theoretical results. The study ends with a simulation study on a planning problem that demonstrates an application of the proposed approach. Managerial implications: Our work provides a new optimization model and a solution approach for optimal allocation of a set of shared resources among multiple parties who expect privacy of their data. The proposed approach is based on the decomposition of the shared resources and the randomization of the optimization iterations. With our analysis, we show that the resulting randomized algorithm does give a guarantee for the privacy of each party's data. As we work with a general optimization model, our analysis and discussion can be used in different application areas including production planning, logistics, and network revenue management.
https://arxiv.org/abs/2102.07178
Video of the talk of Utku Karaca:
Slides of the talk of Utku Karaca:
Seminar: Britta Peis (RWTH Aachen University), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-britta-peis-rwth-aachen-university-international-speaker
- Seminar: Britta Peis (RWTH Aachen University), International speaker
- 2021-11-23T16:00:00+01:00
- 2021-11-23T17:00:00+01:00
- When Nov 23, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Britta Peis (RWTH Aachen)
Title:
Primal-dual approximation framework for weighted integer covering problems.
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Lucas Slot (CWI) + Juan José Maulén (Groningen), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-lucas-slot-cwi-juan-jose-maulen-groningen-2-phd-talks
- Seminar: Lucas Slot (CWI) + Juan José Maulén (Groningen), 2 PhD talks
- 2021-10-28T16:00:00+02:00
- 2021-10-28T17:00:00+02:00
- When Oct 28, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Web Visit external website
- Add event to calendar iCal
Speaker: Lucas Slot (CWI Amsterdam) + Juan José Maulén (RU Groningen)
Title:
Lucas Slot: Degree bounds for positivity certificates and the polynomial kernel method
Juan José Maulén: Acceleration of fixed point algorithms via inertia
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Degree bounds for positivity certificates and the polynomial kernel method" (Lucas Slot):
We apply the PKM to additional sets, including the binary hypercube {-1, 1}^n, the unit box [-1, 1]^n and the unit ball.
This is based on joint work with Monique Laurent.
Arxiv link: https://arxiv.org/abs/2011.04027
Video of the talk of Lucas Slot:
Slides of the talk of Lucas Slot:
Abstract of "Acceleration of fixed point algorithms via inertia" (Juan José Maulén):
In this talk, we will use the results about the convergence of inertial optimization algorithms, defined as fixed point iterations from a family of cocoercive operators. This result implies that exists inertial versions of the Primal-dual splitting algorithm proposed by Briceño and Roldan on 2019, and for the three-operator splitting scheme proposed by Davis and Yin on 2015. Both algorithms fit on the framework of optimization algorithms defined by cocoercive operators. The inertial versions obtained are tested in several numerical experiments, where better performance with respect to the original algorithms can be observed.
Video of the talk of Juan José Maulén:
Slides of the talk of Juan José Maulén:
Seminar: Martin Skutella (TU Berlin), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-martin-skutella-tu-berlin-international-speaker
- Seminar: Martin Skutella (TU Berlin), International speaker
- 2021-09-30T16:00:00+02:00
- 2021-09-30T17:00:00+02:00
- When Sep 30, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Martin Skutella (TU Berlin)
Title:
A Faster Algorithm for Quickest Transshipments via an Extended Discrete Newton Method
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Samuel Fiorini (Bruxelles), International speaker
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-samuel-fiorini-bruxelles-international-speaker
- Seminar: Samuel Fiorini (Bruxelles), International speaker
- 2021-08-26T16:00:00+02:00
- 2021-08-26T17:00:00+02:00
- When Aug 26, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Samuel Fiorini (Université libre de Bruxelles)
Title:
Integer programs with bounded subdeterminants and two nonzeros per row
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
Video:
Slides:
Seminar: Lightning Talks (several speakers)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-lightning-talks-several-speakers
- Seminar: Lightning Talks (several speakers)
- 2021-06-24T16:00:00+02:00
- 2021-06-24T17:00:00+02:00
- When Jun 24, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Several speakers (hopefully 12-15)
Title: Lightning Talks
Lightning talks are 1 to 5 min talks meant to foster interaction in the community. This can include:
1. Introducing yourself & what you do
2. Announcing a recent result & why its cool
3. Posing an open problem / advertising a research area (or an open position)
4. Anything awesome you want to tell us about :)
If you'd like to sign up for a talk, please add your name and a tentative title here:
https://docs.google.com/spreadsheets/d/1YebbULLoO6FmIrOcEdkA_3pzePLe0pWj2lQCvvKwdA8/edit?usp=sharing
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Our goal is to include as many people as possible, so we'll try and fit everyone.
Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-celine-swennenhuis-eindhoven-sophie-huiberts-cwi-2-phd-talks
- Seminar: Celine Swennenhuis (Eindhoven) + Sophie Huiberts (CWI), 2 PhD talks
- 2021-05-27T16:00:00+02:00
- 2021-05-27T17:00:00+02:00
- When May 27, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Céline Swennenhuis (TU Eindhoven) + Sophie Huiberts (CWI)
Title:
Céline Swennenhuis: A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins
Sophie Huiberts: Combinatorial Diameter of Random Polytopes
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins" (Céline Swennenhuis):
Björklund, Husfeldt and Koivisto (SICOMP 2009) presented an O(2^n) time algorithm for Bin Packing. In this paper we show that for every m there exists a constant s_m > 0 such that an instance of Bin Packing with m bins can be solved in O((2-s_m)^n) time.
Video of the talk of Céline Swennenhuis:
Slides of the talk of Céline Swennenhuis:
Abstract of "Combinatorial Diameter of Random Polytopes" (Sophie Huiberts):
The combinatorial diameter of a polytope is the maximum shortest path between any two vertices of the polytope, in the graph consisting of that polytope's vertices and edges. This diameter is closely related to the simplex method for linear programming and has been studied since the 1950's, when Hirsch asked in a letter to Dantzig whether the combinatorial diameter of a polytope in R^n with m facets has diameter at most m-n.
In this paper we study random polytopes, either the intersection of random halfspaces or the convex hull of random vectors, chosen from the unit sphere. In the first case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (4√2)^n m^1/(n-1)) with high probability up to logarithmic factors. In the second case, we prove that the diameter is between Omega(m)^{1/(n-1)} and O( (√2)^n m^1/(n-1)) with high probability up to logarithmic factors.
Video of the talk of Sophie Huiberts:
Notes of the talk of Sophie Huiberts, the website with polytopes, and a nice twitter abstract:
Seminar: Juan Peypouquet (RU Groningen)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-juan-peypouquet-groningen
- Seminar: Juan Peypouquet (RU Groningen)
- 2021-04-29T16:00:00+02:00
- 2021-04-29T17:00:00+02:00
- When Apr 29, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC200)
- Add event to calendar iCal
Speaker: Juan Peypouquet (RU Groningen)
Title:
Function Curvature and Algorithm Complexity in Convex Optimization
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
impact on the complexity of optimization algorithms. In this talk, we will
present some basic concepts related to function curvature and discuss their
relationship with descent properties and convergence rates of first-order
methods.
Video:
Slides:
Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-moritz-buchem-maastricht-michelle-sweering-cwi-2-phd-talks
- Seminar: Moritz Buchem (Maastricht) + Michelle Sweering (CWI)
- 2021-03-25T16:00:00+01:00
- 2021-03-25T17:00:00+01:00
- When Mar 25, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Moritz Buchem (Maastricht) + Michelle Sweering (CWI), 2 PhD talks
Title:
Moritz Buchem: Additive Approximation Schemes for Load Balancing problems
Michelle Sweering: On Breaking k-Trusses
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract of "Additive Approximation Schemes for Load Balancing problems" (Moritz Buchem):
Additive approximation schemes compute a solution with an absolute error in the objective of at most εh for some suitable parameter h and any given ε > 0. We consider the problem of assigning jobs to identical machines with respect to common load balancing objectives like makespan minimization, the Santa Claus problem (on identical machines), and the envy-minimizing Santa Claus problem. For these settings we present additive approximation schemes for h = pmax, the maximum processing time of the jobs.
Our technical contribution is two-fold. First, we introduce a new relaxation based on integrally assigning slots
to machines and fractionally assigning jobs to the slots. We refer to this relaxation as the slot-MILP. While it has a linear number of integral variables, we identify structural properties of (near-)optimal solutions, which allow us to compute those in polynomial time. The second technical contribution is a local-search algorithm which rounds any given solution to the slot-MILP, introducing an additive error on the machine loads of at most εpmax.
This is joint work together with Lars Rohwedder (EPFL), Tjark Vredeveld (UM) and Andreas Wiese (UChile).
Video of the talk of Moritz Buchem:
Slides of the talk of Moritz Buchem:
Abstract of "On Breaking k-Trusses" (Michelle Sweering):
This talk is about breaking communities in networks, specifically k-trusses.
A subgraph H of G is a k-truss if each edge of H is contained in at least k-2 triangles in H.
We discuss how to break k-trusses by deleting as few edges as possible.
Since the problem of breaking k-trusses is NP-hard and even hard to approximate, we also give various heuristics.
Video of the talk of Michelle Sweering:
Slides of the talk of Michelle Sweering:
Seminar: Santanu Dey (Georgia Tech)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-santanu-dey-georgia-tech-international-speaker
- Seminar: Santanu Dey (Georgia Tech)
- 2021-02-25T16:00:00+01:00
- 2021-02-25T17:00:00+01:00
- When Feb 25, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: Santanu Dey (Georgia Tech)
Title: Sparse PSD approximation of the PSD cone
Zoom link: https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract: While semidefinite programming (SDP) problems are polynomially solvable in theory, it is often difficult to solve large SDP instances in practice. One computational technique used to address this issue is to relax the global positive-semidefiniteness (PSD) constraint and only enforce PSD-ness on smaller k × k principal submatrices — we call this the sparse SDP relaxation. Surprisingly, it has been observed empirically that in some cases this approach appears to produce bounds that are close to the optimal objective function value of the original SDP.
In this talk, we formally attempt to compare the strength of the sparse SDP relaxation vis-`a-vis the original SDP from a theoretical perspective. In order to simplify the question, we arrive at a data independent version of it, where we compare the sizes of SDP cone and the k-PSD closure, which is the cone of matrices where PSDness is enforced on all k × k principal submatrices. In particular, we investigate the question of how far a matrix of unit Frobenius norm in the k-PSD closure can be from the SDP cone. We provide two incomparable upper bounds on this farthest distance as a function of k and n. We also provide matching lower bounds, which show that the upper bounds are tight within a constant in different regimes of k and n.
Other than linear algebra techniques, we use probabilistic methods to arrive at these bounds. Two other key ingredients are: (i) observing that the hyperbolicity cone of the elementary symmetric polynomial is a convex relaxation of the set of eigenvalues of matrices in k-PSD closure (ii) Observing a connection between matrices in the k-PSD closure and matrices satisfying the restricted isometry property (RIP).
Video:
Slides:
Seminar: David de Laat (TU Delft)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/seminar-david-de-laat-tu-delft
- Seminar: David de Laat (TU Delft)
- 2021-01-28T16:00:00+01:00
- 2021-01-28T17:00:00+01:00
- When Jan 28, 2021 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Add event to calendar iCal
Speaker: David de Laat (TU Delft)
Title: Sphere packing and semidefinite programming
Zoom link:
https://cwi-nl.zoom.us/j/84909645595?pwd=b1M4QnNKVzNMdmNSVFNaZUJmR1kvUT09
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
compute bounds in discrete geometry. First I will focus on compact problems
such as the spherical code problem, which asks for the largest number of
points on a unit sphere such that the inner product between any pair of
disctinct points is at most some given constant. Then I will discuss the
(noncompact) sphere packing problem, explain how this connects to problems
in analytic number theory and the conformal bootstrap program, and discuss
how semidefinite programming can be used to obtain improved bounds.
Video:
Slides:
Kick-off seminar: Laura Sanita (TU Eindhoven)
- https://wsc.project.cwi.nl/dutch-optimization-seminar/events/kick-off-seminar-laura-sanita-tu-eindhoven
- Kick-off seminar: Laura Sanita (TU Eindhoven)
- 2020-12-16T16:00:00+01:00
- 2020-12-16T17:00:00+01:00
- Laura Sanita (TU Eindhoven) will kick-off the Dutch Seminar on Optimization.
- When Dec 16, 2020 from 04:00 PM to 05:00 PM (Europe/Amsterdam / UTC100)
- Where Zoom link in the details
- Contact Name Nikhil Bansal
- Web Visit external website
- Add event to calendar iCal
Speaker: Laura Sanita (TU Eindhoven)
Title: On the diameter and the circuit-diameter of polytopes
Zoom link:
Click here to join the zoom meeting.
(Meeting ID: 849 0964 5595, Passcode: 772448)
Abstract:
between a pair of vertices of P, when one is allowed to walk on the
edges (1-dimensional faces) of P. Despite decades of studies, it is
still not known whether the diameter of a d-dimensional polytope with n
facets can be bounded by a polynomial function of n and d. This is a
fundamental open question in discrete mathematics, motivated by the
(still unknown) existence of a polynomial pivot rule for the Simplex
method for solving Linear Programs.
A generalized notion of diameter, recently introduced in the
literature, is that of circuit-diameter, defined as the maximum length
of a shortest path between two vertices of P, where the path can use
all edge directions (called circuits) that can arise by translating
some of the facets of P.
In this talk, I will discuss some algorithmic and complexity results
related to the diameter and the circuit-diameter of polytopes,
highlighting important open questions.
Video:
Slides: Slides Laura Sanita