Confidence regions of two-stage stochastic linear complementarity problems

Two-stage stochastic linear complementarity problems (TSLCP) model a large class of equilibrium problems subject to data uncertainty, and are closely related to two-stage stochastic optimization problems. The sample average approximation (SAA) method is one of the basic approaches for solving TSLCP and the consistency of the SAA solutions has been well studied. This paper focuses on building confidence regions of the solution to TSLCP when SAA is implemented. We first establish the error-bound condition of TSLCP and then build the asymptotic and nonasymptotic confidence regions of the solutions to TSLCP by error-bound approach, which is to combine the error-bound condition with central limit theory, empirical likelihood theory, and large deviation theory.     

Sampling average approximation method for a class of stochastic Nash equilibrium problems

We consider a class of stochastic Nash equilibrium problems (SNEP). Under some mild conditions, we reformulate the SNEP as a stochastic mixed complementarity problem (SMCP). We apply the well-known sample average approximation (SAA) method to solve the SMCP. We further introduce a semismooth Newton method to solve the SAA problems. The comprehensive convergence analysis is given as well. In addition, we demonstrate the proposed approach on a stochastic Nash equilibrium model in the wholesale gas–oil markets.     

A non-monotone inexact regularized smoothing Newton method for solving nonlinear complementarity problems

In the paper [S.P. Rui and C.X. Xu, A smoothing inexact Newton method for nonlinear complementarity problems, J. Comput. Appl. Math. 233 (2010), pp. 2332–2338], the authors proposed an inexact smoothing Newton method for nonlinear complementarity problems (NCP) with the assumption that F is a uniform P function. In this paper, we present a non-monotone inexact regularized smoothing Newton method for solving the NCP which is based on Fischer–Burmeister smoothing function. We show that the proposed algorithm is globally convergent and has a locally superlinear convergence rate under the weaker condition that F is a P ₀ function and the solution of NCP is non-empty and bounded. Numerical results are also reported for the test problems, which show the effectiveness of the proposed algorithm.     

非线性互补问题的光滑化拟牛顿算法

为求解非线性互补问题,给出了一种新的基于光滑对称扰动Fischer-Burmeister函数的光滑化拟牛顿算法。该算法利用了无导数线搜索。数值实验表明,算法是有效的。     

应用非单调线搜索求解一类互补问题

考虑一类含非Lipschtizian连续函数的非线性互补问题。引入plus函数的一类广义光滑函数,讨论其性质。应用所引入函数将互补问题重构为一系列光滑方程组,提出一个具有非单调线搜索的Newton算法求解重构的方程组以得到原问题的解。在很弱的条件下,该算法具有全局收敛性和局部二次收敛性。利用该算法求解一自由边界问题,其数值结果显示该算法是有效的。     

Accelerating iterative algorithms for symmetric linear complementarity problems

We propose a method for accelerating iterative algorithms for solving symmetric linear complementarity problems. The method consists in performing a one-dimensional optimization in the direction generated by a splitting method even for non-descent directions. We give strong convergence proofs and present numerical experiments that justify using this acceleration.     

A semidefinite method for tensor complementarity problems

In this paper, we study how to compute all real solutions of the tensor complimentary problem, if there are finite many ones. We formulate the problem as a sequence of polynomial optimization problems. The solutions can be computed sequentially. Each of them can be obtained by solving Lasserre's hierarchy of semidefinite relaxations. A semidefinite algorithm is proposed and its convergence properties are discussed. Some numerical experiments are also presented.     

A predictor-corrector smoothing Newton method for solving the mixed complementarity problem with a P 0-function

The mixed complementarity problem (denoted by MCP(F)) can be reformulated as the solution of a nonsmooth system of equations. In the paper, based on a perturbed mid function, we contract a new smoothing function. The existence and continuity of a smooth path for solving the mixed complementarity problem with a P ₀ function are discussed. Then we presented a predictor-corrector smoothing Newton algorithm to solve the MCP with a P ₀-function. The global convergence of the proposed algorithm is verified under mild conditions. And by using the smooth and semismooth technique, the local superlinear convergence of the method is proved under some suitable assumptions.     

A new SQP approach for nonlinear complementarity problems

