A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

A perturbation bound for the generalized polar decomposition

LetA be anm×n complex matrix. A decompositionA=QH is termed ageneralized polar decomposition ofA ifQ is anm×n subunitary matrix (sometimes also called a partial isometry) andH a positive semidefinite Hermitian matrix. It was proved that a nonzero matrixA ^m×n has a unique generalized polar decompositionA=QH with the property (Q ^H )=(H), whereQ ^H denotes the conjugate transpose ofQ and (H) the column space ofH. The main result of this note is a perturbation bound forQ whenA is perturbed.     

Regularized minimization under weaker hypotheses

LetV andW be two Banach spaces, withV reflexive, a bounded convex set ofV, A a linear mapping fromV intoW, and letF be a convex functional onW. We minimizeJ(v)=F(Av) on using hypotheses about particular sequences in IfV is uniformly convex, we prove existence and uniqueness of a solution of minimal norm minimizingJ. In the Hilbert space case, withF defined byF(w)=w–f ²,f given inW, we get existence and uniqueness of the projection off on A(), which generalizes the case where A() is a closed set ofW (taking closed andA continuous). Finally, we give examples, and we study an unbounded operator case.     

Convex programs with an additional reverse convex constraint

A method is presented for solving a class of global optimization problems of the form (P): minimizef(x), subject toxD,g(x)0, whereD is a closed convex subset ofR ⁿ andf,g are convex finite functionsR ⁿ . Under suitable stability hypotheses, it is shown that a feasible point is optimal if and only if 0=max{g(x):xD,f(x)f( )}. On the basis of this optimality criterion, the problem is reduced to a sequence of subproblemsQ _k ,k=1, 2, ..., each of which consists in maximizing the convex functiong(x) over some polyhedronS _k . The method is similar to the outer approximation method for maximizing a convex function over a compact convex set.     

Inequalities for the interpolation points in Chebyshev approximation by polynomials

Letf andg be approximated in the Chebyshev sense by polynomials of degree n and n–1, respectively. It is shown that if the sum and difference of the normalized (n+1)-st derivatives off andg do not change sign, then the interpolation points ofg separate those off. A corollary is that the zeros of the Chebyshev polynomialT _n separate the interpolation points off iff ⁽ⁿ⁺¹⁾ does not change sign. The sharpness of this result is demonstrated.     

On the Lipschitzian properties of polyhedral multifunctions

In this paper, we show that for a polyhedral multifunctionF:R ⁿ →R ^m with convex range, the inverse functionF ⁻¹ is locally lower Lipschitzian at every point of the range ofF (equivalently Lipschitzian on the range ofF) if and only if the functionF is open. As a consequence, we show that for a piecewise affine functionf:R ⁿ →R ⁿ ,f is surjective andf ⁻¹ is Lipschitzian if and only iff is coherently oriented. An application, via Robinson's normal map formulation, leads to the following result in the context of affine variational inequalities: the solution mapping (as a function of the data vector) is nonempty-valued and Lipschitzian on the entire space if and only if the solution mapping is single-valued. This extends a recent result of Murthy, Parthasarathy and Sabatini, proved in the setting of linear complementarity problems. Research supported by the National Science Foundation Grant CCR-9307685.     

Solution of augmented linear systems using orthogonal factorizations

We consider solvingx+Ay=b andA ^T x=c for givenb, c andm ×n A of rankn. This is called the augmented system formulation (ASF) of two standard optimization problems, which include as special cases the minimum 2-norm of a linear underdetermined system (b=0) and the linear least squares problem (c=0), as well as more general problems. We examine the numerical stability of methods (for the ASF) based on the QR factorization ofA, whether by Householder transformations, Givens rotations, or the modified Gram-Schmidt (MGS) algorithm, and consider methods which useQ andR, or onlyR. We discuss the meaning of stability of algorithms for the ASF in terms of stability of algorithms for the underlying optimization problems.We prove the backward stability of several methods for the ASF which useQ andR, inclusing a new one based on MGS, and also show under what circumstances they may be regarded as strongly stable. We show why previous methods usingQ from MGS were not backward stable, but illustrate that some of these methods may be acceptable-error stable. We point out that the numerical accuracy of methods that do not useQ does not depend to any significant extent on which of of the above three QR factorizations is used. We then show that the standard methods which do not useQ are not backward stable or even acceptable-error stable for the general ASF problem, and discuss how iterative refinement can be used to counteract these deficiencies.Dedicated to Carl-Eric Fröberg on the occasion of his 75th birthdayThis research was partially supported by NSERC of Canada Grant No. A9236.     

