On the gradient-projection method for solving the nonsymmetric linear complementarity problem

The Levitin-Poljak gradient-projection method is applied to solve the linear complementarity problem with a nonsymmetric matrixM, which is either a positive-semidefinite matrix or aP-matrix. Further-more, if the quadratic functionx ^T(Mx + q) is pseudoconvex on the feasible region {x R ⁿ |Mx + q 0,x0}, then the gradient-projection method generates a sequence converging to a solution, provided that the problem has a solution. For the case when the matrixM is aP-matrix and the solution is nondegenerate, the gradient-projection method is finite.This work is based on the author's PhD Dissertation, which was supported by NSF Grant No. MCS-79-01066 at the University of Wisconsin, Madison, Wisconsin.The author would like to thank Professor O. L. Mangasarian for his guidance of the dissertation.     

On the Achievement of the Griesmer Bound

The main theorem in this paper is that there does not exist an [n,k,d]_q code with d = (k-2)q ^k-1 - (k-1)q^k-2 attaining the Griesmer bound for q k, k=3,4,5 and for q 2k-3, k 6.     

Characterization of {(q + 1) + 2, 1;t,q}-min · hypers and {2(q + 1) + 2, 2; 2,q}-min · hypers in a Finite projective geometry

In this paper, we shall characterize all {(q + 1) + 2, 1;t, q}-min · hypers and all {2(q + 1) + 2, 2; 2,q}-min · hypers for any integert 2 and any prime powerq 3. In the next paper [8], we shall characterize all {2(q + 1) + 2, 2;t, q}-min · hypers for any integert 3 and any prime powerq 5 using the results in this paper.     

Finite extinction time for some perturbed Hamilton-Jacobi equations

In this paper we study initial value problems likeu _t–R¦u¦^m+u^q=0 in ⁿ× ₊, u(·,0⁺)=u_o(·) in ^N, whereR > 0, 0 <q < 1,m 1, andu _o is a positive uniformly continuous function verifying –R¦u _o¦^m+u ₀ ^q 0 in ^N . We show the existence of the minimum nonnegative continuous viscosity solutionu, as well as the existence of the function t(·) defined byu(x, t) > 0 if 0<t<t (x) andu(x, t)=0 ift t (x). Regularity, extinction rate, and asymptotic behavior of t(x) are also studied. Moreover, form=1 we obtain the representation formulau(x, t)=max{([(u _o(x – t))^1–q –(1–q)t]₊)^1/(1–q): ¦¦R}, (x, t) ₊ ^N+1 .Partially supported by the DGICYT No. 86/0405 project.     

On strong solutions of Poisson's equation in Beppo Levi spaces

LetG sun (n 2) be an unbounded open set having a compact complement and a smooth boundary G of classC ². InG we consider the equations — u=f,u¦G= and prove the existence of a solutionu L ^2,q(G) providedf L ^q(G) and W ^{2 —1/q-q}(G) (1 <q < ). HereL ^2,q(G) is the space of all functionsu L _Ioc ^q (G) having all second order distributional derivatives inL ^q(G). Concerning the uniqueness of this solution we show that the corresponding nullspace has dimensionn + 1 (n 2).

---

Zusammenfassung SciG ⁿ (n 2) eine unbeschränkte offene Menge mit kompaktem Komplement und mit glattem Rand G der KlasseC ². InG betrachten wir das Randwertproblem — u=f,u¦g= und beweisen die Existenz einer Lösungu L ^2,q(G) für beliebigef L ^q(G) und Randwerte W ^2-1/q,q(G) (1 <q < ). Dabei istL ^2,q(G) der Raum aller Funktionenu L _Ioc ^q (G), die Distributionsableitungen zweiter Ordnung inL ^q (G) besitzen. Bezüglich der Eindeutigkeit solcher Lösungen zeigen wir, daß der entsprechende Nullraum die Dimensionn + 1 (n 2) besitzt.

     

A degenerate and strongly coupled quasilinear parabolic system not in divergence form

