More results on the convergence of iterative methods for the symmetric linear complementarity problem

In an earlier paper, the author has given some necessary and sufficient conditions for the convergence of iterative methods for solving the linear complementarity problem. These conditions may be viewed as global in the sense that they apply to the methods regardless of the constant vector in the linear complementarity problem. More precisely, the conditions characterize a certain class of matrices for which the iterative methods will converge, in a certain sense, to a solution of the linear complementarity problem for all constant vectors. In this paper, we improve on our previous results and establish necessary and sufficient conditions for the convergence of iterative methods for solving each individual linear complementarity problem with a fixed constant vector. Unlike the earlier paper, our present analysis applies only to the symmetric linear complementarity problem. Various applications to a strictly convex quadratic program are also given.The author gratefully acknowledges several stimulating conversations with Professor O. Mangasarian on the subject of this paper. He is also grateful to a referee, who has suggested Lemma 2.2 and the present (stronger) version of Theorem 2.1 as well as several other constructive comments.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571, sponsored by the United States Army under Contract No. DAAG29-80-C-0041, and was completed while the author was visiting the Mathematics Research Center at the University of Wisconsin, Madison, Wisconsin.     

Quadratic convergence of a special quasi-cyclic Jacobi method

This paper considers the ultimate asymptotic convergence of a block- oriented, quasi-cyclic Jacobi method for symmetric matrices. The conclusion applies to the new one-sided Jacobi method for computing the singular value decomposition, recently proposed by Drmač and Veselić. Using a simple qualitative analysis, the discussion indicates that a quadratic off-norm reduction per quasi-sweep is to be expected in all perceivable cases.      

A real algorithm for the Hermitian eigenvalue decomposition

Modifying complex plane rotations, we derive a new Jacobi-type algorithm for the Hermitian eigendecomposition, which uses only real arithmetic. When the fast-scaled rotations are incorporated, the new algorithm brings a substantial reduction in computational costs. The new method has the same convergence properties and parallelism as the symmetric Jacobi algorithm. Computational test results show that it produces accurate eigenvalues and eigenvectors and achieves great reduction in computational time.The work of this author was supported in part by the National Science Foundation grant CCR-8813493 and by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.The work of this author was supported in part by the University of Minnesota Army High Performance Computing Research Center contract DAAL 03-89-C-0038.     

Weierstraß-type representation of affine spheres

Affine spheres are discussed in the context of loop groups. We show that every affine sphere can be obtained by solving two ordinary differential equations followed by an application of a generalized Birkhoff Decomposition Theorem (which we proof in the Appendix). A geometric interpretation of the coefficients of the ODE is given. Finally the method is applied to construct all ruled surfaces. Most of this work was done while the second named author was visiting the University of Kansas.     

Global optimization of concave functions subject to quadratic constraints: An application in nonlinear bilevel programming

When the follower's optimality conditions are both necessary and sufficient, the nonlinear bilevel program can be solved as a global optimization problem. The complementary slackness condition is usually the complicating constraint in such problems. We show how this constraint can be replaced by an equivalent system of convex and separable quadratic constraints. In this paper, we propose different methods for finding the global minimum of a concave function subject to quadratic separable constraints. The first method is of the branch and bound type, and is based on rectangular partitions to obtain upper and lower bounds. Convergence of the proposed algorithm is also proved. For computational purposes, different procedures that accelerate the convergence of the proposed algorithm are analysed. The second method is based on piecewise linear approximations of the constraint functions. When the constraints are convex, the problem is reduced to global concave minimization subject to linear constraints. In the case of non-convex constraints, we use zero-one integer variables to linearize the constraints. The number of integer variables depends only on the concave parts of the constraint functions.Parts of the present paper were prepared while the second author was visiting Georgia Tech and the University of Florida.     

Arnoldi versus nonsymmetric Lanczos algorithms for solving matrix eigenvalue problems

