Conical projection algorithms for linear programming

The Linear Programming Problem is manipulated to be stated as a Non-Linear Programming Problem in which Karmarkar's logarithmic potential function is minimized in the positive cone generated by the original feasible set. The resulting problem is then solved by a master algorithm that iteratively rescales the problem and calls an internal unconstrained non-linear programming algorithm. Several different procedures for the internal algorithm are proposed, giving priority either to the reduction of the potential function or of the actual cost. We show that Karmarkar's algorithm is equivalent to this method in the special case in which the internal algorithm is reduced to a single steepest descent iteration. All variants of the new algorithm have the same complexity as Karmarkar's method, but the amount of computation is reduced by the fact that only one projection matrix must be calculated for each call of the internal algorithm.Research partly sponsored by CNPq-Brazilian National Council for Scientific and Technological Development, by National Science Foundation grant ECS-857362, Office of Naval Research contract N00014-86-K-0295, and AFOSR grant 86-0116.On leave from COPPE-Federal University of Rio de Janeiro, Cx. Postal 68511, 21941 Rio de Janeiro, RJ, Brasil.     

Bourgain's analytic projection revisited

For a positive function on the unit circle with , the following two statements are equivalent: (a) ; (b) there is an operator projecting onto for all at once and having weak type (1,1) with respect to .

     

变测度的积分-水平集确定性算法

提出了一个求总极值的变测度确定性算法,对不同的箱子采用不同的测度,结合确定性数论方法选取一致分布佳点集来代替Monte-Carlo随机投点,使水平值充分地下降,更快地到达全局最小,从而提高算法的计算效率.在文中给出了算法的收敛性证明,并通过数值算例验证了它的有效性.     

Computational acceleration of projection algorithms for the linear best approximation problem

This is an experimental computational account of projection algorithms for the linear best approximation problem. We focus on the sequential and simultaneous versions of Dykstra’s algorithm and the Halpern-Lions-Wittmann-Bauschke algorithm for the best approximation problem from a point to the intersection of closed convex sets in the Euclidean space. These algorithms employ different iterative approaches to reach the same goal but no mathematical connection has yet been found between their algorithmic schemes. We compare these algorithms on linear best approximation test problems that we generate so that the solution will be known a priori and enable us to assess the relative computational merits of these algorithms. For the simultaneous versions we present a new component-averaging variant that substantially accelerates their initial behavior for sparse systems.     

Normal operators and inequalities in norm ideals

In this work we characterize normal invertible operators via inequalities with unitarily invariant norm of elementary operators.     

Strong convergence of projection algorithms for a family of relatively quasi-nonexpansive mappings and an equilibrium problem in Banach spaces

In this article, we introduce two kinds of new hybrid projection algorithms for finding a common element of the set of solutions of an equilibrium problem and the set of common fixed points of an infinitely countable family of relatively quasi-nonexpansive mappings in a Banach space. Our main results improve and extend the result obtained by Martinez-Yanes and Xu [Strong convergence of the CQ method for fixed point iteration processes, Nonlinear Anal. 64 (2006), pp. 2400–2411] and the corresponding results.     

Global convergence of Rosen's gradient projection method

The convergence of Rosen's gradient method is a long-standing problem in nonlinear programming. Recently, progress has been made by several researchers. In this paper, we completely resolve the problem.This author's work was supported in part by AF OSR-86-0078, NSF DMS-86-06225, and NSF of China.     

On the convergence of projection methods: Application to the decomposition of affine variational inequalities

In this paper, we first discuss the global convergence of symmetric projection methods for solving nonlinear monotone variational inequalities under a cocoercivity assumption. A similar analysis is applied to asymmetric projection methods, when the mapping is affine and monotone. Under a suitable choice of the projection matrix, decomposition can be achieved. It is proved that this scheme achieves a linear convergence rate, thus enhancing results previously obtained by Tseng (Ref. 1) and by Luo and Tseng (Ref. 2).The research of the first author was supported by NSERC Grant A5789 and DND-FUHBP. The research of the second author was supported by NSERC Grant OGP-0157735.The authors are indebted to the referees and Associate Editor P. Tseng for their constructive comments.     

Ass（M／N） and Ann（M／N） on the Noetherian Module M

Let R is a noetherian ring,M is a finitely generated R-module.This paper studies the relationbetween associated prime Ass(M/N)and annihilator Ann(M/N),and has given the necessary andsufficient conditions of Ass(M/N)=Ann(M/N).     

A convergence theorem of Rosen’s gradient projection method

Since Rosen’s gradient projection method was published in 1960, a rigorous convergence proof of his method has remained an open question. A convergence theorem is given in this paper. Part of this author’s work was done while he studied at the Department of Mathematics, University of California at Santa Barbara, and was supported by the National Science Foundation under Grant No. MCS83-14977. Part of this author’s work was done while he visited the Computer Science Department, University of Minnesota, Minneapolis, and was supported by the National Science Foundation under Grant No. MCS81-01214.     

