Publications

For an electric power mix subject to uncertainty, the stochastic unit-commitment problem finds short-term optimal generation schedules that satisfy several system-wide constraints. In regulated electricity markets, this very practical and important problem is used by the system operator to decide when each unit is to be started or stopped, and to define how to generate enough energy to meet the load. For hydro-dominated systems, an accurate description of the hydro-production function involves non-convex relations. This feature, combined with the fine time discretization needed to represent uncertainty of renewable generation, yields a large-scale mathematical optimization model that is nonlinear and has mixed-integer variables. To make the problem tractable, a novel solution strategy, based on multi-horizon scenario trees, is proposed. The approach deals in a first level with the integer decision variables representing whether units are on or off. Once units are committed, the expected operational cost is minimized by solving a continuous second-level problem, which is separable by scenarios. The coordination between the two decision levels is done by means of a bundle-like variant of Benders decomposition that proves very efficient for the considered setting. To assess the quality of the optimal commitment on out-of-sample scenarios, a new simulation technique, based on certain sustainable pseudo-distance is proposed. For the numerical experiments, a mix of hydro, thermal, and wind power plants extracted from the Brazilian power system is considered. The results confirm the interest of the approach, particularly regarding a more efficient management of hydro-plants, because non-convex operational regions are considered by the model.

When minimizing a nonsmooth convex function bundle methods are well known by their robustness and reliability. While such features are related to global convergence properties of the algorithm, speed of convergence is a different matter, as fast rates cannot be expected if the objective function lacks smoothness. In the typical bundle dichotomy that splits iterates between null and serious steps, the latter subsequence converges with R-linear speed. Moving from the first-order method realm to the world of superlinear speed is possible when realizing that nonsmoothness often appears in a structured manner. This is the basis of the VU-decomposition approach presented in this chapter. Thanks to this decomposition, it is possible to make a Newton-like move in certain U-subspace, where all the function “smoothness” concentrates at least locally. On its orthogonal complement, the “sharp” V-subspace, an intermediate iterate is defined such that the overall convergence is driven by the U-step. As a result, the serious-step subsequence converges with superlinear speed. By focusing on the proximal variants of bundle methods, this chapter introduces gradually the VU-theory and the ingredients needed to build superlinearly convergent algorithms in nonsmooth optimization. For functions whose proximal points are easy to compute, as in machine learning, an implementable quasi-Newton VU-algorithm is given. The bundle machinery is incorporated for functions whose proximal points are not readily available. In this case, superlinear speed can be achieved by solving two quadratic programming problems per iteration.

To describe the joint dynamics of prices of crude oil and refined products we extend two-factor models to a multidimensional setting. The new model captures directly the general correlation structure between the different commodities in the form of certain covariance matrix. Since the associated state-space formulation makes use of such correlations, the feasible set of the resulting estimation problem includes the cone of positive semidefinite matrices. Tractability is ensured by means of an interior point method, specially tailored for nonlinear semidefinite programming problems. For different sets of historical prices of crude oil, heating oil, and gasoline, the empirical out-of-sample forecasts obtained with the approach proposed in this work systematically provide an excellent fit to data.

For problems when decisions are taken prior to observing the realization of underlying random events, probabilistic constraints are an important modeling tool if reliability is a concern. A key concept to numerically dealing with probabilistic constraints is that of p-efficient points. By adopting a dual point of view, we develop a solution framework that includes and extends various existing formulations. The unifying approach is built on the basis of a recent generation of bundle methods called with on-demand accuracy, characterized by its versatility and flexibility. Numerical results for several difficult problems confirm the interest of the approach.

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.

The last few years have seen the advent of a new generation of bundle methods, capable to handle inexact oracles, polluted by “noise”. Proving convergence of a bundle method is never simple and coping with inexact oracles substantially increases the technicalities. Besides, several variants exist to deal with noise, each one needing an ad hoc proof to show convergence. We state a synthetic convergence theory, in which we highlight the main arguments and specify which assumption is used to establish each intermediate result. The framework is comprehensive and generalizes in various ways a number of algorithms proposed in the literature. Based on the ingredients of our synthetic theory, we consider various bundle methods adapted to oracles for which high accuracy is possible, yet it is preferable not to make exact calculations often, because they are too time consuming.

For non-smooth convex optimization, we consider level bundle methods built using an oracle that computes values for the objective function and a subgradient at any given feasible point. For the problems of interest, the exact oracle information is computable, but difficult to obtain. In order to save computational effort the oracle can provide estimations with an accuracy that depends on two additional parameters, informed to the oracle together with the evaluation point. The first of such parameters is a descent target, while the second one is a bound for inexactness. If the oracle can reach the target with its function estimation, then the corresponding error is bounded by the second parameter. Otherwise, if the oracle detects that the target cannot be met, the function and subgradient estimations can be rough and have an unknown accuracy. For some selected iterates the considered methods drive the inexactness parameter to zero, thus ensuring that an exact solution to the optimization problem is asymptotically found. The approach is comprehensive and covers known exact and inexact level methods as well as some novel variants that can handle inaccuracy in an adaptive manner. In particular, when the feasible set is also compact, some of the new on-demand accuracy methods have the same rate of convergence of exact level variants known in the literature. A numerical benchmark on a battery of two-stage stochastic linear programs assesses the interest of the approach, substantially faster than the L-shaped method, without any accuracy loss.

