The purpose of the workshop is to bring together researchers working in convex geometry, polynomial optimisation and related areas.

Organisers

Minh Dao, Vera Roshchina

Confirmed participants

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

Workshop Program

Abstracts

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 $N$ points $\mathcal{X}_N = \{\mathbf{x}_1, \ldots, \mathbf{x}_N\} \subset \mathbb{S}^d$ where $\mathbb{S}^d$ is the unit sphere in $\mathbb{R}^{d+1}$. The aim is to find sets of points which minimize the radius $h$ for covering the sphere $\mathbb{S}^d$ by spherical caps centered at each point $\mathbf{x}_j, j = 1,\ldots,N$ and of the same radius $h$. This is the same as finding sets of $N$ points which minimize the mesh norm $h_{\mathcal{X}_N} = \max_{\mathbf{x}\in\mathbb{S}^d} \; \min_{j=1,\ldots,N} \; \mbox{dist}(\mathbf{x}, \mathbf{x}_j)$ where $\mbox{dist}(\mathbf{x}, \mathbf{y}) = \cos^{-1} (\mathbf{x} \cdot \mathbf{y})$ for $\mathbf{x}, \mathbf{y} \in \mathbb{S}^d$ 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 $\mathbb{S}^2$ and $\mathbb{S}^3$, in particular how close computer results are to known lower bounds.