We present theoretical and numerical comparisons between Arnoldi and nonsymmetric Lanczos procedures for computing eigenvalues of nonsymmetric matrices. In exact arithmetic we prove that any type of eigenvalue convergence behavior obtained using a nonsymmetric Lanczos procedure may also be obtained using an Arnoldi procedure but on a different matrix and with a different starting vector. In exact arithmetic we derive relationships between these types of procedures and normal matrices which suggest some interesting questions regarding the roles of nonnormality and of the choice of starting vectors in any characterizations of the convergence behavior of these procedures. Then, through a set of numerical experiments on a complex Arnoldi and on a complex nonsymmetric Lanczos procedure, we consider the more practical question of the behavior of these procedures when they are applied to the same matrices.This work was supported by NSF grant GER-9450081 while the author was visiting the University of Maryland.     

A class of test functions for global optimization

We suggest weighted least squares scaling, a basic method in multidimensional scaling, as a class of test functions for global optimization. The functions are easy to code, cheap to calculate, and have important applications in data analysis. For certain data these functions have many local minima. Some characteristic features of the test functions are investigated.This paper was written while the second author was a visiting Professor at Aachen University of Technology, funded by the Deutsche Forschungsgemeinschaft.     

Convergence of a generalized subgradient method for nondifferentiable convex optimization

A generalized subgradient method is considered which uses the subgradients at previous iterations as well as the subgradient at current point. This method is a direct generalization of the usual subgradient method. We provide two sets of convergence conditions of the generalized subgradient method. Our results provide a larger class of sequences which converge to a minimum point and more freedom of adjustment to accelerate the speed of convergence.Most of this research was performed when the first author was visiting Decision and Information Systems Department, College of Business, Arizona State University.     

On global optimization in two-dimensional scaling

We consider multidimensional scaling for embedding dimension two, which allows the detection of structures in dissimilarity data by simply drawing two-dimensional figures. The corresponding objective function, called STRESS, is generally nondifferentiable and has many local minima. In this paper we investigate several features of this function, and discuss the application of different global optimization procedures. A method based on combining a local search algorithm with an evolutionary strategy of generating new initial points is proposed, and its efficiency is investigated by numerical examples.This paper was written while the second author was visiting Professor at Aachen University of Technology, funded by the Deutsche Forschungsgemeinschaft.     

On sharp quadratic convergence bounds for the serial Jacobi methods

Summary Using a new technique we derive sharp quadratic convergence bounds for the serial symmetric and SVD Jacobi methods. For the symmetric Jacobi method we consider the cases of well and poorely separated eigenvalues. Our result implies the result proposed, but not correctly proved, by Van Kempen. It also extends the well-known result of Wilkinson to the case of multiple eigenvalues.This work was supported in part by the U.S. Army. Contract DAAL03-89-C-0038     

Difference schemes with best possible truncation error

In this paper we present a variety of schemes for solving the initial value problem for a class of hyperbolic systems of partial differential equations. These schemes arise as solutions of constrained minimization problems for a quadratic form. The form is an expression for the local truncation error for a certain class of difference schemes.This work was performed while the author was a visiting Professor of Mathematics of the Hebrew University of Jerusalem.     

Some finite groups with large conjugacy classes

We derive some properties of a family of finite groups, which was investigated by Camina, Macdonald, and others. For instance, we give information about the Schur multipliers of the class twop-groups in this family. A large part of this paper was written while the author was visiting the Department of Mathematics of the University of Trento. The author is indebted to this department, and in particular to C.M. Scoppola, for their kind hospitality. The author is also grateful to D. Chillag for his constructively destructive criticism of the first version of this paper.     

A global optimization approach for the linear two-level program

Linear two-level programming deals with optimization problems in which the constraint region is implicity determined by another optimization problem. Mathematical programs of this type arise in connection with policy problems to which the Stackelberg leader-follower game is applicable. In this paper, the linear two-level programming problem is restated as a global optimization problem and a new solution method based on this approach is developed. The most important feature of this new method is that it attempts to take full advantage of the structure in the constraints using some recent global optimization techniques. A small example is solved in order to illustrate the approach.The paper was completed while this author was visiting the Department of Mathematics of Linköping University.     

