On convergence of the inexact Rayleigh quotient iteration with the Lanczos method used for solving linear systems

For the Hermitian inexact Rayleigh quotient iteration(RQI),we consider the local convergence of the in exact RQI with the Lanczos method for the linear systems involved.Some attractive properties are derived for the residual,whose norm is ξk,of the linear system obtained by the Lanczos method at outer iteration k+1.Based on them,we make a refned analysis and establish new local convergence results.It is proved that(i) the inexact RQI with Lanczos converges quadratically provided that ξk≤ξ with a constant ξ1 and (ii) the method converges linearly provided that ξk is bounded by some multiple of1/||rk|| with rkthe residual norm of the approximate eigenpair at outer iteration k.The results are fundamentally diferent from the existing ones that always require ξk<1,and they have implications on efective implementations of the method.Based on the new theory,we can design practical criteria to control ξkto achieve quadratic convergence and implement the method more efectively than ever before.Numerical experiments confrm our theory and demonstrate that the inexact RQI with Lanczos is competitive to the inexact RQI with MINRES.     

混合互补问题牛顿型算法的二阶收敛性

在凸规划理论中,通过ＫＴ条件,往往将约束最优化问题归结为一个混合互补问题来求解。该文就正则解和一般解两种情形分别给出了求解混合互补问题牛顿型算法的二阶收敛性的充分性条件,并在一定条件下证明了非精确牛顿法和离散牛顿法所具有的二阶收敛性。     

Two‐step Newton‐type methods for solving inverse eigenvalue problems

In this paper, we apply the two‐step Newton method to solve inverse eigenvalue problems, including exact Newton, Newton‐like, and inexact Newton‐like versions. Our results show that both two‐step Newton and two‐step Newton‐like methods converge cubically, and the two‐step inexact Newton‐like method is super quadratically convergent. Numerical implementations demonstrate the effectiveness of new algorithms.     

Iterative linear programming solution of convex programs

An iterative linear programming algorithm for the solution of the convex programming problem is proposed. The algorithm partially solves a sequence of linear programming subproblems whose solution is shown to converge quadratically, superlinearly, or linearly to the solution of the convex program, depending on the accuracy to which the subproblems are solved. The given algorithm is related to inexact Newton methods for the nonlinear complementarity problem. Preliminary results for an implementation of the algorithm are given.This material is based on research supported by the National Science Foundation, Grants DCR-8521228 and CCR-8723091, and by the Air Force Office of Scientific Research, Grant AFOSR-86-0172. The author would like to thank Professor O. L. Mangasarian for stimulating discussions during the preparation of this paper.     

New Inexact Line Search Method for Unconstrained Optimization

We propose a new inexact line search rule and analyze the global convergence and convergence rate of related descent methods. The new line search rule is similar to the Armijo line-search rule and contains it as a special case. We can choose a larger stepsize in each line-search procedure and maintain the global convergence of related line-search methods. This idea can make us design new line-search methods in some wider sense. In some special cases, the new descent method can reduce to the Barzilai and Borewein method. Numerical results show that the new line-search methods are efficient for solving unconstrained optimization problems. The work was supported by NSF of China Grant 10171054, Postdoctoral Fund of China, and K. C. Wong Postdoctoral Fund of CAS Grant 6765700. The authors thank the anonymous referees for constructive comments and suggestions that greatly improved the paper.     

The Modified Rayleigh Quotient Iteration

The Rayleigh Quotient Iteration (RQI) is a very popular method for computing eigenpairs of symmetric matrices. It is a special kind of inverse iteration method using the Rayleigh Quotient as shifts. Unfortunately, poor initial approximations may render RQI to slow convergence or even to divergence, In this paper we suggest two kinds of numbers each of which can be used instead of the Rayleigh Quotient as a shifts in the RQI. We call the iteration using the new shifts the Modified Rayleigh Quotient Iteration (MRQI). It has been proved that the MRQI always converges and its convergence rate is cubic.     

A globally convergent algorithm for the Euclidean multiplicity location problem

The Euclidean single facility location problem (ESFL) and the Euclidean multiplicity location problem (EMFL) are two special nonsmooth convex programming problems which have attracted a large literature. For the ESFL problem, there are algorithms which converge both globally and quadratically. For the EMFL problem, there are some quadratically convergent algorithms, but for global convergence, they all need nontrivial assumptions on the problem.In this paper, we present an algorithm for EMFL. With no assumption on the problem, it is proved that from any initial point, this algorithm generates a sequence of points which converges to the closed convex set of optimal solutions of EMFL.This research is supported in part by the Air Force Office of Scientific Research Grant AFOSR-87-0127, the National Science Foundation Grant DCR-8420935 and University of Minnesota Graduate School Doctoral Dissertation Fellowship awarded to G.L. Xue.     

