Multi-sweep asynchronous parallel successive overrelaxation for the nonsymmetric linear complementarity problem

Convergence is established for themulti-sweep asynchronous parallel successive overrelaxation (SOR) algorithm for thenonsymmetric linear complementarity problem. The algorithm was originally introduced in [4] for the symmetric linear complementarity problem. Computational tests show the superiority of the multi-sweep asynchronous SOR algorithm over its single-sweep counterpart on both symmetric and nonsymmetric linear complementarity problems.This material is based on research supported by National Science Foundation Grants CCR-8723091 and DCR-8521228, and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0124.     

Parallel gradient projection successive overrelaxation for symmetric linear complementarity problems and linear programs

A gradient projection successive overrelaxation (GP-SOR) algorithm is proposed for the solution of symmetric linear complementary problems and linear programs. A key distinguishing feature of this algorithm is that when appropriately parallelized, the relaxation factor interval (0, 2) isnot reduced. In a previously proposed parallel SOR scheme, the substantially reduced relaxation interval mandated by the coupling terms of the problem often led to slow convergence. The proposed parallel algorithm solves a general linear program by finding its least 2-norm solution. Efficiency of the algorithm is in the 50 to 100 percent range as demonstrated by computational results on the CRYSTAL token-ring multicomputer and the Sequent Balance 21000 multiprocessor.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFOSR-86-0172 and AFOSR-86-0255.     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

A new general form of conjugate gradient methods with guaranteed descent and strong global convergence properties

Although the study of global convergence of the Polak–Ribière–Polyak (PRP), Hestenes–Stiefel (HS) and Liu–Storey (LS) conjugate gradient methods has made great progress, the convergence of these algorithms for general nonlinear functions is still erratic, not to mention under weak conditions on the objective function and weak line search rules. Besides, it is also interesting to investigate whether there exists a general method that converges under the standard Armijo line search for general nonconvex functions, since very few relevant results have been achieved. So in this paper, we present a new general form of conjugate gradient methods whose theoretical significance is attractive. With any formula β _k  ≥ 0 and under weak conditions, the proposed method satisfies the sufficient descent condition independently of the line search used and the function convexity, and its global convergence can be achieved under the standard Wolfe line search or even under the standard Armijo line search. Based on this new method, convergence results on the PRP, HS, LS, Dai–Yuan–type (DY) and Conjugate–Descent–type (CD) methods are established. Preliminary numerical results show the efficiency of the proposed methods.     

Partially and totally asynchronous algorithms for linear complementarity problems

A unified treatment is given for partially and totally asynchronous parallel successive overrelaxation (SOR) algorithms for the linear complementarity problem. Convergence conditions are established and compared to previous results. Convergence of the partially asynchronous method for the symmetric linear complementarity problem can be guaranteed if the relaxation factor is sufficiently small. Unlike previous results, this relaxation factor interval does not depend explicitly on problem size.This material is based on research supported by the Air Force Office of Scientific Research Grant No. AFOSR-89-0410.The author wishes to thank the referee for pointing out how to improve the bound (12). The same technique can be used to reduce the factorn in Ref. 5, p. 553, to .     

Global convergence of BFGS and PRP methods under a modified weak Wolfe–Powell line search

The BFGS method is one of the most effective quasi-Newton algorithms for optimization problems. However, its global convergence for general functions is still open. In this paper, under a new line search technique, this problem is solved, and it is shown that other methods in the Broyden class also possess this property. Moreover, the global convergence of the PRP method is established in the case of this new line search. Numerical results are reported to show that the new line search technique is competitive to that of the normal line search.     

Parallel successive overrelaxation methods for symmetric linear complementarity problems and linear programs

A parallel successive overrelaxation (SOR) method is proposed for the solution of the fundamental symmetric linear complementarity problem. Convergence is established under a relaxation factor which approaches the classical value of 2 for a loosely coupled problem. The parallel SOR approach is then applied to solve the symmetric linear complementarity problem associated with the least norm solution of a linear program.This work was sponsored by the United States Army under Contract No. DAAG29-80-C-0041. This material is based on research sponsored by National Science Foundation Grant DCR-84-20963 and Air Force Office of Scientific Research Grants AFOSR-ISSA-85-00080 and AFOSR-86-0172.on leave from CRAI, Rende, Cosenza, Italy.     

Minimization Algorithms Based on Supervisor and Searcher Cooperation