Sequential quadratic programming (SQP) methods have been extensively studied to handle nonlinear programming problems. In this paper, a new SQP approach is employed to tackle nonlinear complementarity problems (NCPs). At each iterate, NCP conditions are divided into two parts. The inequalities and equations in NCP conditions, which are violated in the current iterate, are treated as the objective function, and the others act as constraints, which avoids finding a feasible initial point and feasible iterate points. NCP conditions are consequently transformed into a feasible nonlinear programming subproblem at each step. New SQP techniques are therefore successful in handling NCPs.     

The general two-sweep modulus-based matrix splitting iteration method for solving linear complementarity problems

In this paper, we present a general two-sweep modulus-based iteration method to solve a class of linear complementarity problems. Convergence analysis shows that the general two-sweep modulus-based matrix splitting iteration method will converge to the exact solution of linear complementarity problem under appropriate conditions. Numerical experiments further show that the proposed methods are superior to the existing methods in actual implementation.     

非线性互补问题的粒子群算法

针对非线性互补问题求解的困难,利用粒子群算法并结合极大熵函数法给出了该类问题的一种新的有效算法。该算法首先利用极大熵函数将非线性互补问题转化为一个无约束最优化问题,将该函数作为粒子群算法的适应值函数;然后应用粒子群算法来优化该问题。数值结果表明,该算法收敛快、数值稳定性较好,是求解非线性互补问题的一种有效算法。     

New identification method for Hammerstein models based on approximate least absolute deviation

Disorder and peak noises or large disturbances can deteriorate the identification effects of Hammerstein non-linear models when using the least-square (LS) method. The least absolute deviation technique can be used to resolve this problem; however, its absolute value cannot meet the need of differentiability required by most algorithms. To improve robustness and resolve the non-differentiable problem, an approximate least absolute deviation (ALAD) objective function is established by introducing a deterministic function that exhibits the characteristics of absolute value under certain situations. A new identification method for Hammerstein models based on ALAD is thus developed in this paper. The basic idea of this method is to apply the stochastic approximation theory in the process of deriving the recursive equations. After identifying the parameter matrix of the Hammerstein model via the new algorithm, the product terms in the matrix are separated by calculating the average values. Finally, algorithm convergence is proven by applying the ordinary differential equation method. The proposed algorithm has a better robustness as compared to other LS methods, particularly when abnormal points exist in the measured data. Furthermore, the proposed algorithm is easier to apply and converges faster. The simulation results demonstrate the efficacy of the proposed algorithm.     

The effect of few historical data on the performance of sample average approximation method for operating room scheduling

We model the scheduling problem of a single operating room for outpatient surgery, with uncertain case durations and an objective function comprising waiting time, idle time, and overtime costs. This stochastic scheduling problem has been studied in diverse forms. One of the most common approaches used is the sample average approximation (SAA). Our contribution is to study the use of SAA to solve this problem under few historical data using families of log t distributions with varying degrees of freedom. We analyze the results of the SAA method in terms of optimality convergence, the effect of the number of scenarios, and average computational time. Given the case sequence, computational results demonstrate that SAA with an adequate number of scenarios performs close to the exact method. For example, we find that the optimality gap, in units of proportional weighted time, is relatively small when 500 scenarios are used: 99% of the instances have an optimality gap of less than 2.6 7% (1.74%, 1.23%) when there are 3 (9, many) historical samples. Increasing the number of SAA scenarios improves performance, but is not critical when the case sequence is given. However, choosing the number of SAA scenarios becomes critical when the same method is used to choose among sequencing heuristics when there are few historical data. For example, when there are only three (nine, many) historical samples, 99% of the instances have less than 25.38% (13.15%, 6.87%) penalty in using SAA with 500 scenarios to choose the best sequencing heuristic.     

A feasible directions algorithm for nonlinear complementarity problems and applications in mechanics

Complementarity problems are involved in mathematical models of several applications in engineering, economy and different branches of physics. We mention contact problems and dynamics of multiple bodies systems in solid mechanics. In this paper we present a new feasible direction algorithm for nonlinear complementarity problems. This one begins at an interior point, strictly satisfying the inequality conditions, and generates a sequence of interior points that converges to a solution of the problem. At each iteration, a feasible direction is obtained and a line search performed, looking for a new interior point with a lower value of an appropriate potential function. We prove global convergence of the present algorithm and present a theoretical study about the asymptotic convergence. Results obtained with several numerical test problems, and also application in mechanics, are described and compared with other well known techniques. All the examples were solved very efficiently with the present algorithm, employing always the same set of parameters.     

A multiplicative multisplitting method for solving the linear complementarity problem