Ergodicity of reversible reaction diffusion processes

Summary Reaction-diffusion processes were introduced by Nicolis and Prigogine, and Haken. Existence theorems have been established for most models, but not much is known about ergodic properties. In this paper we study a class of models which have a reversible measure. We show that the stationary distribution is unique and is the limit starting from any initial distribution.The work was begun while the first author was visiting Cornell and supported by the Chinese government. The initial results (for Schlögl's first model) was generalized while the three authors were visiting the Nankai Institute for Mathematics, Tianjin, People's Republic of ChinaPartially supported by the National Science Foundation and the Army Research Office through the Mathematical Sciences Institute at Cornell UniversityPartially supported by NSF grant DMS 86-01800     

Exponential convergence for one dimensional contact processes

The complete convergence theorem implies that starting from any initial distribution the one dimensional contact process converges to a limit ast. In this paper we give a necessary and sufficient condition on the initial distribution for the convergence to occur with exponential rapidity.This work was discussed while the authors were visiting the Nankai Mathematics Institute in Tianjin.Partially supported by the National Science Foundation, the Army Research Office through the Mathematical Sciences Institute at Cornell University, and a Guggenheim fellowship.Research supported by the National Science Foundation of China.     

A method for finding sharp error bounds for Newton's method under the Kantorovich assumptions

Summary This paper gives a method for finding sharpa posteriori error bounds for Newton's method under the assumptions of Kantorovich's theorem. On the basis of this method, new error bounds are derived, and comparison is made among the known bounds of Dennis [2], Döring [4], Gragg-Tapia [5], Kantorovich [6, 7], Kornstaedt [9], Lancaster [10], Miel [11–13], Moret [14], Ostrowski [17, 18], Potra [19], and Potra-Pták [20].This paper was written while the author was visiting the Mathematics Research Center, University of Wisconsin-Madison, U.S.A. from March 29, 1985 to October 21, 1985Sponsored by the Ministry of Education in Japan and the United States Army under Contract No. DAAG 29-80-C-0041     

SomeL 1 existence and dependence results for semilinear elliptic equations under nonlinear boundary conditions

In this paper we study questions of existence, uniqueness, and continuous dependence for semilinear elliptic equations with nonlinear boundary conditions. In particular, we obtain results concerning the continuous dependence of the solutions on the nonlinearities in the problem, which in turn implies analogous results for a related parabolic problem. Such questions arise naturally in the study of potential theory, flow through porous media, and obstacle problems.Sponsored by the United States Army under Contract Nos. DAAG29-80-C-0041 and DAAL03-87-K-0043, and by the Air Force Office of Scientific Research under Contract No. AFOSR 84-0252 and by the National Science Foundation under Grant No. DMS-8505531. Research of the third author was carried out in part while visiting the Institute for Mathematics and Its Applications at the University of Minnesota.     

A convergence condition for the quadrilateral Wilson element

Summary The paper deals with the convergence properties of the nonconforming quadrilateral wilson element which violates the patch test. The convergence of the element is proved under a certain condition on mesh subdivisions without any modifications of the variational formulation. This result extends the range of applicability of Wilson's element. The necessity of the proposed condition is also discussed.This work was written while the author was visiting the University of Frankfurt, Federal Republic of Germany, on a grant by the Alexander von Humboldt Foundation     

On Discretization Schemes for Stochastic Evolution Equations

Stochastic evolutional equations with monotone operators are considered in Banach spaces. Explicit and implicit numerical schemes are presented. The convergence of the approximations to the solution of the equations is proved. Mathematics Subject Classifications (2000) Primary: 60H15; Secondary: 65M60.István Gyöngy: This paper was written while the first named author was visiting the University of Paris X. The research of this author is partially supported by EU Network HARP.Annie Millet: The research of the second named author is partially supported by the research project BMF2003-01345.     

平板几何迁移算子的特征值问题

研究L^p(1相似文献