Universal quantification for deterministic chaos in dynamical systems

A cell dynamical system model for deterministic chaos enables precise quantification of the round-off error growth, i.e., deterministic chaos in digital computer realizations of mathematical models of continuum dynamical systems. The model predicts the following: (a) The phase space trajectory (strange attractor) when resolved as a function of the computer accuracy has intrinsic logarithmic spiral curvature with the quasiperiodic Penrose tiling pattern for the internal structure. (b) The universal constant for deterministic chaos is identified as the steady-state fractional round-off error k for each computational step and is equal to 1/τ² ( = 0.382) where τ is the golden mean. k being less than half accounts for the fractal (broken) Euclidean geometry of the strange attractor. (c) The Feigenbaum's universal constantsa and d are functions of k and, further, the expression 2a² = πd quantifies the steady-state ordered emergence of the fractal geometry of the strange attractor. (d) The power spectra of chaotic dynamical systems follow the universal and unique inverse power law form of the statistical normal distribution. The model prediction of (d) is verified for the Lorenz attractor and for the computable chaotic orbits of Bernoulli shifts, pseudorandom number generators, and cat maps.     

The use of additional diminishing disturbances in Fejer models of iterative algorithms

The behavior of Fejer processes with diminishing disturbances generated by a small shift in the argument of the Fejer operator is studied. It is shown that, if the operator is locally strongly Fejer, a diminishing disturbance does not prevent convergence to an attracting set. At the same time, such a disturbance can be used to furnish the process with additional properties that ensure convergence to certain subsets of the attracting set. In particular, based on this scheme, new parallel decomposition methods for optimization problems can be suggested that do not require that the constraints possess a specific structure.     

On polars of mixed projection bodies

Recently, Lutwak established general Minkowski inequality, Brunn-Minkowski inequality and Aleksandrov-Fenchel inequality for mixed projection bodies. In this paper, following Lutwak, we established their polar forms. As applications, we prove some interrelated results.     

L-模糊正规子群之间的对应定理

群G的一个L-模糊正规子群A的陪集做成的群G／A与群G的一个商群是自然同构的。如果f：G→G’是群的满同态，则G’的L-模糊正规子群做成的群与G的在f的核上取定值的L-模糊正规子群做成的群之间存在一个保序的双射。     

Linear convergence of gradient projection algorithm for split equality problems

ABSTRACT

In this paper, we consider the varying stepsize gradient projection algorithm (GPA) for solving the split equality problem (SEP) in Hilbert spaces, and study its linear convergence. In particular, we introduce a notion of bounded linear regularity property for the SEP, and use it to establish the linear convergence property for the varying stepsize GPA. We provide some mild sufficient conditions to ensure the bounded linear regularity property, and then conclude the linear convergence rate of the varying stepsize GPA. To the best of our knowledge, this is the first work to study the linear convergence for the SEP.     

Hypernormal form theory: foundations and algorithms

Hypernormal forms (unique normal forms, simplest normal forms) are investigated both from the standpoint of foundational theory and algorithms suitable for use with computer algebra. The Baider theory of the Campbell-Hausdorff group is refined, by a study of its subgroups, to determine the smallest substages into which the hypernormalization process can be divided. This leads to a linear algebra algorithm to compute the generators needed for each substage with the least amount of work. A concrete interpretation of Jan Sanders’ spectral sequence for hypernormal forms is presented. Examples are given, and a proof is given for a little-known theorem of Belitskii expressing the hypernormal form space (in the inner product style) as the kernel of a higher-order differential operator.     

求解结构矩阵低秩逼近的交替投影方法

结构矩阵低秩逼近在图像压缩、计算机代数和语音编码中有广泛应用.首先给出了几类结构矩阵的投影公式,再利用交替投影方法计算结构矩阵低秩逼近问题.数值试验表明新方法是可行的.     

Optimal deterministic algorithms for some variants of Online Quota Traveling Salesman Problem

This paper is concerned with the Online Quota Traveling Salesman Problem. Depending on the symmetry of the metric and the requirement for the salesman to return to the origin, four variants are analyzed. We present optimal deterministic algorithms for each variant defined on a general space, a real line, or a half-line. As a byproduct, an improved lower bound for a variant of Online TSP on a half-line is also obtained.     

Normal/Independent Distributions and Their Applications in Robust Regression

Abstract

Maximum likelihood estimation with nonnormal error distributions provides one method of robust regression. Certain families of normal/independent distributions are particularly attractive for adaptive, robust regression. This article reviews the properties of normal/independent distributions and presents several new results. A major virtue of these distributions is that they lend themselves to EM algorithms for maximum likelihood estimation. EM algorithms are discussed for least L_p regression and for adaptive, robust regression based on the t, slash, and contaminated normal families. Four concrete examples illustrate the performance of the different methods on real data.