The Asymmetric One-Dimensional Constrained Ising Model: Rigorous Results

We study a one-dimensional spin (interacting particle) system, with product Bernoulli (p) stationary distribution, in which a site can flip only when its left neighbor is in state +1. Such models have been studied in physics as simple exemplars of systems exhibiting slow relaxation. In our East model the natural conjecture is that the relaxation time (p), that is 1/(spectral gap), satisfies log (p) as p0. We prove this up to a factor of 2. The upper bound uses the Poincaré comparison argument applied to a wave (long-range) comparison process, which we analyze by probabilistic techniques. Such comparison arguments go back to Holley (1984, 1985). The lower bound, which atypically is not easy, involves construction and analysis of a certain coalescing random jumps process.     

On Analogs of the Tits Alternative for Groups of Homeomorphisms of the Circle and of the Line

In [1] G. Margulis proved Ghys's conjecture stating the validity of the following analog of the Tits alternative: either the group of homeomorphisms of the circle possesses a free subgroup with two generators or there is an invariant probabilistic measure on S ¹ . In the present paper, we prove the following strengthening of Margulis's statement: an invariant probabilistic measure for a group exists if and only if the quotient group does not contain a free subgroup with two generators (here is some specific subgroup of G defined in a canonical way). We also formulate and prove analogs of the Tits alternative for groups of homeomorphisms of the line.     

Weak Copositive and Intertwining Approximation

It is known that shape preserving approximation has lower rates than unconstrained approximation. This is especially true for copositive and intertwining approximations. ForfL_p, 1p<∞, the former only has rateω(f, n⁻¹)_p, and the latter cannot even be bounded byC f_p. In this paper, we discuss various ways to relax the restrictions in these approximations and conclude that the most sensible way is the so-calledalmostcopositive/intertwining approximation in which one relaxes the restriction on the approximants in a neighborhood of radiusΔ_n(y_j) of each sign changey_j.     

Menger概率n-度量空间中的不动点定理

引进了概率ｎ－度量空间,并将文「１」、「２」的某些主要结果拓广至Ｍｅｎｇｅｒ概率ｎ－度量空间。     

QPECgen, a MATLAB Generator for Mathematical Programs with Quadratic Objectives and Affine Variational Inequality Constraints

We describe a technique for generating a special class, called QPEC, of mathematical programs with equilibrium constraints, MPEC. A QPEC is a quadratic MPEC, that is an optimization problem whose objective function is quadratic, first-level constraints are linear, and second-level (equilibrium) constraints are given by a parametric affine variational inequality or one of its specialisations. The generator, written in MATLAB, allows the user to control different properties of the QPEC and its solution. Options include the proportion of degenerate constraints in both the first and second level, ill-conditioning, convexity of the objective, monotonicity and symmetry of the second-level problem, and so on. We believe these properties may substantially effect efficiency of existing methods for MPEC, and illustrate this numerically by applying several methods to generator test problems. Documentation and relevant codes can be found by visiting http://www.ms.unimelb.edu.au/danny/qpecgendoc.html.     

A Shifted-Barrier Primal-Dual Algorithm Model for Linearly Constrained Optimization Problems

In this paper we describe a Newton-type algorithm model for solving smooth constrained optimization problems with nonlinear objective function, general linear constraints and bounded variables. The algorithm model is based on the definition of a continuously differentiable exact merit function that follows an exact penalty approach for the box constraints and an exact augmented Lagrangian approach for the general linear constraints. Under very mild assumptions and without requiring the strict complementarity assumption, the algorithm model produces a sequence of pairs converging quadratically to a pair where satisfies the first order necessary conditions and is a KKT multipliers vector associated to the linear constraints. As regards the behaviour of the sequence x ^k alone, it is guaranteed that it converges at least superlinearly. At each iteration, the algorithm requires only the solution of a linear system that can be performed by means of conjugate gradient methods. Numerical experiments and comparison are reported.     

On the spatial-temporal averaging method for modeling transport in porous media

The spatial-temporal averaging procedure is considered with a nonhomogeneous distribution of elementary domains in the spatial-temporal space and the probabilistic interpretation of the ST-averaging is also given. Several averaging theorems and corollaries about the averages of spatial and temporal derivatives are presented and rigorously proved which allow elementary domain to vary in space and time. The macroscopic transport equation in the most general condition and the simplified macroscopic equation under the special form of distributions are developed which may be reduced to the classical macroscopic transport equation as the spatial-temporal average degenerates into the volume average.     

A CLASS OF TRUST REGION METHODS FOR LINEAR INEQUALITY CONSTRAINED OPTIMIZATION AND ITS THEORY ANALYSIS Ⅱ. LOCAL CONVERGENCE RATE AND NUMERICAL TESTS

In this paper we prove that a class of trust region methods presented in part Ⅰ is superlinearly convergent. Numerical tests are reported thereafter. Results by solving a set of typical problems selected from literatures have demonstrated that our algorithm is effective.     

Correctness proof of an in-place permutation

The correctness of an in-place permutation algorithm is proved. The algorithm exchanges elements belonging to a permutation cycle. A suitable assertion is constructed from which the correctness can be deduced after completion of the algorithm.An in-place rectangular matrix transposition algorithm is given as an example.     

Properties of updating methods for the multipliers in augmented Lagrangians

The convergence properties of different updating methods for the multipliers in augmented Lagrangians are considered. It is assumed that the updating of the multipliers takes place after each line search of a quasi-Newton method. Two of the updating methods are shown to be linearly convergent locally, while a third method has superlinear convergence locally. Modifications of the algorithms to ensure global convergence are considered. The results of a computational comparison with other methods are presented.This work was supported by the Swedish Institute of Applied Mathematics.