On the convergence of the method of analytic centers when applied to convex quadratic programs

This work examines the method of analytic centers of Sonnevend when applied to solve generalized convex quadratic programs — where also the constraints are given by convex quadratic functions. We establish the existence of a two-sided ellipsoidal approximation for the set of feasible points around its center and show, that a simple (zero order) algorithm starting from an initial center of the feasible set generates a sequence of strictly feasible points whose objective function values converge to the optimal value. Concerning the speed of convergence it is shown that an upper bound for the gap in between the objective function value and the optimal value is reduced by a factor of with iterations wherem is the number of inequality constraints. Here, each iteration involves the computation of one Newton step. The bound of Newton iterations to guarantee an error reduction by a factor of in the objective function is as good as the one currently given forlinear programs. However, the algorithm considered here is of theoretical interest only, full efficiency of the method can only be obtained when accelerating it by some (higher order) extrapolation scheme, see e.g. the work of Jarre, Sonnevend and Stoer.This work was supported by the Deutsche Forschungsgemeinschaft, Schwerpunktprogramm für anwendungsbezogene Optimierung und Steuerung.     

A quadratically convergentO((\kappa + 1)\sqrt n L)-iteration algorithm for theP *(κ)-matrix linear complementarity problem

An interior-point predictor-corrector algorithm for theP _*()-matrix linear complementarity problem is proposed. The algorithm is an extension of Mizuno—Todd—Ye's predictor—corrector algorithm for linear programming problem. The extended algorithm is quadratically convergent with iteration complexity . It is the first polynomially and quadratically convergent algorithm for a class of LCPs that are not necessarily monotone.     

Superlinear convergence of Broyden's boundedθ-class of methods

In this paper the so-called Broyden's bounded-class of methods is considered. It contains as a subclass Broyden's restricted-class of methods, in which the updating matrices retain symmetry and positive definiteness. These iteration methods are used for solving unconstrained minimization problems of the following form: It is assumed that the step-size coefficient _k = 1 in each iteration and the functionalf : R ⁿ R¹ satisfies the standard assumptions, viz.f is twice continuously differentiable and the Hessian matrix is uniformly positive definite and bounded (there exist constantsm, M > 0 such that my² y, for ally R ⁿ) and satisfies a Lipschitz-like condition at the optimal point , the gradient vanishes at Under these assumptions the local convergence of Broyden's methods is proved. Furthermore, the Q-superlinear convergence is shown.     

Fonctions Séparément Finement Surharmoniques

Nous montrons que toute fonction séparément finement surharmonique sur un ouvert de la topologie produit _{n_1}×s× _{n_k} des topologies fines des espaces R ⁿ ₁,. . ., R ⁿ _k, _{n_1}×s× _{n_k}-localement bornée inférieurement est finement surharmonique dans . On en déduit que toute fonction séparément finement harmonique, _{n_1}×s× _{n_k}-localement bornée sur est finement harmonique dans .Separately Finely Superharmonic Functions Abstract.We prove that every separately finely surperharmonic function on an open set in R ⁿ ₁×s×R ⁿ _k for the product _{n_1}×s× _{n_k} of the fine topologies on the spaces R ⁿ ₁,. . ., R ⁿ _k, _{n_1}×s× _n-_klocally lower bounded, is finely superharmonic in . We then deduce that every separateltly finely harmonic function _{n_1}×s× _{n k}-locally bounded in is finely harmonic.     

Über die Anzahl der Gitterpunkte in verallgemeinerten Kreissektoren

In this paper we consider lattice points in domains bounded by algebraic curves of the formx ⁿ+yⁿ=Rⁿ fulfilling the additional condition where and are fixed positive real numbers. The number of these lattice points is estimated for largeR and it appears that for rational or badly approximable and the error term in the final result can be made smaller (at least forn3) than it is best possible when counting the lattice points without the additional condition indicated above.     

The Martin boundary and completion of Markov chains

