A new pivoting algorithm for the linear complementarity problem allowing for an arbitrary starting point

The linear complementarity problem is to find nonnegative vectors which are affinely related and complementary. In this paper we propose a new complementary pivoting algorithm for solving the linear complementarity problem as a more efficient alternative to the algorithms proposed by Lemke and by Talman and Van der Heyden. The algorithm can start at an arbitrary nonnegative vector and converges under the same conditions as Lemke's algorithm.This research is part of the VF-program Competition and Cooperation.     

线性双层规划的改进PCP全局求解算法

本文采用K-T条件将线性双层规划模型改写为单层规划后,将参数引入上层目标函数,构造了含参线性互补问题(PLCP)并给出它的一些性质。进而通过改进Lemke算法的进基规则,在保持互补旋转算法原有优势的基础上,引入充分小正数ε,设计了改进参数互补旋转(PCP)算法求取全局最优解,最后通过两个算例说明了其有效性。     

Polynomial expected behavior of a pivoting algorithm for linear complementarity and linear programming problems

We show that a particular pivoting algorithm, which we call the lexicographic Lemke algorithm, takes an expected number of steps that is bounded by a quadratic inn, when applied to a random linear complementarity problem of dimensionn. We present two probabilistic models, both requiring some nondegeneracy and sign-invariance properties. The second distribution is concerned with linear complementarity problems that arise from linear programming. In this case we give bounds that are quadratic in the smaller of the two dimensions of the linear programming problem, and independent of the larger. Similar results have been obtained by Adler and Megiddo.Research partially funded by a fellowship from the Alfred Sloan Foundation and by NSF Grant ECS82-15361.     

A new algorithm for quadratic programming

