Gradient-based optimisation of the conditional-value-at-risk using the multi-level Monte Carlo method

In this work, we tackle the problem of minimising the Conditional-Value-at-Risk (CVaR) of output quantities of complex differential models with random input data, using gradient-based approaches in combination with the Multi-Level Monte Carlo (MLMC) method. In particular, we consider the framework of multi-level Monte Carlo for parametric expectations and propose modifications of the MLMC estimator, error estimation procedure, and adaptive MLMC parameter selection to ensure the estimation of the CVaR and sensitivities for a given design with a prescribed accuracy. We then propose combining the MLMC framework with an alternating inexact minimisation-gradient descent algorithm, for which we prove exponential convergence in the optimisation iterations under the assumptions of strong convexity and Lipschitz continuity of the gradient of the objective function. We demonstrate the performance of our approach on two numerical examples of practical relevance, which evidence the same optimal asymptotic cost-tolerance behaviour as standard MLMC methods for fixed design computations of output expectations.

Trust-region methods based on radial basis functions with application to biomedical imaging

Rodrigue Oeuvray

We have developed a new derivative-free algorithm based on Radial Basis Functions (RBFs). Derivative-free optimization is an active field of research and several algorithms have been proposed recently. Problems of this nature in the industrial setting are quite frequent. The reason is that in a number of applications the optimization process contains simulation packages which are treated as black boxes. The development of our own algorithm was originally motivated by an application in biomedical imaging: the medical image registration problem. The particular characteristics of this problem have incited us to develop a new optimization algorithm based on trust-region methods. However it has been designed to be generic and to be applied to a wide range of problems. The main originality of our approach is the use of RBFs to build the models. In particular we have adapted the existing theory based on quadratic models to our own models and developed new procedures especially designed for models based on RBFs. We have tested our algorithm called BOOSTERS against state-of-the-art methods (UOBYQA, NEWUOA, DFO). On the medical image registration problem, BOOSTERS appears to be the method of choice. The tests on problems from the CUTEr collection show that BOOSTERS is comparable to, but not better than other methods on small problems (size 2-20). It is performing very well for medium size problems (20-80). Moreover, it is able to solve problems of dimension 200, which is considered very large in derivative-free optimization. We have also developed a new class of algorithms combining the robustness of derivative-free algorithms with the faster rate of convergence characterizing Newtonlike-methods. In fact, they define a new class of algorithms lying between derivative-free optimization and quasi-Newton methods. These algorithms are built on the skeleton of our derivative-free algorithm but they can incorporate the gradient when it is available. They can be interpreted as a way of doping derivative-free algorithms with derivatives. If the derivatives are available at each iteration, then our method can be seen as an alternative to quasi-Newton methods. At the opposite, if the derivatives are never evaluated, then the algorithm is totally similar to BOOSTERS. It is a very interesting alternative to existing methods for problems whose objective function is expensive to evaluate and when the derivatives are not available. In this situation, the gradient can be approximated by finite differences and its costs corresponds to n additional function evaluations assuming that Rn is the domain of definition of the objective function. We have compared our method with CFSQP and BTRA, two gradient-based algorithms, and the results show that our doped method performs best. We have also a theoretical analysis of the medical image registration problem based on maximization of mutual information. Most of the current research in this field is concentrated on registration based on nonlinear image transformation. However, little attention has been paid to the theoretical properties of the optimization problem. In our analysis, we focus on the continuity and the differentiability of the objective function. We show in particular that performing a registration without extension of the reference image may lead to discontinuities in the objective function. But we demonstrate that, under some mild assumptions, the function is differentiable almost everywhere. Our analysis is important from an optimization point of view and conditions the choice of a solver. The usual practice is to use generic optimization packages without worrying about the differentiability of the objective function. But the use of gradient-based methods when the objective function is not differentiable may result in poor performance or even in absence of convergence. One of our objectives with this analysis is also that practitioners become aware of these problems and to propose them new algorithms having a potential interest for their applications.

EPFL2005

Optimal control of geodesics in Riemannian manifolds

Roland Rozsnyo

The aim of this dissertation is to solve numerically the following problem, denoted by P : given a Riemannian manifold and two points a and b belonging to that manifold, find a tangent vector T at a, such that expa(T) = b, assuming that T exists. This problem is set under an optimal control formulation, which requires the definition of an objective function and a space of control, the choice of a method for the calculation of the descent direction of that function in the space of control and the use of an optimization algorithm to find its minimum, which corresponds to the solution of the original problem by construction. Several techniques are necessary to be put together, coming from the fields of geometry, numerical analysis and optimization. The first part will concern a recalling of the mathematical context in which this formulation takes place. The general principles of optimal control will also be given. In the second part, we will present an intrinsic formulation of the optimal control problem associated to P, based on Jacobi fields, which will play the role of the so called adjoint state. This derivation leads to necessary optimality conditions. We will illustrate explicitly that formulation by treating the specific case of Riemannian manifolds with constant sectional curvature. Then, we will derive the optimal control problem in coordinates, not only to check the intrinsic formulation but also to reveal how it is hidden behind the expressions in coordinates. Their use reveals some quantities whose interpretation may be given this way. Moreover, we will show that more possibilities exist to chose the cost function and the control space in coordinates. In a second step, an alternative approach will consider the Hamiltonian formulation of geodesics. This is an incursion into symplectic geometry. We will then reformulate the Riemannian optimal control problem in its Hamiltonian version. In the third part, the numerical methods used for solving P will be presented. The discretization imposes the definition of new discrete optimal control problems. The technique shows that the discrete adjoint state equation strongly depends on the numerical scheme used to solve the direct problem. We will give a collection of numerical computations in the specific case of parametric piece of surfaces, where the surface can be defined by one or several Bézier patches, each one corresponding to a chart, which is representative of a Riemannian manifold. We will compare the different numerical approaches. The last but one part will be devoted to the interesting application of wooden roof building, where the structure is made of wooden boards, with geodesic trajectories on the designed piece of surface. The Geos (Geodesic solver) software has been developed for that purpose. After having introduced some specific numerical methods used in the code, we present the Geos application interface (AI) developed as a tool for the conception of such a roof. We then show an existing wooden structure built according to that mean. Finally, we will summarize the results of our research and discuss future possible prospects.

EPFL2007

Analysis of stochastic gradient methods for PDE-constrained optimal Control Problems with uncertain parameters

Sebastian Krumscheid, Matthieu Claude Martin, Fabio Nobile

We consider the numerical approximation of a risk-averse optimal control problem for an elliptic partial differential equation (PDE) with random coefficients. Specifically, the control function is a deterministic, distributed forcing term that minimizes the expected mean squared distance between the state (i.e. solution to the PDE) and a target function, subject to a regularization for well posedness. For the numerical treatment of this risk-averse optimal control problem, we consider a Finite Element discretization of the underlying PDEs, a Monte Carlo sampling method, and gradient type iterations to obtain the approximate optimal control. We provide full error and complexity analysis of the proposed numerical schemes. In particular we compare the complexity of a fixed Monte Carlo gradient method, in which the Finite Element discretization and Monte Carlo sample are chosen initially and kept fixed over the gradient iterations, with a Stochastic Gradient method in which the expectation in the computation of the steepest descent direction is approximated by independent Monte Carlo estimators with small sample sizes and possibly varying Finite Element mesh sizes across iterations. We show in particular that the second strategy results in an improved computational complexity. The theoretical error estimates and complexity results are confirmed by our numerical experiments.