Non-amenable finitely presented torsion-by-cyclic groups

Abstract. – We construct a finitely presented non-amenable group without free non-cyclic subgroups thus providing a finitely presented counterexample to von Neumann’s problem. Our group is an extension of a group of finite exponent n ≫ 1 by a cyclic group, so it satisfies the identity [x,y] ⁿ = 1. Manuscrit reĉu le 8 février 2001. RID="*" ID="*"Both authors were supported in part by the NSF grant DMS 0072307. In addition, the research of the first author was supported in part by the Russian Fund for Basic Research 99-01-00894 and by the INTAS grant, the research of the second author was supported in part by the NSF grant DMS 9978802.     

Attractor for lattice system of dissipative Zakharov equation

We consider the asymptotic behavior of solutions of an infinite lattice dynamical system of dissipative Zakharov equation. By introducing new weight inner product and norm in the space and establishing uniform estimate on ＂Tail End＂ of solutions, we overcome some difficulties caused by the lack of Sobolev compact embedding under infinite lattice system, and prove the existence of the global attractor; then by using element decomposition and the covering property of a polyhedron in the finite-dimensional space, we obtain an upper bound for the Kolmogorov ε-entropy of the global attractor; finally, we present the upper semicontinuity of the global attractor.     

The hypertoric intersection cohomology ring

We present a functorial computation of the equivariant intersection cohomology of a hypertoric variety, and endow it with a natural ring structure. When the hyperplane arrangement associated with the hypertoric variety is unimodular, we show that this ring structure is induced by a ring structure on the equivariant intersection cohomology sheaf in the equivariant derived category. The computation is given in terms of a localization functor which takes equivariant sheaves on a sufficiently nice stratified space to sheaves on a poset. T. Braden’s research was supported in part by NSF grant DMS-0201823. N. Proudfoot’s research was supported in part by an NSF Postdoctoral Research Fellowship and NSF grant DMS-0738335.     

Dynamics of Decision Making in Animal Group Motion

We analyze a continuous-time model of a multi-agent system motivated by simulation studies on dynamics of decision making in animal groups in motion. Each individual moves at constant speed in the plane and adjusts its heading in response to relative headings of others in the population. The population includes two subgroups that are “informed” such that individuals in each subgroup have a preferred direction of motion. The model exhibits fast and slow time scales allowing for a reduction in the dimension of the problem. The stable solutions for the reduced model correspond to compromise by individuals with conflicting preferences. We study the global phase space for the proposed reduced model by computing equilibria and exploring stability and bifurcations. B. Nabet’s and N.E. Leonard’s work is supported in part by AFOSR grant FA9550-07-1-0-0528 and ONR grants N00014-02-1-0826 and N00014-04-1-0534. I.D. Couzin’s work was supported by the Royal Society, Balliol College and EPSRC grants GR/S04765/01 and GR/T11234/01, a Searle Scholar Award and DARPA grant HR001-05-1-0057. S.A. Levin’s work was supported in part by DARPA grant HR0011-05-1-0057 and NSF grant EF-0434319.     

Recognizing underlying sparsity in optimization

Exploiting sparsity is essential to improve the efficiency of solving large optimization problems. We present a method for recognizing the underlying sparsity structure of a nonlinear partially separable problem, and show how the sparsity of the Hessian matrices of the problem’s functions can be improved by performing a nonsingular linear transformation in the space corresponding to the vector of variables. A combinatorial optimization problem is then formulated to increase the number of zeros of the Hessian matrices in the resulting transformed space, and a heuristic greedy algorithm is applied to this formulation. The resulting method can thus be viewed as a preprocessor for converting a problem with hidden sparsity into one in which sparsity is explicit. When it is combined with the sparse semidefinite programming relaxation by Waki et al. for polynomial optimization problems, the proposed method is shown to extend the performance and applicability of this relaxation technique. Preliminary numerical results are presented to illustrate this claim. S. Kim’s research was supported by Kosef R01-2005-000-10271-0. M. Kojima’s research was supported by Grant-in-Aid for Scientific Research on Priority Areas 16016234.     

