Polynomial Algebraic Developments in Optimisation and Computation

11 April 2019

The solution of polynomial algebraic equations is common in the design of efficient numerical and optimisation techniques. Examples include highly accurate quadrature methods in numerical analysis and semi-definite programming relaxation in optimisation.The feasibility of solution techniques is often due to the special structure of these problems. For more general problems, direct solvers used for polynomial systems are based on Buchberger's algorithm. These techniques yield exact answers, yet have prohibitively high computational cost even for moderate-sized problems. They are also affected by numerical instabilities and floating point errors.

Topics of the workshop include: computational algebraic geometry and floating point arithmetic, convex algebraic geometry, polynomial systems of equations and optimisation problems, semialgebraic problems (i.e., polynomials systems with polynomial constraints).

Sessions

11 April 2019
Time Session
10am
Higher order Voronoi cells
Dr Vera Roshchina, UNSW
The classic Voronoi cells can be generalized to a higher-order version by k-element closest subsets of sites. We study the structure of the k-order Voronoi cells and illustrate our theoretical findings with a case study of two-dimensional higher-order Voronoi cells on four sites.
11am
Morning tea
11:30am
Numerical methods for computing the GCD of univariate polynomials using floating point arithmetic
Prof. Markus Hegland, ANU
Computing the greatest common divisor (GCD) for two polynomials in floating point arithmetic is known to be computationally challenging and even in standard library software the methods used there might return the result GCD=1 for the case where the polynomials have a nontrivial GCD. Here we review Euclid's algorithm and test a variant for a class of random polynomials. We find that our variant of Euclid's method often produces an acceptable result. However, close monitoring of the values of the norm of the vector of coefficients of the intermediate polynomials arising in the computations is required.
12:15pm
Lunch
2pm
On the approximation of monotone operators in a general Banach space
Prof. Andrew Eberhard, RMIT
As the analysis of monotone operators with nonempty interior in their domain is much more tractable, the question arises as to whether one can approximate the harder FPV operators with ones with a nicer domain. Domain regularisation of maximal monotone operators exists for type-(NI) operators and general operators in reflexive spaces. In this talk we consider what can be said about approximation of this wider class of operators in the Attouch-Wets topology. We also show that convergence of maximal monotone operators in this sense preserves representativeness of the associated Fitzpatrick function and so we are able to deduce a sum theorem for FPV and FP(=NI) operators. Along the way some technical machinery of independent interest is discussed.
3:30pm
Afternoon tea
4pm
Using polynomials and complex analysis to check for numerical error in the experimental study of an optimisation algorithm
Dr Scott Lindstrom, Hong Kong Polytechnic
Splitting methods are special algorithms that are commonly used to solve optimisation problems for engineering and machine learning. One of these algorithms, the Douglas--Rachford method, works in many cases where the problems are not convex. In an effort to learn about the algorithm's special properties, we use the dynamical geometry software Cinderella to visualise its behaviour when it is used to find a point in the intersection of an ellipse and a line. In order to check the sensitivity of our Cinderella code to compounding numerical error, we use the polynomial structure of an ellipse and borrow a convenient tool from complex analysis: the Schwarz function.

Registration closes 10 April, 2019

Room 4.41, Building #145, Science Road, The Australian National University

Map

Canberra is located in the Australian Capital Territory, on the ancient lands of the Ngunnawal people, who have lived here for over 20,000 years. Canberra’s name is thought to mean ‘meeting place’, derived from the Aboriginal word Kamberra. European settlers arrived in the 1830s, and the area won selection by ballot for the federal capital in 1908. Since then the ‘Bush Capital’ has grown to become the proud home of the Australian story, with a growing population of around 390,000.

Canberra hosts a wide range of tourist attractions, including various national museums, galleries and Parliament House, as well as beautiful parks and walking trails. Several attractions are within walking distance of the ANU campus, including the National Museum of Australia and the Australian National Botanic Gardens. Canberra is also a fantastic base from which to explore the many treasures of the surrounding region, including historic townships, beautiful coastlines and the famous Snowy Mountains. Learn more about what to do and see during your stay in Canberra here.

Accommodation

Below are some accommodation options for your visit to Canberra.

http://www.anu.edu.au/study/accommodation/accommodation-alternatives

Visas

International visitors to Australia require a visa or an electronic travel authority (ETA) prior to arrival. It is your responsibility to ensure documentation is correct and complete before you commence your journey. Information on obtaining visas and ETAs can be found here.

Transportation

There are many ways to get around Canberra. Below is some useful information about Bus & Taxi transport around the ANU, the Airport and surrounding areas.

If you are catching a taxi or Uber to the ANU Mathematical Sciences Institute, ask to be taken to Building #145, Science Road, ANU. We are located close to the Ian Ross Building and the ANU gym. A Taxi will generally cost around $40 and will take roughly 15 minutes. Pricing and time may vary depending on traffic. Taxi bookings can be made through Canberra Elite Taxis - 13 22 27. Airport Shuttle the ACT government has implemented a public bus service from the CBD to the Canberra Airport via bus Route 11 and 11A, seven days a week. Services run approximately every half hour, and better during peak times (weekdays) and every hour (weekends). To travel just use your MyWay card or pay a cash fare to the driver when boarding. A single adult trip when paying cash will cost$4.80 with cheaper fares for students and children. Significant savings can be made when travelling with MyWay.

View MyWay and Fares information.