In the present work, we explore a general framework for the design of new minimization algorithms with desirable characteristics, namely, supervisor-searcher cooperation. We propose a class of algorithms within this framework and examine a gradient algorithm in the class. Global convergence is established for the deterministic case in the absence of noise and the convergence rate is studied. Both theoretical analysis and numerical tests show that the algorithm is efficient for the deterministic case. Furthermore, the fact that there is no line search procedure incorporated in the algorithm seems to strengthen its robustness so that it tackles effectively test problems with stronger stochastic noises. The numerical results for both deterministic and stochastic test problems illustrate the appealing attributes of the algorithm.     

一簇非线性等式约束优化问题的过滤线搜索修正正割方法

本文提供了一簇新的过滤线搜索修正正割方法求解非线性等式约束优化问题.新算法簇的特点是:用修正正割算法簇中的一个算法获得搜索方向,回代线搜索技术得到步长,过滤准则用来决定是否接受步长,引入二阶校正技术减少不可行性并克服Maratos效应.在合理的假设条件下,分析了算法的总体收敛性.并证明了,通过附加二阶校正步,算法簇克服了Maratos效应,并二步Q-超线性收敛到满足二阶充分最优条件的局部解.数值结果表明了所提供的算法具有有效性.     

An inexact line search approach using modified nonmonotone strategy for unconstrained optimization

This paper concerns with a new nonmonotone strategy and its application to the line search approach for unconstrained optimization. It has been believed that nonmonotone techniques can improve the possibility of finding the global optimum and increase the convergence rate of the algorithms. We first introduce a new nonmonotone strategy which includes a convex combination of the maximum function value of some preceding successful iterates and the current function value. We then incorporate the proposed nonmonotone strategy into an inexact Armijo-type line search approach to construct a more relaxed line search procedure. The global convergence to first-order stationary points is subsequently proved and the R-linear convergence rate are established under suitable assumptions. Preliminary numerical results finally show the efficiency and the robustness of the proposed approach for solving unconstrained nonlinear optimization problems.     

Family of Projected Descent Methods for Optimization Problems with Simple Bounds

This paper presents a family of projected descent direction algorithms with inexact line search for solving large-scale minimization problems subject to simple bounds on the decision variables. The global convergence of algorithms in this family is ensured by conditions on the descent directions and line search. Whenever a sequence constructed by an algorithm in this family enters a sufficiently small neighborhood of a local minimizer satisfying standard second-order sufficiency conditions, it gets trapped and converges to this local minimizer. Furthermore, in this case, the active constraint set at is identified in a finite number of iterations. This fact is used to ensure that the rate of convergence to a local minimizer, satisfying standard second-order sufficiency conditions, depends only on the behavior of the algorithm in the unconstrained subspace. As a particular example, we present projected versions of the modified Polak–Ribière conjugate gradient method and the limited-memory BFGS quasi-Newton method that retain the convergence properties associated with those algorithms applied to unconstrained problems.     

Globally convergent Polak-Ribière-Polyak conjugate gradient methods under a modified Wolfe line search

It is well known that global convergence has not been established for the Polak-Ribière-Polyak (PRP) conjugate gradient method using the standard Wolfe conditions. In the convergence analysis of PRP method with Wolfe line search, the (sufficient) descent condition and the restriction β_k?0 are indispensable (see [4,7]). This paper shows that these restrictions could be relaxed. Under some suitable conditions, by using a modified Wolfe line search, global convergence results were established for the PRP method. Some special choices for β_k which can ensure the search direction’s descent property were also discussed in this paper. Preliminary numerical results on a set of large-scale problems were reported to show that the PRP method’s computational efficiency is encouraging.     

An analysis of reduced Hessian methods for constrained optimization

We study the convergence properties of reduced Hessian successive quadratic programming for equality constrained optimization. The method uses a backtracking line search, and updates an approximation to the reduced Hessian of the Lagrangian by means of the BFGS formula. Two merit functions are considered for the line search: the ₁ function and the Fletcher exact penalty function. We give conditions under which local and superlinear convergence is obtained, and also prove a global convergence result. The analysis allows the initial reduced Hessian approximation to be any positive definite matrix, and does not assume that the iterates converge, or that the matrices are bounded. The effects of a second order correction step, a watchdog procedure and of the choice of null space basis are considered. This work can be seen as an extension to reduced Hessian methods of the well known results of Powell (1976) for unconstrained optimization.This author was supported, in part, by National Science Foundation grant CCR-8702403, Air Force Office of Scientific Research grant AFOSR-85-0251, and Army Research Office contract DAAL03-88-K-0086.This author was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U.S. Department of Energy, under contracts W-31-109-Eng-38 and DE FG02-87ER25047, and by National Science Foundation Grant No. DCR-86-02071.     

