Iterative algorithms for the linear complementarity problem

Direct complementary pivot algorithms for the linear complementarity problem with P-matrices are known to have exponential computational complexity. The analog of Gauss-Seidel and SOR iteration for linear complementarity problems with P-matrices has not been extensively developed. This paper extends some work of van Bokhoven to a class of nonsymmetric P-matrices, and develops and compares several new iterative algorithms for the linear complementarity problem. Numerical results for several hundred test problems are presented. Such indirect iterative algorithms may prove useful for large sparse complementarity problems.     

Iteration complexity of an interior-point algorithm for nonlinear p∗-complementarity problems

This paper provides an analysis of the iterative complexity of a predictor-corrector type interior-point algorithm for a class of non-monotone nonlinear complementarity problems, i.e., the nonlinear P?-complementarity problems, which is quite general because it includes as a special case the monotone complementarity problem. At each corrector step, one has to compute an approximate solution of a nonlinear system such that a certain accuracy requirement is satisfied. The proof of the iterative complexity of the proposed algorithm requires that the mapping associated the problem satisfies a scaled Lipschitz condition.     

A cost accounting problem solver and generator

Well-structured problems in many fields can be solved by the computer. By a procedure similar to finding the inverse of a function, the computer can also be used to generate problems with specified characteristics. This paper gives an example of the complementarity of problem solving and problem generation in the discipline of cost accounting     

Asynchronous multisplitting relaxation methods for linear complementarity problems

To solve the linear complementarity problems efficiently on the high-speed multiprocessor systems, we set up a class of asynchronous parallel matrix multisplitting accelerated over-relaxation (AOR) method by technical combination of the matrix multisplitting and the accelerated overrelaxation techniques. The convergence theory of this new method is thoroughly established under the condition that the system matrix of the linear complementarity problem is an H-matrix with positive diagonal elements. At last, we also make multi-parameter extension for this new asynchronous multisplitting AOR method, and investigate the convergence property of the resulted asynchronous multisplitting unsymmetric AOR method. Thereby, an extensive sequence of asynchronous parallel relaxed iteration methods in the sense of multisplitting is presented for solving the large scale linear complementarity problems in the asynchronous parallel computing environments. This not only affords various choices, but also presents systematic convergence theories about the asynchronous parallel relaxation methods for solving the linear complementarity problems.     

多体系统多点碰撞接触问题的数值求解方法

多体系统多点接触碰撞问题可以归结为一个将系统的动力学方程与并协性约束方程相结合的问题.针对这样一个含并协性条件的混合方程组,建立了基于 LCP 格式的包含碰撞/接触问题的多刚体系统动力学分析框架,提出了一种基于步长评价准则的变时间步长的数值求解策略,实现了无摩擦情况下多刚体系统多点接触碰撞问题的数值算法.最后给出了数值算例,验证了算法的有效性.     

浅析我国高速公路收费系统建设

本文阐述了高速公路收费系统的基本概念及功能,详细列举了三种高速公路收费系统,并具体介绍了全自动高速公路收费系统。于此同时,本文还指出了高速公路收费系统建设应该注意的相关问题,并说明了高速公路收费系统的具体维修措施,可供相关人员参考。     

On the rank minimization problem over a positive semidefinitelinear matrix inequality

We consider the problem of minimizing the rank of a positive semidefinite matrix, subject to the constraint that an affine transformation of it is also positive semidefinite. Our method for solving this problem employs ideas from the ordered linear complementarity theory and the notion of the least element in a vector lattice. This problem is of importance in many contexts, for example in feedback synthesis problems, and such an example is also provided     

Comments on "An iterative method for generalized complementarity problems"

In an earlier paper, the author proposed an iterative method for generalized complementarity problems with Lipschitz continuous and strongly monotone functions. Here we show that a slightly modified method can be developed to solve a generalized complementarity problem with a Lipschitz continuous, pseudomonotone, and integrable function.     

Stability results for polyhedral complementarity problems

In this work, we study the multivalued complementarity problem for polyhedral multifunctions under homogeneity assumptions. We employ an approach that consists in approximating the equivalent variational inequality formulation of the problem and studying the asymptotic behavior of sequences of solutions to these approximation problems. To do this, we employ results and the language of Variational Analysis. The novelty of this approach lies in the fact that it allows us to obtain not only existence results but also stability ones. We consider that our results can be used for developing numerical algorithms for solving multivalued complementarity problems.     

A separable programming approach to the linear complementarity problem

The linear complementarity problem (LCP) is reformulated as a nonconvex, separable program and solved with a general branch and bound algorithm. Unlike the principal alternatives, the approach offered here works for all linear complementarity problems regardless of their underlying matrix structure. In the reformulated version, the optimal value is known at the outset so a convergence check can be made at each iteration of the algorithm. This greatly improves its performance; in fact, a number of cases are given where immediate convergence can be expected.     

求解互补支持向量机的非单调信赖域算法

