An automatic relaxation method for solving interval linear inequalities

The problem of solving iteratively a large and possibly sparse system of interval linear inequalities α ? Ax ? β is considered. An algorithm of the row-action type is proposed which, in each iterative step, effectively takes account of a pair of inequalities describing a single interval inequality. The algorithm realizes in an automatic manner a relaxation principle proposed by Goffin but also allows further external relaxation parameters.     

A primal-dual projection method for solving systems of linear inequalities

An algorithm is described for finding a feasible point for a system of linear inequalities. If the solution set has nonempty interior, termination occurs after a finite number of iterations. The algorithm is a projection-type method, similar to the relaxation methods of Agmon, Motzkin, and Schoenberg. It differs from the previous methods in that it solves for a certain “dual” solution in addition to a primal solution.     

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).     

On relaxation methods for systems of linear inequalities

In their classical papers Agmon and Motzkin and Schoenberg introduced a relaxation method to find a feasible solution for a system of linear inequalities. So far the method was believed to require infinitely many iterations on some problem instances since it could (depending on the dimension of the set of feasible soltions) converge asymptotically to a feasible solution, if one exists. Hence it could not be used to determine infeasibility.Using two lemma's basic to Khachian's polynomially bounded algorithm we can show that the relaxation method is finite in all cases and thus can handle infeasible systems as well. In spite of more refined stopping criteria the worst case behaviour of the relaxation method is not polynomially bounded as examplified by a class of problems constructed here.     

On the non-polynomiality of the relaxation method for systems of linear inequalities

A class of linear programs is given in which the relaxation method for inequalities, under the same operating rules as Khacian's method, is not polynomial in the length of the input. This result holds for any value of the relaxation parameter.This research was supported in part by the D.G.E.S. (Quebec), the N.S.E.R.C. of Canada under grant A 4152, and the S.S.H.R.C. of Canada.     

The projective method for solving linear matrix inequalities

Numerous problems in control and systems theory can be formulated in terms of linear matrix inequalities (LMI). Since solving an LMI amounts to a convex optimization problem, such formulations are known to be numerically tractable. However, the interest in LMI-based design techniques has really surged with the introduction of efficient interior-point methods for solving LMIs with a polynomial-time complexity. This paper describes one particular method called the Projective Method. Simple geometrical arguments are used to clarify the strategy and convergence mechanism of the Projective algorithm. A complexity analysis is provided, and applications to two generic LMI problems (feasibility and linear objective minimization) are discussed.     

A discretization method for systems of linear inequalities

We investigate a method for approximating a convex domainCR ⁿ described by a (possibly infinite) set of linear inequalities. In contrast to other methods, the approximating domains (polyhedrons) lie insideC. We discuss applications to semi-infinite programming and present numerical examples.The paper was written at the Institut für Angewandte Mathematik, Universität Hamburg, Hamburg, West Germany. The author thanks Prof. U. Eckhardt, Dr. K. Roleff, and Prof. B. Werner for helpful discussions.     

An two phase abs method for solving over determined systems of linear inequalities

The method, called the Multi-Stage ABS algorithm, for solving the over-determined linear inequalities system and the system combined with the over-determined linear inequalities and the equations is presented. This method is characterized by translating inequalities system to an equations system with slack variables. The explicit solution with the slack variables of the equations system are given by the implicit LU algorithm, then the slack variables can be given by the ABS algorithm. Finally, the upper multiplications of the algorithm are given.     

Integrodifferential systems with infinitely many delays

Summary In this paper we consider the initial-value problems: (P ₁ )X(t)=(AX)(t) for t>0, X(0+)=I, X(t)=0 for t<0 and (P ₂ ) Y(t)=(QY)(t) for t>0, Y(0+)=I, Y(t)=0 for t<0, where A and Q are linear specified operators, I and0 — the identity and null matrices of order n, and X(t), Y(t) are unknown functions whose values are square matrices of order n. Sufficient conditions are established under which the problems (P ₁ ) and (P ₂ ) have the same unique solution, locally summable on the half-axis t ⩾0. Using this fact and some properties of the Laplace transform we find a new proof for the variation of constants formula given in[1, 2]. On the basis of this formula we derive certain results concerning a class of integrodifferential systems with infinite delay. Entrata in Redazione il 2 marzo 1977.     