A two-stage successive overrelaxation algorithm for solving the symmetric linear complementarity problem

We propose a two-stage successive overrelaxation method (TSOR) algorithm for solving the symmetric linear complementarity problem. After the first SOR preprocessing stage this algorithm concentrates on updating a certain prescribed subset of variables which is determined by exploiting the complementarity property. We demonstrate that this algorithm successfully solves problems with up to ten thousand variables.This material is based on research supported by National Science Foundation Grants DCR-8420963 and DCR-8521228 and Air Force Office of Scientific Research Grants AFSOR-86-0172 and AFSOR-86-0255 while the author was at the Computer Sciences Department at the University of Wisconsin-Madison, USA.     

Algorithms for solving nonlinear dynamic decision models

In this paper we discuss two Newton-type algorithms for solving economic models. The models are preprocessed by reordering the equations in order to minimize the dimension of the simultaneous block. The solution algorithms are then applied to this block. The algorithms evaluate numerically, as required, selected columns of the Jacobian of the simultaneous part. Provisions also exist for similar systems to be solved, if possible, without actually reinitialising the Jacobian. One of the algorithms also uses the Broyden update to improve the Jacobian. Global convergence is maintained by an Armijo-type stepsize strategy.The global and local convergence of the quasi-Newton algorithm is discussed. A novel result is established for convergence under relaxed descent directions and relating the achievement of unit stepsizes to the accuracy of the Jacobian approximation. Furthermore, a simple derivation of the Dennis-Moré characterisation of the Q-superlinear convergence rate is given.The model equation reordering algorithm is also described. The model is reordered to define heart and loop variables. This is also applied recursively to the subgraph formed by the loop variables to reduce the total number of above diagonal elements in the Jacobian of the complete system. The extension of the solution algorithms to consistent expectations are discussed. The algorithms are compared with Gauss-Seidel SOR algorithms using the USA and Spanish models of the OECD Interlink system.     

Accelerating the DC algorithm for smooth functions

We introduce two new algorithms to minimise smooth difference of convex (DC) functions that accelerate the convergence of the classical DC algorithm (DCA). We prove that the point computed by DCA can be used to define a descent direction for the objective function evaluated at this point. Our algorithms are based on a combination of DCA together with a line search step that uses this descent direction. Convergence of the algorithms is proved and the rate of convergence is analysed under the ?ojasiewicz property of the objective function. We apply our algorithms to a class of smooth DC programs arising in the study of biochemical reaction networks, where the objective function is real analytic and thus satisfies the ?ojasiewicz property. Numerical tests on various biochemical models clearly show that our algorithms outperform DCA, being on average more than four times faster in both computational time and the number of iterations. Numerical experiments show that the algorithms are globally convergent to a non-equilibrium steady state of various biochemical networks, with only chemically consistent restrictions on the network topology.     

Global Convergence of Algorithms with Nonmonotone Line Search Strategy in Unconstrained Optimization

In this paper we state some nonmonotone line search strategies for unconstrained optimization algorithms. Abstracting from the concrete line search strategy we prove two general convergence results. Using this theory we can show the global convergence of the BFGS method with nonmonotone line search strategy. In contrast to some former results about nonmonotone line search strategies, both our convergence results and their proofs are natural generalizations of known results for the monotone case.     

Convergence of the parallel chaotic waveform relaxation method for stiff systems

In this paper, we establish several algorithms for parallel chaotic waveform relaxation methods for solving linear ordinary differential systems based on some given models. Under some different assumptions on the coefficient matrix A and its multisplittings we obtain corresponding sufficient conditions of convergence of the algorithms. Also a discussion on convergence speed comparison of synchronous and asynchronous algorithms is given.     

带非精确线搜索的调整搜索方向DFP算法

本文介绍一类新的带调整搜索方向的Broyden算法．我们着重讨论带调整搜索方向的DFP算法的收敛性，在某些非精确线搜索的情况下，我们证明对连续可微目标函数，这算法是整体收敛的，而对一致凸目标函数，收敛速度是一步超线收敛的．从这篇文章的证明过程中，可以得到对一致凸目标函数，DFP算法具有一步超线形收敛．     

On a geometrical aspect of SOR and the theory of consistent ordering for positive definite matrices

On the basis of a similarity transformation of , the successive overrelaxation operator, a geometrical interpretation of SOR is given. It is shown how the theory of consistent ordering falls into the resulting framework and how connections between SOR and other algorithms can be established.