Robust Solutions To Uncertain Linear Complementarity Problems

In this paper,we study uncertain linear complementarity problems for which the data is not specified exactly or uncertain,and it is only known to belong to a given uncertainty set.We adopt robust optimization technology to discuss how to solve uncertain linear complementarity problems,and conditions for the existence of a robust solution and so on.Uncertain linear complementarity problems are brand-new field in mathematical programming,which have close correlations with complementarity theory,robust optimization technology,stochastic linear complementarity problems and other mathematics branches,moreover,have widespread applications in the science and technology and the economical domains,and are much attractive research topics.The complementarity problem is a intersecting research area between operations research and computational mathematics.As a kind of new mathematical model,the complementarity problem was proposed firstly by the renowned operation scientist,mathematics programming founder G.B.Dantzig and his student R.W.Cottle,in 1963,and very quickly caused widespread attentions and strong interests from temporal operations research and applied mathematics areas,and many people participate in this research.For having close relations with optimization,variational inequality,equilibrium problem,game theory,as well as fixed point theory and so on,moreover,possessing widespread applications in many actual departments such as mechanics,project,economy,and transportation, the complementarity problem showed more and more importance,and driven further research to it's theory and algorithm,which caused research upsurge since the 1990s. In these more than ten years,people not only have improved and enriched fundamental research of the complementarity problem,but also proposed many effective algorithms.But,in nearly all literature,complementarity problems,are deterministic models which the input data is usually assumed to be known precisely,and equals to some nominal value.However,we know,in numerous situations,the data is not nearly known or precisely measured.If we ignore that the data is inexact or uncertain,possibly appears that restraint constraints are violated,and that the optimal solution we obtain by the nominal data no longer is optimal,even is the infeasible.Therefore,when study complementarity problems, we must consider uncertainty of the input data.In this paper,we mainly discuss linear complementarity problems with different uncertainty sets.At present,in this domain,research which only we may profit from originates from Masao Fukushima and Xiaojun chen(the literature[23]).Masao Fukushima and Xiaojun Chen,according to stochastic programming,probe into uncertain linear complementarity problems.However,stochastic programming requires one to make assumptions about the probability distribution of the uncertain data which may not be appropriate, moreover,allows solutions to violate the constraints affected by uncertainty,thus cannot guarantees satisfaction of certain hard constraints,which is required in some practical settings.In view of this,we use robust optimization technology—a much popular kind of technology to deal with uncertain problems,to inquire into uncertain linear complementarity problems.In the second chapter,we introduce the notion of robust solution of uncertain linear complementarity problems,firstly.Besides,we prove that,if robust counterpart to uncertain quadratic programming—a robust optimization problem,has a optimal solution, x~*,x~*∈R~n,and the optimum value equals to zero,then x~* is the robust solution of the uncertain linear complementarity problem.In the light of it,we obtain a new method of solving uncertain linear complementarity problems:represent semi-infinite programming model-robust counterpart,to a single finite and explicit optimization problem.Whereafter, we let optimal value equal to zero,accordingly,get sufficient and necessary conditions of robust solution of uncertain linear complementarity problems.According to the above method,we discuss uncertain linear complementarity problems with uncertainty sets which are unknown-but-bounded uncertainty,random symmetric uncertainty,simple ellipsoidal uncertainty and intersection-of-ellipsoids uncertainty,four typical forms.Firstly,in the second part of the second chapter,we probe into uncertain linear complementarity problems with unknown-but-bounded uncertainty,we use robust optimization theory:whatever the actual realization in uncertainty set is,constraints must be satisfied,we represent robust optimization model to a quadratic programming,and get sufficient and necessary conditions of robust solution of uncertain linear complementarity problems:when uncertainty set U is a unknown-but-bounded uncertainty,that x is robust solution of the uncertain linear complementarity problem holds if and only if x satisfies the inequality group(2.9).On the ground of it,we construct subscript set I and introduce block matrix classΨ,and transform the inequality group(2.9)into a kind of linear complementarity problems.Relying on complementarity theory on hand,we discuss feasibility of uncertain linear complementarity problems,and existence of robust solution, thus obtain some new results.In last part of the second chapter,under a random symmetric uncertainty,we study linear complementarity problems,compared with the former,difference in methods lies in the uncertainty set including random variables,therefore,it makes sense to pass from the deterministic requirement to its probabilistic version.Accordingly,we introduce conception of almost reliable robust solution,and obtain sufficient and necessary conditions of almost reliable robust solution.The third chapter is linear complementarity problems with simple ellipsoidal uncertainty. In robust optimization theory,the simple ellipsoidal uncertainty possesses important status.In this chapter,we use famous S-lemma,represent semi-infinite programming model to a semidefinite programming problem,and we show that if x can be extended to a solution of some nonlinear complementarity problem,then x is robust solution of uncertain linear complementarity problems.In the fourth chapter,we adopt tow kinds of different method of robust optimization to research into the linear complementarity problem including intersection-of-ellipsoids uncertainty.These two methods,from the other hand,manifest development directions of robust optimization technology.All of these results are not known previously,conclusions we obtain has enriched uncertain complementarity problems.