The Effect of Spatial Autocorrelation on the Error Rates of the Linear Discriminant Functions

The problem of classification of the realization of the intrinsically stationary multivariate Gaussian random field into one of two populations with different means and factorized covariance matrices is considered. Unknown means and the common covariance matrix of the feature vector components are estimated from the spatially correlated training samples assuming spatial correlations to be known. Two plugin linear discriminant functions (DF) are considered. The first linear DF uses the maximum likelihood (ML) estimators of means and the biasadjusted ML estimator of covariance. The second one uses usual sample means and biasadjusted sample covariance. The firstorder asymptotic expansions with respect to the inverses of training sample sizes of the expected error rate associated with two plugin DF's are presented. The numerical results obtained allow us to compare the performance of the suggested DF's. The numerical calculations are done for the exponential spatial correlation function.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Descent methods for convex essentially smooth minimization

Consider the problem of minimizing a convex essentially smooth function over a polyhedral set. For the special case where the cost function is strictly convex, we propose a feasible descent method for this problem that chooses the descent directions from a finite set of vectors. When the polyhedral set is the nonnegative orthant or the entire space, this method reduces to a coordinate descent method which, when applied to certain dual of linearly constrained convex programs with strictly convex essentially smooth costs, contains as special cases a number of well-known dual methods for quadratic and entropy (either –logx orx logx) optimization. Moreover, convergence of these dual methods can be inferred from a general convergence result for the feasible descent method. When the cost function is not strictly convex, we propose an extension of the feasible descent method which makes descent along the elementary vectors of a certain subspace associated with the polyhedral set. The elementary vectors are not stored, but generated using the dual rectification algorithm of Rockafellar. By introducing an -complementary slackness mechanism, we show that this extended method terminates finitely with a solution whose cost is within an order of of the optimal cost. Because it uses the dual rectification algorithm, this method can exploit the combinatorial structure of the polyhedral set and is well suited for problems with a special (e.g., network) structure.This work was partially supported by the US Army Research Office Contract No. DAAL03-86-K-0171 and by the National Science Foundation Grant No. ECS-85-19058.     

Shocks in the asymmetric exclusion process

Summary In this paper, we consider limit theorems for the asymmetric nearest neighbor exclusion process on the integers. The initial distribution is a product measure with asymptotic density at - and at +. Earlier results described the limiting behavior in all cases except for 0<<1/2, +=1. Here we treat the exceptional case, which is more delicate. It corresponds to the one in which a shock wave occurs in an associated partial differential equation. In the cases treated earlier, the limit was an extremal invariant measure. By contrast, in the present case the limit is a mixture of two invariant measures. Our theorem resolves a conjecture made by the third author in 1975 [7]. The convergence proof is based on coupling and symmetry considerations.Research supported in part by NSF Grant DMS 83-1080Research supported in part by NSF Grant MCS 83-00836     

Flatness properties of monocyclic acts

In a previous paper the authors studied flatness properties of cyclic actsS/ (S denotes a monoid, and is a right congruence onS), and determined conditions onS under which all flat or weakly flat acts of this type are actually strongly flat or projective. In the present paper attention is restricted to monocyclic acts (cyclic acts in which is generated by a single pair of elements ofS), and further results on such collapsing of flatness properties are obtained. An observation which is used extensively in this study is the fact that forw andt inS withwtt,S/(wt,t) is flat if and only ift is a regular element ofS.Research supported by Natural Sciences and Engineering Research Council of Canada Operating Grant A4494.Research supported by Estonian Research Foundation Grant No. 930.     

Global Optimization Techniques for Solving the General Quadratic Integer Programming Problem

We consider the problem of minimizing a general quadratic function over a polytope in the n-dimensional space with integrality restrictions on all of the variables. (This class of problems contains, e.g., the quadratic 0-1 program as a special case.) A finite branch and bound algorithm is established, in which the branching procedure is the so-called integral rectangular partition, and the bound estimation is performed by solving a concave programming problem with a special structure. Three methods for solving this special concave program are proposed.     

Bijectivity of -endomorphisms of ℬ(H) and the unilateral shift

