## 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:

(a) to avoid an explicit access to the problem data and

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

*Please note time change:*

**Room**: M/0.34 **Time**: 14:10

**Speaker:** Prof. Adam Letchford (Lancaster)

**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)

**Title:**Cutting planes for a stochastic variant of the network loading

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.