Analysis of two-sample censored data using a semiparametric mixture model

In this article we study a semiparametric mixture model for the two-sample problem with right censored data. The model implies that the densities for the continuous outcomes are related by a parametric tilt but otherwise unspecified. It provides a useful alternative to the Cox （1972） proportional hazards model for the comparison of treatments based on right censored survival data. We propose an iterative algorithm for the semiparametric maximum likelihood estimates of the parametric and nonparametric components of the model. The performance of the proposed method is studied using simulation. We illustrate our method in an application to melanoma.     

Exact Controllability of a Piezoelectric Body. Theory and Numerical Simulation

We study the exact controllability of a three-dimensional body made of a material whose constitutive law introduces an elasticity-electricity coupling. We show that a coupled elastic-electric control acting on the whole boundary of the body drives the system to rest after time large enough. Two-dimensional numerical experiments suggest that controllability can still be achieved by relaxing this restrictive condition using either both controls on a reduced support or elastic control alone. B. Miara supported by the European project “INTAS, Research Project for South Caucasian Republics 06-1000017-8886”. A. Münch partially supported by grants ANR-05-JC-0182-01 and ANR-07-JC-1832-84.     

Examples of dual behaviour of Newton-type methods on optimization problems with degenerate constraints

We discuss possible scenarios of behaviour of the dual part of sequences generated by primal-dual Newton-type methods when applied to optimization problems with nonunique multipliers associated to a solution. Those scenarios are: (a) failure of convergence of the dual sequence; (b) convergence to a so-called critical multiplier (which, in particular, violates some second-order sufficient conditions for optimality), the latter appearing to be a typical scenario when critical multipliers exist; (c) convergence to a noncritical multiplier. The case of mathematical programs with complementarity constraints is also discussed. We illustrate those scenarios with examples, and discuss consequences for the speed of convergence. We also put together a collection of examples of optimization problems with constraints violating some standard constraint qualifications, intended for preliminary testing of existing algorithms on degenerate problems, or for developing special new algorithms designed to deal with constraints degeneracy. Research of the first author is supported by the Russian Foundation for Basic Research Grants 07-01-00270, 07-01-00416 and 07-01-90102-Mong, and by RF President’s Grant NS-9344.2006.1 for the support of leading scientific schools. The second author is supported in part by CNPq Grants 301508/2005-4, 490200/2005-2 and 550317/2005-8, by PRONEX–Optimization, and by FAPERJ Grant E-26/151.942/2004.     

Percolation on random Johnson–Mehl tessellations and related models

We make use of the recent proof that the critical probability for percolation on random Voronoi tessellations is 1/2 to prove the corresponding result for random Johnson–Mehl tessellations, as well as for two-dimensional slices of higher-dimensional Voronoi tessellations. Surprisingly, the proof is a little simpler for these more complicated models. B. Bollobás’s research was supported in part by NSF grants CCR-0225610 and DMS-0505550 and ARO grant W911NF-06-1-0076. O. Riordan’s research was supported by a Royal Society Research Fellowship.     

A measurable-group-theoretic solution to von Neumann’s problem

We give a positive answer, in the measurable-group-theory context, to von Neumann’s problem of knowing whether a non-amenable countable discrete group contains a non-cyclic free subgroup. We also get an embedding result of the free-group von Neumann factor into restricted wreath product factors. D. Gaboriau’s research was supported by CNRS. R. Lyons’ research was supported partially by NSF grant DMS-0705518 and Microsoft Research.     

Monte Carlo and quasi-Monte Carlo sampling methods for a class of stochastic mathematical programs with equilibrium constraints