Optimal prediction for linear regression with infinitely many parameters

The problem of optimal prediction in the stochastic linear regression model with infinitely many parameters is considered. We suggest a prediction method that outperforms asymptotically the ordinary least squares predictor. Moreover, if the random errors are Gaussian, the method is asymptotically minimax over ellipsoids in ?₂. The method is based on a regularized least squares estimator with weights of the Pinsker filter. We also consider the case of dynamic linear regression, which is important in the context of transfer function modeling.     

On polling systems with infinitely many stations

The research was financially supported in part by the International Science Foundation (Grant NR8300) and the INTAS (Grant 93-820).     

Convergence of the cyclical relaxation method for linear inequalities

The relaxation method for linear inequalities is studied and new bounds on convergence obtained. An asymptotically tight estimate is given for the case when the inequalities are processed in a cyclical order. An improvement of the estimate by an order of magnitude takes place if strong underrelaxation is used. Bounds on convergence usually involve the so-called condition number of a system of linear inequalities, which we estimate in terms of their coefficient matrix. Paper presented at the XI. International Symposium on Mathematical Programming, Bonn, August 23–27, 1982.     

Approximate controllability results for viscoelastic flows with infinitely many relaxation modes

We prove results on approximate controllability for linear viscoelastic flows, with a localized distributed control in the momentum balance equation. The constitutive law is a multimode Maxwell or Jeffreys model with an infinite number of relaxation modes.     

The relaxation method for inconsistent systems of linear inequalities (The limit-point set)

The finiteness of the set of limit points obtained by successive projection of an element of Rⁿ on the boundary of the furthest half-space of a finite system of half-spaces with no common points is investigated. Related questions are considered.Translated from Matematicheskie Zametki, Vol. 5, No. 4, pp. 449–456, April, 1969.     

A COCR method for solving complex symmetric linear systems

The Conjugate Orthogonal Conjugate Gradient (COCG) method has been recognized as an attractive Lanczos-type Krylov subspace method for solving complex symmetric linear systems; however, it sometimes shows irregular convergence behavior in practical applications. In the present paper, we propose a Conjugate A$A$-Orthogonal Conjugate Residual (COCR) method, which can be regarded as an extension of the Conjugate Residual (CR) method. Numerical examples show that COCR often gives smoother convergence behavior than COCG.     

Entropic perturbation method for solving a system of linear inequalities

The problem of finding an $\text{x∈}\text{R}{}^{\mathrm{n}}$ such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.     

A conditional gradient method with linear rate of convergence for solving convex linear systems

We consider the problem of finding a point in the intersection of an affine set with a compact convex set, called a convex linear system (CLS). The conditional gradient method is known to exhibit a sublinear rate of convergence. Exploiting the special structure of (CLS), we prove that the conditional gradient method applied to the equivalent minimization formulation of (CLS), converges to a solution at a linear rate, under the sole assumption that Slaters condition holds for (CLS). The rate of convergence is measured explicitly in terms of the problems data and a Slater point. Application to a class of conic linear systems is discussed.Acknowldegements. We thank two referees for their constructive comments which has led to improve the presentation.     

A relaxation modulus-based matrix splitting iteration method for solving linear complementarity problems

In this paper, a relaxation modulus-based matrix splitting iteration method is established, which covers the known general modulus-based matrix splitting iteration methods. The convergence analysis and the strategy of the choice of the parameters are given. Numerical examples show that the proposed methods are efficient and accelerate the convergence performance with less iteration steps and CPU times.