LetH be a separable infinite-dimensional complex Hilbert space. We prove that if : (H)(H) is a^*-preserving ring homomorphism whose range contains a rank-one operator and an operator with dense range, then is an isometric linear or conjugate-linear algebra automorphism of (H). In particular, if the unilateral shift is contained in the range of a^*-endomorphism of (H), then is bijective.Research partially supported by the Hungarian National Research Science Foundation, Operating Grant Number OTKA 1652 and K&H Bank Ltd., Universitas Foundation.     

Disintegration with respect to L p-density functions and singular measures

Summary Let A be a real or complex commutative ordered algebra with identity and involution. Let denote the set of positive multiplicative linear functionals on A. Equip with the topology of simple convergence. For a fixed non-negative probability measure on the set _p of linear functionals f on A which admit an integral representation of the form with FL _p () (1p) is biuniquely identified with L _p () via the map tfF. The norm on _p under which this map becomes an isometry is characterized and a formula for approximating F is derived. The linear functionals which admit representation of the form with are also characterized and appropriately normed. The theory is applied to solve abstract versions of trigonometric and n-dimensional moment problems as well as provide an alternate point of view to the theory of L _p-spaces. New proofs of classical theorems are offered.Research for this paper was sponsored in part by the Danish Natural Science Research Council (Grant No.511-10302) and in part by the National Science Foundation (Grant No. MCS78-03397)The results contained herein include the proofs of theorems announced in [15]     

A Gauss—Newton method for convex composite optimization

An extension of the Gauss—Newton method for nonlinear equations to convex composite optimization is described and analyzed. Local quadratic convergence is established for the minimization ofh F under two conditions, namelyh has a set of weak sharp minima,C, and there is a regular point of the inclusionF(x) C. This result extends a similar convergence result due to Womersley (this journal, 1985) which employs the assumption of a strongly unique solution of the composite functionh F. A backtracking line-search is proposed as a globalization strategy. For this algorithm, a global convergence result is established, with a quadratic rate under the regularity assumption.This material is based on research supported by National Science Foundation Grants CCR-9157632 and DMS-9102059, the Air Force Office of Scientific Research Grant F49620-94-1-0036, and the United States—Israel Binational Science Foundation Grant BSF-90-00455.     

Limit theorems for multitype continuous time Markov branching processes

Summary Let X(t)=(X ₁ (t), X ₂ (t), , X _t (t)) be a k-type (2k<) continuous time, supercritical, nonsingular, positively regular Markov branching process. Let M(t)=((m _ij (t))) be the mean matrix where m _ij (t)=E(X _j (t)¦X _r (0)= _ir for r=1, 2, , k) and write M(t)=exp(At). Let be an eigenvector of A corresponding to an eigenvalue . Assuming second moments this paper studies the limit behavior as t of the stochastic process . It is shown that i) if 2 Re >₁, then · X(t)e{–t¦ converges a.s. and in mean square to a random variable. ii) if 2 Re ₁ then [ · X(t)] f(v · X(t)) converges in law to a normal distribution where f(x)=(x) ^–1 if 2 Re <₁ and f(x)=(x log x)^–1 if 2 Re =₁, ₁ the largest real eigenvalue of A and v the corresponding right eigenvector.Research supported in part under contracts N0014-67-A-0112-0015 and NIH USPHS 10452 at Stanford University.     

Non-equilibrium entropy on stationary Markov processes

We study the evolution of probability measures under the action of stationary Markov processes by means of a non-equilibrium entropy defined in terms of a convex function . We prove that the convergence of the non-equilibrium entropy to zero for all measures of finite entropy is independent of for a wide class of convex functions, including ₀(t)=t log t. We also prove that this is equivalent to the convergence of all the densities of a finite norm to a uniform density, on the Orlicz spaces related to , which include the L ^p -spaces for p>1. By means of the quadratic function ₂(t)=t ²–1, we relate the non-equlibrium entropies defined by the past -algebras of a K-dynamical system with the non-equilibrium entropy of its associated irreversible Markov processes converging to equilibrium.Partially supported by DIB Universidad de Chile, E19468412.     

Level set representation for the Gibbs states of the ferromagnetic ising model