Summary In this paper we treat a time-symmetrical Martin boundary theory for continuous parameter Markov chains. This is done by reversing the time sense of a Markov chainX _t in such a way as to obtain a dual Markov chain , and considering the two chains together. Various relations between the Martin exit boundaries and of these processes are studied. The exit boundary of , is in a sense an entrance boundary forX _t and vice versa. After a natural identification of certain points in and one can topologizeI in such a way thatboth X _t and have standard modifications in this space which are right continuous, have left limits, and are strongly Markov.Research supported in part at Stanford University, Stanford, California under AFOSR 0049.     

On Embeddings of the Flag Geometries of Projective Planes in Finite Projective Spaces

The flag geometry =( ) of a finite projective plane of order s is the generalized hexagon of order (s, 1) obtained from by putting equal to the set of all flags of , by putting equal to the set of all points and lines of and where I is the natural incidence relation (inverse containment), i.e., is the dual of the double of in the sense of Van Maldeghem Mal:98. Then we say that is fully and weakly embedded in the finite projective space PG(d, q) if is a subgeometry of the natural point-line geometry associated with PG(d, q), if s = q, if the set of points of generates PG(d, q), and if the set of points of not opposite any given point of does not generate PG(d, q). Preparing the classification of all such embeddings, we construct in this paper the classical examples, prove some generalities and show that the dimension d of the projective space belongs to {6,7,8}.     

On Translational Clouds for a Convex Body

For a d-dimensional convex body K let C(K) denote the minimum size of translational clouds for K. That is, C(K) is the minimum number of mutually non-overlapping translates of K which do not overlap K and block all the light rays emanating from any point of K. In this paper we prove the general upper bound . Furthermore, for an arbitrary centrally symmetric d-dimensional convex body S we show . Finally, for the d-dimensional ball B^d we obtain the bounds .     

Lifting-Probleme für Vektorfunktionen und ⊗-Sequenzen

In this article the topologically exact sequences of locally convex spaces are characterized for which for every locally convex space F the map id : FE F Q is a homomorphism, or equivalently, the map id L : FK F E is a topological injection. This is motivated by the problem of lifting Q-valued functions with certain given properties to E-valued functions with the same or slightly weaker properties, which may also be considered as the investigation of parameter dependences of solutions of linear (differential) equations. Applications to partial differential equations and to Fredholm functions are given.     

Continuous Quotients for Lattice Actions on Compact Spaces

Let < SL _n ( ) be a subgroup of finite index, where n 5. Suppose acts continuously on a manifold M, where ₁(M) = ⁿ , preserving a measure that is positive on open sets. Further assume that the induced action on H ¹(M) is non-trivial. We show there exists a finite index subgroup < and a equivariant continuous map : M ⁿ that induces an isomorphism on fundamental group. We prove more general results providing continuous quotients in cases where ₁(M) surjects onto a finitely generated torsion free nilpotent group. We also give some new examples of manifolds with actions.     

Spin Models and Strongly Hyper-Self-Dual Bose-Mesner Algebras

We introduce the notion of hyper-self-duality for Bose-Mesner algebras as a strengthening of formal self-duality. Let denote a Bose-Mesner algebra on a finite nonempty set X. Fix p X, and let and denote respectively the dual Bose-Mesner algebra and the Terwilliger algebra of with respect to p. By a hyper-duality of , we mean an automorphism of such that for all ; and is a duality of . is said to be hyper-self-dual whenever there exists a hyper-duality of . We say that is strongly hyper-self-dual whenever there exists a hyper-duality of which can be expressed as conjugation by an invertible element of . We show that Bose-Mesner algebras which support a spin model are strongly hyper-self-dual, and we characterize strong hyper-self-duality via the module structure of the associated Terwilliger algebra.     

Topological algebras of kernels

Given a locally convex spaceE we define thelocally convex algebra of kernels , in such a way that the set of all its proper closed 2-sided ideals coincides with the set of all closed vector subspaces of ker(h), whereh is a continuous algebra morphism of into _b (E). Moreover,h is a strictly irreducible representation such that every representation: ; _b (F) (F a locally convex space) is of the form =oh, where stands for a continuous isomorphis ofIm(h) into _b (F), for a suitable topology onIm(h).     

The Invariants of the Clifford Groups

