LP relaxations for a class of linear semi-infinite programming problems

In this paper, we consider a subclass of linear semi-infinite programming problems whose constraint functions are polynomials in parameters and index sets are polyhedra. Based on Handelman’s representation of positive polynomials on a polyhedron, we propose two hierarchies of LP relaxations of the considered problem which respectively provide two sequences of upper and lower bounds of the optimum. These bounds converge to the optimum under some mild assumptions. Sparsity in the LP relaxations is explored for saving computational time and avoiding numerical ill behaviors.     

The zero-multiplicity of third-order linear recurrences associated to the Tribonacci sequence

In this paper, we consider third-order linear recurrences _{un}n≥0${\left\{u_n\right\}}_{n\ge 0}$ satisfying the recurrence relation _un+3=_un+2+_un+1+_un$u_{n+3}=u_{n+2}+u_{n+1}+u_n$ for all n≥0$n\ge 0$ and investigate the multiplicity of its zeros. We prove that _{un}n≥0${\left\{u_n\right\}}_{n\ge 0}$ has zero-multiplicity at most 2, except for nonzero multiples of shifts of the Tribonacci sequence which has zero-multiplicity 4 when the indices are extended to all the integers.     

Fatou sets of entire solutions of linear differential equations

This paper is devoted to studying the dynamical properties of solutions of f^″+A(z)f=0$f^{″}+A\left(z\right)f=0$, where A(z)$A\left(z\right)$ is an entire function of finite order. With some added conditions on A(z)$A\left(z\right)$, we prove that all the Fatou components of E(z)$E\left(z\right)$ are simply-connected provided that E=_f1f2$E=f_1{f}_2$ and _f1,_f2$f_1,f_2$ are two linearly independent solutions of such equations.     

Explicit bounds for multidimensional linear recurrences with restricted coefficients

This note employs path counting techniques to extend recent results on bounds for odd order linear recurrences to higher dimensions. The results imply optimal zero-free polydisks for multivariable power series with 0, 1 coefficients. Among the applications is a result that states that the optimal zero-free polydisk has radius approximately 1/(v+1), for large dimensions v.     

A new method for a class of linear variational inequalities

In this paper we introduce a new iterative scheme for the numerical solution of a class of linear variational inequalities. Each iteration of the method consists essentially only of a projection to a closed convex set and two matrix-vector multiplications. Both the method and the convergence proof are very simple.This work is supported by the National Natural Science Foundation of the P.R. China and NSF of Jiangsu.     

Finiteness of integral values for the ratio of two linear recurrences

Let {F(n)} _{n ∈ N} ,{G(n)} _{n ∈ N} , be linear recurrent sequences. In this paper we are concerned with the well-known diophantine problem of the finiteness of the set ? of natural numbers n such that F(n)/G(n) is an integer. In this direction we have for instance a deep theorem of van der Poorten; solving a conjecture of Pisot, he established that if ? coincides with N, then {F(n)/G(n)} _{n ∈ N} is itself a linear recurrence sequence. Here we shall prove that if ? is an infinite set, then there exists a nonzero polynomial P such that P(n)F(n)/G(n) coincides with a linear recurrence for all n in a suitable arithmetic progression. Examples like F(n)=2 ⁿ -2, G(n)=n+2 ⁿ +(-2) ⁿ , show that our conclusion is in a sense best-possible. In the proofs we introduce a new method to cope with a notorious crucial difficulty related to the existence of a so-called dominant root. In an appendix we shall also prove a zero-density result for ? in the cases when the polynomial P cannot be taken a constant. Oblatum 12-XI-2001 & 31-I-2002?Published online: 29 April 2002     

A complete class for linear estimation in a general linear model

Summary It is shown that in linear estimation both unbiased and biased, all unique (up to equivalence with respect to risk) locally best estimators and their limits constitute a complete class.     

Estimating the complexity of a class of path-following methods for solving linear programs by curvature integrals

