## Operational Research and Statistics Seminars 2011-2012

### Programme

All seminars will commence at 11:10am in room M/0.34, The Mathematics Institute, Cardiff University, Senghennydd Road (unless otherwise stated).

Please contact Dr Iskander Aliev for more details regarding Operational Research/WIMCS lectures and Dr Denis Denisov for more details regarding Statistics lectures.

##### 14 October 2011

Speaker: Dr Vincent Knight (Cardiff)

Title: Staffing Levels of a Maths Support Centre.

##### 19 October 2011 - 11:00

Speaker: Mark Kelbert (Swansea)

Title: Uniform asymptotics of ruin probabilities for Levy processes.

Abstract: We present, for spectrally negative L\'{e}vy processes $X,$ uniform approximations for the finite time ruin probability $$\Psi(t,u)=P_u[T\leq t], T=\inf\{t\geq 0: X(t) < 0\},$$ when $u=X(0)$ and $t$ tend to infinity such that $v=u/t$ is constant, and the so-called Cram\'{e}r light-tail conditions are satisfied.

##### 14 October 2011

Speaker: Ely Merzbach (Bar Ilan)

Title: The set-indexed L\'evy process

Abstract: We present a satisfactory definition of the important class of L\'evy processes indexed by a general collection of sets. We use a new definition for increment stationarity of set-indexed processes to obtain different characterizations of this class. As an example, the set-indexed compound Poisson process is introduced. The set-indexed L\'evy process is characterized by infinitely divisible laws and a L\'evy-Khintchine representation. Moreover, the following concepts are discussed: projections on flows, Markov properties, and pointwise continuity. Finally the study of sample paths leads to a L\'evy-It\^o decomposition. As a corollary, the semimartingale property is proved. Jointly with Erick Herbin, Ecole Centrale Paris

##### 23 November 2011

Speaker: Ely Merzbach (Bar Ilan).

Title: The set-indexed L\'evy process.

Abstract: TBC.

##### 30 November 2011

Speaker: Valerii Fedorov (GlaxoSmithKline).

Title: Optimal Design of Experiments: from 1918 to Cardiff.

Abstract: Optimal design of experiments is a natural way of gaining more information given time/cost constraints in natural sciences and engineering. For decades statisticians have been contributing to creation and improvement of optimal design methods. While these methods worked almost flawlessly in those areas, they need careful modification to be used in many modern applications. Examples include spatial allocations, computer experiments, genomics and clinical studies. Often the initial enthusiasm about the (mathematical) efficiency of optimal designs quickly disappears during the first discussion between a statistician and a research team. Compromises between the desire to get maximal information and various constraints, some of which are not easy quantifiable, is a well pronounced feature of the contemporary design evolution. It will be a very sketchy talk and immediate questions and comments will make my task simpler and (hopefully) our interaction more enjoyable.

##### 7 December 2011

Speaker: Andrey Pepelyshev (Aachen University).

Title: A new method of nonparametric density estimation.

Abstract:The application of Singular Spectrum Analysis (SSA) to the empirical distribution function sampled at a grid of points spanning the range of the sample leads to a novel and promising method for the computer-intensive nonparametric estimation of both the distribution function and the density function. SSA yields a data-adaptive filter, whose length is a parameter that controls the smoothness of the filtered series. A data-adaptive algorithm for the automatic selection of a general smoothing parameter is introduced, which controls the number of modes of the estimated density.

Extensive computer simulations demonstrate that the new automatic bandwidth selector improves on other popular methods for various densities of interest. The simulation results indicate that the SSA density estimate with the automatic choice of the filter length outperforms the kernel density estimate in terms of the mean integrated squared error and the Kolmogorov-Smirnov distance for various density shapes.

##### 1 February 2012

Speaker: Professor Steve Gallivan.

Title: Geometry, set theory and paediatric heart transplantation.

Abstract: A child judged to need cardiac transplantation must wait until a suitable donor heart becomes available. There are criteria that must be satisfied for suitable donor hearts which depend on the tissue type and body mass of the recipient and potential donor. Depending on the clinical status of the recipient, so-called ‘bridging’ therapy may be given which involves admitting the child to hospital in an effort to ensure survival long enough for a suitable donor heart to become available. Such bridging is both distressing for the child and parents and is also very resource intensive. It is useful to have an estimate of how long the child must wait before a suitably matched donor heart becomes available and the probability of death while waiting. A mathematical model making use of multidimensional geometry and set theory has been devised to derive such estimates. This extends results discussed at the 2011 ORAHS meeting.