Analysis of a self-scaling quasi-Newton method

We study the self-scaling BFGS method of Oren and Luenberger (1974) for solving unconstrained optimization problems. For general convex functions, we prove that the method is globally convergent with inexact line searches. We also show that the directions generated by the self-scaling BFGS method approach Newton's direction asymptotically. This would ensure superlinear convergence if, in addition, the search directions were well-scaled, but we show that this is not always the case. We find that the method has a major drawback: to achieve superlinear convergence it may be necessary to evaluate the function twice per iteration, even very near the solution. An example is constructed to show that the step-sizes required to achieve a superlinear rate converge to 2 and 0.5 alternately.This work was supported by National Science Foundation Grant CCR-9101359, and by the Department of Energy Grant DE-FG02-87ER25047.This work was performed while the author was visiting Northwestern University.     

A Levenberg-Marquardt method with approximate projections

The projected Levenberg-Marquardt method for the solution of a system of equations with convex constraints is known to converge locally quadratically to a possibly nonisolated solution if a certain error bound condition holds. This condition turns out to be quite strong since it implies that the solution sets of the constrained and of the unconstrained system are locally the same. Under a pair of more reasonable error bound conditions this paper proves R-linear convergence of a Levenberg-Marquardt method with approximate projections. In this way, computationally expensive projections can be avoided. The new method is also applicable if there are nonsmooth constraints having subgradients. Moreover, the projected Levenberg-Marquardt method is a special case of the new method and shares its R-linear convergence.     

计算张量特征对的瑞利商迭代法

In this paper,we propose a Rayleigh quotient iteration method (RQI)to calculate the Z-eigenpairs of the symmetric tensor,which can be viewed as a generalization of shifted symmetric higher-order power method (SS-HOPM).The convergence analysis and the fixed-point analysis of this algorithm are given.Nu-merical examples show that RQI needs fewer iterations than SS-HOPM while keep the amount of computation per iteration.     

Local convergence analysis of several inexact Newton-type algorithms for general nonlinear eigenvalue problems

We study the local convergence of several inexact numerical algorithms closely related to Newton’s method for the solution of a simple eigenpair of the general nonlinear eigenvalue problem $T(\lambda )v=0$ . We investigate inverse iteration, Rayleigh quotient iteration, residual inverse iteration, and the single-vector Jacobi–Davidson method, analyzing the impact of the tolerances chosen for the approximate solution of the linear systems arising in these algorithms on the order of the local convergence rates. We show that the inexact algorithms can achieve the same order of convergence as the exact methods if appropriate sequences of tolerances are applied to the inner solves. We discuss the connections and emphasize the differences between the standard inexact Newton’s method and these inexact algorithms. When the local symmetry of $T(\lambda )$ is present, the use of a nonlinear Rayleigh functional is shown to be fundamental in achieving higher order of convergence rates. The convergence results are illustrated by numerical experiments.     

Solving variational inequalities defined on a domain with infinitely many linear constraints

We study a variational inequality problem whose domain is defined by infinitely many linear inequalities. A discretization method and an analytic center based inexact cutting plane method are proposed. Under proper assumptions, the convergence results for both methods are given. We also provide numerical examples to illustrate the proposed methods. The work of S. Wu was partially supported by the National Science Council, Taiwan, ROC (Grant No. 19731001). S.-C. Fang’s research has been supported by the US Army Research Office (Grant No. W911NF-04-D-0003) and National Science Foundation (Grant No. DMI-0553310).     

Remarks on the generalized Newton method

We give some convergence results for the generalized Newton method for the computation of zeros of nondifferentiable functions which we proposed in an earlier work. Our results show that the generalized method can converge quadratically when used to compute the zeros of the sum of a differentiable function and the (multivalued) subgradient of a lower semicontinuous proper convex function. The method is therefore effective for variational inequalities and can be used to find the minimum of a function which is the sum of a twice-differentiable convex function and a lower semicontinuous proper convex function. A numerical example is given.     

On the rate of convergence of certain methods of centers