In this paper we study a particular class of primal-dual path-following methods which try to follow a trajectory of interior feasible solutions in primal-dual space toward an optimal solution to the primal and dual problem. The methods investigated are so-called first-order methods: each iteration consists of a long step along the tangent of the trajectory, followed by explicit recentering steps to get close to the trajectory again. It is shown that the complexity of these methods, which can be measured by the number of points close to the trajectory which have to be computed in order to achieve a desired gain in accuracy, is bounded by an integral along the trajectory. The integrand is a suitably weighted measure of the second derivative of the trajectory with respect to a distinguished path parameter, so the integral may be loosely called a curvature integral.     

A CLASS OF GENERALIZED MULTISPLITTING RELAXATION METHODS FOR LINEAR COMPLEMENTARITY PROBLEMS

In this paper,a class of generalized parallel matrix multisplitting relaxation methods for solving linear complementarity problems on the high-speed multiprocessor systems is set up. This class of methods not only includes all the existing relaxation methods for the linear complementarity problems ,but also yields a lot of novel ones in the sense of multisplittlng. We establish the convergence theories of this class of generalized parallel multisplitting relaxation methods under the condition that the system matrix is an H-metrix with positive diagonal elements.     

On the number of solutions to a class of linear complementarity problems

In this note, we consider the linear complementarity problemw = Mz + q, w 0, z 0, w ^T z = 0, when all principal minors ofM are negative. We show that for such a problem for anyq, there are either 0, 1, 2, or 3 solutions. Also, a set of sufficiency conditions for uniqueness is stated.The work of both authors is partially supported by a grant from the National Science Foundation, MCS 77-03472.     

Investigations of a certain class of linear complementarity problems

A certain class of linear complementarity problems that appeared in an economical study concerning self-employment is investigated. The principal findings for this class of linear complementarity problems are: (i) there is always a solution, which can be found by the Lemke algorithm; (ii) characterizations are found for solutions, some typical for all solutions, some typical for locally nonunique solutions, and some typical for locally unique solutions; (iii) a sufficient condition is found to guarantee a globally unique solution.The research reported in this paper is part of the project Economics of Political Decision Making of the University of Amsterdam. The author acknowledges the financial support obtained from the Ministry of Economic Affairs by way of the Research Institute for Small and Medium-Sized Business as well as the financial support of the Netherlands Organization for Scientific Research. He is grateful to two anonymous referees for many helpful suggestions, to F. A. A. M. Van Winden for stimulating discussions, and to J. J. M. Evers, H. Neudecker, and A. J. J. Talman for comments.     

On a class of finite linear spaces with few lines

A famous result of de Bruijn and Erdős (Indag. Math. 10 (1948) 421–423) states that a finite linear space has at least as many lines as points, with equality only if it is a projective plane or a near-pencil. This result led to the problem of characterizing finite linear spaces for which the difference between the number b of lines and the number v of points is assigned.

In this paper finite linear spaces with b−vm, m being the minimum number of lines on a point, are characterized.     

某些级数的无理性

本文证明了某些与二阶线性递推数列有关的无穷级数的和的无理性．特别，推广了某些与Ｆｉｂｏｎａｃｃｉ和Ｌｕｃａｓ数列有关的无理性结果     

A polynomial-time algorithm for a class of linear complementarity problems

Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x 0,y 0,x _i y _i = 0 (i = 1, 2,,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n ³ L) arithmetic operations by tracing the path of centers,{(x, y) S: x _i y _i = (i = 1, 2,,n) for some > 0} of the feasible regionS = {(x, y) 0:y = Mx + q}, whereL denotes the size of the input data of the problem.     

The growth of meromorphic solutions for a class of higher-order linear differential equations

In this article, the growth of meromorphic solutions for a class of higher-order linear differential equation with meromorphic coefficients is investigated by applying the method of value distribution, and some estimates for the hyper-order of their solutions are obtained.