Benders Decomposition for multi-stage stochastic mixed complementarity problems – Applied to a global natural gas market model

This paper presents and implements a Benders Decomposition type of algorithm for large-scale, stochastic multi-period mixed complementarity problems. The algorithm is applied to various multi-stage natural gas market models accounting for market power exertion by traders. Due to the non-optimization nature of the natural gas market problem, a straightforward implementation of the traditional Benders Decomposition is not possible. The master and subproblems can be derived from the underlying optimization problems and transformed into complementarity problems. However, to complete the master problems optimality cuts are added using the variational inequality-based method developed in Gabriel and Fuller (2010). In this manner, an alternative derivation of Benders Decomposition for Stochastic MCP is presented, thereby making this approach more applicable to a broader audience. The algorithm can successfully solve problems with up to 256 scenarios and more than 600 thousand variables, and problems with over 117 thousand variables with more than two thousand first-stage capacity expansion variables. The algorithm is efficient for solving two-stage problems. The computational time reduction for other stochastic problems is considerable and would be even larger if a parallel implementation of the algorithm were used. The paper concludes with a discussion of infrastructure expansion results, illustrating the impact of hedging on investment timing and optimal capacity sizes.     

变分不等式与互补问题、双层规划与平衡约束数学规划问题的若干进展

考虑有限维变分不等式与互补问题、双层规划以及均衡约束的数学规划问题. 在简单介绍这些问题之后,重点介绍近年来这些领域中发展迅速的几个研究方向,包括对称锥互补问题的理论与算法、变分不等式的投影收缩算法、随机变分不等式与随机互补问题的模型与方法、双层规划以及均衡约束数学规划问题的新方法. 最后提出几个进一步研究的方向.     

On the ERM formulation and a stochastic approximation algorithm of the stochastic-R_0 EVLCP

In this paper, a class of stochastic extended vertical linear complementarity problems is studied as an extension of the stochastic linear complementarity problem. The expected residual minimization (ERM) formulation of this stochastic extended vertical complementarity problem is proposed based on an NCP function. We study the corresponding properties of the ERM problem, such as existence of solutions, coercive property and differentiability. Finally, we propose a descent stochastic approximation method for solving this problem. A comprehensive convergence analysis is given. A number of test examples are constructed and the numerical results are presented.     

Uncertainty in energy-economic modelling of the electrical power sector

The purpose of the present paper is to investigate what significance, if any, inclusion of uncertainties has for the conclusions of the modelling and analysis, i.e., whether the policy recommendations implicit in the results of the analysis depend on the inclusion or not of uncertainties. We do this within the context of a model of the Northern European electricity sector. The paper considers uncertainties about future states of nature. More specifically, we consider the inflow of water into a hydropower production system, where the states of nature are represented by a “dry”, a “normal” and a “wet” year. The problems may be formulated as non-linear optimisation models where the objective function basically consists of the expected value of the sum of consumers', producers', and authorities' surplus. The models take into account that there are losses in the transmission and distribution of electricity, and that the consumers pay an energy tax on their use of electricity. The consumers are divided into two groups, households and industry. Also, complementarity formulations are used, as these are shown to be more adequate for certain aspects, in particular where risk aversion within a liberalised market context is modelled. For each of eight Northern European countries, the basic results of the models are the installation of new production capacities, the production on old and new production capacities, the electricity prices, and the interchange between the countries. The investment in new production capacity is represented by a single value for each country, while the productions differ in that they depend on natural phenomena, which we refer to as the state of nature and represent by stochastic variables. It was found that in this context it was relatively easy to include stochastic elements in the model. Second, complementarity formulations are preferable to optimisation based modelling for some problem types. Third, results of the stochastic model have natural interpretations, also compared to one or several versions of a deterministic model. And fourth, we have seen that the quantitative results, and hence the implied policy recommendations, may differ significantly from those of deterministic models. We therefore conclude that increased attention should be given to the inclusion of stochastic elements into the modelling of energy systems. This revised version was published online in June 2006 with corrections to the Cover Date.     

Stochastic Nonlinear Complementarity Problems: Stochastic Programming Reformulation and Penalty-Based Approximation Method

We consider a class of stochastic nonlinear complementarity problems. We first reformulate the stochastic complementarity problem as a stochastic programming model. Based on the reformulation, we then propose a penalty-based sample average approximation method and prove its convergence. Finally, we report on some numerical test results to show the efficiency of our method.     

Stochastic second-order-cone complementarity problems: expected residual minimization formulation and its applications

This paper considers a class of stochastic second-order-cone complementarity problems (SSOCCP), which are generalizations of the noticeable stochastic complementarity problems and can be regarded as the Karush–Kuhn–Tucker conditions of some stochastic second-order-cone programming problems. Due to the existence of random variables, the SSOCCP may not have a common solution for almost every realization . In this paper, motivated by the works on stochastic complementarity problems, we present a deterministic formulation called the expected residual minimization formulation for SSOCCP. We present an approximation method based on the Monte Carlo approximation techniques and investigate some properties related to existence of solutions of the ERM formulation. Furthermore, we experiment some practical applications, which include a stochastic natural gas transmission problem and a stochastic optimal power flow problem in radial network.     

