Search

We consider the optimal management of hydropower generated by a cascade of three interconnected reservoirs owned by different agents. In this setting, water availability at the downhill reservoirs depends on decisions taken by the agents upstream. This creates an opportunity for the hydroplant at the top to withhold water and take advantage of situations with higher selling prices, which makes the overall decisions of the agents deviate from what can be considered best for the cascade as whole. In order to mitigate the market power of the hydroplant uphill, we propose a mechanism to enforce some collaborative behavior among the agents. This is achieved by agents transferring upstream fractions of their profit in exchange for water released from the top. The corresponding mathematical models are trilevel deterministic and trilevel stochastic linear programming problems, with uncertainty in prices and streamflows (exogenous inflows). For the stochastic variants, analyzed both in two- and multi-stage formulations, we propose new solution methods, extending to the trilevel nested setting the well-known L-Shaped and Stochastic Dual Dynamic Programming methods. A successful implementation of the later depends on certain floating cuts, that represent symbolically Benders-like linearizations. Convergence properties are discussed for some of the procedures. Numerical experiments confirm the interest of the approach, because with the proposed mechanism the top owner as well as the downhill hydroplants earn more money than when acting in an individualistic manner. [ABSTRACT FROM AUTHOR]

Determining reliable price indicators in the long-term is fundamental for optimal management problems in the energy sector. In hydro-dominated systems, the random components of rain and snow that arrive to the reservoirs have a significant impact on the interaction of the low-cost technology of hydro-generation with more expensive ones. The sample employed to discretize uncertainty changes certain Lagrange multipliers in the corresponding optimization problem that represent a marginal cost for the power system and, therefore, changes the price signals. The effect of sampling in yielding different price indicators can be observed even when running twice the same code on the same computer. Although such values are statistically correct, the variability on the dual output puts at stake economic analyses based on marginal prices. To address this issue, we propose a dual regularization that yields sample-insensitive indicators for a two-stage stochastic model. It is shown that the approach provides the minimal-norm multiplier of the energy management problem in the limit, when certain parameter is driven to zero. The new method is implemented in a rolling horizon mode for a real-life case, representing the Northern European energy system over a period of one year with hourly discretization. When compared to SDDP, an established method in the area, the approach yields a significant reduction in the variance of the optimal Lagrange multipliers used to compute the prices, with respect to different samples. [ABSTRACT FROM AUTHOR]

We present an approach to regularize and approximate solution mappings of parametric convex optimization problems that combines interior penalty (log-barrier) solutions with Tikhonov regularization. Because the regularized mappings are single-valued and smooth under reasonable conditions, they can be used to build a computationally practical smoothing for the associated optimal value function. The value function in question, while resulting from parameterized convex problems, need not be convex. One motivating application of interest is two-stage (possibly nonconvex) stochastic programming. We show that our approach, being computationally implementable, provides locally bounded upper bounds for the subdifferential of the value function of qualified convex problems. As a by-product of our development, we also recover that in the given setting the value function is locally Lipschitz continuous. Numerical experiments are presented for two-stage convex stochastic programming problems, comparing the approach with the bundle method for nonsmooth optimization. [ABSTRACT FROM AUTHOR]

We consider a certain class of hierarchical decision problems that can be viewed as single-leader multi-follower games, and be represented by a virtual market coordinator trying to set a price system for traded goods, according to some criterion that balances supply and demand. The objective function of the market coordinator involves the decisions of many agents, which are taken independently by solving convex optimization problems that depend on the price configuration and on realizations of future states of the economy. One traditional way of solving this problem is via a mixed complementarity formulation. However, this approach can become impractical when the numbers of agents and/or scenarios become large. This work concerns agent-wise and scenario-wise decomposition algorithms to solve the equilibrium problems in question, assuming that the solutions of the agents' problems are unique, which is natural in many applications (when solutions are not unique, the approximating problems are still well-defined, but the convergence properties of the algorithm are not established). The algorithm is based on a previous work of the authors, where a suitable regularization of solution mappings of fully parameterized convex problems is developed. Here, we show one specific strategy to manage the regularization parameter, extend some theoretical results to the current setting, and prove that the smooth approximations of the market coordinator's problem converge epigraphically to the original problem. Numerical experiments and some comparisons with the complementarity solver PATH are shown for the two-stage stochastic Walrasian equilibrium problem. [ABSTRACT FROM AUTHOR]

We develop new variants of Benders decomposition methods for variational inequality problems. The construction is done by applying the general class of Dantzig–Wolfe decomposition of Luna et al. (Math Program 143(1–2):177–209, 2014) to an appropriately defined dual of the given variational inequality, and then passing back to the primal space. As compared to previous decomposition techniques of the Benders kind for variational inequalities, the following improvements are obtained. Instead of rather specific single-valued monotone mappings, the framework includes a rather broad class of multi-valued maximally monotone ones, and single-valued nonmonotone. Subproblems' solvability is guaranteed instead of assumed, and approximations of the subproblems' mapping are allowed (which may lead, in particular, to further decomposition of subproblems, which may otherwise be not possible). In addition, with a certain suitably chosen approximation, variational inequality subproblems become simple bound-constrained optimization problems, thus easier to solve. [ABSTRACT FROM AUTHOR]

