Updating of conjugate direction matrices using members of Broyden's family

Many iterative algorithms for optimization calculations use a second derivative approximation,B say, in order to calculate the search directiond = –B ^–1f(x). In order to avoid invertingB we work with matricesZ, whose columns satisfy the conjugacy relationsZ ^T BZ = I. We present an update ofZ that is compatible with members of the Broyden family that generate positive definite second derivative approximations. The algorithm requires only 3n ²+O(n) flops for the update ofZ and the calculation ofd. The columns of the resultantZ matrices have interesting conjugacy and orthogonality properties with respect to previous second derivative approximations and function gradients, respectively. The update also provides a simple proof of Dixon's theorem. For the BFGS method we adapt the algorithm in order to obtain a null space method for linearly constrained calculations.     

Modifying the BFGS update by a new column scaling technique

LetB be a positive definite symmetric approximation to the second derivative matrix of the objective function of a minimization calculation. We study modifications of the BFGS method that apply a scaling technique to the columns of a conjugate direction matrixZ satisfyingZ ^T BZ = I. For a simple scaling technique similar to the ones considered by Powell (1987) and (1989) we show that, due to a two iteration cycle, linear convergence can occur when the method is applied to a quadratic function and Wolfe's line search is employed, although for exact line searches quadratic termination can be proved. We then suggest a different scaling technique that prevents certain columns thought to contain important curvature information from being scaled. For this algorithm we prove global and superlinear convergence and demonstrate the superiority of our method over the BFGS formula on a range of illconditioned optimization problems. Moreover, we present an implementation of our algorithm that requires only 3n ² +O(n) multiplications per iteration.     

Properties of a representation of a basis for the null space

Given a rectangular matrixA(x) that depends on the independent variablesx, many constrained optimization methods involve computations withZ(x), a matrix whose columns form a basis for the null space ofA ^T(x). WhenA is evaluated at a given point, it is well known that a suitableZ (satisfyingA ^T Z = 0) can be obtained from standard matrix factorizations. However, Coleman and Sorensen have recently shown that standard orthogonal factorization methods may produce orthogonal bases that do not vary continuously withx; they also suggest several techniques for adapting these schemes so as to ensure continuity ofZ in the neighborhood of a given point.This paper is an extension of an earlier note that defines the procedure for computingZ. Here, we first describe howZ can be obtained byupdating an explicit QR factorization with Householder transformations. The properties of this representation ofZ with respect to perturbations inA are discussed, including explicit bounds on the change inZ. We then introduceregularized Householder transformations, and show that their use implies continuity of the full matrixQ. The convergence ofZ andQ under appropriate assumptions is then proved. Finally, we indicate why the chosen form ofZ is convenient in certain methods for nonlinearly constrained optimization.The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AM03-76SF00326, PA No. DE-AT03-76ER72018; the National Science Foundation Grants MCS-7926009 and ECS-8312142; the Office of Naval Research Contract N00014-75-C-0267; and the U.S. Army Research Office Contract DAAG29-84-K-0156.The research of G.W. Stewart was supported by the Air Force Office of Scientific Research Contract AFOSR-82-0078.     

The Algebra of Flows in Graphs

We define a contravariant functorKfrom the category of finite graphs and graph morphisms to the category of finitely generated graded abelian groups and homomorphisms. For a graphX, an abelian groupB, and a nonnegative integerj, an element of Hom(K^j(X), B) is a coherent family ofB-valued flows on the set of all graphs obtained by contracting some (j − 1)-set of edges ofX; in particular, Hom(K¹(X), ) is the familiar (real) “cycle-space” ofX. We show thatK ^· (X) is torsion-free and that its Poincaré polynomial is the specializationt^{n − k}T_X(1/t, 1 + t) of the Tutte polynomial ofX(hereXhasnvertices andkcomponents). Functoriality ofK ^· induces a functorial coalgebra structure onK ^· (X); dualizing, for any ringBwe obtain a functorialB-algebra structure on Hom(K ^· (X), B). WhenBis commutative we present this algebra as a quotient of a divided power algebra, leading to some interesting inequalities on the coefficients of the above Poincaré polynomial. We also provide a formula for the theta function of the lattice of integer-valued flows inX, and conclude with 10 open problems.     