It is shown in this paper that a theoretical method of centers, introduced by Huard, converges linearly. It is also shown, by counter-example, that a modified method of centers due to Huard and a method of feasible direction due to Topkis and Veinot cannot converge linearly even under convexity assumptions. Because of this, a new modified method of centers is introduced which uses a quadratic programming direction finding subroutine. In most uses this new method is not more complicated than Huard's modified method of centers. But it does converge linearly. A method for implementing it without loss of rate of convergence is also discussed.Research sponsored by the Joint Services Electronics Program, Grant AF-AFOSR-68-1488 and the National Aeronautics and Space Administration, Grant NGL-05-003-016.     

Newton Methods for Quasidifferentiable Equations and Their Convergence

The Newton method and the inexact Newton method for solving quasidifferentiable equations via the quasidifferential are investigated. The notion of Q-semismoothness for a quasidifferentiable function is proposed. The superlinear convergence of the Newton method proposed by Zhang and Xia is proved under the Q-semismooth assumption. An inexact Newton method is developed and its linear convergence is shown.Project sponsored by Shanghai Education Committee Grant 04EA01 and by Shanghai Government Grant T0502.     

A gradient-related algorithm with inexact line searches

In this paper, a new gradient-related algorithm for solving large-scale unconstrained optimization problems is proposed. The new algorithm is a kind of line search method. The basic idea is to choose a combination of the current gradient and some previous search directions as a new search direction and to find a step-size by using various inexact line searches. Using more information at the current iterative step may improve the performance of the algorithm. This motivates us to find some new gradient algorithms which may be more effective than standard conjugate gradient methods. Uniformly gradient-related conception is useful and it can be used to analyze global convergence of the new algorithm. The global convergence and linear convergence rate of the new algorithm are investigated under diverse weak conditions. Numerical experiments show that the new algorithm seems to converge more stably and is superior to other similar methods in many situations.     

On preconditioned Uzawa methods and SOR methods for saddle-point problems

This paper studies convergence analysis of a preconditioned inexact Uzawa method for nondifferentiable saddle-point problems. The SOR-Newton method and the SOR-BFGS method are special cases of this method. We relax the Bramble-Pasciak-Vassilev condition on preconditioners for convergence of the inexact Uzawa method for linear saddle-point problems. The relaxed condition is used to determine the relaxation parameters in the SOR-Newton method and the SOR-BFGS method. Furthermore, we study global convergence of the multistep inexact Uzawa method for nondifferentiable saddle-point problems.     

On the convergence of an inexact Newton-type method

In this paper we give local convergence results of an inexact Newton-type method for monotone equations under a local error bound condition. This condition may hold even for problems with non-isolated solutions, and it therefore is weaker than the standard non-singularity condition.     

Affine scaling inexact generalized Newton algorithm with interior backtracking technique for solving bound-constrained semismooth equations

We develop and analyze an affine scaling inexact generalized Newton algorithm in association with nonmonotone interior backtracking line technique for solving systems of semismooth equations subject to bounds on variables. By combining inexact affine scaling generalized Newton with interior backtracking line search technique, each iterate switches to inexact generalized Newton backtracking step to strict interior point feasibility. The global convergence results are developed in a very general setting of computing trial steps by the affine scaling generalized Newton-like method that is augmented by an interior backtracking line search technique projection onto the feasible set. Under some reasonable conditions we establish that close to a regular solution the inexact generalized Newton method is shown to converge locally p-order q-superlinearly. We characterize the order of local convergence based on convergence behavior of the quality of the approximate subdifferentials and indicate how to choose an inexact forcing sequence which preserves the rapid convergence of the proposed algorithm. A nonmonotonic criterion should bring about speeding up the convergence progress in some ill-conditioned cases.     

Exponential Convergence of Time-Delay Systems in the Presence of Bounded Disturbances

In this paper, the problem of control design for exponential convergence of state/input delay systems with bounded disturbances is considered. Based on the Lyapunov–Krasovskii method combining with the delay-decomposition technique, a new sufficient condition is proposed for the existence of a state feedback controller, which guarantees that all solutions of the closed-loop system converge exponentially (with a pre-specified convergence rate) within a ball whose radius is minimized. The obtained condition is given in terms of matrix inequalities with one parameter needing to be tuned, which can be solved by using a one-dimensional search method with Matlab’s LMI Toolbox to minimize the radius of the ball. Two numerical examples are given to illustrate the superiority of the proposed method.