The convergence of the multiplicative multisplitting-type method for solving the linear complementarity problem with an H-matrix is discussed using classical and new results from the theory of splitting. This directly results in a sufficient condition for guaranteeing the convergence of the multiplicative multisplitting method. Moreover, the multiplicative multisplitting method is applied to the H-compatible splitting and the multiplicative Schwarz method, separately. Finally, we establish the monotone convergence of the multiplicative multisplitting method under appropriate conditions.     

Error estimates for the logarithmic barrier method in linear quadratic stochastic optimal control problems

We consider a linear quadratic stochastic optimal control problem with non-negativity control constraints. The latter are penalized with the classical logarithmic barrier. Using a duality argument and the stochastic minimum principle, we provide error estimates for the central path which are the natural extensions of the well known estimates in the deterministic framework.     

A neural network based on the generalized Fischer-Burmeister function for nonlinear complementarity problems

In this paper, we consider a neural network model for solving the nonlinear complementarity problem (NCP). The neural network is derived from an equivalent unconstrained minimization reformulation of the NCP, which is based on the generalized Fischer-Burmeister function ?_p(a,b)=‖(a,b)‖_p-(a+b). We establish the existence and the convergence of the trajectory of the neural network, and study its Lyapunov stability, asymptotic stability as well as exponential stability. It was found that a larger p leads to a better convergence rate of the trajectory. Numerical simulations verify the obtained theoretical results.     

Monte Carlo simulation-compatible stochastic field for application to expansion-based stochastic finite element method

In order to endow the expansion-based stochastic formulation with the capability of representing the characteristic behavior of stochastic systems, i.e., the non-linear dependence of the response variability on the coefficient of variation of the stochastic field, a Monte Carlo simulation-compatible stochastic field is suggested. Through a theoretical comparison of displacement vectors in the Monte Carlo method and an expansion-based scheme, it is found that the stochastic field adopted in the expansion-based scheme is not compatible with that appearing in the Monte Carlo simulation. The Monte Carlo simulation-compatible stochastic field is established by means of enforcing the compatibility between the stochastic fields in the expansion-based scheme and the Monte Carlo simulation. Employing the stochastic field suggested in this study, the response variability is reproduced with high precision even for uncertain fields with a moderately large coefficient of variation. Furthermore, the formulation proposed here can be used as an indirect Monte Carlo scheme by directly substituting the numerically simulated random fields into the covariance formula. This yields a pronounced reduction in the computation cost while resulting in virtually the same response variability as the Monte Carlo technique.     

A rolling horizon approach for stochastic mixed complementarity problems with endogenous learning: Application to natural gas markets

In this paper we present a new approach for solving energy market equilibria that is an extension of the classical Nash-Cournot approach. Specifically, besides allowing the market participants to decide on their own decision variables such as production, flows or the like, we allow them to compete in terms of adjusting the data in the problem such as scenario probabilities and costs, consistent with a dynamic, more realistic approach to these markets. Such a problem in its original form is very hard to solve given the product of terms involving decision-dependent data and the variables themselves. Moreover, in its more general form, the players can affect not only each others׳ objective functions but also the constraint sets of opponents making such a formulation a more complicated instance of generalized Nash problems. This new approach involves solving a sequence of stochastic mixed complementarity (MCP) problems where only partial foresight is used, i.e., a rolling horizon. Each stochastic MCP or roll, involves a look-ahead for a fixed number of time periods with learning on the part of the players to approximate the extended Nash paradigm. Such partial foresight stochastic MCPs also offer a realism advantage over more traditional perfect foresight formulations. Additionally, the rolling-horizon approach offers a computational advantage over scenario-reduction methods as is demonstrated with numerical tests on a natural gas market stochastic MCP. Lastly, we introduce a new concept, the Value of the Rolling Horizon (VoRH) to measure the closeness of different rolling horizon schemes to a perfect foresight benchmark and provide some numerical tests on it using a stylized natural gas market.     

A priori error estimates of a meshless method for optimal control problems of stochastic elliptic PDEs

In this paper, we study the optimal control problems of stochastic elliptic equations with random field in its coefficients. The main contributions of this work are two aspects. Firstly, a meshless method coupled with the stochastic Galerkin method is investigated to approximate the control problems, which is competitive for high-dimensional random inputs. Secondly, a priori error estimates are derived for the solutions to the control problems. Some numerical tests are carried out to confirm the theoretical results and to demonstrate the efficiency of the proposed method.