Upcoming Events 

Research Seminar

Wednesday 1 May, 10:30-13:00pm

Lecture Theatre, ICMS at Bayes Centre (5th floor)
47 Potterrow, Edinburgh EH8 9BT

OR Group of Scotland is delighted to invite you to this new cycle of research seminars which will highlight research across OR in the Scotland region. For this inaugural seminar, we are proud to welcome two outstanding speakers: Professor Jacek Gondzio (University of Edinburgh) and Doctor Spyridon Pougkakiotis (University of Dundee). Attendance is free but, please, you must register in order to attend. The venue has limited seats. This will be an in-person event exclusively.

We look forward to seeing you there!

OR Group of Scotland Board (Boray, Dom, and Sergio)

Schedule

book now

Professor Jacek Gondzio, University of Edinburgh

The research interests of Professor Jacek Gondzio ( https://www.maths.ed.ac.uk/~gondzio/ ) include the theory and implementation of algorithms for very large-scale optimisation.  He is best known for his contributions in the area of interior point methods. He was educated in Poland and since 1998 he has held a position at the School of Mathematics, the University of Edinburgh. Professor Gondzio is an editor of four leading optimisation journals: Computational Optimisation and Applications, European Journal of Operational Research, Mathematical Programming Computation and Optimisation Methods and Software. He has been elected the EUROPT Fellow 2019 ( https://www.euro-online.org/websites/continuous-optimization/europt-fellows/ )

Interior Point Methods and Column Generation: Discrete Optimal Transport and Network Flow Problems

In this talk we shall explain the reasons why interior point methods (IPMs) deliver particularly attractive features when they are applied in the context of cutting plane schemes and column generation techniques. These features include:

• Finding (stable) well-centred solutions of restricted master problems,
• Delivering on-demand accuracy in column generation.

It goes without saying that these features cannot be delivered by the simplex-based solvers. Some of the advantages will be illustrated when solving very large discrete optimal transport problems. (The OR Audience will easily
recognise that those are closely related to network flow problems.) IPMs excel on such problems and outperform state-of-the-art network solvers.

References:
* S. Cipolla, J. Gondzio and F. Zanetti, A regularized interior point method for sparse optimal transport on graphs, European Journal of Operational Research (published online 19 November 2023, https://arxiv.org/abs/2307.05186)
* F. Zanetti and J. Gondzio, An interior-point-inspired algorithm for linear programs arising in discrete optimal transport, INFORMS Journal on Computing 35 (2023) pp. 1061--1078
* J.Gondzio, Interior Point Methods in the Year 2024, Technical Report, February 28, 2024. Submitted for publication.

Doctor Spyridon Pougkakiotis, University of Dundee

Spyridon Pougkakiotis is a Lecturer in Mathematics at the School of Science and Engineering of the University of Dundee. He received his PhD in Optimization and Operational Research from the University of Edinburgh in 2022. Before joining the University of Dundee, he was a postdoctoral research associate at the Electrical Engineering department of Yale University. Spyridon’s research revolves around optimization, risk-aware decision-making, and computational mathematics, with applications in operational research, data science, and engineering.

Strong Duality in Risk-Constrained Nonconvex Functional Programming.

Functional programming (also known as policy optimisation/search) appears naturally in situations where optimal decisions are needed on the basis of observed information.  Such problems arise across a variety of disciplines, e.g., machine/reinforcement learning (predictors/classifiers/controllers are policies), estimation and control, finance/economics, and networking/communications. At the same time, functional (i.e., policy-related) constraints are desirable in modern applications, due to the need to induce robustness, fairness, safety, and more generally trustworthiness in policy design, which if remain unconstrained can reportedly result in highly undesirable or even catastrophic outcomes. Popular related areas include fair learning, safe reinforcement learning, adversarial learning, constrained estimation/control and constrained MDPs, robust resource allocation, and others.

Even though sometimes it may be possible to get away with convex (re)formulations, intrinsic nonconvexity is prevalent in most such problems, and the prominent framework of Lagrangian duality, which would enable rigorous scalarization of constraints, does not work in general. Nevertheless, it has been shown that strong duality indeed holds for expectation-constrained, arbitrarily nonconvex functional programs, under standard assumptions. This is remarkable and far-reaching, and is a consequence of standard (though deep) facts of convex geometry. However, expectation constraints are by construction inadequate to capture risky events, which are related to the statistical variability, dispersion or (fat) tail behaviour of the randomness involved in applications; properly treating such randomness is key in ensuring trustworthiness. Instead, risky behaviour is quantified by certain nonlinear generalisations of the expectation functional, called risk measures, but such functionals once again challenge the applicability of Lagrangian duality in the context of constrained programming.

In this talk, we show that, under the same assumptions, risk-constrained functional optimisation problems with general integrable nonconvex instantaneous reward functions also exhibit strong duality, regardless of nonconvexity. We consider risk constraints based on convex and positively homogeneous risk measures (evaluating those nonconvex rewards and) admitting dual representations with bounded risk envelopes, strictly generalising expectations. Beyond expectations, very popular risk measures supported within our setting include the conditional value-at-risk (CVaR), the mean-absolute deviation (including the non-monotone case), certain distributionally robust representations and more generally all real-valued coherent risk measures on the space of integrable functions L1. Our proof technique is new and relies on risk conjugate duality in tandem with J. J. Uhl's weak extension of A. A. Lyapunov's convexity theorem for vector measures taking values in general infinite-dimensional Banach spaces. We discuss the applicability of our result in the context of risk-aware resource allocation in wireless communication networks and risk-aware constrained machine learning.

A preprint of this work may be found on arXiv: https://arxiv.org/abs/2206.11948v3

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.