In many mathematical optimization applications, dual variables are an important output of the solving process, due to their role as price signals. When dual solutions are not unique, different solvers or different computers, even different runs in the same computer if the problem is stochastic, often end up with different optimal multipliers. From the perspective of a decision maker, this variability makes the price signals less reliable and, hence, less useful. We address this issue for a particular family of linear and quadratic programs by proposing a solution procedure that, among all possible optimal multipliers, systematically yields the one with the smallest norm. The approach, based on penalization techniques of nonlinear programming, amounts to a regularization in the dual of the original problem. As the penalty parameter tends to zero, convergence of the primal sequence and, more critically, of the dual is shown under natural assumptions. The methodology is illustrated on a battery of two-stage stochastic linear programs. [ABSTRACT FROM AUTHOR]

We consider two models for stochastic equilibrium: one based on the variational equilibrium of a generalized Nash game, and the other on the mixed complementarity formulation. Each agent in the market solves a single-stage risk-averse optimization problem with both here-and-now (investment) variables and (production) wait-and-see variables. A shared constraint couples almost surely the wait-and-see decisions of all the agents. An important characteristic of our approach is that the agents hedge risk in the objective functions (on costs or profits) of their optimization problems, which has a clear economic interpretation. This feature is obviously desirable, but in the risk-averse case it leads to variational inequalities with set-valued operators-a class of problems for which no established software is currently available. To overcome this difficulty, we define a sequence of approximating differentiable variational inequalities based on smoothing the nonsmooth risk measure in the agents' problems, such as average or conditional value-at-risk. The smoothed variational inequalities can be tackled by the PATH solver, for example. The approximation scheme is shown to converge, including the case when smoothed problems are solved approximately. An interesting by-product of our proposal is that the smoothing approach allows us to show existence of an equilibrium for the original problem. To assess the proposed technique, numerical results are presented. The first set of experiments is on randomly generated equilibrium problems, for which we compare the proposed methodology with the standard smooth reformulation of average value-at-risk minimization (using additional variables to rewrite the associated max-function). The second set of experiments deals with a part of the real-life European gas network, for which Dantzig-Wolfe decomposition can be combined with the smoothing approach. [ABSTRACT FROM AUTHOR]

We consider a class of decomposition methods for variational inequalities, which is related to the classical Dantzig-Wolfe decomposition of linear programs. Our approach is rather general, in that it can be used with certain types of set-valued or nonmonotone operators, as well as with various kinds of approximations in the subproblems of the functions and derivatives in the single-valued case. Also, subproblems may be solved approximately. Convergence is established under reasonable assumptions. We also report numerical experiments for computing variational equilibria of the game-theoretic models of electricity markets. Our numerical results illustrate that the decomposition approach allows to solve large-scale problem instances otherwise intractable if the widely used PATH solver is applied directly, without decomposition. [ABSTRACT FROM AUTHOR]

We consider minimization of nonsmooth functions which can be represented as the composition of a positively homogeneous convex function and a smooth mapping. This is a sufficiently rich class that includes max-functions, largest eigenvalue functions, and norm-1 regularized functions. The bundle method uses an oracle that is able to compute separately the function and subgradient information for the convex function, and the function and derivatives for the smooth mapping. With this information, it is possible to solve approximately certain proximal linearized subproblems in which the smooth mapping is replaced by its Taylor-series linearization around the current serious step. Our numerical results show the good performance of the Composite Bundle method for a large class of problems. [ABSTRACT FROM AUTHOR]

We consider risk-averse formulations of stochastic linear programs having a structure that is common in real-life applications. Specifically, the optimization problem corresponds to controlling over a certain horizon a system whose dynamics is given by a transition equation depending affinely on an interstage dependent stochastic process. We put in place a rolling-horizon time consistent policy. For each time step, a risk-averse problem with constraints that are deterministic for the current time step and uncertain for future times is solved. To each uncertain constraint corresponds both a chance and a Conditional Value-at-Risk constraint. We show that the resulting risk-averse problems are numerically tractable, being at worst conic quadratic programs. For the particular case in which uncertainty appears only on the right-hand side of the constraints, such risk-averse problems are linear programs. We show how to write dynamic programming equations for these problems and define robust recourse functions that can be approximated recursively by cutting planes. The methodology is assessed and favourably compared with Stochastic Dual Dynamic Programming on a real size water-resource planning problem. [ABSTRACT FROM AUTHOR]

We discuss the energy generation expansion planning with environmental constraints, formulated as a nonsmooth convex constrained optimization problem. To solve such problems, methods suitable for constrained nonsmooth optimization need to be employed. We describe a recently developed approach, which applies the usual unconstrained bundle techniques to a dynamically changing 'improvement function'. Numerical results for the generation expansion planning are reported. [ABSTRACT FROM AUTHOR]

We consider the problem of optimally determining an investment portfolio for an energy company owning a network of gas pipelines, and in charge of purchasing, selling and distributing gas. We propose a two stage stochastic investment model which hedges risk by means of Conditional Value at Risk constraints. The model, solved by a decomposition method, is assessed on a real-life case, of a Brazilian integrated company that operates on the oil, gas, and energy sectors. [ABSTRACT FROM AUTHOR]