-
作者：Bienstock, Daniel; Zambelli, Giacomo
作者单位：Columbia University; University of London; London School Economics & Political Science
-
作者：Chen, Rui; Luedtke, James
作者单位：University of Wisconsin System; University of Wisconsin Madison
摘要：We investigate sample average approximation (SAA) for two-stage stochastic programs without relatively complete recourse, i.e., for problems in which there are first-stage feasible solutions that are not guaranteed to have a feasible recourse action. As a feasibility measure of the SAA solution, we consider the recourse likelihood, which is the probability that the solution has a feasible recourse action. For epsilon is an element of (0, 1), we demonstrate that the probability that a SAA solut...
-
作者：Bauschke, Heinz H.; Ouyang, Hui; Wang, Xianfu
作者单位：University of British Columbia
摘要：The notion of best approximation mapping (BAM) with respect to a closed affine subspace in finite-dimensional spaces was introduced by Behling, Bello Cruz and Santos to show the linear convergence of the block-wise circumcentered-reflection method. The best approximation mapping possesses two critical properties of the circumcenter mapping for linear convergence. Because the iteration sequence of a BAM linearly converges, the BAM is interesting in its own right. In this paper, we naturally ext...
-
作者：Gannot, Oran
摘要：We study robustness properties of some iterative gradient-based methods for strongly convex functions, as well as for the larger class of functions with sector-bounded gradients, under a relative error model. Proofs of the corresponding convergence rates are based on frequency-domain criteria for the stability of nonlinear systems. Applications are given to inexact versions of gradient descent and the Triple Momentum Method. To further emphasize the usefulness of frequency-domain methods, we d...
-
作者：Guo, Shaoyan; Xu, Huifu
作者单位：Dalian University of Technology; Chinese University of Hong Kong
摘要：Choice of a risk measure for quantifying risk of an investment portfolio depends on the decision maker's risk preference. In this paper, we consider the case when such a preference can be described by a law invariant coherent risk measure but the choice of a specific risk measure is ambiguous. We propose a robust spectral risk approach to address such ambiguity. Differing from Wang and Xu (SIAM J Optim 30(4):3198-3229, 2020), the new robust model allows one to elicit the decision maker's risk ...
-
作者：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...
