2015 Workshop - Program

Please scroll down for talk details or click on a name.

9:00-9:50 Jonathan Borwein
9:50-10:20 Morning coffee
10:20-10:50 Marc Demange
10:50-11:20 Cerasela Tanasescu
11:20-11:50 Shuai Liu
11:50-13:20 Lunch time (self sponsored)
13:20-13:50 Olivia Smith
13:50-14:20 Sameh Al-Shihabi
14:20- 15:10 Jonathan Borwein
15:10-15:40 Afternoon tea
15:40-16:10 Andrew Eberhard
16:10-16:40 Tian Sang
16:40-17:10 Vera Roshchina

9:00-9:50 and 14:20-15:10: Jonathan Borwein

Speaker: Jonathan Borwein
CARMA, University of Newcastle

Title: Two lectures on reflection methods for feasibility problems.
Abstract: In the first lecture I will sketch the theory of reflection methods aimed at finding a point in the intersection of two or more closed convex sets in Hilbert space. I will then turn to non-convex problems where much less is known.

In the second lecture, I will turn to a set of examples and heuristics for solving a variety of feasibility problems viewed as matrix completion problems. These include: solving Sudoku, reconstructing proteins, and finding Hadamard matrices.

10:20-10:50: Marc Demange

Speaker: Marc Demange
SMGS, RMIT University

Title: Are my dogs competitive? A short introduction to online optimisation
Abstract:
Online optimisation deals with instances of problems that are incrementally revealed over time. One should take decisions as soon as data are presented without information about the future data. The objective is to design strategies with worst case performance guaranties on the quality of the online computed solution vs the best possible solution with complete information.

This framework allows to address dynamic environments with continuous flow of data, in particular when it is hard to assign a relevant probability system on possible futures. This approach reveals to be particularly interesting nowadays as more and more applications request to take into account ongoing instantaneous data.
From a theoretical perspective, the online framework allows to better understand how the solutions of a problem may be affected by a lack of information. In some sense, this topic can be seen as a continuation of approximation theory.

As an example, I will discuss the problem of online Traveling Salesman Problem and some variants in metric spaces. This will show us typical kinds of results and approaches in online optimisation, but also a nice class of online time dependent problems.

I conclude by an ongoing project for an application in emergency fire management, leading to an online TSP with time windows constraints.

Joint work with G. Ausiello, L. Laura, V. Paschos, C. Tamasescu, J. Nim, Misty and Picsou.

10:50-11:20: Cerasela Tanasescu

Speaker: Cerasela Tanasescu
SMGS, RMIT University

Title: A Graph Approach for Fuel Management
Abstract: Fuel Management is a main component of wildfire mitigation strategies. The aim is to reduce the effects of potential bushfires and their risk to escape by prevention actions on fuel. Since such treatments, before the fire season, require a large amount of resources these actions need to focus on specific areas. Most fuel management models consider a landscape divided into cells representing candidate locations for fuel treatment. The key decision is to determine which cells should be treated during each time period (i.e., each year). Spatially explicit multi-period fuel treatment scheduling is a complex problem and most of the modeling efforts have considered small landscapes, sometimes of very particular shape like, for instance, grids. Two recent papers [Minas, Hearne, and Martell, 2014] and [Rachmawati , Ozlen, Reinke, Hearne, 2015] investigate interesting mixed integer programming models (MIP) for multi-year landscape level fuel treatment planning. Although very promising, these approaches require extended computational efforts.

In this ongoing work we investigate a complementary point of view using a pure combinatorial graph theory approach. Contrary to mathematical programming, it allows us to take into account the very particular structure of the neighbourhood graphs, planar and even sometimes (near) triangulated. For this first study, we address two different problems, without and with year budget constraints. For the first problem we reveal strong connections with the Minimum Weighted Vertex Cover problem and deduce good approximation algorithms, in particular for a long period of time. It reveals also some interesting polynomial cases. The second problem reveals to be radically different. We give first complexity results, even in grid-like graphs and present the future research direction and open questions. This work gives a different insight to fuel management with the potential to better understand the specific structure of different versions and lead to algorithms that may complement MIP approaches.

