Amir Ali Ahmadi (Princeton University) 
http://aaa.princeton.edu/ Title: Local Minima in Polynomial Optimization Abstract: We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if a polynomial has a point of that type. Our results characterize the complexity of these two questions for all degrees left open by prior literature. Our main contributions reveal that many of these questions turn out to be tractable for cubic polynomials. By contrast, we show that it is NP-hard to find a point within Euclidean distance $c^n$ (for any constant $c\geq 0$) of a local minimizer of an $n$-variate quadratic polynomial over a polytope.
Bio: Amir Ali Ahmadi is a Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Program in Applied and Computational Mathematics, the Department of Computer Science, the Department of Mechanical and Aerospace Engineering, the Department of Electrical Engineering, and the Center for Statistics and Machine Learning. He is also a part-time visiting research scientist at Google Brain (in the Robotics group). Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the Presidential Early Career Award for Scientists and Engineers (PECASE), the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the MURI award of the AFOSR, the Howard B. Wentz Junior Faculty Award as well as the Innovation Award of Princeton University, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization'') is a three-time recipient of the Teaching Award of the Princeton Engineering Council, as well as a recipient of the Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers, and the Phi Beta Kappa Award for Excellence in Undergraduate Teaching at Princeton University. Amir Ali's research has been recognized by a number of best-paper awards, including the INFORMS Optimization Society's Young Researchers Prize, the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 2013-2015. Rekha Thomas (University of Washington)
https://sites.math.washington.edu/~thomas/
Title: Graphical Designs: Structure, Complexity and Applications
Abstract: Graphical designs are quadrature rules on graphs that are discrete analogs of spherical designs on the sphere. They have a number of applications to areas such as graph sampling and random walks. An important question about designs is how to compute/optimize over them. I will explain how positively weighted designs can be organized on the faces of a polytope, and how this connection can be used to compute and optimize designs in several families of graphs. The polytope connection also yields complexity results.
Bio: Rekha Thomas received a Ph.D. in Operations Research from Cornell University in 1994 under the supervision of Bernd Sturmfels, followed by postdoctoral positions at the Cowles Foundation for Economics at Yale University and the Konrad-Zuse-Zentrum for Informationstechnik in Berlin. She is currently the Walker Family Endowed Professor of Mathematics at the University of Washington in Seattle. Thomas is a Fellow of the American Math Society and was an invited speaker at the International Congress of Mathematicians in 2018. Her research interests are in optimization and applied algebraic geometry. Etienne de Klerk (Tilburg University)
https://sites.google.com/site/homepageetiennedeklerk/ Title: Proving inequalities using semidefinite programming duality: applications in the worst-case analysis of iterative methods
Abstract: Semidefinite programming (SDP) may be seen as a generalization of linear programming, and similarly has a strong duality theory. Dual optimal solutions may be viewed as certificates of optimality, i.e. certifying nonnegativity of a given function on a given set. Since SDP problems are computationally tractable, this provides a computer-assisted approach to proving inequalities. An interesting application of this idea is in the worst-case analysis of iterative optimization methods. Surprisingly, the worst-case performance may often be certified via a dual SDP solution, e.g. for the gradient descent method of Cauchy on the class of L-smooth functions. In this talk we will present the basic ideas of this approach, and survey some recent developments.
Bio: Etienne de Klerk completed his BSc and MSc degrees at the University of Pretoria in South Africa, and obtained his PhD degree from the Delft University of Technology in The Netherlands in 1997. From January 1998 to September 2003, he held assistant professorships at the Delft University of Technology, and from September 2003 to September 2005 an associate professorship at the University of Waterloo, Canada, in the Department of Combinatorics & Optimization. In September 2004 he was appointed at Tilburg University, The Netherlands, first as an associate professor, and then as full professor (from June 2009). From August 29th, 2012, until August 31st, 2013, he was also appointed as full professor in the Division of Mathematics of the School of Physical and Mathematical Sciences at the Nanyang Technological University in Singapore. From September 1st, 2015 to August 31st 2019, he also held a full professorship at the Delft University of Technology (1 day/week position).
https://www.mi.uni-koeln.de/opt/frank-vallentin/) Title: Generalizations and Applications of the Lovász theta number Abstract: The theta number of Lovász of a graph, originally invented to determine the Shannon capacity of the pentagon, has been a source of inspiration for everybody working in the area of semidefinite programming (linear optimization over the convex cone of positive semidefinite matrices). By Lovász' sandwich theorem the theta number is sandwiched between the independence number of the graph and the chromatic number of the complementary graph.
In this lecture I will discuss generalizations, strengthenings, and applications of the Lovász theta number for infinite geometric graphs and hypergraphs. In concrete applications harmonic analysis will be key to perform explicit computations. Bio: Frank Vallentin is a professor of applied mathematics (computer science) at Universität zu Köln. In 2003 he received his Ph.D. in mathematics from Technische Universität München. Past appointments include assistant and associate professor at Technische Universiteit Delft, postdoc at Centrum Wiskunde & Informatica in Amsterdam and postdoc at the Hebrew University of Jerusalem. His research interests include optimization, geometry, discrete and experimental mathematics.
http://aaa.princeton.edu/ Title: Local Minima in Polynomial Optimization Abstract: We consider the notions of (i) critical points, (ii) second-order points, (iii) local minima, and (iv) strict local minima for multivariate polynomials. For each type of point, and as a function of the degree of the polynomial, we study the complexity of deciding (1) if a given point is of that type, and (2) if a polynomial has a point of that type. Our results characterize the complexity of these two questions for all degrees left open by prior literature. Our main contributions reveal that many of these questions turn out to be tractable for cubic polynomials. By contrast, we show that it is NP-hard to find a point within Euclidean distance $c^n$ (for any constant $c\geq 0$) of a local minimizer of an $n$-variate quadratic polynomial over a polytope.
Bio: Amir Ali Ahmadi is a Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Program in Applied and Computational Mathematics, the Department of Computer Science, the Department of Mechanical and Aerospace Engineering, the Department of Electrical Engineering, and the Center for Statistics and Machine Learning. He is also a part-time visiting research scientist at Google Brain (in the Robotics group). Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamics and control, and algorithms and complexity. Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the Presidential Early Career Award for Scientists and Engineers (PECASE), the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the MURI award of the AFOSR, the Howard B. Wentz Junior Faculty Award as well as the Innovation Award of Princeton University, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization'') is a three-time recipient of the Teaching Award of the Princeton Engineering Council, as well as a recipient of the Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers, and the Phi Beta Kappa Award for Excellence in Undergraduate Teaching at Princeton University. Amir Ali's research has been recognized by a number of best-paper awards, including the INFORMS Optimization Society's Young Researchers Prize, the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the Best Conference Paper Award of the IEEE International Conference on Robotics and Automation, and the prize for one of two most outstanding papers published in the SIAM Journal on Control and Optimization in 2013-2015. Rekha Thomas (University of Washington)
https://sites.math.washington.edu/~thomas/
Title: Graphical Designs: Structure, Complexity and Applications
Abstract: Graphical designs are quadrature rules on graphs that are discrete analogs of spherical designs on the sphere. They have a number of applications to areas such as graph sampling and random walks. An important question about designs is how to compute/optimize over them. I will explain how positively weighted designs can be organized on the faces of a polytope, and how this connection can be used to compute and optimize designs in several families of graphs. The polytope connection also yields complexity results.
Bio: Rekha Thomas received a Ph.D. in Operations Research from Cornell University in 1994 under the supervision of Bernd Sturmfels, followed by postdoctoral positions at the Cowles Foundation for Economics at Yale University and the Konrad-Zuse-Zentrum for Informationstechnik in Berlin. She is currently the Walker Family Endowed Professor of Mathematics at the University of Washington in Seattle. Thomas is a Fellow of the American Math Society and was an invited speaker at the International Congress of Mathematicians in 2018. Her research interests are in optimization and applied algebraic geometry. Etienne de Klerk (Tilburg University)
https://sites.google.com/site/homepageetiennedeklerk/ Title: Proving inequalities using semidefinite programming duality: applications in the worst-case analysis of iterative methods
Abstract: Semidefinite programming (SDP) may be seen as a generalization of linear programming, and similarly has a strong duality theory. Dual optimal solutions may be viewed as certificates of optimality, i.e. certifying nonnegativity of a given function on a given set. Since SDP problems are computationally tractable, this provides a computer-assisted approach to proving inequalities. An interesting application of this idea is in the worst-case analysis of iterative optimization methods. Surprisingly, the worst-case performance may often be certified via a dual SDP solution, e.g. for the gradient descent method of Cauchy on the class of L-smooth functions. In this talk we will present the basic ideas of this approach, and survey some recent developments.
Bio: Etienne de Klerk completed his BSc and MSc degrees at the University of Pretoria in South Africa, and obtained his PhD degree from the Delft University of Technology in The Netherlands in 1997. From January 1998 to September 2003, he held assistant professorships at the Delft University of Technology, and from September 2003 to September 2005 an associate professorship at the University of Waterloo, Canada, in the Department of Combinatorics & Optimization. In September 2004 he was appointed at Tilburg University, The Netherlands, first as an associate professor, and then as full professor (from June 2009). From August 29th, 2012, until August 31st, 2013, he was also appointed as full professor in the Division of Mathematics of the School of Physical and Mathematical Sciences at the Nanyang Technological University in Singapore. From September 1st, 2015 to August 31st 2019, he also held a full professorship at the Delft University of Technology (1 day/week position).
Dr. De Klerk's main research interest is mathematical optimization, and his publications include the monograph Aspects of Semidefinite Programming (Kluwer/Springer, 2002). He has served five 3-year terms as associate editor of the SIAM Journal on Optimization, two 3-year terms as associate editor of the INFORMS Journal Operations Research, and has been guest editor of two issues of Mathematical Programming B.
He is a co-recipient of the Canadian Foundation for Innovation's New Opportunities Fund award, a recipient of the VIDI grant of the Dutch Organization for Scientific Research (NWO), and a co-recipient of the ENW-GROOT grant of the NWO. He received the 2017 Best Paper Prize from the Springer journal Optimization Letters for joint work on the complexity of gradient descent methods.
Frank Vallentin (Universität zu Köln)https://www.mi.uni-koeln.de/opt/frank-vallentin/) Title: Generalizations and Applications of the Lovász theta number Abstract: The theta number of Lovász of a graph, originally invented to determine the Shannon capacity of the pentagon, has been a source of inspiration for everybody working in the area of semidefinite programming (linear optimization over the convex cone of positive semidefinite matrices). By Lovász' sandwich theorem the theta number is sandwiched between the independence number of the graph and the chromatic number of the complementary graph.
In this lecture I will discuss generalizations, strengthenings, and applications of the Lovász theta number for infinite geometric graphs and hypergraphs. In concrete applications harmonic analysis will be key to perform explicit computations. Bio: Frank Vallentin is a professor of applied mathematics (computer science) at Universität zu Köln. In 2003 he received his Ph.D. in mathematics from Technische Universität München. Past appointments include assistant and associate professor at Technische Universiteit Delft, postdoc at Centrum Wiskunde & Informatica in Amsterdam and postdoc at the Hebrew University of Jerusalem. His research interests include optimization, geometry, discrete and experimental mathematics.
