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.     

On the effectiveness of projection methods for convex feasibility problems with linear inequality constraints

The effectiveness of projection methods for solving systems of linear inequalities is investigated. It is shown that they often have a computational advantage over alternatives that have been proposed for solving the same problem and that this makes them successful in many real-world applications. This is supported by experimental evidence provided in this paper on problems of various sizes (up to tens of thousands of unknowns satisfying up to hundreds of thousands of constraints) and by a discussion of the demonstrated efficacy of projection methods in numerous scientific publications and commercial patents (dealing with problems that can have over a billion unknowns and a similar number of constraints).     

A relaxation method for reconstructing objects from noisy X-rays

An algorithm is presented for estimating the density distribution in a cross section of an object from X-ray data, which in practice is unavoidably noisy. The data give rise to a large sparse system of inconsistent equations, not untypically 10⁵ equations with 10⁴ unknowns, with only about 1% of the coefficients non-zero. Using the physical interpretation of the equations, each equality can in principle be replaced by a pair of inequalities, giving us the limits within which we believe the sum must lie. An algorithm is proposed for solving this set of inequalities. The algorithm is basically a relaxation method. A finite convergence result is proved. In spite of the large size of the system, in the application area of interest practical solution on a computer is possible because of the simple geometry of the problem and the redundancy of equations obtained from nearby X-rays. The algorithm has been implemented, and is demonstrated by actual reconstructions.     

An algorithm for linear least squares problems with equality and nonnegativity constraints

We present a new algorithm for solving a linear least squares problem with linear constraints. These are equality constraint equations and nonnegativity constraints on selected variables. This problem, while appearing to be quite special, is the core problem arising in the solution of the general linearly constrained linear least squares problem. The reduction process of the general problem to the core problem can be done in many ways. We discuss three such techniques.The method employed for solving the core problem is based on combining the equality constraints with differentially weighted least squares equations to form an augmented least squares system. This weighted least squares system, which is equivalent to a penalty function method, is solved with nonnegativity constraints on selected variables.Three types of examples are presented that illustrate applications of the algorithm. The first is rank deficient, constrained least squares curve fitting. The second is concerned with solving linear systems of algebraic equations with Hilbert matrices and bounds on the variables. The third illustrates a constrained curve fitting problem with inconsistent inequality constraints.     

Fejér processes in theory and practice: Recent results

In this paper we briefly survey the recent results of the theory of Fejér mappings and processes as applied to solving various mathematical problems, including structured systems of linear and convex inequalities, operator equations, as well as problems of linear and quadratic programming which are not necessarily solvable (improper ones).     

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

Nonlinear mappings associated with the generalized linear complementarity problem

We show that the Cottle—Dantzig generalized linear complementarity problem (GLCP) is equivalent to a nonlinear complementarity problem (NLCP), a piecewise linear system of equations (PLS), a multiple objective programming problem (MOP), and a variational inequalities problem (VIP). On the basis of these equivalences, we provide an algorithm for solving problem GLCP.Project partially supported by a grant from Oak Ridge Associated Universities, TN, USA.     

The linearization method: Principal concepts and perspective directions

The linearization method, for solving the general problem of nonlinear programming and its various modifications, is considered. On the basic ideas of the linearization method, the algorithms for solving the various problems of mathematical programming are constructed for (a) solving systems of equalities and inequalities, (b) multiobjective programming and (c) complementary problem.     

An Algorithm for Solving Optimization Problems with One Linear Objective Function and Finitely Many Constraints of Fuzzy Relation Inequalities

An optimization model with one linear objective function and fuzzy relation equation constraints was presented by Fang and Li (1999) as well as an efficient solution procedure was designed by them for solving such a problem. A more general case of the problem, an optimization model with one linear objective function and finitely many constraints of fuzzy relation inequalities, is investigated in this paper. A new approach for solving this problem is proposed based on a necessary condition of optimality given in the paper. Compared with the known methods, the proposed algorithm shrinks the searching region and hence obtains an optimal solution fast. For some special cases, the proposed algorithm reaches an optimal solution very fast since there is only one minimum solution in the shrunk searching region. At the end of the paper, two numerical examples are given to illustrate this difference between the proposed algorithm and the known ones.     

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.     

The Γ-algorithm and some applications

In this paper the power of the Γ-algorithm for obtaining the dual of a given cone and some of its multiple applications is discussed. The meaning of each sequential tableau appearing during the process is interpreted. It is shown that each tableau contains the generators of the dual cone of a given cone and that the algorithm updates the dual cone when new generators are incorporated. This algorithm, which is based on the duality concept, allows one to solve many problems in linear algebra, such as determining whether or not a vector belongs to a cone, obtaining the minimal representations of a cone in terms of a linear space and an acute cone, obtaining the intersection of two cones, discussing the compatibility of linear systems of inequalities, solving systems of linear inequalities, etc. The applications are illustrated with examples.     

Absolute value programming