This paper deals with positive solutions of degenerate and strongly coupled quasi-linear parabolic system not in divergence form: u_t=v^p(u+au), v_t=u^q (v+bv) with null Dirichlet boundary condition and positive initial condition, where p, q, a and b are all positive constants, and p, q 1. The local existence of positive classical solution is proved. Moreover, it will be proved that: (i) When min {a, b} ₁ then there exists global positive classical solution, and all positive classical solutions can not blow up in finite time in the meaning of maximum norm (we can not prove the uniqueness result in general); (ii) When min {a, b} > ₁, there is no global positive classical solution (we can not still prove the uniqueness result), if in addition the initial datum (u₀v₀) satisfies u₀ + au₀ 0, v₀+bv₀ 0 in , then the positive classical solution is unique and blows up in finite time, where ₁ is the first eigenvalue of – in with homogeneous Dirichlet boundary condition.This project was supported by PRC grant NSFC 19831060 and 333 Project of JiangSu Province.     

Approximation of the Distribution of the Supremum of a Centered Random Walk. Application to the Local Score

Let (X _n ) _{n 0} be a real random walk starting at 0, with centered increments bounded by a constant K. The main result of this study is: |P(S _n n x)–P( sup_{0 u 1} B _u x)| C(n,K) n/n, where x 0, ² is the variance of the increments, S _n is the supremum at time n of the random walk, (B _u ,u 0) is a standard linear Brownian motion and C(n,K) is an explicit constant. We also prove that in the previous inequality S _n can be replaced by the local score and sup₀ u 1 B _u by sup₀ u 1|B _u |.     

On the number of nowhere zero points in linear mappings

LetA be a nonsingularn byn matrix over the finite fieldGF _q ,k=n/2,q=p ^a ,a1, wherep is prime. LetP(A,q) denote the number of vectorsx in (GF _q ) ⁿ such that bothx andAx have no zero component. We prove that forn2, and ,P(A,q)[(q–1)(q–3)] ^k (q–2) ^n–2k and describe all matricesA for which the equality holds. We also prove that the result conjectured in [1], namely thatP(A,q)1, is true for allqn+23 orqn+14.     

A parametric linear complementarity problem involving derivatives

The problem considered in this paper is given by the conditions:w = q + tp + Mz, w 0, 0,w ^T = 0, where a dot denotes the derivative with respect to the scalar parametert 0. In this problem,q, p aren-vectors withq 0 andM is an byn P-matrix. This problem arises in a certain basic problem in the field of structural mechanics. The main result in this paper is the existence and uniqueness theorem of a solution to this problem. The existence proof is constructive providing a computational method of obtaining the solution asymptotically.This research is in part supported by the National Science Foundation under Grant No. ENG77-11136.     

An improved asymptotic analysis of the expected number of pivot steps required by the simplex algorithm

Leta ₁ ...,a _m be i.i.d. points uniformly on the unit sphere in ⁿ ,m n 3, and letX:= {x ⁿ |a _i ^T x1} be the random polyhedron generated bya ₁, ...,a _m . Furthermore, for linearly independent vectorsu, in ⁿ , letS _u , (X) be the number of shadow vertices ofX inspan(u,). The paper provides an asymptotic expansion of the expectation value¯S _n,m := _in4 ¹ E(S _u, ) for fixedn andm .¯S _n,m equals the expected number of pivot steps that the shadow vertex algorithm — a parametric variant of the simplex algorithm — requires in order to solve linear programming problems of type max u ^T ,xX, if the algorithm will be started with anX-vertex solving the problem max ^T ,x X. Our analysis is closely related to Borgwardt's probabilistic analysis of the simplex algorithm. We obtain a refined asymptotic analysis of the expected number of pivot steps required by the shadow vertex algorithm for uniformly on the sphere distributed data.     

On properties of the probabilistic constrained linear programming problem and its dual

In this paper, the two problems inf{inf{cx:x R ⁿ,A ₁ xy,A ₂ xb}:y suppF R ^m,F(y)p} and sup{inf{uy:y suppF R ^m,F(y)p}+vb:uA ₁+vA ₂=c, (u,v0} are investigated, whereA ₁,A ₂,b,c are given matrices and vectors of finite dimension,F is the joint probability distribution of the random variables ₁,..., _m, and 0<p<1. The first problem was introduced as the deterministic equivalent and the second problem was introduced as the dual of the probabilistic constrained linear programming problem inf{cx:P(A ₁ x)p,A ₂ xb}.b}. Properties of the sets and the functions involved in the two problems and regularity conditions of optimality are discussed.     

On near-polygons and the coxeter cap in PG(5,3)

We find an upper bound for the cardinality of a set of points in PG(n, q) with the property that nol of them are contained in a (l– 2)-fiat (n l – 2 0) and we treat the case of equality. We also determine all ovoids and Cameron closed sets of the regular near-hexagon related to the extended ternary Golay code.Research assistent of The Fund of Scientific Research — Flanders (Belgium)     

