• ### AC optimal power flow in the presence of renewable sources and uncertain loads(1702.02967)

May 30, 2019 math.OC
The increasing penetration of renewable energy resources, paired with the fact that load can vary significantly, introduce a high degree of uncertainty in the behavior of modern power grids. Given that classical dispatch solutions are "rigid," their performance in such an uncertain environment is in general far from optimal. For this reason, in this paper, we consider AC optimal power flow (AC-OPF) problems in the presence of uncertain loads and (uncertain) renewable energy generators. The goal of AC-OPF design is to guarantee that controllable generation is dispatched at minimum cost, while satisfying constraints on generation and transmission for "almost all" realizations of the uncertainty. We propose an approach based on a randomized technique recently developed, named "scenario with certificates", which allows to tackle the problem without assuming any a-priori dependence of the voltages in the network on the uncertain generators/loads. The proposed solution can exploit the usually available probabilistic description of the uncertainty and variability, and provides solutions with a-priori probabilistic guarantees on the risk of violating the constraints on generation and transmission.
• ### Non-Concave Network Utility Maximization in Connectionless Networks: A Fully Distributed Traffic Allocation Algorithm(1702.08539)

Feb. 27, 2017 math.OC
This paper considers the optimization-based traffic allocation problem among multiple end points in connectionless networks. The network utility function is modeled as a non-concave function, since it is the best description of the quality of service perceived by users with inelastic applications, such as video and audio streaming. However, the resulting non-convex optimization problem, is challenging and requires new analysis and solution techniques. To overcome these challenges, we first propose a hierarchy of problems whose optimal value converges to the optimal value of the non-convex optimization problem as the number of moments tends to infinity. From this hierarchy of problems, we obtain a convex relaxation of the original non-convex optimization problem by considering truncated moment sequences. For solving the convex relaxation, we propose a fully distributed iterative algorithm, which enables each node to adjust its date allocation/ rate adaption among any given set of next hops solely based on information from the neighboring nodes. Moreover, the proposed traffic allocation algorithm converges to the optimal value of the convex relaxation at a $O(1/K)$ rate, where $K$ is the iteration counter, with a bounded optimality. At the end of this paper, we perform numerical simulations to demonstrate the soundness of the developed algorithm.
• ### Convex Constrained Semialgebraic Volume Optimization: Application in Systems and Control(1701.08910)

Jan. 31, 2017 math.OC
In this paper, we generalize the chance optimization problems and introduce constrained volume optimization where enables us to obtain convex formulation for challenging problems in systems and control. We show that many different problems can be cast as a particular cases of this framework. In constrained volume optimization, we aim at maximizing the volume of a semialgebraic set under some semialgebraic constraints. Building on the theory of measures and moments, a sequence of semidefinite programs are provided, whose sequence of optimal values is shown to converge to the optimal value of the original problem. We show that different problems in the area of systems and control that are known to be nonconvex can be reformulated as special cases of this framework. Particularly, in this work, we address the problems of probabilistic control of uncertain systems as well as inner approximation of region of attraction and invariant sets of polynomial systems. Numerical examples are presented to illustrate the computational performance of the proposed approach.
• ### Convex Chance Constrained Model Predictive Control(1603.07413)

May 3, 2016 math.OC
We consider the Chance Constrained Model Predictive Control problem for polynomial systems subject to disturbances. In this problem, we aim at finding optimal control input for given disturbed dynamical system to minimize a given cost function subject to probabilistic constraints, over a finite horizon. The control laws provided have a predefined (low) risk of not reaching the desired target set. Building on the theory of measures and moments, a sequence of finite semidefinite programmings are provided, whose solution is shown to converge to the optimal solution of the original problem. Numerical examples are presented to illustrate the computational performance of the proposed approach.
• ### Simple Approximations of Semialgebraic Sets and their Applications to Control(1509.04200)

