Necessary and sufficient conditions for the convergence of iterative methods for the linear complementarity problem

Necessary and sufficient conditions are established for the convergence of various iterative methods for solving the linear complementarity problem. The fundamental tool used is the classical notion of matrix splitting in numerical analysis. The results derived are similar to some well-known theorems on the convergence of iterative methods for square systems of linear equations. An application of the results to a strictly convex quadratic program is also given.This research was based on work supported by the National Science Foundation under Grant No. ECS-81-14571.The author gratefully acknowledges several comments by K. Truemper on the topics of this paper.     

Incomplete projection algorithms for solving the convex feasibility problem

We present a general scheme for solving the convex feasibility problem and prove its convergence under mild conditions. Unlike previous schemes no exact projections are required. Moreover, we also introduce an acceleration factor, which we denote as the factor, that seems to play a fundamental role to improve the quality of convergence. Numerical tests on systems of linear inequalities randomly generated give impressive results in a multi-processing environment. The speedup is superlinear in some cases. New acceleration techniques are proposed, but no tests are reported here. As a by-product we obtain the rather surprising result that the relaxation factor, usually confined to the interval (0,2), gives better convergence results for values outside this interval.     

Proximal Methods in View of Interior-Point Strategies

This paper deals with regularized penalty-barrier methods for convex programming problems. In the spirit of an iterative proximal regularization approach, an interior-point method is constructed, in which at each step a strongly convex function has to be minimized and the prox-term can be scaled by a variable scaling factor. The convergence of the method is studied for an axiomatically given class of barrier functions. According to the results, a wide class of barrier functions (in particular, logarithmic and exponential functions) can be applied to design special algorithms. For the method with a logarithmic barrier, the rate of convergence is investigated and assumptions that ensure linear convergence are given.     

An interior point potential reduction method for constrained equations

We study the problem of solving a constrained system of nonlinear equations by a combination of the classical damped Newton method for (unconstrained) smooth equations and the recent interior point potential reduction methods for linear programs, linear and nonlinear complementarity problems. In general, constrained equations provide a unified formulation for many mathematical programming problems, including complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities and nonlinear programs. Combining ideas from the damped Newton and interior point methods, we present an iterative algorithm for solving a constrained system of equations and investigate its convergence properties. Specialization of the algorithm and its convergence analysis to complementarity problems of various kinds and the Karush-Kuhn-Tucker systems of variational inequalities are discussed in detail. We also report the computational results of the implementation of the algorithm for solving several classes of convex programs. The work of this author was based on research supported by the National Science Foundation under grants DDM-9104078 and CCR-9213739 and the Office of Naval Research under grant N00014-93-1-0228. The work of this author was based on research supported by the National Science Foundation under grant DMI-9496178 and the Office of Naval Research under grants N00014-93-1-0234 and N00014-94-1-0340.     

Multigrid methods for boundary integral equations

Summary Multigrid methods are applied for solving algebraic systems of equations that occur to the numerical treatment of boundary integral equations of the first and second kind. These methods, originally formulated for partial differential equations of elliptic type, combine relaxation schemes and coarse grid corrections. The choice of the relaxation scheme is found to be essential to attain a fast convergent iterative process. Theoretical investigations show that the presented relaxation scheme provides a multigrid algorithm of which the rate of convergence increases with the dimension of the finest grid. This is illustrated for the calculation of potential flow around an aerofoil.     

Iterative Schemes for Nonconvex Variational Inequalities

In this paper, we suggest and analyze some iterative methods for solving nonconvex variational inequalities using the auxiliary principle technique, the convergence of which requires either only pseudomonotonicity or partially relaxed strong monotonicity. Our proofs of convergence are very simple. As special cases, we obtain earlier results for solving general variational inequalities involving convex sets.     

On the numerical treatment of nonconvex energy problems of mechanics

The present paper presents three numerical methods devised for the solution of hemivariational inequality problems. The theory of hemivariational inequalities appeared as a development of variational inequalities, namely an extension foregoing the assumption of convexity that is essentially connected to the latter. The methods that follow partly constitute extensions of methods applied for the numerical solution of variational inequalities. All three of them actually use the solution of a central convex subproblem as their kernel. The use of well established techniques for the solution of the convex subproblems makes up an effective, reliable and versatile family of numerical algorithms for large scale problems. The first one is based on the decomposition of the contigent cone of the (super)-potential of the problem into convex components. The second one uses an iterative scheme in order to approximate the hemivariational inequality problem with a sequence of variational inequality problems. The third one is based on the fact that nonconvexity in mechanics is closely related to irreversible effects that affect the Hessian matrix of the respective (super)-potential. All three methods are applied to solve the same problem and the obtained results are compared.     

A relaxed version of Bregman's method for convex programming

A new type of relaxation for Bregman's method, an iterative primal-dual algorithm for linearly constrained convex programming, is presented. It is shown that the new relaxation procedure generalizes the usual concept of relaxation and preserves the convergence properties of Bregman's algorithm for a suitable choice of the relaxation parameters. For convergence, Bregman's method requires that the objective function satisfy certain conditions. A sufficient and easily checkable condition for these requirements to hold is also given.     

Constraint aggregation principle in convex optimization

A general constraint aggregation technique is proposed for convex optimization problems. At each iteration a set of convex inequalities and linear equations is replaced by a single surrogate inequality formed as a linear combination of the original constraints. After solving the simplified subproblem, new aggregation coefficients are calculated and the iteration continues. This general aggregation principle is incorporated into a number of specific algorithms. Convergence of the new methods is proved and speed of convergence analyzed. Next, dual interpretation of the method is provided and application to decomposable problems is discussed. Finally, a numerical illustration is given.     

一致凸Banach空间中渐近非扩张映射不动点的粘性逼近