Linear programming by minimizing distances

To solve the linear program (LP): minimizec ^T l subject toA l+b0, for ann×d-matrixA, ann-vectorb and ad-vectorc, the positive orthantS and the planeE(t) are defined by S={(x₁,x)ⁿ⁺¹ ¦(x₁,x)0}, E(t)={(x₁,x)ⁿ⁺¹¦x₁=–c ^c l+t, x=Al+b}. First a geometric algorithm is given to determine d(E(t),S) for fixedt, where d(·,·) denotes euclidean distance. This algorithm is used to construct a second algorithm to find the minimalt with E(t) S , and thus solve LP. It is shown that all algorithms are finite.     

Positive supersolutions to general nonlinear elliptic equations in exterior domains

We study the problem of non-existence of positive solutions to the elliptic inequalities involving quasilinear operators of the type –divA(x,u,u)|x|^su^p, in the exterior domains in ^N, N3, p>1.Acknowledgement Parts of this work were discussed during I.V.Skrypniks visit to Bristol. Support of the Institute of Advanced Studies of the University of Bristol via a Benjamin Meaker Professorship is gratefully acknowledged.     

The binding number of a graph and its circuits

In this paper we prove the following main results: Theorem A. If bind (G)3/2, thenG–u has a Hamiltonian circuit for every vertexu of graphG _i, unlessG belongs either to two classesH ₁ andH ₂ of graphs or to some smaller order graphs with |V(G)|17. Theorem B. If bind (G)3/2 and the maximum degree (G)>(n–1)/2, |V(G)|=n>17, thenG is pancyclic (i.e., it contains a circuit of every lengthm, 3m|V(G)|).     

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.     

Leaves in Representation Diagrams of Bipartite Distance-Regular Graphs

Let denote a bipartite distance-regular graph with diameter D 3 and valency k 3. Let ₀ > ₁ ··· > _D denote the eigenvalues of and let q ^h _ij (0 h, i, j D) denote the Krein parameters of . Pick an integer h (1 h D – 1). The representation diagram = _h is an undirected graph with vertices 0,1,...,D. For 0 i, j D, vertices i, j are adjacent in whenever i j and q ^h _ij 0. It turns out that in , the vertex 0 is adjacent to h and no other vertices. Similarly, the vertex D is adjacent to D – h and no other vertices. We call 0, D the trivial vertices of . Let l denote a vertex of . It turns out that l is adjacent to at least one vertex of . We say l is a leaf whenever l is adjacent to exactly one vertex of . We show has a nontrivial leaf if and only if is the disjoint union of two paths.     

On the Minimum Size of Some Minihypers and Related Linear Codes

We denote by m_r,q(s) the minimum value of f for which an {f, _r-2+s ; r,q }-minihyper exists for r 3, 1 s q–1, where _j=(q^j+1–1)/(q–1). It is proved that m_3,q(s)=₁(₁+s) for many cases (e.g., for all q 4 when ) and that m_r,q(s) _r-1+s₁+q for 1 s q – 1,~q 3,~r 4. The nonexistence of some [n,k,n+s–q^k-2]_q codes attaining the Griesmer bound is given as an application.AMS classification: 94B27, 94B05, 51E22, 51E21     

A Fujita type global existence-global nonexistence theorem for a weakly coupled system of reaction-diffusion equations

LetDR ^N be a region with smooth boundaryD. Letp·q>1,p, q1. We consider the system:u _t=u+v ^p,v _t=u+u ^q inD×[0, ) withu=v=0 inD×[0, ) andu ₀,v ₀ nonnegative. Let=max(p, q). We show that ifD isR ^N, a cone or the exterior of a bounded domain, then there is a numberpc(D) such that (a) if (+1)/(pq–1)>pc(D) no nontrivial global positive solutions of the system exist while (b) if (+1)/(pq–1)<pc(D) both nontrivial global and nonglobal solutions exist. In caseD is a cone orD=R ^N, (a) holds with equality. An explicit formula forpc(D) is given.This research was supported in part by NSF Grant DMS-8822788 and in part by the Air Force Office of Scientific Research.     

Minimal Blocking Sets in Projective Spaces of Square Order

In this paper minimal m-blocking sets of cardinality at most in projective spaces PG(n,q) of square order q, q 16, are characterized to be (t, 2(m-t-1))-cones for some t with . In particular we will find the smallest m-blocking sets that generate the whole space PG(n,q) for 2m n m.