We investigate equations, inequalities and mathematical programs involving absolute values of variables such as the equation Ax+B|x| = b, where A and B are arbitrary m× n real matrices. We show that this absolute value equation is NP-hard to solve, and that solving it with B = I solves the general linear complementarity problem. We give sufficient optimality conditions and duality results for absolute value programs as well as theorems of the alternative for absolute value inequalities. We also propose concave minimization formulations for absolute value equations that are solved by a finite succession of linear programs. These algorithms terminate at a local minimum that solves the absolute value equation in almost all solvable random problems tried.     

Upper bounds on the complexity of solving systems of linear equations

The article is of the nature of a survey and is devoted to direct (exact) methods of solving systems of linear equations examined from the point of view of their computational complexity. The construction of most of the algorithms is outlined. The paper consists of two parts. Series methods of solving systems of linear equations are examined in the first part. It includes the algorithms of Gauss and of Konoval'tsev, Strassen's algorithm and its modifications, the YunGustavson results for Toeplitz systems, etc. The second part is devoted to parallel methods of solving systems of linear equations. Examined here are the parallelization of the Gauss algorithm, the results of Hyafil and Kung on complexity estimate of the parallel solution of triangular systems, Csanky's results based on the parallelization of Leverrier's method, Hyabil's general result on the parallelization of a straight-line program for computing polynomials, Stone's algorithm for the parallel solving of tridiagonal systems. Several new bounds are derived. In particular, if a pair of (n×n) -matrices can be multiplied sequentially by a straight-line program of complexity O(n^d), then it is possible to solve an arbitrary system of m linear equations in n unknowns on p processors with the complexity $$0\left( {\frac{{max(m, n)min(m, n)^{\alpha - 1} }}{p} + min(m, n)log_2 max(m, n)} \right),$$ , and to solve a triangular system of sizen with the complexity $$0\left( {\frac{{n^2 }}{p} + \frac{n}{{p^{1/\alpha } }}log_2^{1 - \tfrac{1}{\alpha }} n + log_2^2 n} \right).$$      

Serre’s Reduction of Linear Functional Systems

Serre’s reduction aims at reducing the number of unknowns and equations of a linear functional system. Finding an equivalent presentation of a linear functional system containing fewer equations and fewer unknowns can generally simplify both the study of the structural properties of the linear functional system and of different numerical analysis issues, and it can sometimes help solving the linear functional system. The purpose of this paper is to present a constructive approach to Serre’s reduction for determined and underdetermined linear functional systems.     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

正交异性双材料的Ⅱ型界面裂纹尖端场

通过引入含16个待定实系数和两个实应力奇异指数的应力函数,再借助边界条件,得到了两个八元非齐次线性方程组.求解该方程组,在双材料工程参数满足适当条件下,确定了两个实应力奇异指数.根据极限唯一性定理,求出了全部系数,得到了应力函数的表示式.代入相应的力学公式,推出了当特征方程组两个判别式都小于0时,每种材料的裂纹尖端应力强度因子、应力场和位移场的理论解.裂纹尖端附近的应力和位移有混合型断裂特征,但没有振荡奇异性和裂纹面相互嵌入现象作为特例,当两种正交异性材料相同时,可以推出正交异性单材料Ⅱ型断裂的应力奇异指数、应力强度因子公式、应力场、位移场表示式.     

Convergence results for an accelerated nonlinear cimmino algorithm

Summary We present an accelerated version of Cimmino's algorithm for solving the convex feasibility problem in finite dimension. The algorithm is similar to that given by Censor and Elfving for linear inequalities. We show that the nonlinear version converges locally to a weighted least squares solution in the general case and globally to a feasible solution in the consistent case. Applications to the linear problem are suggested.     

Economic dynamics with computer algebra systems

The aim of this work is to analyse some possibilities offered by computer algebra systems as a tool for studying economic dynamics. Not only do they enable the solving of problems of considerable difficulty with undergraduate levels of mathematical knowledge but they also allow the approach to the problem itself to be transformed. In this context, the paper illustrates the strategies for studying the Shinkai two-sector model using Maple V®.     

Two-sided linear split quaternionic equations with n unknowns

In this paper, we investigate linear split quaternionic equations with the terms of the form axb. We give a new method of solving general linear split quaternionic equations with one, two and n unknowns. Moreover, we present some examples to show how this procedure works.     

On designing H∞ fault estimator for switched nonlinear systems of neutral type

This paper deals with the problem of fault estimation for a class of switched nonlinear systems of neutral type. The nonlinearities are assumed to satisfy global Lipschitz conditions and appear in both the state and measured output equations. By employing a switched observer-based fault estimator, the problem is formulated as an H_∞ filtering problem. Sufficient delay-dependent existence conditions of the H_∞ fault estimator (H_∞-FE) are given in terms of certain matrix inequalities based on the average dwell time approach. In addition, by using cone complementarity algorithm, the solutions to the observer gain matrices are obtained by solving a set of linear matrix inequalities (LMIs). A numerical example is provided to demonstrate the effectiveness of the proposed approach.