Summary We prove the existence of a real valued random field with parameters in thed-dimensional cubic lattice, such that the distribution of the level set of this random field is a Gibbs state for the nearest neighbour ferromagnetic Ising model. Using this, we prove the continuity of the percolation probability with respect to the parameter (,h) in the uniqueness region except on the critical curve _c ={(,h _c ())}, whereh _c() is the critical level of the external field above which percolation takes place.Supported in part by JSPS, BiBoS, Grant in Aid for Cooperative research no. 62303006 and Grant in Aid for Scientific Research no. 63540168     

An intersection property for starshaped sets in the plane

Let be a family of compact starshaped sets in the plane. If every three and every two members of have a union which is connected and simply connected, then {F:F in } is simply connected and nonempty. Of course, if every three and every two members of have a starshaped union, the same result holds.Supported in part by NSF grants DMS-8705336, DMS-8908717 and by a Senior Faculty Summer Research Fellowship, Research Council, University of Oklahoma.     

A Semidefinite Programming Heuristic for Quadratic Programming Problems with Complementarity Constraints

The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these feasible solutions and the best resulting solution provides an estimate for the optimal solution to the quadratic program with complementarity constraints. Computational testing of such an approach is described for a problem arising in portfolio optimization.Research supported in part by the National Science Foundations VIGRE Program (Grant DMS-9983646).Research partially supported by NSF Grant number CCR-9901822.     

Deriving collinear scaling algorithms as extensions of quasi-Newton methods and the local convergence of DFP- and BFGS-related collinear scaling algorithms

This paper is concerned with collinear scaling algorithms for unconstrained minimization where the underlying local approximants are forced to interpolate the objective function value and gradient at only the two most recent iterates. By suitably modifying the procedure of Sorensen (1980) for deriving such algorithms, we show that two members of the algorithm class derived related to the DFP and BFGS methods respectively are locally and q-superlinearly convergent. This local analysis as well as the results they yield exhibit the same sort of duality exhibited by those of Broyden, Dennis and Moré (1973) and Dennis and Moré (1974) for the DFP and BFGS methods. The results in this paper also imply the local and q-superlinear convergence of collinear scaling algorithms of Sorensen (1982, pp. 154–156) related to the DFP and BFGS methods.Research supported in part by funds provided by the Washington State University Research and Arts Committee, by NSF Grant DMS-8414460 and by DOE Grant DE-FG06-85ER25007.     

Equations de convolution et formes quadratiques

Résumé On étudie, sans hypothèse de convexité, les équations f=g, f=g et f=g.

---

Summary We study, without any convexity hypothesis, equations f=g, f=g and f=g where and respectively denote infimal convolution and deconvolution. We give an explicit formulation of these results in the quadratic hilbertian frame, and we interpret them in terms of parallel addition and subtraction of non necessarily semi-definite positive operators.

     

Properties of Solutions to Second Order Evolution Control Systems. II

We continue the research of the first part of the article. We mainly study codensity for the set of admissible trajectory-control pairs of a system with nonconvex constraints in the set of admissible trajectory-control pairs of the system with convexified constraints. We state necessary and sufficient conditions for the set of admissible trajectory-control pairs of a system with nonconvex constraints to be closed in the corresponding function spaces. Using an example of a control hyperbolic system, we give an interpretation of the abstract results obtained. As application we consider the minimization problem for an integral functional on solutions of a control system.     

A characterization of nonlinear φ-accretive operators

Let E be a Banach space and E(–,] a proper lower semi-continuous convex function. The main purpose of this paper is to characterize those m-accretive operators AE x E that are also -accretive. This is done by using the semigroup S generated by -A, and by first establishing a necessary and sufficient condition for to be a Lyapunov function for S. We also obtain similar results for accretive operators that are not necessarily m-accretive, and deduce invariance and order-preserving criteria for nonlinear semigroups.This research was partially supported by the National Science Foundation under Grant MCS-8102086.     

β-Shifts have unique maximal measure

It is proved that -shifts have unique measure with maximal entropy by constructing an isomorphism of the -shift with another topological dynamical system and proving it for this system.