Some numerical experiments with variable-storage quasi-Newton algorithms

This paper describes some numerical experiments with variable-storage quasi-Newton methods for the optimization of some large-scale models (coming from fluid mechanics and molecular biology). In addition to assessing these kinds of methods in real-life situations, we compare an algorithm of A. Buckley with a proposal by J. Nocedal. The latter seems generally superior, provided that careful attention is given to some nontrivial implementation aspects, which concern the general question of properly initializing a quasi-Newton matrix. In this context, we find it appropriate to use a diagonal matrix, generated by an update of the identity matrix, so as to fit the Rayleigh ellipsoid of the local Hessian in the direction of the change in the gradient.Also, a variational derivation of some rank one and rank two updates in Hilbert spaces is given.Work supported in part by FNRS (Fonds National de la Recherche Scientifique), Belgium.     

Proof of the ionization conjecture in a reduced Hartree-Fock model

Summary The ionization conjecture for atomic models states that the ionization energy and maximal excess charge are bounded by constants independent of the nuclear charge. We prove this for the Hartree-Fock model without the exchange term.Oblatum 3-V-1990Work supported in part by the U.S. National Science Foundation grant DMS-9002416     

A note on a theorem of Yamamuro

Conditions are presented which are necessary for the existence of a regular fixed point of aC ¹ map.Work supported in part by NSF Grant No. MCS 77-15509.Work supported in part by ONR Grant No. N0014-75-C-0495 and NSF Grant No. Eng. 76-81058.     

On the solution of concave knapsack problems

We consider a version of the knapsack problem which gives rise to a separable concave minimization problem subject to bounds on the variables and one equality constraint. We characterize strict local miniimizers of concave minimization problems subject to linear constraints, and use this characterization to show that although the problem of determining a global minimizer of the concave knapsack problem is NP-hard, it is possible to determine a local minimizer of this problem with at most O(n logn) operations and 1+[logn] evaluations of the function. If the function is quadratic this algorithm requires at most O(n logn) operations.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by a Fannie and John Hertz Foundation graduate fellowship.     

The horospherical geometry of surfaces in hyperbolic 4-space

We study some geometrical properties associated to the contacts of surfaces with hyperhorospheres inH ₊ ⁴ (−1). We introduce the concepts of osculating hyperhorospheres, horobinormals, horoasymptotic directions and horospherical points and provide conditions ensuring their existence. We show that totally semiumbilical surfaces have orthogonal horoasymptotic directions. Work partially supported by Grant-in-Aid for Scientific Research, JSPS, No. 12874007. Work partially supported by Grant-in-Aid for Scientific Research, JSPS, No. 12000266. Work partially supported by DGCYT grant no. BFM2003-02037.     

Phase transitions in Mandelbrot's percolation process in three dimensions

Summary We study the phase structure and transitions in three-dimensional Mandelbrot percolation—a process which generates random fractal sets. We establish the existence of three distinct phase transitions, and we show that two of these transitions, corresponding to percolation across the initial set by paths and sheets, are discontinuous.Work partially supported by NSF Grant: DMS 8806552Work partially supported by NSF Grant: DMS 8902152     

A Robin formula for the Fekete-Leja transfinite diameter

We generalize the classical Robin formula to higher dimensions. Work supported in part by NSF grant DMS-0300784.     

On the codimensions of the verbally prime P.I. algebras

Razmyslov’s theory of trace identities for the prime P.I. algebrasM _{k, l} is applied to give bounds for the cocharacters and the codimensions of these algebrasM _{k, l}, as well as for the matrix algebrasM _k(E) over the Grassmann algebraE. These bounds are easier to obtain and are better (tighter) than earlier obtained bounds. Work supported by NSF grant DMS 9100258. Work supported by NSF grant DMS 9101488.     

An elementary approach to lower bounds in geometric discrepancy

For eachd≥2, it is possible to placen points ind-space so that, given any two-coloring of the points, a half-space exists within which one color outnumbers the other by as much ascn ^1/2−1/2d , for some constantc>0 depending ond. This result was proven in a slightly weaker form by Beck and the bound was later tightened by Alexander. It was recently shown to be asymptotically optimal by Matoušek. We present a proof of the lower bound, which is based on Alexander's technique but is technically simpler and more accessible. We present three variants of the proof, for three diffrent cases, to provide more intuitive insight into the “large-discrepancy” phenomenon. We also give geometric and probabilistic interpretations of the technique. Work by Bernard Chazelle has been supported in part by NSF Grant CCR-90-02352 and The Geometry Center, University of Minnesota, an STC funded by NSF, DOE, and Minnesota Technology, Inc. Work by Jiří Matoušek has been supported by Charles University Grant No. 351, by Czech Republic Grant GAČR 201/93/2167 and in part by DIMACS. Work by Micha Sharir has been supported by NSF Grant CCR-91-22103, by a Max-Planck Research Award, and by grants from the U.S.-Israeli Binational Science Foundation, the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

Analysis of heuristics for the design of tree networks

We analyze the tour partitioning heuristics for the Capacitated Minimum Spanning Tree problem. Lower bounds for the worst-case performance ratios of these heuristics are obtained by using worst-case examples. We also generalize the heuristics to the multi-center case with the same worst-case bounds.The work of the first author was supported by a Dean Summer Research Grant from Owen Graduate School of Management, Vanderbilt University.Work done in part in the Department of Industrial Engineering and Operations Research at Columbia University.The work of the last two authors was supported in part by ONR contract N00014-90-J-1649, NSF contract DDM-8922712 and the Center for Telecommunications Research under NSF contract CDR 84-21402.     