Joint chance constrained problems give rise to many algorithmic challenges. Even in the convex case, i.e., when an appropriate transformation of the probabilistic constraint is a convex function, its cutting-plane linearization is just an approximation, produced by an oracle providing subgradient and function values that can only be evaluated inexactly. As a result, the cutting-plane model may lie above the true constraint. For dealing with such upper inexact oracles, and still solving the problem up to certain precision, a special numerical algorithm must be put in place. We introduce a family of constrained bundle methods, based on the so-called improvement functions, that is shown to be convergent and encompasses many previous approaches as well as new algorithms. Depending on the oracle accuracy, we analyze to what extent the considered methods solve the joint chance constrained program. The approach is assessed on real-life energy problems, arising when dealing with stochastic hydroreservoir management.

Liquefied Natural Gas contracts offer cancelation options that make their pricing difficult, especially if many gas storages need to be taken into account. We develop a valuation mechanism from the buyer’s perspective, a large gas company whose main interest in these contracts is to provide to clients a reliable supply of gas. The approach combines valuation with hedging, taking into account that price-risk is driven by international markets, while volume-risk depends on local weather and is stage-wise dependent. The methodology is based on setting risk-averse stochastic mixed 0-1 programs, for different contract configurations. These difficult problems are solved with light computational effort, thanks to a robust rolling-horizon approach. The resulting pricing mechanism not only shows how a specific set of contracts will impact the company business, but also provides the manager with alternative contract configurations to counter-propose to the contract seller.

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.

Electricity and natural gas transmission and distribution networks are subject to regulation in price, service quality, and emission limits. The interaction of competing agents in an energy market subject to various regulatory interventions is usually modeled through equilibrium problems that ensure profit maximization for all the agents. These types of models can be written in different manners, for example, by means of mixed complementarity problems, variational inequalities, and game-theoretical formulations. More generally, we consider energy markets both in deterministic and stochastic settings and explore theoretical relations between the various formulations found in the literature and in practice. Our analysis shows that the profit-maximization complementarity model is equivalent to a game with agents minimizing costs if the setting is deterministic or risk neutral. On the other hand, when the agents exhibit risk aversion which is natural in this type of markets, the equivalence no longer holds. This gives rise to an interesting economical interpretation. As a complement to our theoretical study, and for the European natural gas market with deterministic data, we present some numerical results showing the impact of market power on equilibrium prices.

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.

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.

We consider an interstage dependent stochastic process whose components follow an autoregressive model with time varying order. At a given time, we give some recursive formulæ linking future values of the process with past values and noises. We then consider multistage stochastic linear programs with uncertain sets depending affinely on such processes. At each stage, dealing with uncertainty using probabilistic constraints, the recursive relations can be used to obtain explicit expressions for the feasible set.

Modern electricity systems provide a plethora of challenging issues in optimization. The increasing penetration of low carbon renewable sources of energy introduces uncertainty in problems traditionally modeled in a deterministic setting. The liberalization of the electricity sector brought the need of designing sound markets, ensuring capacity investments while properly reflecting strategic interactions. In all these problems, hedging risk, possibly in a dynamic manner, is also a concern. The fact of representing uncertainty and/or competition of different companies in a multi-settlement power market considerably increases the number of variables and constraints. For this reason, usually a trade-off needs to be found between modeling and numerical tractability: the more details are brought into the model, the harder becomes the optimization problem. For structured optimization and generalized equilibrium problems, we explore some variants of solution methods based on Lagrangian relaxation and on Benders decomposition. Throughout we keep as a leading thread the actual practical value of such techniques in terms of their efficiency to solve energy related problems.

We consider the optimal management of a hydro-thermal power system in the mid and long terms. From the optimization point of view, this amounts to a large-scale multistage stochastic linear program, often solved by combining sampling with decomposition algorithms, like stochastic dual dynamic programming. Such methodologies, however, may entail prohibitive computational time, especially when applied to a risk-averse formulation of the problem. We propose instead a risk-averse rolling-horizon policy that is nonanticipative, feasible, and time consistent. The policy is obtained by solving a sequence of risk-averse problems with deterministic constraints for the current time step and future chance and CVaR constraints. The considered hydro-thermal model takes into account losses resulting from run-of-river plants efficiencies as well as uncertain demand and streamflows. Constraints aim at satisfying demand while keeping reservoir levels above minzones almost surely. We show that if the problem uncertainty is represented by a periodic autoregressive stochastic process with lag one, then the probabilistic constraints can be computed explicitly. As a result, each one of the aforementioned risk-averse problems is a medium-size linear program, easy to solve. For a real-life power system we compare our approach with three alternative policies. Namely, a robust nonrolling-horizon policy and two risk-neutral policies obtained by stochastic dual dynamic programming, implemented in nonrolling- and rolling-horizon modes, respectively. Our numerical assessment confirms the superiority of the risk-averse rolling-horizon policy that yields comparable average indicators, but with reduced volatility and with substantially less computational effort.

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.

Stochastic programming problems arise in many practical situations. In general, the deterministic equivalents of these problems can be very large and may not be solvable directly by general-purpose optimization approaches. For the particular case of two-stage stochastic programs, we consider decomposition approaches akin to a regularized L-shaped method that can handle inexactness in the subproblem solution. From a nonsmooth optimization perspective, these variants amount to applying a proximal bundle method to an oracle that gives inaccurate values for the objective function and a subgradient. Rather than forcing early termination of the subproblem optimization to define inexact oracles, we select a small subset of scenarios for which the subproblem solution is exact, and we replace the information for the remaining scenarios by a fast procedure that does not involve solving an optimization problem. The inaccurate oracle information creates inexact cuts in the master program, which are well handled by the recently introduced inexact bundle methods. The proposed approaches are validated by encouraging numerical results on several two-stage stochastic linear programs found in the literature.