On stable least squares solution to the system of linear inequalities

The system of inequalities is transformed to the least squares problem on the positive ortant. This problem is solved using orthogonal transformations which are memorized as products. Author’s previous paper presented a method where at each step all the coefficients of the system were transformed. This paper describes a method applicable also to large matrices. Like in revised simplex method, in this method an auxiliary matrix is used for the computations. The algorithm is suitable for unstable and degenerate problems primarily.      

A hybrid algorithm for solving linear inequalities in a least squares sense

The need for solving a system of linear inequalities, A x ≥ b, arises in many applications. Yet in some cases the system to be solved turns out to be inconsistent due to measurement errors in the data vector b. In such a case it is often desired to find the smallest correction of b that recovers feasibility. That is, we are looking for a small nonnegative vector, y ≥ 0, for which the modified system A x ≥ b - y is solvable. The problem of calculating the smallest correction vector is called the least deviation problem. In this paper we present new algorithms for solving this problem. Numerical experiments illustrate the usefulness of the proposed methods.     

A smoothing-type algorithm for solving system of inequalities

In this paper we consider system of inequalities. By constructing a new smoothing function, the problem is approximated via a family of parameterized smooth equations. A Newton-type algorithm is applied to solve iteratively the smooth equations so that a solution of the problem concerned is found. We show that the algorithm is globally and locally quadratically convergent under suitable assumptions. Preliminary numerical results are reported.     

A method of local convex majorants for solving variational-like inequalities

A numerical method based on convex approximations that locally majorize a gap function is proposed for solving a variational-like inequality. The algorithm is theoretically validated and the results of comparison of its numerical efficiency to that of the conventional methods are presented.     

Perturbation analysis of global error bounds for systems of linear inequalities

This paper studies the existence of a uniform global error bound when a system of linear inequalities is under local arbitrary perturbations. Specifically, given a possibly infinite system of linear inequalities satisfying the Slater’s condition and a certain compactness condition, it is shown that for sufficiently small arbitrary perturbations the perturbed system is solvable and there exists a uniform global error bound if and only if the original system is bounded or its homogeneous system has a strict solution. Received: April 12, 1998 / Accepted: February 11, 2000?Published online July 20, 2000     

A GENERATOR AND A SIMPLEX SOLVER FOR NETWORK PIECEWISE LINEAR PROGRAMS

ＡＧＥＮＥＲＡＴＯＲＡＮＤＡＳＩＭＰＬＥＸＳＯＬＶＥＲＦＯＲＮＥＴＷＯＲＫＰＩＥＣＥＷＩＳＥＬＩＮＥＡＲＰＲＯＧＲＡＭＳＳＵＮＪＩＥ（孙捷）（ＩｎｓｔｉｔｕｔｅｏｆＡｐｐｌｉｅｄＭａｔｈｅｍｅｍａｔｉｃｓ，ｔｈｅＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉ...     

A variant of Karmarkar's linear programming algorithm for problems in standard form

This paper presents a variant of Karmarkar's linear programming algorithm that works directly with problems expressed in standard form and requires no a priori knowledge of the optimal objective function value. Rather, it uses a variation on Todd and Burrell's approach to compute ever better bounds on the optimal value, and it can be run as a prima-dual algorithm that produces sequences of primal and dual feasible solutions whose objective function values convege to this value. The only restrictive assumption is that the feasible region is bounded with a nonempty interior; compactness of the feasible region can be relaxed to compactness of the (nonempty) set of optimal solutions.     

A new algorithm for pole assignment of single-input linear systems using state feedback

In this paper we present a new algorithm for the single-input pole assignment problem using state feedback. This algorithm is based on the Schur decomposition of the closed-loop system matrix, and the numerically stable unitary transformations are used whenever possible, and hence it is numerically reliable.The good numerical behavior of this algorithm is also illustrated by numerical examples.     

An algorithm of sequential systems of linear equations for nonlinear optimization problems with arbitrary initial point

For current sequential quadratic programming (SQP) type algorithms, there exist two problems: (i) in order to obtain a search direction, one must solve one or more quadratic programming subproblems per iteration, and the computation amount of this algorithm is very large. So they are not suitable for the large-scale problems; (ii) the SQP algorithms require that the related quadratic programming subproblems be solvable per iteration, but it is difficult to be satisfied. By using ε-active set procedure with a special penalty function as the merit function, a new algorithm of sequential systems of linear equations for general nonlinear optimization problems with arbitrary initial point is presented. This new algorithm only needs to solve three systems of linear equations having the same coefficient matrix per iteration, and has global convergence and local superlinear convergence. To some extent, the new algorithm can overcome the shortcomings of the SQP algorithms mentioned above. Project partly supported by the National Natural Science Foundation of China and Tianyuan Foundation of China.     

On modification of certain methods of the conjugate direction type for solving systems of linear algebraic equations

A modification of certain well-known methods of the conjugate direction type is proposed and examined. The modified methods are more stable with respect to the accumulation of round-off errors. Moreover, these methods are applicable for solving ill-conditioned systems of linear algebraic equations that, in particular, arise as approximations of ill-posed problems. Numerical results illustrating the advantages of the proposed modification are presented.     