We present a new finite algorithm for quadratic programming. Our algorithm is based on the solution procedures of linear programming (pivoting, Bland's rule, Hungarian Methods, criss-cross method), however this method does not require the enlargement of the basic tableau as Frank-Wolfe method does. It can be considered as a feasible point active-set method. We solve linear equation systems in oder to reach an active constraint set (complementary solutions) and we solve a feasibility problem in order to check that optimality can be reached on this active set or to improve the actual solution. This algorithm is a straightforward generalization of Klafszky's and Terlaky's Hungarian Method. It has nearly the same structure as Ritter's algorithm (which is based on conjugate directions), but it does not use conjugate directions.     

Computational complexity of Van der Heyden's variable dimension algorithm and Dantzig-Cottle's principal pivoting method for solving LCP's

We show that Van der Heyden's variable dimension algorithm and Dantzig and Cottle's principal pivoting method require 2ⁿ–1 pivot steps to solve a class of linear complementarity problems of ordern. Murty and Fathi have previously shown that the computational effort required to solve a linear complementarity problem of ordern by Lemke's complementary pivot algorithm or by Murty's Bard-type algorithm is not bounded above by a polynomial inn. Our study shows that the variable dimension algorithm and the principal pivoting method have similar worst case computational requirements.     

Linear complementarity and discounted switching controller stochastic games

The class of discounted switching controller stochastic games can be solved in one step by a linear complementarity program (LCP). Following the proof of this technical result is a discussion of a special formulation and initialization of a standard LCP pivoting algorithm which has, in numerical experiments, always terminated in a complementary solution. That the LCP algorithm as formulated always finds a complementary solution has not yet been proven, but these theoretical and experimental results have the potential to provide an alternative proof of the ordered field property for these games. Numerical experimentation with the reformulated LCP is reviewed.     

A combinatorial abstraction of linear programming

In the context of oriented matroids we establish and elaborate upon an abstraction of linear programming duality foreseen by Rockafellar in his work on elementary vectors. We describe a pivoting operation for oriented matroids and a finite pivoting method, which elucidate the combinatorial nature of Dantzig's simplex method. The pivoting method specializes, when the oriented matroids arise from real vector spaces, to the simplex method with a new pivot selection rule. A very simple pivot selection rule for which finiteness has been established in the linear programming context, but not in the broader setting of oriented matroids, is also described.     

Evolution towards the Maximum Clique

As is well known, the problem of finding a maximum clique in a graph isNP-hard. Nevertheless, NP-hard problems may have easy instances. This paperproposes a new, global optimization algorithm which tries to exploit favourabledata constellations, focussing on the continuous problem formulation: maximizea quadratic form over the standard simplex. Some general connections of thelatter problem with dynamic principles of evolutionary game theory areestablished. As an immediate consequence, one obtains a procedure whichconsists (a) of an iterative part similar to interior-path methods based on theso-called replicator dynamics; and (b) a routine to escape from inefficient,locally optimal solutions. For the special case of finding a maximum clique ina graph where the quadratic form arises from a regularization of the adjacencematrix, part (b), i.e. escaping from maximal cliques not of maximal size, isaccomplished with block pivoting methods based on (large) independent sets,i.e. cliques of the complementary graph. A simulation study is included whichindicates that the resulting procedure indeed has some merits.     

Geometric random edge

Mathematical Programming - We show that a variant of the random-edge pivoting rule results in a strongly polynomial time simplex algorithm for linear programs $\max \{c^Tx :x \in \mathbb R^n, \,...     

二分单纯形算法中子规划问题的进一步研究

本对二分单纯形算法的子规划问题作进一步研究,提出一个新的子规划问题来改善问题的不可行性,并确定了相应的主元旋转规则,并编制了相应于新子规划的新二分算法,并对94个线性规划问题进行了数值实验,实验结果表明,新二分算法是一种改进的二分算法。     

Borsuk's theorem through complementary pivoting

In this short note a simple and constructive proof is given for Borsuk's theorem on antipodal points. This is done through a special application of the complementary pivoting algorithm.     

Ordering algorithms for irreducible sparse linear systems

Ordinary algorithms aim to pre-order a matrix in order to achieve a favourable structure for factorization. Two prototype structures are described which are commonly aimed at by current algorithms. A different structure, based on a lower Hessenberg form, is introduced. We show that the common structures may be obtained from the Hessenberg form in a simple way. A fundamental and very simple algorithm is presented for deriving the lower Hessenberg form. This algorithm is inherently a part of other common algorithms, but is usually obscured by other detailed heuristics. Some of these heuristics are seen to correspond to different tie-break rules in the fundamental algorithm. We describe a particularly simple tie-break rule used in SPK1 [11], which is effective and not at all well known. Ordinary algorithms need to be modified to enable pivoting for numerical stability to be carried out. We describe how the idea of threshold pivoting can be used in the context of these algorithms. Most ordering algorithms in common use employ some sort of look-ahead to promote a favourable structure. It is argued that look-ahead is generally ineffective in practice, and that numerical evidence supports the use of very simple strategies. A new ordering algorithm is presented which aims to obtain a narrower bandwidth in the lower Hessenberg form. Some limited numerical experience is presented which enables us to draw tentative conclusions about various ordering strategies, and how they compare with those in common use.     

A NUMERICALLY STABLE BLOCK MODIFIED GRAM-SCHMIDT ALGORITHM FOR SOLVING STIFF WEIGHTED LEAST SQUARES PROBLEMS

Recently, Wei in proved that perturbed stiff weighted pseudoinverses and stiff weighted least squares problems are stable, if and only if the original and perturbed coefficient matrices A and A^- satisfy several row rank preservation conditions. According to these conditions, in this paper we show that in general, ordinary modified Gram-Schmidt with column pivoting is not numerically stable for solving the stiff weighted least squares problem. We then propose a row block modified Gram-Schmidt algorithm with column pivoting, and show that with appropriately chosen tolerance, this algorithm can correctly determine the numerical ranks of these row partitioned sub-matrices, and the computed QR factor R^- contains small roundoff error which is row stable. Several numerical experiments are also provided to compare the results of the ordinary Modified Gram-Schmidt algorithm with column pivoting and the row block Modified Gram-Schmidt algorithm with column pivoting.     

A generalized complementary pivoting algorithm

Complementary pivot algorithms known at the present time fall into several quite general categories, with obvious similarities. This paper deals with general pivoting systems which provide a natural setting for the study of complementary pivot algorithms. A generalized algorithm is presented for these systems. We give results on the number of iterations necessary for such an algorithm.This paper is based on the author's doctoral dissertation for the Department of Administrative Sciences, Yale University. The author would like to thank his advisors, Professors G.H. Bradley, D. Brown and N. White. This research was supported in part by National Science Foundation grants GK-13757 and GP-32158X.     

A fast algorithm for coloring Meyniel graphs

We color the nodes of a graph by first applying successive contractions to non-adjacent nodes until we get a clique; then we color the clique and decontract the graph. We show that this algorithm provides a minimum coloring and a maximum clique for any Meyniel graph by using a simple rule for choosing which nodes are to be contracted. This O(n³) algorithm is much simpler than those already existing for Meyniel graphs. Moreover, the optimality of this algorithm for Meyniel graphs provides an alternate nice proof of the following result of Hoàng: a graph G is Meyniel if and only if, for any induced subgraph of G, each node belongs to a stable set that meets all maximal cliques. Finally we give a new characterization for Meyniel graphs.     

Pebbling in diameter two graphs and products of paths

Results regarding the pebbling number of various graphs are presented. We say a graph is of Class 0 if its pebbling number equals the number of its vertices. For diameter d we conjecture that every graph of sufficient connectivity is of Class 0. We verify the conjecture for d = 2 by characterizing those diameter two graphs of Class 0, extending results of Pachter, Snevily and Voxman. In fact we use this characterization to show that almost all graphs have Class 0. We also present a technical correction to Chung's alternate proof of a number theoretic result of Lemke and Kleitman via pebbling. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 119–128, 1997     

Doppelgangers and Lemke graphs

Let $G$ be a connected graph. A configuration of pebbles on $G$ is a function that assigns a nonnegative integer to each vertex. A pebbling move consists of removing two pebbles from one vertex and placing one pebble on an adjacent vertex. A configuration is solvable if after making pebbling moves any vertex can get at least one pebble. The pebbling number of $G$, denoted $\pi \left(G\right)$, is the smallest integer such that any configuration of $\pi \left(G\right)$ pebbles on $G$ is solvable. A graph has the two-pebbling property if after placing more than $2\pi \left(G\right)?q$ pebbles on $G$, where $q$ is the number of vertices with pebbles, there is a sequence of pebbling moves so that at least two pebbles can be placed on any vertex. A graph without the two-pebbling property is called a Lemke graph. Previously, an infinite family of Lemke graphs was shown to exist by subdividing edges of the original Lemke graph. In this paper, we introduce a new way to create infinite families of Lemke graphs based on adding vertices as well as subdividing edges. We also characterize the configurations that violate the two-pebbling property on these graphs and conjecture another infinite family of Lemke graphs that generalizes the original Lemke graph.     

Comparative computer results of a new complementary pivot algorithm for solving equality and inequality constrained optimization problems

This paper reports the development of a new algorithm for solving the general constrained optimization problem (that of optimizing an objective function subject to both equality and inequality constraints). The approach is based on the complementary pivoting algorithms which have been developed to solve certain classes of fixed point problems. The specific approach is to use the equality constraints to solve for some variables in terms of the remaining ones thus enabling one to eliminate the equality constraints altogether. The result, under certain circumstances, is an optimization problem which may be transformed into a fixed point problem in such a way that a complementary pivoting code may be used to search for a solution.Seventeen test problems have been solved by this method and the results are compared against those obtained from GRG (Generalized Reduced Gradient method). The results of the tests indicate that the fixed point approach is robust (all 17 problems were solved by this method where as GRG solved 16). As to the computer times, the fixed point code proved to be as fast or faster than GRG on the lower dimensional problems; however, as the dimension increased, the trend reversed and on a 40 dimensional problem GRG was approximately 11 times faster. The conclusion from these tests is that when the dimension of the original problem can be reduced sufficiently by the equality constraints, the fixed point approach appears to be more effective than GRG.     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

变量有广义界线性规划的叠累单纯形法

本文建立变量有广义界线性规划一个新的转轴算法,称之为叠累单纯形算法,新算法其有三个主要特征：１对于检验数为“坏”的非基变量 ｘｓ,进行一轮子转轴运算,使得ｘｓ进基,转轴中具有“好”的检验数的变量始终保持“好”的检验数;２ｘ．进基的子转轴所产生的基既不是原始可行基,也不是对偶可行基,但子转轴结束时产生的基是原始可行的;３目标函数值在整个转抽运算中是单调下降,从而算法可有限步终止．