模糊线性规划问题的一种新的单纯形算法

提出求解模糊线性规划问题的一种新的思路 ,就是应用单纯形法先求解与 (FLP)相应的普通线性规划问题 ,通过模糊约束集与模糊目标集的隶属度的比较 ,获得两个集合交集的最优隶属度 ,将此最优隶属度代入最优单纯形表中 ,即可求得 (FLP)的解。本算法只需在一张适当的迭代表台上执行单纯形迭代过程 ,简捷方便适用     

Variable metric relaxation methods,part II: The ellipsoid method

The deepest, or least shallow, cut ellipsoid method is a polynomial (time and space) method which finds an ellipsoid, representable by polynomial space integers, such that the maximal ellipsoidal distance relaxation method using this fixed ellipsoid is polynomial: this is equivalent to finding a linear transforming such that the maximal distance relaxation method of Agmon, Motzkin and Schoenberg in this transformed space is polynomial. If perfect arithmetic is used, then the sequence of ellipsoids generated by the method converges to a set of ellipsoids, which share some of the properties of the classical Hessian at an optimum point of a function; and thus the ellipsoid method is quite analogous to a variable metric quasi-Newton method. This research was supported in part by the F.C.A.C. of Quebec, and the N.S.E.R.C. of Canada under Grant A 4152.     

A barrier method for dynamic Leontief-type linear programs

In this paper, we specialize Gill et al.'s projected Newton barrier method to solve a large-scale linear program of dynamic (i.e. multistage) Leontief-type constraints. We propose an efficient and stable method for solving the least-squares subproblems, the crucial part of the barrier method. The key step is to exploit a special structure of the constraint matrix and reduce the matrix of the normal equation for the least-squares problem to a banded matrix. By comparing the average-case operations count of this specialized barrier method with that of the sparse simplex method, we show that this method performs at least O(T) faster than the simplex method for such stype of linear programs, where T is the number of time periods (i.e. stages).     

Intelligent gradient search in linear programming

The simplex algorithm is still the best known and most frequently used way to solve LP problems. Khachian has suggested a method to solve these problems in polynomial time. The average behaviour of his method, however, is still inferior to the modern simplex based LP codes. A new gradient based approach which also has polynomial worst-case behaviour has been suggested by Karmarkar. This method was modified, programmed and compared with other available LP codes. It is shown that the numerical efficiency of Karmarkar's method compares favourably with other LP codes, particularly for problems with high numbers of variables and few constraints.     

线性规划在回归分析中的应用

线性回归中,针对最小二乘法的两个替代准则一绝对离差和最小准则以及最大绝对离差最小准则,利用线性规划技术建立回归预测模型。实用分析表明,线性规划模型具有较好的预测效果,有郊地消除了统计数据中异常值对回归方程的影响。     

A convergent criss-cross method

Our paper presents a new Criss-Cross method for solving linear programming problems. Starting from a neither primal nor dual feasible solution, we reach an optimal solution in finite number of steps if it exists. If there is no optimal solution, then we show that there is not primal feasible or dual feasible solution, We prove the finiteness of this procedure. Our procedure is not the same as the primal or dual simplex method if we have a primal or dual feasible solution, so we have constructed a quite new procedure for solving linear programming problems.     

一种改进的多维偏好线性规划分析方法

本文对传统的多维偏好线性规划分析方法—LINMAP法进行改进,提出一种新的多维偏好线性规划分析方法,该方法运用加性加权法建立线性规划模型,同时引入任意小正数δ,使得评价结果更加符合决策人偏好集。     

Affirmative action algorithms

Affirmative action is a new variety of selection rule which employs historical information to favor the choice of elements that have not been selected in the past. We categorize three implementations of this principle and discuss their application to the simplex method, to Bard-type schemes for the linear complementarity problem, and to augmenting path methods for network flow problems. We present analytical and computational results, and some open questions.Research supported by the Georgia Institute of Technology.Research supported by the New Faculty Research Development Program of the Georgia Institute of Technology. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

求解线性矩问题的一个修正方法

1．引言许多问题都可化为线性矩问题的求解,最典型的例子就是求解第一类线性积分方程的配置法．第一类算子方程在不同国数空间的离散化得到不同形式的线性矩问题．1968年,地质学家GBackusandFGilbert给出了一种求解线性矩问题的方法,用来求解地球物理反问题,后来称之为B－G方法,山从理论上严格论证了其收敛性．问给出了一种求解线形矩问题的光顺方法,门讨论了再生核空间的rG方法,并将其用于信号处理．以上方法的核心思想是在某类函数空间寻求对利一函数的逼近,从而得到线性矩问题的近似解．本交给出了一种求解线性矩问题的修正方…     

Solving staircase linear programs by the simplex method, 1: Inversion

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or staircase, structure. The present paper looks at inversion routines within the simplex method, particularly those for sparse triangular factorization of a basis by Gaussian elimination and for solution of triangular linear systems. The succeeding paper examines pricing routines. Both papers describe extensive (though preliminary) computational experience, and can point to some quite promising results.     