The Superlinear Convergence of a Modified BFGS-Type Method for Unconstrained Optimization

The BFGS method is the most effective of the quasi-Newton methods for solving unconstrained optimization problems. Wei, Li, and Qi [16] have proposed some modified BFGS methods based on the new quasi-Newton equation B _k+1 s _k = y* _k , where y* _k is the sum of y _k and A _k s _k, and A _k is some matrix. The average performance of Algorithm 4.3 in [16] is better than that of the BFGS method, but its superlinear convergence is still open. This article proves the superlinear convergence of Algorithm 4.3 under some suitable conditions.     

Asymptotics of heavy atoms in high magnetic fields: I. Lowest landau band regions

The ground state energy of an atom of nuclear charge Ze in a magnetic field B is evaluated exactly to leading order as Z → ∞. In this and a companion work (see [28]) we show that there are five regions as Z → ∞: B < Z^4/3, B ～ Z^4/3, Z^4/3 < B < Z³, B ～ Z³, B > Z³. Regions 1, 2, 3, and 4 (and conceivably 5) are relevant for neutron stars. Different regions have different physics and different asymptotic theories. Regions 1, 2, and 3 are described by a simple density functional theory of the semiclassical Thomas-Fermi form. Here we concentrate mainly on regions 4 and 5 which cannot be so described, although 3, 4, and 5 have the common feature (as shown here) that essentially all electrons are in the lowest Landau band. Region 5 does have, however, a simple non-classical density functional theory (which can be solved exactly). Region 4 does not, but, surprisingly, it can be described by a novel density matrix functional theory. © 1994 John Wiley & Sons, Inc.     

Zolotarevω-Polynomials inWH[0, 1]

The main result of this paper characterizes generalizationsof Zolotarev polynomials as extremal functions in the Kolmogorov–Landauproblemwhereω(t) is a concave modulus of continuity,r, m: 1?m?r,are integers, andB?B₀(r, m, ω). We show that theextremal functionsZ_Bhaver+1 points of alternance andthe full modulus of continuity ofZ^(r)_B: ω(Z^(r)_B; t)=ω(t) for allt∈[0, 1]. This generalizesthe Karlin's result on the extremality of classical Zolotarevpolynomials in the problem () forω(t)=tand allB?B_r.     

Sur Les Groupes D’Homotopie Des Espaces Dont La Cohomologie Modulo 2 Est Nilpotente

The main object of this note is to prove the following generalisation of a theorem of Serre. A simply connected space of finite type whose mod. 2 cohomology is nilpotent (and non-trivial) has infinitely many homotopy groups which are not of odd torsion. Incidentally we show that for every fibrationF( _→ ^ί )E ( _→ ^p )B, satisfying certain mild conditions, the following holds. If a classx in the mod. 2 cohomology ofE belongs to the kernel ofi*, then some power ofx belongs to the ideal generated by the image underp* of the mod. 2 reduced cohomology ofB.      

Zolotarevω-Polynomials inWH[0, 1]

The main result of this paper characterizes generalizationsof Zolotarev polynomials as extremal functions in the Kolmogorov–Landauproblem

Full-size image

whereω(t) is a concave modulus of continuity,r, m: 1mr,are integers, andBB₀(r, m, ω). We show that theextremal functionsZ_Bhaver+1 points of alternance andthe full modulus of continuity ofZ^(r)_B: ω(Z^(r)_B; t)=ω(t) for allt[0, 1]. This generalizesthe Karlin's result on the extremality of classical Zolotarevpolynomials in the problem () forω(t)=tand allBB_r.     

A double-dual characterization of separable Banach spaces containingl 1

It is proved that a separable Banach spaceB contains a subspace isomorphic tol ¹ if (and only if) there exists an element inB**, the double-dual ofB, which is not a weak* limit of a sequence of elements inB. ConsequentlyB contains an isomorph ofl ¹ if (and only if) the cardinality ofB** is greater than that of the continuum. The research of the second-named author was partially supported by NSF — GP — 30798X1     

On Sequential Fixed-Size Confidence Regions for the Mean Vector