On modification of certain methods of the conjugate direction type for solving rectangular systems of linear algebraic equations

The use of modifications of certain well-known methods of the conjugate direction type for solving systems of linear algebraic equations with rectangular matrices is examined. The modified methods are shown to be superior to the original versions with respect to the round-off accumulation; the advantage is especially large for ill-conditioned matrices. Examples are given of the efficient use of the modified methods for solving certain fairly large ill-conditioned problems.     

不等式约束优化一个可行序列线性方程组算法

提出了求解非线性不等式约束优化问题的一个可行序列线性方程组算法. 在每次迭代中, 可行下降方向通过求解两个线性方程组产生, 系数矩阵具有较好的稀疏性. 在较为温和的条件下, 算法具有全局收敛性和强收敛性, 数值试验表明算法是有效的.     

An optimal regularizing algorithm for the recovery of functionals in linear inverse problems with sourcewise represented solution

A linear operator equation with a sourcewise represented exact solution is solved approximately. To this end, the method of extending compacts developed in an earlier work is applied. Based on this method, a new algorithm is proposed for recovering the value of a linear functional at the solution of the linear operator equation. This algorithm is shown to be an optimal regularizing one.     

A new sequential systems of linear equations algorithm of feasible descent for inequality constrained optimization

Based on a new efficient identification technique of active constraints introduced in this paper, a new sequential systems of linear equations （SSLE） algorithm generating feasible iterates is proposed for solving nonlinear optimization problems with inequality constraints. In this paper, we introduce a new technique for constructing the system of linear equations, which recurs to a perturbation for the gradients of the constraint functions. At each iteration of the new algorithm, a feasible descent direction is obtained by solving only one system of linear equations without doing convex combination. To ensure the global convergence and avoid the Maratos effect, the algorithm needs to solve two additional reduced systems of linear equations with the same coefficient matrix after finite iterations. The proposed algorithm is proved to be globally and superlinearly convergent under some mild conditions. What distinguishes this algorithm from the previous feasible SSLE algorithms is that an improving direction is obtained easily and the computation cost of generating a new iterate is reduced. Finally, a preliminary implementation has been tested.     

Convergence properties of trust region methods for linear and convex constraints

We develop a convergence theory for convex and linearly constrained trust region methods which only requires that the step between iterates produce a sufficient reduction in the trust region subproblem. Global convergence is established for general convex constraints while the local analysis is for linearly constrained problems. The main local result establishes that if the sequence converges to a nondegenerate stationary point then the active constraints at the solution are identified in a finite number of iterations. As a consequence of the identification properties, we develop rate of convergence results by assuming that the step is a truncated Newton method. Our development is mainly geometrical; this approach allows the development of a convergence theory without any linear independence assumptions.Work supported in part by the Applied Mathematical Sciences subprogram of the Office of Energy Research of the U.S. Department of Energy under Contract W-31-109-Eng-38.Work supported in part by the National Science Foundation grant DMS-8803206 and by the Air Force Office of Scientific Research grant AFSOR-860080.     

A two-step matrix splitting iteration paradigm based on one single splitting for solving systems of linear equations

For solving large sparse systems of linear equations, we construct a paradigm of two-step matrix splitting iteration methods and analyze its convergence property for the nonsingular and the positive-definite matrix class. This two-step matrix splitting iteration paradigm adopts only one single splitting of the coefficient matrix, together with several arbitrary iteration parameters. Hence, it can be constructed easily in actual applications, and can also recover a number of representatives of the existing two-step matrix splitting iteration methods. This result provides systematic treatment for the two-step matrix splitting iteration methods, establishes rigorous theory for their asymptotic convergence, and enriches algorithmic family of the linear iteration solvers, for the iterative solutions of large sparse linear systems.     

A parallel projection method for a system of nonlinear variational inequalities

In this paper, we introduce and consider a new system of nonlinear variational inequalities involving two different operators. Using the parallel projection technique, we suggest and analyze an iterative method for this system of variational inequalities. We establish a convergence result for the proposed method under certain conditions. Our results can be viewed as a refinement and improvement of the previously known results for variational inequalities.     

A highly accurate Jacobi collocation algorithm for systems of high‐order linear differential–difference equations with mixed initial conditions

In this paper, a shifted Jacobi–Gauss collocation spectral algorithm is developed for solving numerically systems of high‐order linear retarded and advanced differential–difference equations with variable coefficients subject to mixed initial conditions. The spatial collocation approximation is based upon the use of shifted Jacobi–Gauss interpolation nodes as collocation nodes. The system of differential–difference equations is reduced to a system of algebraic equations in the unknown expansion coefficients of the sought‐for spectral approximations. The convergence is discussed graphically. The proposed method has an exponential convergence rate. The validity and effectiveness of the method are demonstrated by solving several numerical examples. Numerical examples are presented in the form of tables and graphs to make comparisons with the results obtained by other methods and with the exact solutions more easier. Copyright © 2015 John Wiley & Sons, Ltd.