The automorphism group of the Barnes-Wall lattice L _m in dimension 2 ^m (m ; 3) is a subgroup of index 2 in a certain Clifford group of structure 2 ₊ ^1+2m . O ⁺(2m,2). This group and its complex analogue of structure .Sp(2m, 2) have arisen in recent years in connection with the construction of orthogonal spreads, Kerdock sets, packings in Grassmannian spaces, quantum codes, Siegel modular forms and spherical designs. In this paper we give a simpler proof of Runge@apos;s 1996 result that the space of invariants for of degree 2k is spanned by the complete weight enumerators of the codes , where C ranges over all binary self-dual codes of length 2k; these are a basis if m k - 1. We also give new constructions for L _m and : let M be the -lattice with Gram matrix . Then L _m is the rational part of M ^m, and = Aut(M^m). Also, if C is a binary self-dual code not generated by vectors of weight 2, then is precisely the automorphism group of the complete weight enumerator of . There are analogues of all these results for the complex group , with doubly-even self-dual code instead of self-dual code.     

Largek-arcs in inversive planes of odd order

An infinite family of largek-arcs in the inversive plane over a finite field GF(q), withq 1 (mod 3),q71 orq {17,23, 27,29,41,47,49,53,59} is constructed.Research supported by G.N.S.A.G.A. of C.N.R., project Applicazioni della matematica per la tecnologia e la società, subproject Calcolo simbolico.     

Interpolation theorems for a family of spanning subgraphs

Let G be a graph with order p, size q and component number . For each i between p – and q, let be the family of spanning i-edge subgraphs of G with exactly components. For an integer-valued graphical invariant if H H is an adjacent edge transformation (AET) implies |(H)-(H^')|1 then is said to be continuous with respect to AET. Similarly define the continuity of with respect to simple edge transformation (SET). Let M _j() and m _j() be the invariants defined by . It is proved that both M _p–() and m _p–(;) interpolate over , if is continuous with respect to AET, and that M _j() and m _j() interpolate over , if is continuous with respect to SET. In this way a lot of known interpolation results, including a theorem due to Schuster etc., are generalized.     

Convex Subgroups of Partially Right-Ordered Groups

We study into the question of whether a partial order can be induced from a partially right-ordered group onto a space of right cosets of w.r.t. some subgroup of . Examples are constructed showing that the condition of being convex for in is insufficient for this. A necessary and sufficient condition (in terms of a subgroup and a positive cone of ) is specified under which an order of can be induced onto . Sufficient conditions are also given. We establish properties of the class of partially right-ordered groups for which is partially ordered for every convex subgroup , and properties of the class of groups such that is partially ordered for every partial right order on and every subgroup that is convex under .     

Efficient Smooth Stratification of an Algebraic Variety in Zero Characteristic and Its Applications

Consider a projective algebraic variety V defined as the set of common zeros of a family of homogeneous polynomials of degree less than d in variables with coefficients from a field k of zero characteristic. We prove that V can be represented as a union (respectively, a disjoint union) of at most (respectively, ) smooth quasiprojective algebraic varieties such that the degrees of these varieties are bounded from above by , where depends only on n. We propose algorithms for constructing regular sequences and sequences of local parameters for irreducible components of V and for computing the dimension of a real variety. The complexity of these algorithms is polynomial in the size of the input and in . Bibliography: 15 titles.     

Sharp Large Deviation Estimates for the Stochastic Heat Equation

We consider the family {X , 0} of solution to the heat equation on [0,T]×[0,1] perturbed by a small space-time white noise, that is _t X = X +b({X })+({X }) . Then, for a large class of Borelian subsets of the continuous functions on [0,T]×[0,1], we get an asymptotic expansion of P({X }A) as 0. This kind of expansion has been handled for several stochastic systems, ranging from Wiener integrals to diffusion processes.     

On Interpolation Sequences of One Class of Functions, Analytic in the Half-Plane

A new criterion of solvability of the interpolation problem f( _n )=b_n in the class of functions f, analytic in the right half-plane and such that there exists c ₁(0;+) such that |f(z)|c ₁exp((c₁|z|)) for all z , where is a positive increasing continuous differentiable function on [0;+), for which (t)+ as t+ and there exists c ₂(0;+) such that