In order to construct a fixed-size confidence region for the mean vector of an unknown distribution functionF, a new purely sequential sampling strategy is proposed first. For this new procedure, under some regularity conditions onF, the coverage probability is shown (Theorem 2.1) to be at least (1−α)−Bα²d²+o(d²) asd→0, where (1−α) is the preassigned level of confidence,Bis an appropriate functional ofF, and 2dis the preassigned diameter of the proposed spherical confidence region for the mean vector ofF. An accelerated version of the stopping rule is also provided with the analogous second-order characteristics (Theorem 3.1). In the special case of ap-dimensional normal random variable, analogous purely sequential and accelerated sequential procedures as well as a three-stage procedure are briefly introduced together with their asymptotic second-order characteristics.     

Integer programming and convex analysis: Intersection cuts from outer polars

Recently a new, geometrically motivated approach was proposed [1] for integer programming, based on generating intersection cuts from some convex setS whose interior contains the linear programming optimum but no feasible integer point. Larger sets tend to produce stronger cuts, and in this paper convex analysis is used to construct sets as large as possible within the above requirements. Information is generated from all problem constraints within a unit cubeK containing The key concept is that of outer polars, viewed as maximal convex extensions of the ballB circumscribingK, relative to the problem constraints. The outer polarF ^* of the feasible setF overB is shown to be a convex set whose boundary contains all feasible vertices ofK, and whose interior contains no feasible integer point. The existence of a dual correspondence betweenF andF ^*, and the fact that polarity is inclusion-reversing, leads to a dualization of operations onF. As one possible procedure based on this approach, we construct a generalized intersection cut, that can be strengthened whenever some vertex ofF is cut off. This makes it possible to fruitfully combine intersection cuts with implicit enumeration or branch-and-bound. While valid for arbitrary integer programs, the theory developed here is relevant primarily to (pure or mixed-integer) 0–1 problems. Other topics discussed include: generalized polars, intersection cuts from related problems, connections with asymptotic theory.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands.The research underlying this paper was partially supported by the National Science Foundation under grant GP-31699 and by the Office of Naval Research under contract N00014-67-A-0314-0007 NR 047-048.     

Inference on superimposed subcritical Galton-Watson processes with immigration

Summary In this paper we consider the superimposed processZ generated by two independent subcritical Galton-Watson processesX ₁ andX ₂, with immigration, by the relationZ=X ₁ +X ₂. The seemingly second order autoregressive relation, that is identified inZ, is exploted towards proposing CAN estimators for the parameters ofZ,X ₁ andX ₂, based on only a partial realisation ofZ, using time series techniques. The results of this paper are motivated by a time series approach for studying specific branching processes due to Venkataraman (1982,Adv. Appl. Prob.,14, 1–20).     

On Kendall's Process

LetZ₁, …, Z_nbe a random sample of sizen?2 from ad-variate continuous distribution functionH, and letV_i, nstand for the proportion of observationsZ_j,j≠i, such thatZ_j?Z_icomponentwise. The purpose of this paper is to examine the limiting behavior of the empirical distribution functionK_nderived from the (dependent) pseudo-observationsV_i, n. This random quantity is a natural nonparametric estimator ofK, the distribution function of the random variableV=H(Z), whose expectation is an affine transformation of the population version of Kendall's tau in the cased=2. Since the sample version ofτis related in the same way to the mean ofK_n, Genest and Rivest (1993,J. Amer. Statist. Assoc.) suggested that[formula]be referred to as Kendall's process. Weak regularity conditions onKandHare found under which this centered process is asymptotically Gaussian, and an explicit expression for its limiting covariance function is given. These conditions, which are fairly easy to check, are seen to apply to large classes of multivariate distributions.     

An extension theorem for separable Banach spaces

We construct a totally disconnected ω^*, norming subsetF of the unit ballB ^* of an arbitrary separable Banach space,X, and an operator fromC(F) toC(B^*) that “amost” commutes with the natural embeddings ofX. This is used to give a new proof of Milutin's theorem and to prove some new results on complemented subspaces ofC[0, 1] with separable dual. In particular we show that a complemented subspace ofC(ω^ω), is either isomorphic toC(ω^ω) or toc _u.     

