A globally and quadratically convergent affine scaling method for linearℓ 1 problems

Recently, various interior point algorithms related to the Karmarkar algorithm have been developed for linear programming. In this paper, we first show how this interior point philosophy can be adapted to the linear ₁ problem (in which there are no feasibility constraints) to yield a globally and linearly convergent algorithm. We then show that the linear algorithm can be modified to provide aglobally and ultimatelyquadratically convergent algorithm. This modified algorithm appears to be significantly more efficient in practise than a more straightforward interior point approach via a linear programming formulation: we present numerical results to support this claim.This paper was presented at the Third SIAM Conference on Optimization, in Boston, April 1989.Research partially supported by the Applied Mathematical Sciences Research Program (KC-04-02) of the Office of Energy Research of the U.S. Department of Energy under grant DE-FG02-86ER25013.A000, by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University, and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.Research partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute, Cornell University and by the Computational Mathematics Program of the National Science Foundation under grant DMS-8706133.     

Properties of algebras of primary order with one ternary Mal'tsev operation

We study properties of free solvable p-algebras and of p-algebras of primary orders. It is shown that a free solvable p-algebra is embeddable in a subdirect product of algebras with these orders. An example of a simple non-Abelian p-algebra of a primary order is constructed, and we also give an example of a solvable non-nilpotent p-algebra of any finite order not less than 6.Translated fromAlgebra i Logika, Vol. 34, No. 2, pp. 132-141, March-April, 1995.Partially supported by the Russian Foundation for Fundamental Research, the Program Universities of Russia, and the Russian Ministry of Science, Higher Schools of Learning, and Technical Policy, grant No. 2-11-1-2.     

Extremal problems of Bloch function spaces

Letf be analytic in a hyperbolic region . The Bloch constant _f off is defined by , where (z)|dz| is the Poincaré metric in . Suppose is hyperbolic and where . Then for allf withf() , we have _f 1/(). In this paper we study the extremal functions defined by _f =1/() and the existence of those functions.Supported by the National Natural Science Foundation of China.     

On the growth of sums of independent random variables

Some estimates of the growth of sums of independent random variables almost surely are established without any moment conditions. Bibliography: 6 titles.Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 294, 2002, pp. 158–164.This research was partially supported by the Russian Foundation for Basic Research, grant 02-01-00779, and by the Program Leading Scientific Schools, grant 00-15-96019.Translated by V. V. Petrov.     

A class of formally normal operators

A densely closed operator N given in Hilbert space is called formally normal if D(N) D(N*)and Nf = N*f for allf D(N). In the present work the necessary and sufficient conditions for a formally normal operator, possessing a bounded inverse, to have a normal extension in the original Hilbert space are given. The result obtained is analogous to a result of M. I. Vishik [1], relating to the case of a symmetric operator [7 References].Translated from Matematicheskie Zametki, Vol. 2, No. 6, pp. 605–614, December, 1967.     

Thermodynamics and Hydrodynamics (Statistical Foundations): 3. Hydrodynamic Equations

We show that all the hydrodynamic equations can be obtained from the BBGKY hierarchy. The theory is constructed by expanding the distribution functions in series in a small parameter = R/L 10^–8, where R 10^–7cm is the radius of the correlation sphere and L is the characteristic macroscopic dimension. We also show that in the zeroth-order approximation with respect to this parameter, the BBGKY hierarchy implies the local equilibrium and the transport equations for the ideal Euler fluid; in the first-order approximation with respect to , the BBGKY hierarchy implies the hydrodynamic equations for viscous fluids. Moreover, we prove that the intrinsic energy flux must include both the kinetic energy flux proportional to the temperature gradient and the potential energy flux proportional to the density gradient. We show that the hydrodynamic equations hold for t 10^–12s and L R 10^–7cm.     

Recognizing Berge Graphs

A graph is Berge if no induced subgraph of G is an odd cycle of length at least five or the complement of one. In this paper we give an algorithm to test if a graph G is Berge, with running time O(|V (G)|⁹). This is independent of the recent proof of the strong perfect graph conjecture.* Currently this author is a Clay Mathematics Institute Research Fellow.** Supported by NSF grant DMI-0352885 and ONR grant N00014-97-1-0196. Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912. Supported by EPSRC grant GR/R35629/01.     

Worst case asymptotics for some classical optimization problems

We provide a simple and natural method for obtaining the worst case asymptotics of some of the classical problems in combinatorial optimization and operations research. Worst case asymptotics for the minimal spanning tree, shortest tour, and minimal matching onn points are found. The key simplifying idea involves consideration of the associated boundary processes. The general approach considered here also handles the case of power weighted edges.Research supported in part by NSA grant MDA904-95-H-1005.     

Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem

We provide positive and negative results concerning the standard method of identifying a hidden subgroup of a nonabelian group using a quantum computer.* Supported in part by NSF grants CCR-9820931 and CCR-0208929. Supported in part by NSF CAREER grant 0049092, the NSF Institute for Quantum Information, the Charles Lee Powell Foundation, and the Mathematical Sciences Research Institute. Supported in part by an NSF Mathematical Sciences Postdoctoral Research Fellowship and NSF grant DMS-0301320.§ Supported in part by DARPA QUIST grant F30602-01-2-0524, ARO grant DAAD19-03-1-0082, and NSF ITR grant CCR-0121555.     

RUC-decompositions in symmetric operator spaces

We show that ifX is a Banach space of type 2 andG is a compact Abelian group, then any system of eigenvectors {x }_G (with respect to a strongly continuous representation ofG onX) is an RUC-system. As an application, we exhibit new examples of RUC-bases in certain symmetric spaces of measurable operators.Research supported by the Australian Research Council