Polynomial systems with few real zeroes

We study some systems of polynomials whose support lies in the convex hull of a circuit, giving a sharp upper bound for their numbers of real solutions. This upper bound is non-trivial in that it is smaller than either the Kouchnirenko or the Khovanskii bounds for these systems. When the support is exactly a circuit whose affine span is ℤⁿ, this bound is 2n+1, while the Khovanskii bound is exponential in n². The bound 2n+1 can be attained only for non-degenerate circuits. Our methods involve a mixture of combinatorics, geometry, and arithmetic. Part of work done at MSRI was supported by NSF grant DMS-9810361. Work of Sottile is supported by the Clay Mathematical Institute. Sottile and Bihan were supported in part by NSF CAREER grant DMS-0134860. Bertrand is supported by the European research network IHP-RAAG contract HPRN-CT-2001-00271.     

Diameter,width, closest line pair,and parametric searching

We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, anO(n ^1+ε) algorithm for computing the diameter of a point set in 3-space, anO(^8/5+ε) algorithm for computing the width of such a set, and onO(n ^8/5+ε) algorithm for computing the closest pair in a set ofn lines in space. All these algorithms are deterministic. Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.     

A class of martingales with non-symmetric limit distributions

Summary A class of non-pathological martingales is exhibited to which current martingale central limit theory does not apply. The problem consists in the convergence of the normalized sums of squares being only in distribution. The class is that of degenerate U-statistics.This work was done while the first two authors were on Sabbatical leave at the Technion.Work supported in part by National Research Council of Canada, Grant No. A-9068Work supported in part by National Research Council of Canada, Grant No. A-9076     

SD-splittings for Some Bordered 3-Manifolds

In the present paper, we characterize the bordered 3-manifolds with genus 1 D-splittings and SD-splittings. We also describe a minimal genus SD-splitting for a handlebody and surface × I.     

A robust sequential quadratic programming method

The sequential quadratic programming method developed by Wilson, Han and Powell may fail if the quadratic programming subproblems become infeasible, or if the associated sequence of search directions is unbounded. This paper considers techniques which circumvent these difficulties by modifying the structure of the constraint region in the quadratic programming subproblems. Furthermore, questions concerning the occurrence of an unbounded sequence of multipliers and problem feasibility are also addressed.Work supported in part by the National Science Foundation under Grant No. DMS-8602399 and by the Air Force Office of Scientific Research under Grant No. ISSA-860080.Work supported in part by the National Science Foundation under Grant No. DMS-8602419.     

Reflections in submanifolds

This is a study of geodesic symmetries of a Riemannian manifold with respect to a submanifold. We analyze the significance of the property to be volume-preserving, isometric or preserving the mean curvature of the tubular neighborhoods.Work supported in part by the National Science Foundation and the Max-Planck-Institut für Mathematik, Bonn.     

Relative mean curvature configurations for surfaces in ℝ<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>, <Emphasis Type="Italic">n</Emphasis> ≥ 5

We define the relative mean curvature directions on surfaces immersed in ℝⁿ, n ≥ 4, generalizing the concept of mean curvature directions for surfaces in 4-space studied by Mello. We obtain their differential equations and study their corresponding generic configurations. *Work partially supported by DGCYT grant no. MTM2004-03244 and Unimontes-BR. †Work partially supported by DGCYT grant no. MTM2004-03244. ‡Work partially supported by DGCYT grant no. BFM2003-0203.     

Large deviations without principle: join the shortest queue

We develop a methodology for studying “large deviations type” questions. Our approach does not require that the large deviations principle holds, and is thus applicable to a large class of systems. We study a system of queues with exponential servers, which share an arrival stream. Arrivals are routed to the (weighted) shortest queue. It is not known whether the large deviations principle holds for this system. Using the tools developed here we derive large deviations type estimates for the most likely behavior, the most likely path to overflow and the probability of overflow. The analysis applies to any finite number of queues. We show via a counterexample that this system may exhibit unexpected behavior Work of the first author was performed in part while visiting the Technion. Work of the second author was performed in part while visiting the Vrije Universiteit, Amsterdam, and was supported in part by Fund for the promotion of research at the Technion.     

Quadrature formulae on half-infinite intervals

We develop two classes of quadrature rules for integrals extended over the positive real axis, assuming given algebraic behavior of the integrand at the origin and at infinity. Both rules are expressible in terms of Gauss-Jacobi quadratures. Numerical examples are given comparing these rules among themselves and with recently developed quadrature formulae based on Bernstein-type operators.Work supported, in part, by the National Science Foundation under grant CCR-8704404.     

Duality for Semiantichains and Unichain Coverings in Products of Special Posets

Saks and West conjectured that for every product of partial orders, the maximum size of a semiantichain equals the minimum number of unichains needed to cover the product. We prove the case where both factors have width 2. We also use the characterization of product graphs that are perfect to prove other special cases, including the case where both factors have height 2. Finally, we make some observations about the case where both factors have dimension 2. Work supported in part by NSA Award No. H98230-06-1-0065.