Globally and superlinearly convergent algorithms for two-stage stochastic variational inequalities and their applications

Abstract

The two-stage stochastic variational inequality (SVI) is a powerful modeling paradigm for many real applications in the fields of finance, engineering and economics, which characterizes the first-order optimality condition of the two-stage stochastic program and models some equilibrium problems under uncertain environments. The research for two-stage SVI has received much attention during past decades. Numerically, we solve the sample discretization problem of the two-stage SVI, which is a large-scale problem due to the large sample size. Many existing deterministic VI solvers fail to handle such large-scale problems. The well-known progressive hedging algorithm (PHA) proposed by Rockafellar and Sun is a competitive algorithm for the large-scale monotone two-stage SVI. However, only a linear convergence rate is established for the monotone affine SVI. So far, to the best of our knowledge, there are no superlin­early convergent algorithms being developed for the two-stage SVI. This thesis aims to develop globally and superlinearly convergent algorithms for the two-stage SVI. Firstly, a projection semismooth Newton algorithm (PSNA) is proposed, which is a hybrid algorithm that combines the projection algorithm and the classic semismooth Newton algorithm. At each step of PSNA, the second stage problem is split into a number of small problems and solved in parallel for a fixed first stage decision iterate. The projection algorithm and the semismooth Newton algorithm are used to find a new first stage decision iterate. The global convergence and the superlinear convergence rate are established under suitable assumptions. Numerical results for monotone problems show that PSNA outperforms PHA. Moreover, PSNA is efficient to solve some nonmonotone problems which PHA fails to solve. Secondly, a regularized PSNA (rPSNA) is developed to solve a two-stage stochastic linear complementarity problem (SLCP) that describes the global crude oil market share under the impact of the COVID-19 pandemic. The existence, uniqueness and robustness of the solution to the model are analyzed. As the regularized parameter goes to zero, the sequence generated by rPSNA converges to the unique solution of the single-stage SVI reformulation of the original problem. Numerical results for randomly generated examples illustrate that rPSNA performs better than PHA in terms of the number of iterations as well as CPU time. In addition, the two-stage SLCP model is applied to recover and predict the crude oil market share under the influence of COVID-19 with related parameters determined by oil data from reliable sources. This problem is solved by rPSNA efficiently, and the solution obtained is suitable to explain and rationalize the behavior of main oil-producing countries. Lastly, rPSNA is further applied to solve two classes of nonmonotone traffic assignment problems. One is the stochastic user equilibrium problem in the form of the two-stage SVI. The second is the stochastic dynamic user equilibrium problem, which is formulated as a differential linear stochastic complementarity system (DLSCS) with the discretization problem being a special two-stage SVI. Numerically, rPSNA is more efficient for solving these problems compared with PHA.