求解支持向量机的核心问题是对一个大规模凸二次规划问题进行求解。基于支持向量机的修正模型,得到一个与之等价的互补问题,利用Fischer-Burmeister互补函数,从一个新的角度提出了求解互补支持向量机的非单调信赖域算法。新算法避免了求解Hesse矩阵或矩阵求逆运算,减少了工作量,提高了运算效率。在不需要任何假设的情况下,证明算法具有全局收敛性。数值实验结果表明,对于大规模非线性分类问题,该算法的运行速度比LSVM算法和下降法快,为求解SVM优化问题提供了一种新的可行方法。     

A Genetic Algorithm Based Approach to Optimal Toll Level and Location Problems

The derivative based approach to solve the optimal toll problem is demonstrated in this paper for a medium scale network. It is shown that although the method works for most small problems with only a few links tolled, it fails to converge for larger scale problems. This failure led to the development of an alternative genetic algorithm (GA) based approach for finding optimal toll levels for a given set of chargeable links. A variation on the GA based approach is used to identify the best toll locations making use of location indices suggested by Verhoef (2002).     

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

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

公路联网收费系统网络故障诊断与解决措施探讨

随着社会经济的蓬勃发展,我国的公路系统也越来越发达。网络给公路收费系统带来便利的同时,也带来了危机。本文对公路联网收费系统常见网络故障进行了分析,并提出了相关解决措施。     

基于Hadoop的高速公路OD数据存储模型和计算方法

高速公路OD数据是高速公路运营管理和状况分析的一类重要数据,如何利用海量的收费数据快速生成并有效管理高速公路OD数据是当前高速公路智能化建设中的一个重要问题.针对高速公路OD数据的种类多、周期长等问题,提出一种基于Hadoop的高速公路OD矩阵存储模型和相应的计算方法.建立统计高速公路车辆旅行时间、统计高速公路车流量两类OD矩阵作为存储模型.通过基于海量真实的高速公路收费数据的实验和传统的存储高速公路收费数据对比表明本文的存储方法相对于传统的关系数据存储,拥有更高效的存储效率并节省了存储空间.     

高速公路联网收费中费率计算的研究

对高速公路联网收费环境下联网区域通行费费率的规划和计算问题进行了研究。根据联网区域中路网、车辆通行及收费方式的实际情况,建立了一个区域联网通行费费率的实用模型,并在此基础上提出了两个计算联网收费区域通行费费率的算法,同时给出了这两个算法正确性的简要证明。实际应用表明所提出的快速算法能满足区域联网收费的要求,快速正确地完成计算。最后,描述了一个联网收费区域标识站辅助规划的实用方案,可以减轻联网区域费率规划过程中的困难。     

New second-order cone linear complementarity formulation and semi-smooth Newton algorithm for finite element analysis of 3D frictional contact problem

We propose a new second-order cone linear complementarity problem (SOCLCP) formulation for the numerical finite element analysis of three-dimensional (3D) frictional contact problems by the parametric variational principle. Specifically, we develop a regularization technique to resolve the multi-valued difficulty involved in the frictional contact law, and use a second-order cone complementarity condition to handle the regularized Coulomb friction law in contact analysis. The governing equations of the 3D frictional contact problem is represented by an SOCLCP via the parametric variational principle and the finite element method, which avoids the polyhedral approximation to the Coulomb friction cone so that the problem to be solved has much smaller size and the solution has better accuracy. In this paper, we reformulate the SOCLCP as a semi-smooth system of equations via a one-parametric class of second-order cone complementarity functions, and then apply the non-smooth Newton method for solving this system. Numerical results confirm the effectiveness and robustness of the SOCLCP approach developed.     

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.     

An interactive approach based on a discrete differential evolution algorithm for a class of integer bilevel programming problems

This paper presents an interactive approach based on a discrete differential evolution algorithm to solve a class of integer bilevel programming problems, in which integer decision variables are controlled by an upper-level decision maker and real-value or continuous decision variables are controlled by a lower-level decision maker. Using the Karush--Kuhn–Tucker optimality conditions in the lower-level programming, the original discrete bilevel formulation can be converted into a discrete single-level nonlinear programming problem with the complementarity constraints, and then the smoothing technique is applied to deal with the complementarity constraints. Finally, a discrete single-level nonlinear programming problem is obtained, and solved by an interactive approach. In each iteration, for each given upper-level discrete variable, a system of nonlinear equations including the lower-level variables and Lagrange multipliers is solved first, and then a discrete nonlinear programming problem only with inequality constraints is handled by using a discrete differential evolution algorithm. Simulation results show the effectiveness of the proposed approach.     

TollSim: Simulation and evaluation of toll stations

This work presents a stochastic simulation model and experimentation for a toll system developed for a highly concurred highway toll in Venezuela, followed by a discussion of performance and economic indicators. Although mathematical models for resource problems have been developed, their use is not widespread, particularly in developing countries were toll systems are manually operated. The main objective of TollSim is to start building an infrastructure and infostructure to be used in a decision support system for management of traffic related issues in a technologically excluded region. The model was developed using an object‐oriented approach and implemented in MODSIM‐III, SIMGRAPHICSII and SIMDRAW.