##### 8 February 2012

Speaker: Prof. Jacek Gondzio (Edinburgh)

Title: Large Scale Optimization with Interior Point Methods.

Abstract:Interior Point Methods (IPMs) for linear, quadratic and
nonlinear programming have been around for more than 25 years
and have completely changed the field of optimization.
In this talk we will focus on the major features responsible
for their spectacular success:
(a) nice properties (self-concordance) of logarithmic barriers
which are responsible for the polynomial complexity of IPMs,
(b) a unified view of IPMs for linear, quadratic, convex
nonlinear, second-order cone, and semidefinite programming,
(c) IPMs' ability to solve very large problems.

A redesign of interior point methods for LP/QP problems
will then be addressed bearing two objectives in mind:
to allow only matrix-vector products to be executed
with the Hessian and Jacobian and its transpose; and
(b) to allow the method work in a limited-memory regime.

If time permits, numerical results of applying the new approach
to three classes of challenging problems will be presented:
- relaxations of quadratic assignment problems,
- quantum information problems,
- sparse approximation problems arising in compressed sensing.

References:

J. Gondzio, Matrix-Free Interior Point Method,
Computational Optimization and Applications,
Published online: October 15, 2010,
DOI: 10.1007/s10589-010-9361-3

J. Gondzio, Interior Point Methods 25 Years Later,
European Journal of Operational Research, 218 (2012), pp. 587-601.
DOI: http://dx.doi.org/10.1016/j.ejor.2011.09.017

##### 15 February 2012

Please note time and venue change:

Room: M/1.25 Time: 12:10

Speaker: Dr Peter Richtarik (Edinburgh)

Title: How to Climb a Hill in Billion Dimensions Using a Coin and a Compass?

Subtitle: Solving regularized convex problems in huge dimensions via greedy,
randomized, serial and parallel coordinate descent

Abstract:Optimization problems of large-enough sizes (millions of variables or more) are difficult or impossible to solve using standard algorithms based on the evaluation of the Hessian or even the gradient. This is mainly due to memory restrictions and/or bad dependence of the methods on problem dimension.

In this talk we will examine some recent results on iteration complexity and practical efficiency of algorithms which at each iteration only need to evaluate a single partial derivative (or a directional derivative in a small dimensional subspace), and which never need to evaluate the function value. In certain applications of favorable structure this means that the work done per iteration is virtually constant and much smaller than the dimension.

We give the first true iteration complexity bounds for randomized
block-coordinate descent methods applied to the problem of minimizing
the sum of a smooth convex and a simple separable nonsmooth convex
function. We show that the method can be accelerated, in theory and in
practice, by parallelization, under a certain natural and easily verifiable assumption on the objective function, and give explicit formula for the acceleration factor. Time permitting, greedy variants of the methods will be considered as well.

In the second part of the talk we demonstrate numerically that the algorithms are able to solve huge-scale L1-regularized support vector machine and least squares problems with billion variables. Finally, we present computational results with a GPU-accelerated parallel version of the method, on truss topology design and other problems, achieving speedups of up to two orders of magnitude when compared to a single-core implementation in C.

##### 20 February 2012

Room: M/0.34 Time: 14:10

Title: Second-Order Cone Programming and Its Applications

Abstract:
It has become clear over the past fifteen years or so that the three most fundamental and important kinds of convex optimisation techniques are Linear Programming (LP), Second-Order Cone Programming (SOCP) and Semidefinite Programming (SDP). This seminar will introduce SOCP to the non-expert. As well as covering theory and algorithms, it will give examples of applications of SOCP to problems in statistics, finance and operational research.

##### 22 February 2012

Speaker: Peter Moerters (Bath)

Title: Shifting Brownian motion

Abstract:
Let $B=(B_t)_{t\in\R}$ be a two-sided standard Brownian motion. An
unbiased shift of $B$ is a random time $T$, which is a measurable
function of $B$, such that $(B_{T+t}-B_T)_{t\in\R}$ is a Brownian
motion independent of~$B_T$. We characterise unbiased shifts and solve
the Skorokhod embedding problem for unbiased shifts by constructing,
for any probability distribution~$\nu$ on the reals, a nonnegative
unbiased shift such that $B_T$ has distribution~$\nu$. We show that
our solution is minimal and discuss its moment properties. The talk is
based on joint work with Guenter Last (Karlsruhe) and Hermann
Thorisson (Reykjavik).