Sept. 14, 2015 math.OC, cs.SY
Many uncertainty sets encountered in control systems analysis and design can be expressed in terms of semialgebraic sets, that is as the intersection of sets described by means of polynomial inequalities. Important examples are for instance the solution set of linear matrix inequalities or the Schur/Hurwitz stability domains. These sets often have very complicated shapes (non-convex, and even non-connected), which renders very difficult their manipulation. It is therefore of considerable importance to find simple-enough approximations of these sets, able to capture their main characteristics while maintaining a low level of complexity. For these reasons, in the past years several convex approximations, based for instance on hyperrect-angles, polytopes, or ellipsoids have been proposed. In this work, we move a step further, and propose possibly non-convex approximations , based on a small volume polynomial superlevel set of a single positive polynomial of given degree. We show how these sets can be easily approximated by minimizing the L1 norm of the polynomial over the semialgebraic set, subject to positivity constraints. Intuitively, this corresponds to the trace minimization heuristic commonly encounter in minimum volume ellipsoid problems. From a computational viewpoint, we design a hierarchy of linear matrix inequality problems to generate these approximations, and we provide theoretically rigorous convergence results, in the sense that the hierarchy of outer approximations converges in volume (or, equivalently, almost everywhere and almost uniformly) to the original set. Two main applications of the proposed approach are considered. The first one aims at reconstruction/approximation of sets from a finite number of samples. In the second one, we show how the concept of polynomial superlevel set can be used to generate samples uniformly distributed on a given semialgebraic set. The efficiency of the proposed approach is demonstrated by different numerical examples.
• ### Randomized Approximations of the Image Set of Nonlinear Mappings with Applications to Filtering(1507.08032)

July 29, 2015 math.OC, cs.SY
The aim of this paper is twofold: In the first part, we leverage recent results on scenario design to develop randomized algorithmsfor approximating the image set of a nonlinear mapping, that is, a (possibly noisy) mapping of a set via a nonlinear function.We introduce minimum-volume approximations which have the characteristic of guaranteeing a low probability of violation, i.e.,we admit for a probability that some points in the image set are not contained in the approximating set,but this probability is kept below a pre-specified threshold.In the second part of the paper, this idea is then exploited to develop a new family of randomized prediction-corrector filters.These filters represent a natural extension and rapprochement of Gaussian and set-valued filters,and bear similarities with modern tools such as particle filters.
• ### Semidefinite Programming For Chance Constrained Optimization Over Semialgebraic Sets(1402.6382)

May 9, 2015 math.OC
In this paper, "chance optimization" problems are introduced, where one aims at maximizing the probability of a set defined by polynomial inequalities. These problems are, in general, nonconvex and computationally hard. With the objective of developing systematic numerical procedures to solve such problems, a sequence of convex relaxations based on the theory of measures and moments is provided, whose sequence of optimal values is shown to converge to the optimal value of the original problem. Indeed, we provide a sequence of semidefinite programs of increasing dimension which can arbitrarily approximate the solution of the original problem. To be able to efficiently solve the resulting large-scale semidefinite relaxations, a first-order augmented Lagrangian algorithm is implemented. Numerical examples are presented to illustrate the computational performance of the proposed approach.
• ### Reconstruction of Support of a Measure From Its Moments(1403.6399)

March 25, 2014 math.OC
In this paper, we address the problem of reconstruction of support of a measure from its moments. More precisely, given a finite subset of the moments of a measure, we develop a semidefinite program for approximating the support of measure using level sets of polynomials. To solve this problem, a sequence of convex relaxations is provided, whose optimal solution is shown to converge to the support of measure of interest. Moreover, the provided approach is modified to improve the results for uniform measures. Numerical examples are presented to illustrate the performance of the proposed approach.
• ### Uniform sample generation in semialgebraic sets(1403.4810)

March 19, 2014 math.OC
We propose efficient techniques for generating independent identically distributed uniform random samples inside semialgebraic sets. The proposed algorithm leverages recent results on the approximation of indicator functions by polynomials %\cite{DabHen:13} to develop acceptance/rejection based sample generation algorithms with guaranteed performance in terms of rejection rate (the number of samples that should be generated in order to obtain an accepted sample). Moreover, the {acceptance} rate is shown to be is asymptotically optimal, in the sense that it tends to one (all samples accepted) as the degree of the polynomial approximation increases. The performance of the proposed method is illustrated by a numerical example.