This page contains historical information about a workshop held in the past.
The purpose of the workshop was to bring together researchers working in convex geometry, polynomial optimisation and related areas.
5-6 November 2019, UNSW Sydney
Minh Dao, Vera Roshchina
Abhishek Bhardwaj, ANU
Minh Dao, UNSW Sydney
Sabrina Deo, UNSW Sydney
Martin Helmer, ANU
Guoyin Li, UNSW Sydney
Bruno Lourenço, University of Tokyo
Ryan McKewen, UNSW Sydney
Vinesha Peiris, Swinburne University of Technology
Vera Roshchina, UNSW Sydney
Björn Rüffer, University of Newcastle
James Saunderson, Monash University
Nadia Sukhorukova, Swinburne University of Technology
Julien Ugon, Deakin University
Rob Womersley, UNSW Sydney
|Tuesday 5 November, RC-4082|
|9:15–10:15||Bruno Lourenço, Amenable cones and error bounds|
|10:45–11:20||Guoyin Li, High order power methods for tensor rank one best approximation problem|
|11:20–11:50||Sabrina Deo, Optimal Selling Mechanisms for a Financially
(note a talk by Jesse Burke on Singularities and minimal free resolutions in the same room at 12pm)
|13:10–14:00||Björn Rüffer, Lyapunov Functions and Non-Convex Douglas-Rachford|
|14:00–14:30||Vinesha Peiris, Solving nonclassical Chebyshev approximation problems|
|15:00–15:35||Minh Dao, Conical averagedness and convergence analysis of fixed point algorithms|
|Wednesday 6 November, RC-3085|
|9:15–10:15||Martin Helmer, Segre-Driven Containment Testing and Multiplicity Computation for Varieties|
|10:45–11:20||Nadia Sukhorukova,Optimisation and signal approximations|
|11:20–11:50||Ryan McKewen, Plesiohedra: Voronoi Diagrams & Properties|
|13:10–13:45||Julien Ugon, Necessary and sufficient conditions for globally best Chebyshev approximation|
|13:45–14:30||James Saunderson, Limitations on the expressive power of convex cones without long chains of faces|
|15:00–15:30||Abhishek Bhardwaj, The Moment Problem: Recent advances and open questions|
|15:30–16:10||Rob Womersley, Good Covering of the Sphere by Spherical Caps|
|16:10–17:00||Open Problem/Discussion session|
Speaker: Minh Dao, UNSW Sydney
Title: Conical averagedness and convergence analysis of fixed point algorithms
Abstract: In this work, we consider a conical extension of averaged nonexpansive operators and its usefulness in the convergence analysis of fixed point algorithms. Various properties of conically averaged operators are systematically studied, in particular, the stability under relaxations, convex combinations, and compositions. We then derive the conical averagedness of the resolvents of operators that possess certain types of generalized monotonicity. These properties are used to analyze the convergence of fixed point algorithms including the proximal point algorithm, the forward-backward algorithm, and the adaptive Douglas–Rachford algorithm. Our results not only unify and improve recent studies but also provide a different perspective on the topic.
Speaker: Martin Helmer, ANU
Title: Segre-Driven Containment Testing and Multiplicity Computation for Varieties
Abstract: In this talk we consider new methods to test pairwise containment of projective varieties (i.e. the solutions to systems of homogeneous polynomial equations). Previous approaches to this problem have doubly exponential complexity, in this talk we present a new effective algorithm with singly exponential complexity. This algorithm can also determine algebraic multiplicity of singular points and subvarieties without working in local rings. These methods may be implemented without using Gröbner bases; in particular numeric methods can be used. The methods arise from techniques developed to compute the Segre class s(X,Y) of X in Y for X and Y arbitrary subschemes of an affine or projective space. These algorithms are implemented in Macaulay2 and have been found to be effective on a variety of examples. This is joint work with Corey Harris (University of Oslo).
Speaker: Guoyin Li, UNSW Sydney
Title: High order power methods for tensor rank one best approximation problem
Speaker: Bruno Lourenço, University of Tokyo
Title: Amenable cones and error bounds
Abstract: In this talk, we will discuss error bounds for conic linear systems.
Usually, in order to obtain error bound results, it is necessary to assume constraint qualifications and/or regularity conditions. However, in 2000, Jos Sturm showed how error bounds for SDPs can be obtained without assuming regularity conditions.
Furthermore, he showed that the quality of the bound depends on the singularity degree of the problem. The singularity degree, by its turn, is related to facial reduction, which is a general approach for regularizing optimization problems.
Taking Sturm’s work as a starting point, we show that error bounds without constraint qualifications hold for a broad new family of cones called “amenable cones”. Similarly, we show that the quality of the bound is also controlled by the singularity degree of the underlying problem. This highlights that facial reduction and error bounds are intrinsically connected, even in a relatively general setting. In particular, we provide a new Hölderian error bound for the doubly nonnegative cone and for symmetric cones, which recovers Sturm’s result as a special case.
Speaker: Vinesha Peiris, Swinburne University of Technology
Title: Solving nonclassical Chebyshev approximation problems
Abstract:In Chebyshev approximation problem, the goal is to minimise the supremum of linear functions. In the case of polynomials and piecewise polynomial approximation with fixed knots, the corresponding problems are convex. Consider the rational approximation where the parameters of both polynomials must be optimised. This problem is not convex anymore, instead it is quasiconvex which is not a general nonconvex optimisation problem. In this talk I will first introduce rational approximation and then move on to EEG signal approximation using rational approximation.
EEG signals are known as the electric brain activity and approximating EEG signals is very beneficial for medical doctors to identify specific wave patterns. We approximate the EEG signals by optimising the amplitude using the rational approximation where we find the minimum objective value for specific frequency and shift value.
Speaker: Björn Rüffer, University of Newcastle
Title: Lyapunov Functions and Non-Convex Douglas-Rachford
Abstract: While global convergence of the Douglas-Rachford iteration is often observed in applications, proving it is still limited to convex and a handful of other special cases. Lyapunov functions for difference inclusions provide not only global or local convergence certificates, but also imply robust stability, which means that the convergence is still guaranteed in the presence of persistent disturbances. In this work, a global Lyapunov function is constructed by combining known local Lyapunov functions for simpler, local sub-problems via an explicit formula that depends on the problem parameters. Specifically, we consider the scenario where one set consists of the union of two lines and the other set is a line, so that the two sets intersect in two distinct points. Locally, near each intersection point, the problem reduces to the intersection of just two lines, but globally the geometry is non-convex and the Douglas-Rachford operator multi-valued. Our approach is intended to be prototypical for addressing the convergence analysis of the Douglas-Rachford iteration in more complex geometries that can be approximated by polygonal sets through the combination of local, simple Lyapunov functions. (Joint work with Ohad Giladi).
Speaker: James Saunderson, Monash University
Title: Limitations on the expressive power of convex cones without long chains of faces
Abstract: A central idea in conic optimisation is that of a “lifted” representation of a convex body—a description as the projection of an affine slice of a convex cone K in a higher dimensional space. Often such a lifted representation is more computationally tractable than a description involving the original variables alone.
In this talk I’ll briefly introduce this idea, and then present recent results showing that a certain neighbourliness property is an obstruction to having a lifted representation using a finite Cartesian product of cones, each of which has no long chains of faces. From this, one can show that various convex bodies arising in convex optimisation-based approaches to polynomial optimisation do not have lifts using finite Cartesian products of second-order cones, smooth cones, low-dimensional cones, or cones defined by hyperbolic polynomials of low degree.
Speaker: Rob Womersley, UNSW Sydney
Title: Good Covering of the Sphere by Spherical Caps
Abstract: Consider a set of points where is the unit sphere in . The aim is to find sets of points which minimize the radius for covering the sphere by spherical caps centered at each point and of the same radius . This is the same as finding sets of points which minimize the mesh norm where for is the geodesic distance. The mesh norm represents the largest hole in the set of points, and arises in a variety of contexts when approximating or numerically integrating functions on the sphere. This talk will concentrate on algorithms for calculating such point sets and numerical results for and , in particular how close computer results are to known lower bounds.