A class of nonlinear complementarity problems for multifunctions

Given a continuous mapF:R ⁿ R ⁿ and a lower semicontinuous positively homogeneous convex functionh:R ⁿ R, the nonlinear complementarity problem considered here is to findxR ₊ ⁿ andyh(x), the subdifferential ofh atx, such thatF(x)+y0 andx ^T (F(x)+y)=0. Some existence theorems for the above problem are given under certain conditions on the mapF. An application to quasidifferentiable convex programming is also shown.The authors are grateful to Professor O. L. Mangasarian and the referee for their substantive suggestions.     

On sets having finitely many points of local nonconvexity and propertyP m

If a pointq ofS has the property that each neighborhood ofq contains pointsx andy such that the segmentxy is not contained byS, q is called a point of local nonconvexity ofS. LetQ denote the set of points of local nonconvexity ofS. Tietze’s well known theorem that a closed connected setS in a linear topological space is convex ifQ=φ is generalized in the result:If S is a closed set in a linear topological space such that S ∼ Q is connected and |Q|=n<∞,then S is the union of n+1or fewer closed convex sets. Letk be the minimal number of convex sets needed in a convex covering ofS. Bounds fork in terms ofm andn are obtained for sets having propertyP _m and |Q|=n.     

Solving more linear complementarity problems with Murty's bard-type algorithm

The linear complementarity problem (M|q) is to findw andz inR ⁿ such thatw–Mz=q,w0,z0,w ^t z=0, givenM inR ^n×n andq in . Murty's Bard-type algorithm for solving LCP is modeled as a digraph.Murty's original convergence proof considered allq inR ⁿ andM inR ^n×n , aP-matrix. We show how to solve more LCP's by restricting the set ofq vectors and enlarging the class ofM matrices beyondP-matrices. The effect is that the graph contains an embedded graph of the type considered by Stickney and Watson wheneverM is a matrix containing a principal submatrix which is aP-matrix. Examples are presented which show what can happen when the hypotheses are further weakened.     

A remark on generalized iterates

Letf be an invertible function on the real lineR, and letZ denote the set of integers. For eachx Z, letf ^|n| denote then'th iterate off. Clearlyf ^|m|(f ^|n|(x))=f ^|m+n|(x) for allm,nZ and allxR. LetG be any group of orderc, the cardinality of the continuum, which contains (an isomorphic copy of)Z as a normal subgroup. If for eachxR, the iteration trajectory (orbit) ofx is non-periodic, then there exists a set of invertible functionsF={F ^||:G} on the real line with the properties (i)F ^||(F ^||(x))=F ^|+| (x) for allxR and (ii)F ^|n|(x)=f ^|n|(x) for allnZ andxR. That is,f can be embedded in a set ofG-generalized iterates. In particular,f can be embedded in a set of complex generalized iterates.Dedicated to Professor Janos Aczél on his 60th birthday     

Bi-Lipschitz concordance implies bi-Lipschitz isotopy

We modify the proof of an earlier result of ours to deforming topological, bi-Lipschitz, and quasiconformal embeddings of an open subsetU ofR ⁿ which now are of small uniform distance from the inclusion map. As an application we show that two bi-Lipschitz homeomorphismsf ₀,f ₁:R ⁿRⁿ are bi-Lipschitz isotopic if and only ifd(f ₀,f ₁)<.Research supported in part by a grant from the Institut Mittag-Leffler.     

Infinite retrogression in the Eaves—Saigal algorithm

For certain functionsf fromR ⁿ toR ⁿ , the Eaves—Saigal algorithm computes a path inR ⁿ × (0, 1] which converges to a zero off. In this case, it is shown that even whenf is of classC and has a unique zero, the converging path may retrogress infinitely many times.Army Research Office, Durham, Contract No. DAAG-29-78-G-0026; National Science Foundation Grant No. MCS-77-05623.     

Lower bounds at infinity of solutions of partial differential equations in the exterior of a proper cone