A pseudo Newton-Raphson method for function minimization

A pseudo Newton-Raphson algorithm for function minimization is presented. As in all such algorithms, an estimate of the inverse Hessian is calculated. In this case, the estimate is of the formXZX ^T , whereZ is a diagonal matrix; and this feature permits the use of the simple procedures to maintain the positive definiteness ofZ, and hence of the restriction ofXZX ^T to the range ofX. The algorithm is shown to have finite convergence for quadratic functions and asymptotic convergence for a fairly general class of functions. Some numerical results are presented, and the extension of the algorithm to deal with linear equality and inequality constraints is briefly discussed.R. Mamen acknowledges with gratitude the financial support afforded by an Athlone Fellowship and a National Research Council of Canada Post-Graduate Bursary. Dr. S. C. Chuang made useful comments on some of the proofs. Some of the results are closely related to those of Allwright (Ref. 1).     

Discrete characterization of the Paley-Wiener space with several variables

In this paper, we obtain a characterization of the Paley-Wiener space with several variables, which is denoted byB _{π, p} (R ⁿ ), 1≤p<∞, i.e., for 1<p<∞,B _{π, p} (R ⁿ ) is isomorphic tol _p (Z ⁿ ), and forp=1,B _{π, 1} (R ⁿ ) is isomorphic to the discrete Hardy space with several variables, which is denoted byH(Z ⁿ ). This project is supported by the National Natural Science Foundation of China (19671012) and Doctoral Programme Institution of Higher Education Foundation of Chinese Educational Committee and supported by Youth Foundation of Sichuan.     

On the reconstruction of boolean algebras from their automorphism groups

A Boolean algebraB is called faithful, if for every direct summandB ₁ ofB: ifB ₁ is rigid, (that is, it does not have any automorphisms other than the identity), then there isB ₂ such thatBB ₁×B ₁×B ₁×B ₂. LetB be a complete Boolean algebra, thenB can be uniquely represented asBB ^R×B ^D×B ^D×B ^F, whereB ^R,B ^D,B ^F are pairwise totally different, (that is, no two of them have non-zero isomorphic direct summands),B ^R,B ^D are rigid andB ^F is faithful. Aut(B) denotes the automorphism group ofB.I thank the NSF for supporting this research by a grant.     

Recognition problems for special classes of polynomials in 0–1 variables

This paper investigates the complexity of various recognition problems for pseudo-Boolean functions (i.e., real-valued functions defined on the unit hypercubeB ⁿ = {0, 1} ⁿ ), when such functions are represented as multilinear polynomials in their variables. Determining whether a pseudo-Boolean function (a) is monotonic, or (b) is supermodular, or (c) is threshold, or (d) has a unique local maximum in each face ofB ⁿ , or (e) has a unique local maximum inB ⁿ , is shown to be NP-hard. A polynomial-time recognition algorithm is presented for unimodular functions, previously introduced by Hansen and Simeone as a class of functions whose maximization overB ⁿ is reducible to a network minimum cut problem.     

Hypergroup deformations and Markov chains

Persi Diaconis and Phil Hanlon in their interesting paper⁽⁴⁾ give the rates of convergence of some Metropolis Markov chains on the cubeZ ^d (2). Markov chains on finite groups that are actually random walks are easier to analyze because the machinery of harmonic analysis is available. Unfortunately, Metropolis Markov chains are, in general, not random walks on group structure. In attempting to understand Diaconis and Hanlon's work, the authors were led to the idea of a hypergroup deformation of a finite groupG, i.e., a continuous family of hypergroups whose underlying space isG and whose structure is naturally related to that ofG. Such a deformation is provided forZ ^d (2), and it is shown that the Metropolis Markov chains studied by Diaconis and Hanlon can be viewed as random walks on the deformation. A direct application of the Diaconis-Shahshahani Upper Bound Lemma, which applies to random walks on hypergroups, is used to obtain the rate of convergence of the Metropolis chains starting at any point. When the Markov chains start at 0, a result in Diaconis and Hanlon⁽⁴⁾ is obtained with exactly the same rate of convergence. These results are extended toZ ^d (3).Research supported in part by the Office of Research and Sponsored Programs, University of Oregon.