Solving stochastic mathematical programs with equilibrium constraints via approximation and smoothing implicit programming with penalization

In this paper, we consider the stochastic mathematical programs with linear complementarity constraints, which include two kinds of models called here-and-now and lower-level wait-and-see problems. We present a combined smoothing implicit programming and penalty method for the problems with a finite sample space. Then, we suggest a quasi-Monte Carlo approximation method for solving a problem with continuous random variables. A comprehensive convergence theory is included as well. We further report numerical results with the so-called picnic vender decision problem.     

On the existence of solutions to stochastic quasi-variational inequality and complementarity problems

Variational inequality problems allow for capturing an expansive class of problems, including convex optimization problems, convex Nash games and economic equilibrium problems, amongst others. Yet in most practical settings, such problems are complicated by uncertainty, motivating the examination of a stochastic generalization of the variational inequality problem and its extensions in which the components of the mapping contain expectations. When the associated sets are unbounded, ascertaining existence requires having access to analytical forms of the expectations. Naturally, in practical settings, such expressions are often difficult to derive, severely limiting the applicability of such an approach. Consequently, our goal lies in developing techniques that obviate the need for integration and our emphasis lies in developing tractable and verifiable sufficiency conditions for claiming existence. We begin by recapping almost-sure sufficiency conditions for stochastic variational inequality problems with single-valued maps provided in our prior work Ravat and Shanbhag (in: Proceedings of the American Control Conference (ACC), 2010), Ravat and Shanbhag (SIAM J Optim 21: 1168–1199, 2011) and provide extensions to multi-valued mappings. Next, we extend these statements to quasi-variational regimes where maps can be either single or set-valued. Finally, we refine the obtained results to accommodate stochastic complementarity problems where the maps are either general or co-coercive. The applicability of our results is demonstrated on practically occuring instances of stochastic quasi-variational inequality problems and stochastic complementarity problems, arising as nonsmooth generalized Nash-Cournot games and power markets, respectively.     

Expected Value and Sample Average Approximation Method for Solving Stochastic Second-Order Cone Complementarity Problems

In this paper, we consider the stochastic second-order cone complementarity problems (SSOCCP). We first formulate the SSOCCP contained expectation as an optimization problem using the so-called second-order cone complementarity function. We then use sample average approximation method and smoothing technique to obtain the approximation problems for solving this reformulation. In theory, we show that any accumulation point of the global optimal solutions or stationary points of the approximation problems are global optimal solution or stationary point of the original problem under suitable conditions. Finally, some numerical examples are given to explain that the proposed methods are feasible.     

Monotone generalized variational inequalities and generalized complementarity problems

Some existence results for generalized variational inequalities and generalized complementarity problems involving quasimonotone and pseudomonotone set-valued mappings in reflexive Banach spaces are proved. In particular, some known results for nonlinear variational inequalities and complementarity problems in finite-dimensional and infinite-dimensional Hilbert spaces are generalized to quasimonotone and pseudomonotone set-valued mappings and reflexive Banach spaces. Application to a class of generalized nonlinear complementarity problems studied as mathematical models for mechanical problems is given.The research of the first author was supported by the National Natural Science Foundation of P. R. China and by the Ethel Raybould Fellowship, University of Queensland, St. Lucia, Brisbane, Australia.     

An Oligopolistic Investment Model of the Finnish Electricity Market

The investment problem faced by producers in deregulated electricity markets contains high uncertainties about the future. It can also be seen as a game, as only a small number of large players act in the market. A dynamic stochastic oligopoly model to describe the production and investment in such a situation is developed and applied to the Finnish electricity market. The demand growth rate is modeled as a stochastic variable. The strategies of the firms consist of investments and production levels for base and peak load periods. The firms have nuclear, hydro and thermal capacities, but are only allowed to invest in new thermal capacity. Using a so-called sample-path adapted open-loop information structure, the model contributes to the understanding of the dynamics of production, investment and market power in a medium time horizon. The solution method uses recent developments in variational inequality and mixed complementarity problem formulations.     

Solution Sets of Quadratic Complementarity Problems

In this paper, we study quadratic complementarity problems, which form a subclass of nonlinear complementarity problems with the nonlinear functions being quadratic polynomial mappings. Quadratic complementarity problems serve as an important bridge linking linear complementarity problems and nonlinear complementarity problems. Various properties on the solution set for a quadratic complementarity problem, including existence, compactness and uniqueness, are studied. Several results are established from assumptions given in terms of the comprising matrices of the underlying tensor, henceforth easily checkable. Examples are given to demonstrate that the results improve or generalize the corresponding quadratic complementarity problem counterparts of the well-known nonlinear complementarity problem theory and broaden the boundary knowledge of nonlinear complementarity problems as well.     

Column sufficient tensors and tensor complementarity problems