Joint work with Marc Demange (RMIT)

11:20-11:50: Shuai Liu

Speaker: Shuai Liu
SMGS, RMIT University

Title: The U-Lagrangian of a prox-regular function
Abstract: When restricted to a subspace, a nonsmooth function can be differentiable. It is known that for a nonsmooth convex function f and a point x, the Euclidean space can be decomposed into two subspaces: U, over which a special Lagrangian can be defined and has nice smooth properties and V, the orthogonal complement subspace of U. In this talk we generalize the definition of UV-decomposition and U-Lagrangian to the context of nonconvex functions, specifically that of a prox-regular function.

13:20-13:50: Olivia Smith

Speaker: Olivia Smith
IBM Research

Title: Simultaneous Operating Theatre Planning and Patient Selection

Abstract: Managing operating theatres has a crucial role in hospitals. In this talk, we describe a mixed integer programming approach to simultaneously allocate operating theatre time to surgery units, and select patients to be treated from waiting lists. We take into account resource constraints and financial considerations. This work has been done for a public hospital in Melbourne.

13:50-14:20: Sameh Al-Shihabi

Speaker: Sameh Al-Shihabi

Title: The Nested Partition Framework

Abstract The nested partition (NP) algorithm is a constructive meta-heuristic that implements a divide-and-conquer strategy to find the optimum solution. The solution feasible region is divided into subregions and samples are taken from each of these subregions to find the most promising one: the subregion expected to include the optimum solution. Again, the most promising subregion is divided and sampled to identify a smaller promising subregion. Non promising subregions are also sampled and if there is a higher probability that one of these subregions will have the optimum solutions compared to the promising subregion, then the algorithm backtracks to a larger region. This algorithm creates an ergodic Markov chain in which the optimum solution is an absorbing state. In this short, introductory tutorial, I will explain the basics of the algorithms, key factors for successful implementations, resemblance to other algorithms such as branch and bound and beam search, and an example of a successful implementation to solve the multi-dimensional knapsack problem.

15:40-16:10: Andrew Eberhard

Speaker: Andrew Eberhard
SMGS, RMIT University

Title: Symmetry, Invariance and Criticality
Abstract: The aim of this talk is to summarise, relate, explain and generalise a range of results in nonsmooth, and predominantly nonconvex analysis, that exploit the symmetry of underlying problems. Results of this kind date back to the work of Palais on the principle of symmetric criticality but there are more recent results that can be placed in a similar framework that revolves around the application of groups of symmetries. Some new results of this kind will be discussed including one involving monotone operators. We will discuss some applications including an application to compressed sensing.

Joint work with Vera Roshchina.

16:10-16:40: Tian Sang

Speaker: Tian Sang
SMGS, RMIT University

Title: Limit roots for some infinite Coxeter groups
Abstract: Given a Coxeter datum (V, B, Δ), where V is a vector space, B a symmetric bilinear form on V , and Δ a certain subset of V , we can define a root system (Φ, Δ, V, B) and its associated Coxeter system (W, S). In this talk, we will introduce the concepts of normalised roots, normalised isotropic cone, and limit roots for a root system. We are interested in the fractal behaviour of the set of limit roots, and its relation with the normalised isotropic cone both geometrically and algebraically. We will briefly discuss one of the main theorems on the set of limit roots. We then discuss an open question from the same paper, and compare the open question and the main theorem.

16:40-17:10: Vera Roshchina

Speaker: Vera Roshchina
SMGS, RMIT University

Title: Exact relations between the best conditioned solution and Grassmannian measure of well posedness for general convex cones
Abstract: We generalise and tighten a range of known results that relate a best conditioned solution of a conic feasibility problem with the geometric distance to unfeasibility defined recently by Dennis Amelunxen and Peter Burgisser.

This is joint work with Javier Pena, Carnegie-Mellon University.