Solving staircase linear programs by the simplex method, 2: Pricing

This and a companion paper consider how current implementations of the simplex method may be adapted to better solve linear programs that have a staged, or ‘staircase’, structure. The preceding paper considered ‘inversion’ routines that factorize the basis and solve linear systems. The present paper examines ‘pricing’ routines that compute reduced costs for nonbasic variables and that select a variable to enter the basis at each iteration. Both papers describe extensive (although preliminary) computer experiments, and can point to some quite promising results. For pricing in particular, staircase computation strategies appear to offer modest but consistent savings; staircase selection strategies, properly chosen, may offer substantial savings in number of iterations, time per iteration, or both.     

A relaxed version of Karmarkar's method

A relaxed version of Karmarkar's method is developed. This method is proved to have the same polynomial time complexity as Karmarkar's method and its efficient implementation using inexact projections is discussed. Computational results obtained using a preliminary implementation of the method are presented which indicate that the method is practicable.This research was supported in part by NSF Grants CDR 84-21402 and DMS-85-12277 and ONR Contract N00014-87-K-0214.     

A projection and contraction method for a class of linear complementarity problems and its application in convex quadratic programming

In this paper we propose a new iterative method for solving a class of linear complementarity problems:u 0,Mu + q 0, u^T(Mu + q)=0, where M is a givenl ×l positive semidefinite matrix (not necessarily symmetric) andq is a givenl-vector. The method makes two matrix-vector multiplications and a trivial projection onto the nonnegative orthant at each iteration, and the Euclidean distance of the iterates to the solution set monotonously converges to zero. The main advantages of the method presented are its simplicity, robustness, and ability to handle large problems with any start point. It is pointed out that the method may be used to solve general convex quadratic programming problems. Preliminary numerical experiments indicate that this method may be very efficient for large sparse problems.On leave from the Department of Mathematics, University of Nanjing, Nanjing, People's Republic of China.     

局部线性插值算子的一个构造方法

利用具有紧支集函数平移变换的拟任值是逼近论中的构造算子的一个重要方法,但拟插值算子一般不具有插值性质,本提供了一个简单的方法,该法可以构造出许多具有拟插值优点,又具有插值性质的线性算子。     

Primal—dual methods for linear programming

Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method.In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility.Finally, a new method for treating free variables is proposed.Presented at the Second Asilomar Workshop on Progress in Mathematical Programming, February 1990, Asilomar, CA, United StatesThe material contained in this paper is based upon research supported by the National Science Foundation Grant DDM-9204208 and the Office of Naval Research Grant N00014-90-J-1242.     

Iterative solution of linear equations with unbounded operators

A convergent iterative process is constructed for solving any solvable linear equation in a Hilbert space, including equations with unbounded, closed, densely defined linear operators. The method is proved to be stable towards small perturbation of the data. Some abstract results are established and used in an analysis of variational regularization method for equations with unbounded linear operators. The dynamical systems method (DSM) is justified for unbounded, closed, densely defined linear operators. The stopping time is chosen by a discrepancy principle. Equations with selfadjoint operators are considered separately. Numerical examples, illustrating the efficiency of the proposed method, are given.     

On the convergence of the method for indefinite integration of oscillatory and singular functions

We consider the problem of convergence and error estimation of the method for computing indefinite integrals proposed in Keller [8]. To this end, we have analysed the properties of the difference operator related to the difference equation for the Chebyshev coefficients of a function that satisfies a given linear differential equation with polynomial coefficients. Properties of this operator were never investigated before. The obtained results lead us to the conclusion that the studied method is always convergent. We also give a rigorous proof of the error estimates.     

Sensitivity method for basis inverse representation in multistage stochastic linear programming problems

A version of the simplex method for solving stochastic linear control problems is presented. The method uses a compact basis inverse representation that extensively exploits the original problem data and takes advantage of the supersparse structure of the problem. Computational experience indicates that the method is capable of solving large problems.This research was supported by Programs CPBP02.15 and RPI.02.     

Uzawa block relaxation method for the unilateral contact problem

We present a Uzawa block relaxation method for the numerical resolution of contact problems with or without friction, between elastic solids in small deformations. We introduce auxiliary unknowns to separate the linear elasticity subproblem from the unilateral contact and friction conditions. Applying a Uzawa block relaxation method to the corresponding augmented Lagrangian functional yields a two-step iterative method with a linear elasticity problem as a main subproblem while auxiliary unknowns are computed explicitly. Numerical experiments show that the method are robust and scalable with a significant saving of computational time.     

Families of regular solutions of singular systems

The seminal 1969 paper of W.A. Harris Jr., Y. Sibuya, and L. Weinberg provided new proofs for the Perron-Lettenmeyer theorem, as well as several other classical results, and has stimulated renewed consideration of families of regular solutions of certain singular problems. In this paper we give some further applications of the method developed there and, in addition, examine some connections between the Lettenmeyer theorem and an alternative theorem which addresses a problem posed by H.L. Turrittin that dates back to an 1845 example of Briot and Bouquet