在一致凸并具有一致G可微范数的Banach空间中,研究一类渐近非扩张映象迭代序列的收敛性,给出强收敛定理.     

Iterative Methods of Solving Stochastic Convex Feasibility Problems and Applications

The stochastic convex feasibility problem (SCFP) is the problem of finding almost common points of measurable families of closed convex subsets in reflexive and separable Banach spaces. In this paper we prove convergence criteria for two iterative algorithms devised to solve SCFPs. To do that, we first analyze the concepts of Bregman projection and Bregman function with emphasis on the properties of their local moduli of convexity. The areas of applicability of the algorithms we present include optimization problems, linear operator equations, inverse problems, etc., which can be represented as SCFPs and solved as such. Examples showing how these algorithms can be implemented are also given.     

线性块SOR二级迭代法的收敛性质

内迭代次数充分大时,求解非奇异线性方程组的块SOR二级迭代法与经典的块SOR方法有相同的收敛性和大致相等的收敛速度.因此,用于块SOR方法有效的松弛因子,同样可有效地用于块SOR二级迭代法.     

A new class of alternative theorems for SOS-convex inequalities and robust optimization

In this paper, we present a new class of alternative theorems for SOS-convex inequality systems without any qualifications. This class of theorems provides an alternative equations in terms of sums of squares to the solvability of the given inequality system. A strong separation theorem for convex sets, described by convex polynomial inequalities, plays a key role in establishing the class of alternative theorems. Consequently, we show that the optimal values of various classes of robust convex optimization problems are equal to the optimal values of related semidefinite programming problems (SDPs) and so, the value of the robust problem can be found by solving a single SDP. The class of problems includes programs with SOS-convex polynomials under data uncertainty in the objective function such as uncertain quadratically constrained quadratic programs. The SOS-convexity is a computationally tractable relaxation of convexity for a real polynomial. We also provide an application of our theorem of the alternative to a multi-objective convex optimization under data uncertainty.     

关于非Hermitian正定线性代数方程组的超松弛HSS方法

本文针对求解大型稀疏非Hermitian正定线性方程组的HSS迭代方法,利用迭代法的松弛技术进行加速,提出了一种具有三个参数的超松弛HSS方法(SAHSS)和不精确的SAHSS方法(ISAHSS),它采用CG和一些Krylov子空间方法作为其内部过程,并研究了SAHSS和ISAHSS方法的收敛性.数值例子验证了新方法的有效性.     

Waveform relaxation methods for implicit differential equations

We apply a Runge-Kutta-based waveform relaxation method to initial-value problems for implicit differential equations. In the implementation of such methods, a sequence of nonlinear systems has to be solved iteratively in each step of the integration process. The size of these systems increases linearly with the number of stages of the underlying Runge-Kutta method, resulting in high linear algebra costs in the iterative process for high-order Runge-Kutta methods. In our earlier investigations of iterative solvers for implicit initial-value problems, we designed an iteration method in which the linear algebra costs are almost independent of the number of stages when implemented on a parallel computer system. In this paper, we use this parallel iteration process in the Runge-Kutta waveform relaxation method. In particular, we analyse the convergence of the method. The theoretical results are illustrated by a few numerical examples.     

A simultaneous projections method for linear inequalities

An iterative method for solving general systems of linear inequalities is considered. The method, a relaxed generalization of Cimmino's scheme for solving linear systems, was first suggested by Censor and Elfving. Each iterate is obtained as a convex combination of the orthogonal projections of the previous iterate on the half spaces defined by the linear inequalities. The algorithm is particularly suitable for implementation on computers with parallel processors. We prove convergence from any starting point for both consistent and nonconsistent systems (to a feasible point in the first case, and to a weighted least squares type solutions in the second).     

Application of Relaxation Scheme to Degenerate Variational Inequalities

In this paper we are concerned with the solution of degenerate variational inequalities. To solve this problem numerically, we propose a numerical scheme which is based on the relaxation scheme using non-standard time discretization. The approximate solution on each time level is obtained in the iterative way by solving the corresponding elliptic variational inequalities. The convergence of the method is proved.     

A convergence analysis result for constrained convex minimization problem

Abstract

Our purpose in this paper is to obtain strong convergence result for approximation of solution to constrained convex minimization problem using a new iterative scheme in a real Hilbert space. Furthermore, we give numerical analysis of our iterative scheme.     

On certain optimization methods with finite-step inner algorithms for convex finite-dimensional problems with inequality constraints

Numerical methods are proposed for solving finite-dimensional convex problems with inequality constraints satisfying the Slater condition. A method based on solving the dual to the original regularized problem is proposed and justified for problems having a strictly uniformly convex sum of the objective function and the constraint functions. Conditions for the convergence of this method are derived, and convergence rate estimates are obtained for convergence with respect to the functional, convergence with respect to the argument to the set of optimizers, and convergence to the g-normal solution. For more general convex finite-dimensional minimization problems with inequality constraints, two methods with finite-step inner algorithms are proposed. The methods are based on the projected gradient and conditional gradient algorithms. The paper is focused on finite-dimensional problems obtained by approximating infinite-dimensional problems, in particular, optimal control problems for systems with lumped or distributed parameters.     

Projected subgradient methods with non-Euclidean distances for non-differentiable convex minimization and variational inequalities

We study subgradient projection type methods for solving non-differentiable convex minimization problems and monotone variational inequalities. The methods can be viewed as a natural extension of subgradient projection type algorithms, and are based on using non-Euclidean projection-like maps, which generate interior trajectories. The resulting algorithms are easy to implement and rely on a single projection per iteration. We prove several convergence results and establish rate of convergence estimates under various and mild assumptions on the problem’s data and the corresponding step-sizes. We dedicate this paper to Boris Polyak on the occasion of his 70th birthday.