-
作者：Ramirez-Pico, Cristian; Moreno, Eduardo
作者单位：Universidad Adolfo Ibanez
摘要：We present a method to solve two-stage stochastic linear programming problems with fixed recourse when the uncertainty space can have either discrete or continuous distributions. Given a partition of the uncertainty space, the method is addressed to solve a discrete problem with one scenario for each element of the partition (subregions of the uncertainty space). Fixing first-stage variables, we formulate a second-stage subproblem for each element, and exploiting information from the dual of t...
-
作者：Gonzalez Grandon, T.; Henrion, R.; Perez-Aros, P.
作者单位：Humboldt University of Berlin; Leibniz Association; Weierstrass Institute for Applied Analysis & Stochastics; Universidad de O'Higgins
摘要：The paper investigates analytical properties of dynamic probabilistic constraints (chance constraints). The underlying random distribution is supposed to be continuous. In the first part, a general multistage model with decision rules depending on past observations of the random process is analyzed. Basic properties like (weak sequential) (semi-) continuity of the probability function or existence of solutions are studied. It turns out that the results differ significantly according to whether...
-
作者：Pashkovich, Kanstantsin; Poirrier, Laurent; Pulyassary, Haripriya
作者单位：University of Waterloo
摘要：Recently, Bodur, Del Pia, Dey, Molinaro and Pokutta studied the concept of aggregation cuts for packing and covering integer programs. The aggregation closure is the intersection of all aggregation cuts. Bodur et al. studied the strength of this closure, but left open the question of whether the aggregation closure is polyhedral. In this paper, we answer this question in the positive, i.e., we show that the aggregation closure is polyhedral. Finally, we demonstrate that a generalization, the k...
-
作者：Morell, Sarah; Skutella, Martin
作者单位：Technical University of Berlin
摘要：In a digraph with a source and several destination nodes with associated demands, an unsplittable flow routes each demand along a single path from the common source to its destination. Given some flow x that is not necessarily unsplittable but satisfies all demands, it is a natural question to ask for an unsplittable flow y that does not deviate from x by too much, i.e., ya <= xa for all arcs a. Twenty years ago, in a landmark paper, Dinitz et al. (Combinatorica 19:17-41, 1999) proved that the...
-
作者：Straszak, Damian; Vishnoi, Nisheeth K.
作者单位：Yale University
摘要：We present a connection between two dynamical systems arising in entirely different contexts: the Iteratively Reweighted Least Squares (IRLS) algorithm used in compressed sensing and sparse recovery to find a minimum l(1)-norm solution in an affine space, and the dynamics of a slime mold (Physarum polycephalum) that finds the shortest path in a maze. We elucidate this connection by presenting a new dynamical system - Meta-Algorithm - and showing that the IRLS algorithms and the slime mold dyna...
-
作者：Bourdin, Loic; Dhar, Gaurav
作者单位：Universite de Limoges; Centre National de la Recherche Scientifique (CNRS)
摘要：In the present paper we derive a Pontryagin maximum principle for general nonlinear optimal sampled-data control problems in the presence of running inequality state constraints. We obtain, in particular, a nonpositive averaged Hamiltonian gradient condition associated with an adjoint vector being a function of bounded variation. As a well known challenge, theoretical and numerical difficulties may arise due to the possible pathological behavior of the adjoint vector (jumps and singular part l...
-
作者：Xie, Weijun; Ahmed, Shabbir; Jiang, Ruiwei
作者单位：Virginia Polytechnic Institute & State University; University System of Georgia; Georgia Institute of Technology; University of Michigan System; University of Michigan
摘要：A distributionally robust joint chance constraint involves a set of uncertain linear inequalities which can be violated up to a given probability threshold epsilon, over a given family of probability distributions of the uncertain parameters. A conservative approximation of a joint chance constraint, often referred to as a Bonferroni approximation, uses the union bound to approximate the joint chance constraint by a system of single chance constraints, one for each original uncertain constrain...
-
作者：Dey, Santanu S.; Luedtke, James R.; Sahinidis, Nikolaos, V
作者单位：University System of Georgia; Georgia Institute of Technology; University of Wisconsin System; University of Wisconsin Madison; University System of Georgia; Georgia Institute of Technology
-
作者：Luo, Hao; Chen, Long
作者单位：Sichuan University; University of California System; University of California Irvine
摘要：Convergence analysis of accelerated first-order methods for convex optimization problems are developed from the point of view of ordinary differential equation solvers. A new dynamical system, called Nesterov accelerated gradient (NAG) flow, is derived from the connection between acceleration mechanism and A-stability of ODE solvers, and the exponential decay of a tailored Lyapunov function along with the solution trajectory is proved. Numerical discretizations of NAG flow are then considered ...
-
作者：Lu, Haihao
作者单位：University of Chicago
摘要：There has been a long history of using ordinary differential equations (ODEs) to understand the dynamics of discrete-time algorithms (DTAs). Surprisingly, there are still two fundamental and unanswered questions: (i) it is unclear how to obtain a suitable ODE from a given DTA, and (ii) it is unclear the connection between the convergence of a DTA and its corresponding ODEs. In this paper, we propose a new machinery-an O(s(r))-resolution ODE framework-for analyzing the behavior of a generic DTA...