Stimulated by the study of sufficient matrices in linear complementarity problems, we study column sufficient tensors and tensor complementarity problems. Column sufficient tensors constitute a wide range of tensors that include positive semi-definite tensors as special cases. The inheritance property and invariant property of column sufficient tensors are presented. Then, various spectral properties of symmetric column sufficient tensors are given. It is proved that all H-eigenvalues of an even-order symmetric column sufficient tensor are nonnegative, and all its Z-eigenvalues are nonnegative even in the odd order case. After that, a new subclass of column sufficient tensors and the handicap of tensors are defined. We prove that a tensor belongs to the subclass if and only if its handicap is a finite number. Moreover, several optimization models that are equivalent with the handicap of tensors are presented. Finally, as an application of column sufficient tensors, several results on tensor complementarity problems are established.     

Feasible Semismooth Newton Method for a Class of Stochastic Linear Complementarity Problems

We consider a class of stochastic linear complementarity problems (SLCPs) with finitely many realizations. In this paper we reformulate this class of SLCPs as a constrained minimization (CM) problem. Then, we present a feasible semismooth Newton method to solve this CM problem. Preliminary numerical results show that this CM reformulation may yield a solution with high safety for SLCPs.     

Computational schemes for large-scale problems in extended linear-quadratic programming

Numerical approaches are developed for solving large-scale problems of extended linear-quadratic programming that exhibit Lagrangian separability in both primal and dual variables simultaneously. Such problems are kin to large-scale linear complementarity models as derived from applications of variational inequalities, and they arise from general models in multistage stochastic programming and discrete-time optimal control. Because their objective functions are merely piecewise linear-quadratic, due to the presence of penalty terms, they do not fit a conventional quadratic programming framework. They have potentially advantageous features, however, which so far have not been exploited in solution procedures. These features are laid out and analyzed for their computational potential. In particular, a new class of algorithms, called finite-envelope methods, is described that does take advantage of the structure. Such methods reduce the solution of a high-dimensional extended linear-quadratic program to that of a sequence of low-dimensional ordinary quadratic programs.This work was supported in part by grants AFOSR 87-0821 and AFOSR 89-0081 from the Air Force Office of Scientific Research.     

A FEASIBLE SEMISMOOTH GAUSS-NEWTON METHOD FOR SOLVING A CLASS OF SLCPS

In this paper, we consider a class of the stochastic linear complementarity problems (SLCPs) with finitely many elements. A feasible semismooth damped Gauss-Newton algorithm for the SLCP is proposed. The global and local quadratic convergence of the proposed algorithm are obtained under suitable conditions. Some numerical results are reported in this paper, which confirm the good theoretical properties of the proposed algorithm.     

随机二阶锥二次规划逆问题的SAA方法

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。     

随机二阶锥二次规划逆问题的SAA方法

本文讨论一类随机的二阶锥二次规划逆问题, 该模型是一个含有二阶锥互补约束的随机二次规划模型, 对解释部分实际问题有着一定的优势。为了求解该模型, 本文引入了随机抽样技术和互补约束光滑化近似技术, 得到问题的近似子问题。本文证明, 只要子问题的解是存在且收敛的, 则该极限以概率一是原问题的C-稳定点; 若严格互补条件和二阶必要性条件成立, 则该极限以概率1是原问题的M-稳定点。一个简单的数值实验验证了该算法具有一定的可行性。     

An Interior Point Algorithm for Mixed Complementarity Nonlinear Problems

Nonlinear complementarity and mixed complementarity problems arise in mathematical models describing several applications in Engineering, Economics and different branches of physics. Previously, robust and efficient feasible directions interior point algorithm was presented for nonlinear complementarity problems. In this paper, it is extended to mixed nonlinear complementarity problems. At each iteration, the algorithm finds a feasible direction with respect to the region defined by the inequality conditions, which is also monotonic descent direction for the potential function. Then, an approximate line search along this direction is performed in order to define the next iteration. Global and asymptotic convergence for the algorithm is investigated. The proposed algorithm is tested on several benchmark problems. The results are in good agreement with the asymptotic analysis. Finally, the algorithm is applied to the elastic–plastic torsion problem encountered in the field of Solid Mechanics.     

An MPCC approach for stochastic Stackelberg–Nash–Cournot equilibrium

In this article, we investigate a Stochastic Stackelberg–Nash–Cournot Equilibrium problem by reformulating it as a Mathematical Program with Complementarity Constraints (MPCC). The complementarity constraints are further reformulated as a system of nonsmooth equations. We characterize the followers’ Nash–Cournot equilibria by studying the implicit solution of a system of equations. We outline numerical methods for the solution of a stochastic Stackelberg–Nash–Cournot Equilibrium problem with finite distribution of market demand scenarios and propose a discretization approach based on implicit numerical integration to deal with stochastic Stackelberg–Nash–Cournot Equilibrium problem with continuous distribution of demand scenarios. Finally, we discuss the two-leader Stochastic Stackelberg–Nash–Cournot Equilibrium problem.