Abstract We provide a novel method for sensitivity analysis of parametric robust Markov chains. These models incorporate parameters and sets of probability distributions to alleviate the often unrealistic assumption that precise probabilities are available. We measure sensitivity in terms of partial derivatives with respect to the uncertain transition probabilities regarding measures such as the expected reward. As our main contribution, we present an efficient method to compute these partial derivatives. To scale our approach to models with thousands of parameters, we present an extension of this method that selects the subset of k parameters with the highest partial derivative. Our methods are based on linear programming and differentiating these programs around a given value for the parameters. The experiments show the applicability of our approach on models with over a million states and thousands of parameters. Moreover, we embed the results within an iterative learning scheme that profits from having access to a dedicated sensitivity analysis.

We derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We do this for a broad range of uncertainty sets. Our results provide extensions to known results from the literature. We also consider hard quadratic constraints: those that are convex in uncertain matrix-valued parameters. For the robust counterpart of such constraints, we derive inner and outer tractable approximations. As an application, we show how to construct a natural uncertainty set based on a statistical confidence set around a sample mean vector and covariance matrix and use this to provide a tractable reformulation of the robust counterpart of an uncertain portfolio optimization problem. We also apply the results of this paper to norm approximation problems. Summary of Contribution: This paper develops new theoretical results and algorithms that extend the scope of a robust quadratic optimization problem. More specifically, we derive computationally tractable formulations of the robust counterparts of convex quadratic and conic quadratic constraints that are concave in matrix-valued uncertain parameters. We also consider hard quadratic constraints: those that are convex in uncertain matrix-valued parameters. For the robust counterpart of such constraints, we derive inner and outer tractable approximations.

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear programming problems. We show that disjoint bilinear programming problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, and techniques for two-stage robust optimization can be used to solve the resulting problems. To this end, a scheme based on a blending of Fourier-Motzkin elimination and linear decision rules is used. Moreover, we show that the approximation via linear decision rules for the two-stage robust optimization reformulation is equivalent to applying a reformulation-linearization technique to the original disjoint bilinear problem. We then extend our approach to solve general bilinear problems. Numerical experiments on bimatrix games and concave quadratic minimization problems show that the proposed method is superior to the off-the-shelf solvers SCIP and CPLEX.

Uncertain partially observable Markov decision processes (uPOMDPs) allow the probabilistic transition and observation functions of standard POMDPs to belong to a so-called uncertainty set. Such uncertainty, referred to as epistemic uncertainty, captures uncountable sets of probability distributions caused by, for instance, a lack of data available. We develop an algorithm to compute finite-memory policies for uPOMDPs that robustly satisfy specifications against any admissible distribution. In general, computing such policies is theoretically and practically intractable. We provide an efficient solution to this problem in four steps. (1) We state the underlying problem as a nonconvex optimization problem with infinitely many constraints. (2) A dedicated dualization scheme yields a dual problem that is still nonconvex but has finitely many constraints. (3) We linearize this dual problem and (4) solve the resulting finite linear program to obtain locally optimal solutions to the original problem. The resulting problem formulation is exponentially smaller than those resulting from existing methods. We demonstrate the applicability of our algorithm using large instances of an aircraft collision-avoidance scenario and a novel spacecraft motion planning case study.