In this paper, we consider a class of stochastic mathematical programs with equilibrium constraints introduced by Birbil et al. (Math Oper Res 31:739–760, 2006). Firstly, by means of a Monte Carlo method, we obtain a nonsmooth discrete approximation of the original problem. Then, we propose a smoothing method together with a penalty technique to get a standard nonlinear programming problem. Some convergence results are established. Moreover, since quasi-Monte Carlo methods are generally faster than Monte Carlo methods, we discuss a quasi-Monte Carlo sampling approach as well. Furthermore, we give an example in economics to illustrate the model and show some numerical results with this example. The first author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science and SRF for ROCS, SEM. The second author’s work was supported in part by the United Kingdom Engineering and Physical Sciences Research Council grant. The third author’s work was supported in part by the Scientific Research Grant-in-Aid from Japan Society for the Promotion of Science.     

Some weak fragments of Martin’s axiom related to the rectangle refining property

We introduce the anti-rectangle refining property for forcing notions and investigate fragments of Martin’s axiom for ℵ₁ dense sets related to the anti-rectangle refining property, which is close to some fragment of Martin’s axiom for ℵ₁ dense sets related to the rectangle refining property, and prove that they are really weaker fragments. T. Yorioka was partially supported by Grant-in-aids for Scientific Research No.16340022 and No.18840022.     

Polynomiality of primal-dual affine scaling algorithms for nonlinear complementarity problems

This paper provides an analysis of the polynomiality of primal-dual interior point algorithms for nonlinear complementarity problems using a wide neighborhood. A condition for the smoothness of the mapping is used, which is related to Zhu’s scaled Lipschitz condition, but is also applicable to mappings that are not monotone. We show that a family of primal-dual affine scaling algorithms generates an approximate solution (given a precision ε) of the nonlinear complementarity problem in a finite number of iterations whose order is a polynomial ofn, ln(1/ε) and a condition number. If the mapping is linear then the results in this paper coincide with the ones in Jansen et al., SIAM Journal on Optimization 7 (1997) 126–140. Research supported in part by Grant-in-Aids for Encouragement of Young Scientists (06750066) from the Ministry of Education, Science and Culture, Japan. Research supported by Dutch Organization for Scientific Research (NWO), grant 611-304-028     

On projected newton barrier methods for linear programming and an equivalence to Karmarkar’s projective method

Interest in linear programming has been intensified recently by Karmarkar’s publication in 1984 of an algorithm that is claimed to be much faster than the simplex method for practical problems. We review classical barrier-function methods for nonlinear programming based on applying a logarithmic transformation to inequality constraints. For the special case of linear programming, the transformed problem can be solved by a “projected Newton barrier” method. This method is shown to be equivalent to Karmarkar’s projective method for a particular choice of the barrier parameter. We then present details of a specific barrier algorithm and its practical implementation. Numerical results are given for several non-trivial test problems, and the implications for future developments in linear programming are discussed. The research of the Stanford authors was supported by the U.S. Department of Energy Contract DE-AA03-76SF00326, PA No. DE-AS03-76ER72018; National Science Foundation Grants DCR-8413211 and ECS-8312142; the Office of Naval Research Contract N00014-85-K-0343; and the U.S. Army Research Office Contract DAAG29-84-K-0156. The research of J.A. Tomlin was supported by Ketron, Inc. and the Office of Naval Research Contract N00014-85-C-0338.     

Mathematical Programs with Vanishing Constraints: Optimality Conditions,Sensitivity, and a Relaxation Method

We consider a class of optimization problems with switch-off/switch-on constraints, which is a relatively new problem model. The specificity of this model is that it contains constraints that are being imposed (switched on) at some points of the feasible region, while being disregarded (switched off) at other points. This seems to be a potentially useful modeling paradigm, that has been shown to be helpful, for example, in optimal topology design. The fact that some constraints “vanish” from the problem at certain points, gave rise to the name of mathematical programs with vanishing constraints (MPVC). It turns out that such problems are usually degenerate at a solution, but are structurally different from the related class of mathematical programs with complementarity constraints (MPCC). In this paper, we first discuss some known first- and second-order necessary optimality conditions for MPVC, giving new very short and direct justifications. We then derive some new special second-order sufficient optimality conditions for these problems and show that, quite remarkably, these conditions are actually equivalent to the classical/standard second-order sufficient conditions in optimization. We also provide a sensitivity analysis for MPVC. Finally, a relaxation method is proposed. For this method, we analyze constraints regularity and boundedness of the Lagrange multipliers in the relaxed subproblems, derive a sufficient condition for local uniqueness of solutions of subproblems, and give convergence estimates. Research of the first author was supported by the Russian Foundation for Basic Research Grants 07-01-00270, 07-01-00416 and 07-01-90102-Mong, and by RF President’s Grant NS-9344.2006.1 for the support of leading scientific schools. The second author was supported in part by CNPq Grants 301508/2005-4, 490200/2005-2 and 550317/2005-8, by PRONEX-Optimization, and by FAPERJ.     

