Distributionally Robust Optimisation With Matrix Moment Constraints: A Semi-Infinite and Semi-Definite Programming Approach

One of the most challenging issues in decision analysis is to find an optimal decision under uncertainty. The solvability of such a decision problem and the quality of the optimal decision rely heavily on available information on the underlying uncertainties which are often mathematically represented by a vector of random variables or a random process. If a decision maker has complete information on the distribution of the random parameters, then he can either obtain a closed form of the integral of the random functions in the problem and then convert it into a deterministic optimisation problem, or alternatively use various statistical and numerical integration approaches such as scenario method, Monte Carlo sampling method and quadrature rules to develop some approximation schemes and then solve this using standard linear/nonlinear programming codes.

The situation can become far more complex if the decision maker does not have complete information on the distribution of the random variables. For instance, if the decision maker does not have any information other than the range of the random variables, then it might be a reasonable strategy to choose an optimal decision on the basis of the worst scenario of the random parameters in order to immunize the risks from the uncertainty. This kind of decision making framework is known as robust optimisation and it is well known in engineering design where an optimal design must take into account of the extreme (albeit rare) event. However, this kind of robust scheme is not necessarily economical in that it sets out excessive resources for preventing a rare event. From numerical perspective, the resulting optimization problem could be intractable. A alternative and possibly less conservative robust optimisation model, which is known as distributionally robust optimisation, is to consider a set of distributions with historical data, computer simulation or subjective judgements which contain the true distribution with certain confidence and the optimal decision is chosen on the basis of the worst distribution rather than the worst scenario.

In this project, we concentrate on a class of distributionally robust optimization problems where the set of distributions is estimated through moment of random matrices which capture some partial information such as the mean value, the standard deviation or the correlation of the random variables.Through some duality theory in convex analysis, we transform the distributional robust optimization into mathematical programs with semi-infinite and semi-definite constraints (MPSISDC). Two fundamental questions arise: 1. If the moments are calculated from samples, how reliable are the optimal value and the optimal solution (or stationary points if the problem is nonconvex) obtained from solving the MPSISDC? This requires one to carry out comprehensive qualitative and quantitative statistical analysis. This kind of analysis is known as asymptotic convergence analysis or stability analysis in stochastic programming but little has been done for robust or distributionally robust optimization. 2. How do we solve the MPSISDC? This is a deterministic optimization problem which involves semi-definite and semi-infinite constraints with matrix variables. If the underlying function is linear or quadratic and the support of the random variables are polynomial or semi-algebraic, then the MPSISDC may be recast as a semi-definite programming problem or a convex conic programming problem, but here we do not assume the specific structure and hence there is no existing optimization method which can be readily applied to solve MPSISDC.

This project is to use MPSISDC as a platform to establish the theory of asymptotic analysis for the class of distributionally robust optimization problems and develop novel numerical methods for solving them.

Robust optimisation is unequivocally one of most influential and challenging topics in operational research and optimisation over the past decade for its ubiquitous applications such as decision analysis, data classification, finance, engineering and management sciences. It involves a number of important disciplinary areas including stochastic optimisation, risk analysis, convex analysis, applied probability and variational analysis.

This project lies at the cutting edge of research on robust optimisation. We consider a simple but fundamental issue: if a decision problem constitutes some uncertainty parameters and there is an ambiguity on the distribution of the uncertainty, how do we choose an optimal decision which can effectively immunise the risk from incomplete information on the uncertainty and how much confidence may we have in the optimal solution? Previous research has partly addressed this for a number of specific problems particularly in portfolio optimization where the support set of the random variables or the range of the their statistical quantities is well structured (e.g. polyhedral, semi-algebraic) and the underlying functions are linear or quadratic.

This proposal builds on the state of the art of research in the area of robust optimization and advances it by taking a new direction from modelling, to theory and methodology. Instead of considering moments of scalar functions as in the classical minimax distributionally robust optimization models, we consider matrix moments which subsume a number of practically interesting models and allow us to develop a new dual formulation, that is, a mathematical program with semi-infinite and semi-definite constraints; differing from the main stream methods in the literature of robust optimization which build on convex conic programming or semidefinite programming, the randomization approaches for solving the dual problem in this proposal will take a new route and allow one to apply them to a broader class of problems (with less restrictions on the underlying functions and the support of the random variables); the theory of asymptotic analysis will provide a foundation for qualitative and quantitative analysis of the optimal value, optimal solutions and the stationary points.

Researchers in robust optimization, stochastic programming and semi-infinite programming will benefit directly from the new model, theory and computational methods as detailed in the academic beneficiaries.

The proposed model and computational schemes may be used by practitioners working in practical application areas such as portfolio optimization, data classification, supply chain management, capacity expansion in energy and transportation where an optimal decision needs to be made before realization of uncertainty and there is a limited information on the distribution of the uncertainty.