An extension of a classical theorem of Rellich to the exterior of a closed proper convex cone is proved: Let Γ be a closed convex proper cone inR ⁿ and −Γ′ be the antipodes of the dual cone of Γ. Let be a partial differential operator with constant coefficients inR ⁿ, whereQ(ζ)≠0 onR ⁿ−iΓ′ andP _i is an irreducible polynomial with real coefficients. Assume that the closure of each connected component of the set {ζ∈R ⁿ−iΓ′;P _j(ζ)=0, gradP _j(ζ)≠0} contains some real point on which gradP _j≠0 and gradP _j∉Γ∪(−Γ). LetC be an open cone inR ⁿ−Γ containing both normal directions at some such point, and intersecting each normal plane of every manifold contained in {ξ∈R ⁿ;P(ξ)=0}. Ifu∈ℒ′∩L _loc ² (R ⁿ−Γ) and the support ofP(−i∂/∂x)u is contained in Γ, then the condition implies that the support ofu is contained in Γ.     

The upper envelope of piecewise linear functions and the boundary of a region enclosed by convex plates: Combinatorial analysis

Letf ₁, ...,f _m be (partially defined) piecewise linear functions ofd variables whose graphs consist ofn d-simplices altogether. We show that the maximal number ofd-faces comprising the upper envelope (i.e., the pointwise maximum) of these functions isO(n ^d (n)), where(n) denotes the inverse of the Ackermann function, and that this bound is tight in the worst case. If, instead of the upper envelope, we consider any single connected componentC enclosed byn d-simplices (or, more generally, (d – 1)-dimensional compact convex sets) in ^d+1 , then we show that the overall combinatorial complexity of the boundary ofC is at mostO(n ^d+1–(d+1) ) for some fixed constant(d+1)>0.Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development.     

Exact solution of linear equations usingP-adic expansions

Summary A method is described for computing the exact rational solution to a regular systemAx=b of linear equations with integer coefficients. The method involves: (i) computing the inverse (modp) ofA for some primep; (ii) using successive refinements to compute an integer vector such that (modp ^m ) for a suitably large integerm; and (iii) deducing the rational solutionx from thep-adic approximation . For matricesA andb with entries of bounded size and dimensionsn×n andn×1, this method can be implemented in timeO(n ³(logn)²) which is better than methods previously used.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (Grant No. A 7171)     

On the family of translations of a tight probability measure on a topological group

Summary Let P be a tight probability measure on an Abelian normal topological group and the family of all its translations ({P(t ^–1)}). We shall investigate the closed convex hull of the set , where the closure is taken in the weak topology. Theorem 3 shows that a probability measure Q is an element of the closed convex hull of if and only if there exists a probability measure R such that Q=P*R, where P*     

A generalized conjugate gradient algorithm for minimization

Summary A generalized conjugate gradient algorithm which is invariant to a nonlinear scaling of a strictly convex quadratic function is described, which terminates after at mostn steps when applied to scaled quadratic functionsf: R _n R₁ of the formf(x)=h(F(x)) withF(x) strictly convex quadratic andhC ¹ (R₁) an arbitrary strictly monotone functionh. The algorithm does not suppose the knowledge ofh orF but only off(x) and its gradientg(x).     

Surrogate methods for linear inequalities

Three algorithms are developed and validated for finding a pointx inR ⁿ that satisfies a given system of inequalities,Axb. A andb are a given matrix and a given vector inR ^m×n andR ^m , respectively, with the rows ofA assumed normalized. The algorithms are iterative and are based upon the orthogonal projection of an infeasible point onto the manifold of the bounding hyperplanes of some of the given constraints. The choice of the active constraints and the actual projection are accomplished through the use of surrogate constraints.This work was supported in part by the City University of New York Research Center. The author thanks Professor D. Goldfarb for suggesting the problem and also for his valuable literature information and time. The word surrogate was borrowed from one of his works.     

Galerkin method and optimal error algorithms in hilbert spaces

Summary We consider operator equations of the formLu=f, whereL belongs to the class of linear, bounded (by a constantM) and coercive (with a constantm) operators from a Hilbert spaceV onto its dualV ^* andf belongs to a Hilbert spaceWV ^*. We study optimality of the Galerkin methodP _n ^* Lu _n =P _n ^* f, whereu _n V _n ,V _n is subspace ofV, P _n is the orthogonal projector ontoV _n andP _n ^* is dual toP _n . We show that the Galerkin method is quasi optimal independently of the choice of the subspaceV _n and the spaceW ifM>m. In the caseM=m, optimality of the method depends strongly on the choice ofV _n andW. Therefore we define a new algorithm which is always optimal (independently of the choice ofV _n andW and relations betweenM andm).