The Odd-Distance Plane Graph

The vertices of the odd-distance graph are the points of the plane ℝ². Two points are connected by an edge if their Euclidean distance is an odd integer. We prove that the chromatic number of this graph is at least five. We also prove that the odd-distance graph in ℝ² is countably choosable, while such a graph in ℝ³ is not. The research of J. Maňuch was supported in part by MITACS (Mathematics of Information Technology and Complex Systems). The research of M. Rosenfeld was supported in part by the Chancellor Research Grant and the Institute of Technology, UWT. The research of S. Shelah was supported by the United States-Israel Binational Science Foundation (Grant no. 2002323), and by NSF grant No. NSF-DMS 0600940. No. 923 on Shelah’s publication list. The research of L. Stacho was supported in part by NSERC (Natural Science and Engineering Research Council of Canada) grant.     

On Teichmüller’s theorem on the quasi-invariance of cross ratios

Teichmüller’s theorem gives necessary and sufficient conditions for mapping one ordered quadruple by aK-quasiconformal map onto a second ordered quadruple. We give a simple non-computational proof of the necessity part. We then characterize such extremal mappings, and obtain as a consequence a new formula for the modular function, with leads to a very simple derivation of the known expression for the Poincaré metric on the thrice-punctured sphere. Research partially supported by NSF grant MCS 76-04969A01.     

Estimation of Kullback–Leibler Divergence by Local Likelihood

Motivated from the bandwidth selection problem in local likelihood density estimation and from the problem of assessing a final model chosen by a certain model selection procedure, we consider estimation of the Kullback–Leibler divergence. It is known that the best bandwidth choice for the local likelihood density estimator depends on the distance between the true density and the ‘vehicle’ parametric model. Also, the Kullback–Leibler divergence may be a useful measure based on which one judges how far the true density is away from a parametric family. We propose two estimators of the Kullback-Leibler divergence. We derive their asymptotic distributions and compare finite sample properties. Research of Young Kyung Lee was supported by the Brain Korea 21 Projects in 2004. Byeong U. Park’s research was supported by KOSEF through Statistical Research Center for Complex Systems at Seoul National University.     

Green’s functions for stationary problems with nonlocal boundary conditions

In this paper, we investigate Green’s functions for various stationary problems with nonlocal boundary conditions. We express the Green’s function per Green’s function for a problem with classical boundary conditions. This property is illustrated by various examples. Properties of Green’s functions with nonlocal boundary conditions are compared with those for classical problems. The research was partially supported by the Lithuanian State Science and Studies Foundation, grant No. T-73/09.     

Local Topological Toughness and Local Factors

We localize and strengthen Katona’s idea of an edge-toughness to a local topological toughness. We disprove a conjecture of Katona concerning the conection between edge-toughness and factors. For the topological toughness we prove a theorem similar to Katona’s 2k-factor-conjecture, which turned out to be false for his edge-toughness. We prove, that besides this the topological toughness has nearly all known nice properties of Katona’s edge-toughness and therefore is worth to be considered. Research supported by the “Mathematics in Information Society” project carried out by Alfréd Rényi Institute of Mathematics - Hungarian Academy of Sciences, in the framework of the European Community’s “Confirming the International Role of Community Research” programme. Research supported by the Ministry of Education OTKA grant OTKA T 043520.