TY - JOUR A1 - Kuchlbauer, Martina A1 - Liers, Frauke A1 - Stingl, Michael T1 - Outer approximation for mixed-integer nonlinear robust optimization N2 - Currently, few approaches are available for mixed-integer nonlinear robust optimization. Those that do exist typically either require restrictive assumptions on the problem structure or do not guarantee robust protection. In this work, we develop an algorithm for convex mixed-integer nonlinear robust optimization problems where a key feature is that the method does not rely on a specific structure of the inner worst-case (adversarial) problem and allows the latter to be non-convex. A major challenge of such a general nonlinear setting is ensuring robust protection, as this calls for a global solution of the non-convex adversarial problem. Our method is able to achieve this up to a tolerance, by requiring worst-case evaluations only up to a certain precision. For example, the necessary assumptions can be met by approximating a non-convex adversarial via piecewise relaxations and solving the resulting problem up to any requested error as a mixed-integer linear problem. In our approach, we model a robust optimization problem as a nonsmooth mixed-integer nonlinear problem and tackle it by an outer approximation method that requires only inexact function values and subgradients. To deal with the arising nonlinear subproblems, we render an adaptive bundle method applicable to this setting and extend it to generate cutting planes, which are valid up to a known precision. Relying on its convergence to approximate critical points, we prove, as a consequence, finite convergence of the outer approximation algorithm. As an application, we study the gas transport problem under uncertainties in demand and physical parameters on realistic instances and provide computational results demonstrating the efficiency of our method. Y1 - 2021 ER - TY - INPR A1 - Aßmann, Denis A1 - Liers, Frauke A1 - Stingl, Michael A1 - Vera, Juan T1 - Deciding Robust Feasibility and Infeasibility Using a Set Containment Approach: An Application to Stationary Passive Gas Network Operations N2 - In this paper we study feasibility and infeasibility of nonlinear two-stage fully adjustable robust feasibility problems with an empty first stage. This is equivalent to deciding set containment of a projection of the feasible region and the uncertainty set. For answering this question, two very general approaches using methods from polynomial optimization are presented --- one for showing feasibility and one for showing infeasibility. The developed methods are approximated through sum of squares polynomials and solved using semidefinite programs. Deciding robust feasibility and infeasibility is important for gas network operations, which is a \nonconvex quadratic problem with absolute values functions. Concerning the gas network problem, different topologies are considered. It is shown that a tree structured network can be decided exactly using linear programming. Furthermore, a method is presented to reduce a tree network with one additional arc to a single cycle network. In this case, removing the absolute values and solving the problem can be decided with linearly many polynomial optimization problems. Lastly, the effectivity of the methods is tested on a variety of small cyclic networks. For instances where robust feasibility or infeasibility can be decided, level~2 or level~3 of the Lasserre relaxation hierarchy is typically sufficient. KW - robust optimization KW - polynomial optimization KW - stationary gas transport Y1 - 2017 ER - TY - INPR A1 - Kuchlbauer, Martina A1 - Liers, Frauke A1 - Stingl, Michael T1 - Adaptive bundle methods for nonlinear robust optimization N2 - Currently, there are few theoretical or practical approaches available for general nonlinear robust optimization. Moreover, the approaches that do exist impose restrictive assumptions on the problem structure. We present an adaptive bundle method for nonlinear and non-convex robust optimization problems with a suitable notion of inexactness in function values and subgradients. As the worst case evaluation requires a global solution to the adversarial problem, it is a main challenge in a general non-convex nonlinear setting. Moreover, computing elements of an epsilon-perturbation of the Clarke subdifferential in the l2-norm sense is in general prohibitive for this class of problems. In this article, instead of developing an entirely new bundle concept, we demonstrate how existing approaches, such as Noll's bundle method for non-convex minimization with inexact information (Computational and analytical mathematics 50: 555-592, 2013) can be modified to be able to cope with this situation. Extending the non-convex bundle concept to the case of robust optimization in this way, we prove convergence under two assumptions: Firstly, that the objective function is lower C1 and secondly, that approximately optimal solutions to the adversarial maximization problem are available. The proposed method is hence applicable to a rather general setting of nonlinear robust optimization problems. In particular, we do not rely on a specific structure of the adversary's constraints. The considered class of robust optimization problems covers the case that the worst-case adversary only needs to be evaluated up to a certain precision. One possibility to evaluate the worst case with the desired degree of precision is the use of techniques from mixed-integer linear programming (MIP). We investigate the procedure on some analytic examples. As applications, we study the gas transport problem under uncertainties in demand and in physical parameters that affect pressure losses in the pipes. Computational results for examples in large realistic gas network instances demonstrate the applicability as well as the efficiency of the method. Y1 - 2020 ER - TY - JOUR A1 - Adelhütte, Dennis A1 - Aßmann, Denis A1 - Gonzàlez Grandòn, Tatiana A1 - Gugat, Martin A1 - Heitsch, Holger A1 - Liers, Frauke A1 - Henrion, René A1 - Nitsche, Sabrina A1 - Schultz, Rüdiger A1 - Stingl, Michael A1 - Wintergerst, David T1 - Joint model of probabilistic/robust (probust) constraints applied to gas network optimization N2 - Optimization tasks under uncertain conditions abound in many real-life applications. Whereas solution approaches for probabilistic constraints are often developed in case the uncertainties can be assumed to follow a certain probability distribution, robust approaches are usually used in case solutions are sought that are feasible for all realizations of uncertainties within some pre-defined uncertainty set. As many applications contain different types of uncertainties that require robust as well as probabilistic treatments, we deal with a class of joint probabilistic/robust constraints as its appears in optimization problems under uncertainty. Focusing on complex uncertain gas network optimization problems, we show the relevance of this class of problems for the task of maximizing free booked capacities in an algebraic model for a stationary gas network. We furthermore present approaches for their solution. Finally, we study the problem of controlling a transient system that is governed by the wave equation. The task consists in determining controls such that a certain robustness measure remains below some given upper bound, with high probability. KW - robust optimization KW - chance constraints KW - optimal control KW - spheric-radial decomposition Y1 - 2017 U6 - https://doi.org/10.1007/s10013-020-00434-y ER - TY - INPR A1 - Aßmann, Denis A1 - Liers, Frauke A1 - Stingl, Michael T1 - Decomposable Robust Two-Stage Optimization: An Application to Gas Network Operations Under Uncertainty N2 - We study gas network problems with compressors and control valves under uncertainty that can be formulated as two-stage robust optimization problems. Uncertain data are present in the physical parameters of the pipes as well as in the overall demand. We show how to exploit the special decomposable structure of the problem in order to reformulate the two-stage robust problem as a standard single-stage optimization problem. Since this structure is present in similar problems on e.g., water or direct current electricity networks, we investigate the consequences of the decomposable structure in an abstract setting: The right-hand side of the single-stage problem can be precomputed by solving a series of optimization problems and multiple elements of the right-hand side can be combined into one optimization task. In order to apply our results to gas network problems, we extend piecewise relaxations and preprocessing techniques to incorporate uncertain input data. The practical feasibility and effectiveness of our approach is demonstrated with benchmarks on realistic gas network instances. We observe large speedups due to the described aggregation method together with the developed preprocessing strategies. Furthermore, we are able to solve even comparably large gas network instances quickly for the price of slightly more conservative solutions. KW - robust optimization KW - gas networks KW - relaxations Y1 - 2017 ER - TY - JOUR A1 - Kreimeier, Timo A1 - Kuchlbauer, Martina A1 - Liers, Frauke A1 - Stingl, Michael A1 - Walther, Andrea T1 - Towards the Solution of Robust Gas Network Optimization Problems Using the Constrained Active Signature Method N2 - This work studies robust gas network optimization under uncertainties in demand and in the physical parameters. The corresponding optimization problems are nonconvex in node pressures and flows along the pipes. They are thus very difficult to solve for realistic instance sizes. In recent approaches, an adaptive bundle method has been developed, where one solves the occurring adversarial problems via iteratively refined piecewise linear relaxations. These subproblems need to be solved always from scratch using mixed-integer linear programming (MIP). As alternative to the MIP solver, we employ here a nonsmooth optimization approach that allows a warm start strategy such that it can profit from the results obtained for coarser relaxations. We evaluate the approach for realistic gas network topologies and outline possibilities for future research. Y1 - 2022 ER - TY - INPR A1 - Pflug, Lukas A1 - Grieshammer, Max A1 - Uihlein, Andrian A1 - Stingl, Michael T1 - CSG: A stochastic gradient method for a wide class of optimization problems appearing in a machine learning or data-driven context N2 - In a recent article the so called continuous stochastic gradient method (CSG) for the efficient solution of a class of stochastic optimization problems was introduced. While the applicability of known stochastic gradient type methods is typically limited to so called expected risk functions, no such limitation exists for CSG. The key to this lies in the computation of design dependent integration weights, which allows for an optimal usage of available information leading to stronger convergence properties. However, due to the nature of the formula for these integration weights, the practical applicability was essentially limited to problems, in which stochasticity enters via a low-dimensional and suficiently simple probability distribution. In this paper the scope of the CSG method is significantly extended presenting new ways of calculating the integration weights. A full convergence analysis for this new variant of the CSG method is presented and its efficiency is demonstrated in comparison to more classical stochastic gradient methods by means of a number of problem classes, relevant in stochastic optimization and machine learning. KW - stochastic gradient method KW - nonlinear stochastic optimization KW - chance constraints KW - machine learning Y1 - 2021 ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael A1 - Uihlein, Andrian T1 - A Gradient-Based Method for Joint Chance-Constrained Optimization with Continuous Distributions N2 - The input parameters of an optimization problem are often affected by uncertainties. Chance constraints are a common way to model stochastic uncertainties in the constraints. Typically, algorithms for solving chance-constrained problems require convex functions or discrete probability distributions. In this work, we go one step further and allow non-convexities as well as continuous distributions. We propose a gradient-based approach to approximately solve joint chance-constrained models. We approximate the original problem by smoothing indicator functions. Then, the smoothed chance constraints are relaxed by penalizing their violation in the objective function. The approximation problem is solved with the Continuous Stochastic Gradient method that is an enhanced version of the stochastic gradient descent and has recently been introduced in the literature. We present a convergence theory for the smoothing and penalty approximations. Under very mild assumptions, our approach is applicable to a wide range of chance-constrained optimization problems. As an example, we illustrate its computational efficiency on difficult practical problems arising in the operation of gas networks. The numerical experiments demonstrate that the approach quickly finds nearly feasible solutions for joint chance-constrained problems with non-convex constraint functions and continuous distributions, even for realistically-sized instances. Y1 - ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael T1 - Robust chance-constrained optimization with discrete distributions N2 - Typically, probability distributions that generate uncertain parameters cannot be measured exactly in practice. As a remedy, distributional robustness determines optimized decisions that are protected in a robust fashion against all probability distributions in some appropriately chosen ambiguity set. In this work, we consider robust joint chance-constrained optimization problems and focus on discrete probability distributions. Many methods for this kind of problems study convex or even linear constraint functions. In contrast, we introduce a practically efficient scenario-based bundle method without convexity assumptions on the constraint functions. We start by deriving an approximation problem to the original robust chance-constrained version by using smoothing and penalization techniques that build on our former work on chance-constrained optimization. Our convergence results with respect to the smoothing approximation and well-known results for penalty approximations suggest replacing the original problem with the approximation problem for large smoothing and penalty parameters. Our scenario-based bundle method starts by solving the approximation problem with a bundle method, and then uses the bundle solution to decide which scenarios to include in a scenario-expanded formulation. This formulation is a standard nonlinear optimization problem. Our approach is guaranteed to find feasible solutions. Furthermore, in the numerical experiments on real-world gas transport problems with uncertain demands, we mostly find globally optimal solutions. Comparing these results to the classical robust reformulations for ambiguity sets consisting of confidence intervals and Wasserstein balls, we observe that the scenario-based bundle method typically outperforms solving the classical reformulation directly. Y1 - 2024 ER - TY - INPR A1 - Bernhard, Daniela A1 - Stingl, Michael A1 - Liers, Frauke T1 - Algorithms for robust chance-constrained optimization with mixture ambiguity N2 - Constructing ambiguity sets in distributionally robust optimization is difficult and currently receives increased attention. In this paper, we focus on mixture models with finitely many reference distributions. We present two different solution concepts for robust joint chance-constrained optimization problems with these ambiguity sets and non-convex constraint functions. Both concepts rely on solving an approximation problem that is based on well-known smoothing and penalization techniques. On the one side, we consider a classical bundle method together with an approach for finding good starting points. On the other side, we integrate the Continuous Stochastic Gradient method, a variant of the stochastic gradient descent that is able to exploit regularity in the data. On the example of gas networks we compare the two algorithmic concepts for different topologies and two types of mixture ambiguity sets with Gaussian reference distributions and polyhedral and ϕ-divergence based feasible sets for the mixing coefficients. The results show that both solution approaches are well-suited to solve this difficult problem class. Based on the numerical results we provide some general advices for choosing the more efficient algorithm depending on the main challenges of the considered optimization problem. We give an outlook for the applicability of the method in a wider context. Y1 - ER - TY - INPR A1 - Bernhard, Daniela A1 - Liers, Frauke A1 - Stingl, Michael T1 - Branch-and-cut for mixed-integer robust chance-constrained optimization with discrete distributions N2 - We study robust chance-constrained problems with mixed-integer design variables and ambiguity sets consisting of discrete probability distributions. Allowing general non-convex constraint functions, we develop a branch-and-cut framework using scenario-based cutting planes to generate lower bounds. The cutting planes are obtained by exploiting the classical big-M reformulation of the chance-constrained problem in the case of discrete distributions. Furthermore, we include the calculation of initial feasible solutions based on a bundle method applied to an approximation of the original problem into the branch-and-cut procedure. We conclude with a detailed discussion about the practical performance of the branch-and-cut framework with and without initial feasible solutions. In our experiments we focus on gas transport problems under uncertainty and provide a comparison of our method with solving the classical reformulation directly for various real-world sized instances. Y1 - ER - TY - JOUR A1 - Bernhard, Daniela A1 - Heitsch, Holger A1 - Henrion, René A1 - Liers, Frauke A1 - Stingl, Michael A1 - Uihlein, Andrian A1 - Zipf, Viktor T1 - Continuous stochastic gradient and spherical radial decomposition N2 - In this paper, a new method is presented for solving chance-constrained optimization problems. The method combines the well-established Spherical-Radial Decomposition approach with the Continuous Stochastic Gradient method. While the Continuous Stochastic Gradient method has been successfully applied to chance-constrained problems in the past, only the combination with the Spherical-Radial Decomposition allows to avoid smoothing of the integrand. In this chapter, we prove this fact for a relevant class of chance-constrained problems and apply the resulting method to the capacity maximization problem for gas networks. KW - chance constraints KW - continuous stochastic gradient KW - spheric-radial decomposition Y1 - ER -