Improving the rate of convergence of interior point methods for linear programming

This paper proposes a procedure for improving the rate of convergence of interior point methods for linear programming. If (x ^k ) is the sequence generated by an interior point method, the procedure derives an auxiliary sequence ( ). Under the suitable assumptions it is shown that the sequence ( ) converges superlinearly faster to the solution than (x ^k ). Application of the procedure to the projective and afflne scaling algorithms is discussed and some computational illustration is provided.     

On a class of least-element complementarity problems

The present paper studies the linear complementarity problem of finding vectorsx andy inR ₊ ⁿ such thatc + Dx + y 0,b – x 0 andx ^T (c + Dx + y) = y ^T (b – x) = 0 whereD is aZ-matrix andb > 0. Complementarity problems of this nature arise, for example, from the minimization of certain quadratic functions subject to upper and lower bounds on the variables. Two least-element characterizations of solutions to the above linear complementarity problem are established first. Next, a new and direct method to solve this class of problems, which depends on the idea of least-element solution is presented. Finally, applications and computational experience with its implementation are discussed.Research partially supported by the National Science Foundation Grant MCS 71-03341 A04 and the Air Force Office of Scientific Research Contract F 44620 14 C 0079.     

The a posteriori error estimates of Chebyshev–Petrov–Galerkin methods for second-order equations

In this paper, the a posteriori error estimates of Chebyshev–Petrov–Galerkin approximations are investigated. For simplicity, we choose the Poisson equation with Dirichlet boundary conditions to discuss the a posteriori error estimators, and deduce their efficient and reliable properties. Some numerical experiments are performed to verify the theoretical analysis for the a posteriori error estimators.     

Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

We present in this paper an improved estimation of duality gap between binary quadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations.     

The polynomial reconstruction problem: The first 50 years

The problem of reconstructing the characteristic polynomial of a graph of order at least 3 from the collection of characteristic polynomials of its vertex-deleted subgraphs was posed by Cvetkovi? in 1973 as a spectral counter part to the well-known Ulam's reconstruction conjecture. Over the last 50 years, this problem has received notable attention, many positive results have been obtained, but in the general case the problem is still unresolved. In particular, no counter example is found in literature. In this expository paper we survey classical and some more recent results concerning the polynomial reconstruction problem, discuss some related problems, variations and generalizations.     

Dimension polynomials of difference local algebras

We extend the concept of the difference dimension polynomial of a difference field extension to difference local algebras. The main theorem of the paper establishes the existence and form of the dimension polynomial associated with the localization of a finitely generated well-mixed difference algebra at a prime reflexive difference ideal.     

IMPORTANCE MEASURE OF CORRELATED VARIABLES IN POLYNOMIAL OUTPUT

为了解决一般工程问题中输出量为多项式情况下相关正态输入变量的贡献识别问题，以二次不含交叉项的多项输出量为例，利用多维相关正态分布及其条件分布的性质，解析地推导了相关正态输入变量对输出量总方差的独立贡献及相关贡献，采用算例验证了所推导的解析表达式的正确性．文中所推导的相关正态变量独立贡献和相关贡献的表达式可直接用于输出量为二次不含交叉项多项式或一次多项式情况下的输入变量贡献的识别，并且为其他新的算法提供了对照解，另外此方法亦可以推广至含交叉项的高阶多项式，解决更为复杂输出量情况下输入量的贡献识别问题．     

Approximating exponential and logarithmic functions using polynomial interpolation

This article takes a closer look at the problem of approximating the exponential and logarithmic functions using polynomials. Either as an alternative to or a precursor to Taylor polynomial approximations at the precalculus level, interpolating polynomials are considered. A measure of error is given and the behaviour of the error function is analysed. The results of interpolating polynomials are compared with those of Taylor polynomials.     

Bombieri's Theorem in Short Intervals

Under the assumption of sixth power large sieve mean-value of Dirichlet L-function,we improve Bombieri's theorem in short intervals by virtue of the large sieve method and Heath-Brown's identity.