##### 29 February 2012 11:00

Speaker: Dr Konstantinos Kaparis (Lancaster)

problem.

Abstract: In the Network Loading Problem (NLP) one is given an undirected
graph G=(V,E) along with a set of demands within V. The task is to choose
the amount of integer capacities to be installed on each edge in such a
away that the cost is minimised and all the commodities can be routed
simultaneously.In this work, a stochastic variant of this problem is being
considered. Moreover, the demand is uncertain and its realization depends
on a finite number of scenarios. We model this problem as a 2-stage
stochastic mixed-integer program with complete recourse. We introduce the
new class of probabilistic metric inequalities and we describe a heuristic
separation algorithm.

##### 29 February 2012 15:00

Speaker: Prof. S. Foss (Heriot-Watt University, Edinburgh)

Title: TBC

Abstract: TBC

##### 7 March 2012

Speaker: Prof. Jorg Fliege (University of Southampton)

Title: TBC

Abstract: TBC

##### 7 March 2012

Speaker: Prof. V. V. Anh (Queensland University of Technology, Brisbane, Australia)

Title: TBC

Abstract: TBC

##### 7 March 2012

Speaker: Dr A. Olenko (La Trobe University, Melbourne, Australia)

Title: TBC

Abstract: TBC

##### 14 March 2012

Speaker: Dr Per Kristian Lehre (Nottingham)

Title: Probabilistic Analysis of Evolutionary Algorithms.

Abstract: Evolutionary algorithms (EAs) tackle optimisation problems by
simulating natural evolution. A "population" of individuals, ie
candidate solutions to the optimisation problem, is evolved over
several "generations". A new generation is obtained by reproducing
with some variation the "fitter" individuals in the current
generation.

EAs have been used extensively since the 1960s, but their mathematical
properties are poorly understood. Of particular interest is the
distribution of the random variable T that expresses the number of
generations before the population contains an optimal individual, the
so-called runtime distribution.

This talk focuses on how the variation operator and the selection
mechanism influence the runtime distribution. The main result
presented is a phase-transition in the expected runtime from
polynomial to exponential (in the number of problem dimensions) when
the degree of variation surpasses a certain threshold that depends on
the "selective pressure". This result is compared with the notion of
error thresholds in Eigen's quasispecies model of evolution. Some
proof ideas will be discussed, including a multi-type branching
process model of the EA, and drift analysis.

##### 21 March 2012

Speaker: Prof. V.V.Anh (Queensland University of Technology, Brisbane, Australia)

Title: Diffusion in heterogeneous domains

Abstract: This work is motivated by the problem of saltwater intrusion in coastal aquifers. These underground aquifers can be a major source of water for irrigation, industrial and town water usage. Due to their proximity to the ocean, excessive demand for groundwater may result in saltwater intrusion with a substantial loss of agricultural land. It is therefore an essential task to develop suitable mathematical models and computational tools for visualisation and prediction of salinity diffusion in aquifers for scenario analysis and management planning.

Due to the complex nature of the aquifers, with alternating layers of permeable sandstone and impermeable clay sediments, it is a challenge to understand the role of heterogeneity in the aquifer and in the physical law governing the saltwater flow. We will formulate the problem in the framework of fractional diffusion in heterogeneous domains. We will outline the existing theory of diffusion on fractals, then move on to a theory of diffusion on multifractals based on the RKHS approach. This latter theory yields a class of models for fractional diffusion with variable singularity order in heterogeneous domains. We will look at the wavelet transforms of these space-time random fields for their statistical estimation and interpolation.

##### 28 March 2012

Speaker: Dr A.Olenko (La Trobe University, Melbourne, Australia)

Title: On Asymptotic Properties of Long-Range Dependent Random Fields

Abstract: We describe a framework for asymptotic behaviour of covariance functions or variances of averaged functionals of random fields at infinity and spectral densities at zero. We survey some Abelian and Tauberian theorems for long-range dependent random fields. The use of the theorems and their limitations are demonstrated through applications to some new and less-known examples of covariance functions of long-range dependent random fields.

We also discuss some limit theorems for weighted functionals of random fields with spectral singularities at non-zero frequencies. For general schemes, in contrast to the Donsker line, we demonstrate that the singularities at non-zero frequencies play a role even for linear functionals.