Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Distributed Algorithm for Multi-scale Multi-stage Stochastic Programs with Application to Electricity Capacity Expansion
101
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This paper applies the N-block PCPM algorithm to solve multi-scale multi-stage stochastic programs, with the application to electricity capacity expansion models. Numerical results show that the proposed simplified N-block PCPM algorithm, along with the hybrid decomposition method, exhibits much better scalability for solving the resulting deterministic, large-scale block-separable optimization problem when compared with the ADMM algorithm and the PHA algorithm. The superiority of the algorithms scalability is attributed to the two key features of the algorithm design: first, the proposed hybrid scenario-node-realization decomposition method with extended nonanticipativity constraints can decompose the original problem under various uncertainties of different temporal scales; second, when applying the N-block PCPM algorithm to solve the resulting deterministic, large-scale N-block convex optimization problem, the technique of orthogonal projection we exploit greatly simplifies the iteration steps and reduce the communication overhead among all computing units, which also contributes to the efficiency of the algorithm.
rate research
Read More
In this paper, we consider multi-stage stochastic optimization problems with convex objectives and conic constraints at each stage. We present a new stochastic first-order method, namely the dynamic stochastic approximation (DSA) algorithm, for solving these types of stochastic optimization problems. We show that DSA can achieve an optimal ${cal O}(1/epsilon^4)$ rate of convergence in terms of the total number of required scenarios when applied to a three-stage stochastic optimization problem. We further show that this rate of convergence can be improved to ${cal O}(1/epsilon^2)$ when the objective function is strongly convex. We also discuss variants of DSA for solving more general multi-stage stochastic optimization problems with the number of stages $T > 3$. The developed DSA algorithms only need to go through the scenario tree once in order to compute an $epsilon$-solution of the multi-stage stochastic optimization problem. As a result, the memory required by DSA only grows linearly with respect to the number of stages. To the best of our knowledge, this is the first time that stochastic approximation type methods are generalized for multi-stage stochastic optimization with $T ge 3$.
This paper studies flexible multi-facility capacity expansion with risk aversion. In this setting, the decision maker can periodically expand the capacity of facilities given observations of uncertain demand. We model this situation as a multi-stage stochastic programming problem. We express risk aversion in this problem through conditional value-at-risk (CVaR), and we formulate a mean-CVaR objective. To solve the multi-stage problem, we optimize over decision rules. In particular, we approximate the full policy space of the problem with a tractable family of if-then policies. Subsequently, a decomposition algorithm is proposed to optimize the decision rule. This algorithm decomposes the model over scenarios and it updates solutions via the subgradients of the recourse function. We demonstrate that this algorithm can quickly converge to high-performance policies. To illustrate the practical effectiveness of this method, a case study on the waste-to-energy system in Singapore is presented. These simulation results show that by adjusting the weight factor of the objective function, decision makers are able to trade off between a risk-averse policy that has a higher expected cost but a lower value-at-risk, and a risk-neutral policy that has a lower expected cost but a higher value-at-risk risk.
This work develops effective distributed strategies for the solution of constrained multi-agent stochastic optimization problems with coupled parameters across the agents. In this formulation, each agent is influenced by only a subset of the entries of a global parameter vector or model, and is subject to convex constraints that are only known locally. Problems of this type arise in several applications, most notably in disease propagation models, minimum-cost flow problems, distributed control formulations, and distributed power system monitoring. This work focuses on stochastic settings, where a stochastic risk function is associated with each agent and the objective is to seek the minimizer of the aggregate sum of all risks subject to a set of constraints. Agents are not aware of the statistical distribution of the data and, therefore, can only rely on stochastic approximations in their learning strategies. We derive an effective distributed learning strategy that is able to track drifts in the underlying parameter model. A detailed performance and stability analysis is carried out showing that the resulting coupled diffusion strategy converges at a linear rate to an $O(mu)-$neighborhood of the true penalized optimizer.
We present a method to solve two-stage stochastic 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 (sub-regions of the uncertainty space). Fixing first stage variables, we formulate a second stage subproblem for each element, and exploiting information from the dual of these problems, we provide conditions that the partition must satisfy to obtain the optimal solution. These conditions provide guidance on how to refine the partition, converging iteratively to the optimal solution. Results from computational experiments show how the method automatically refines the partition of the uncertainty space in the regions of interest for the problem. Our algorithm is a generalization of the adaptive partition-based method presented by Song & Luedtke (2015) for discrete distributions, extending its applicability to more general cases.
We study distributed stochastic gradient (D-SG) method and its accelerated variant (D-ASG) for solving decentralized strongly convex stochastic optimization problems where the objective function is distributed over several computational units, lying on a fixed but arbitrary connected communication graph, subject to local communication constraints where noisy estimates of the gradients are available. We develop a framework which allows to choose the stepsize and the momentum parameters of these algorithms in a way to optimize performance by systematically trading off the bias, variance, robustness to gradient noise and dependence to network effects. When gradients do not contain noise, we also prove that distributed accelerated methods can emph{achieve acceleration}, requiring $mathcal{O}(kappa log(1/varepsilon))$ gradient evaluations and $mathcal{O}(kappa log(1/varepsilon))$ communications to converge to the same fixed point with the non-accelerated variant where $kappa$ is the condition number and $varepsilon$ is the target accuracy. To our knowledge, this is the first acceleration result where the iteration complexity scales with the square root of the condition number in the context of emph{primal} distributed inexact first-order methods. For quadratic functions, we also provide finer performance bounds that are tight with respect to bias and variance terms. Finally, we study a multistage version of D-ASG with parameters carefully varied over stages to ensure exact $mathcal{O}(-k/sqrt{kappa})$ linear decay in the bias term as well as optimal $mathcal{O}(sigma^2/k)$ in the variance term. We illustrate through numerical experiments that our approach results in practical algorithms that are robust to gradient noise and that can outperform existing methods.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
