Formulation of linear problems and solution by a universal machine

Using the predicate language for ordered fields a class of problems referred to aslinear problems is defined. This class contains, for example, all systems of linear equations and inequalities, all linear programming problems, all integer programming problems with bounded variables, all linear complementarity problems, the testing of whether sets that are defined by linear inequalities are semilattices, all satisfiability problems in sentenial logic, the rank-computation of matrices, the computation of row-reduced echelon forms of matrices, and all quadratic programming problems with bounded variables. A single, one, algorithm, to which we refer as theUniversal Linear Machine, is described. It solves any instance of any linear problem. The Universal Linear Machine runs in two phases. Given a linear problem, in the first phase a Compiler running on a Turing Machine generates alinear algorithm for the problem. Then, given an instance of the linear problem, in the second phase the linear algorithm solves the particular instance of the linear problem. The linear algorithm is finite, deterministic, loopless and executes only the five ordered field operations — additions, multiplications, subtractions, divisions and comparisons. Conversely, we show that for each linear algorithm there is a linear problem which the linear algorithm solves uniquely. Finally, it is shown that with a linear algorithm for a linear problem, one can solve certain parametric instances of the linear problem.Research was supported in part by the National Science Foundation Grant DMS 92-07409, by the Department of Energy Grant DE-FG03-87-ER-25028, by the United States—Israel Binational Science Foundation Grant 90-00434 and by ONR Grant N00014-92-J1142.Corresponding author.     

不可约线性置换及其计数

提出了不可约线性置换的概念,利用线性代数理论研究了不可约线性置换σ的性质,利用这些性质给出了最大线性置换的一个刻画,进而证明了不可约线性置换σ关于Fn2中任意非零元素的轮换长度一定等于σ的特征多项式的周期,最后利用群在集合上作用的有关结果给出了不可约线性置换的一个计数公式.     

矩阵损失下一般Gauss-Markov模型线性预测的可容许性

本文研究了一般Gauss-Markov模型中线性可预测变量的线性预测的可容许性.在给出线性预测可容许性定义的基础上,通过构造一个特殊的常量矩阵D0,分别得到了齐次和非齐次线性预测类中可容许的充要条件.     

Maximality of linear continuous logic

The linear compactness theorem is a variant of the compactness theorem holding for linear formulas. We show that the linear fragment of continuous logic is maximal with respect to the linear compactness theorem and the linear elementary chain property. We also characterize linear formulas as those preserved by the ultramean construction.     

延迟积分微分方程线性多步方法的稳定性分析

考虑带常延迟的延迟积分微分方程线性系统零解的渐近稳定性，本文采用拉格朗日插值的线性多步方法，探讨了系统数值方法的线性稳定性。证明了所有A-稳定且强零-稳定的Pouzet型线性多步方法能够保持原线性系统的延迟不依赖稳定性。     

Über die Gleichstetigkeit von Mengen von linearen Abbildungen und eine Klasse von topologischen linearen Räumen

In the first part of this paper we proof the following theorem: Let E and F be topological linear spaces, α an infinite cardinal number, and H a set of linear mappings from E into F such that every subset G of H with cardinality |G|≤α is equicontinuous. Then H is equicontinuous on every linear subspace of E which is the closed linear hull of a family (B_L;L∈I), |I|≤α, of precompact subsets of E. In the second part we introduce the class of all topological linear spaces E with the following property: A set H of linear mappings from E into a topological linear space is equicontinuous, if every countable subset of H is equicontinuous. We show that this class is closed with respect to forming topological products and linear final topologies.     

Models of linear logic

We engage a study of nonmodal linear logic which takes times ⊗ and the linear conditional ⊸ to be the basic connectives instead of times and linear negation ()^⊥ as in Girard's approach. This difference enables us to obtain a very large subsystem of linear logic (called positive linear logic) without an involutionary negation (if the law of double negation is removed from linear logic in Girard's formulation, the resulting subsystem is extremely limited). Our approach enables us to obtain several natural models for various subsystems of linear logic, including a generic model for the so-called minimal linear logic. In particular, it is seen that these models arise spontaneously in the transition from set theory to multiset theory. We also construct a model of full (nonmodal) linear logic that is generic relative to any model of positive linear logic. However, the problem of constructing a generic model for positive linear logic remains open. Bibliography: 2 titles. Published inZapiski Nauchnykh Seminarov POMI, Vol. 220, 1995, pp. 23–35. Original     

平衡损失下约束线性回归模型中回归系数的可容许估计

本文在平衡损失函数下得到等式约束模型中回归系数在齐次(非齐次)估计类中存在可容许估计的充要条件,给出带有不完全椭球约束模型中回归系数的线性估计在一切估计类中为可容许估计的充要条件.     

Parametric simplex algorithms for solving a special class of nonconvex minimization problems

It is shown that parametric linear programming algorithms work efficiently for a class of nonconvex quadratic programming problems called generalized linear multiplicative programming problems, whose objective function is the sum of a linear function and a product of two linear functions. Also, it is shown that the global minimum of the sum of the two linear fractional functions over a polytope can be obtained by a similar algorithm. Our numerical experiments reveal that these problems can be solved in much the same computational time as that of solving associated linear programs. Furthermore, we will show that the same approach can be extended to a more general class of nonconvex quadratic programming problems.     

Aglianò-Montagna type decomposition of linear pseudo hoops and its applications

We decompose every linear pseudo hoop as an Aglianò-Montagna type of ordinal sum of linear Wajsberg pseudo hoops which are either negative cones of linear ?-groups or intervals in linear unital ?-groups with strong unit. We apply the decomposition to present a new proof that every linear pseudo BL-algebra and consequently every representable pseudo BL-algebra is good. Moreover, we show that every maximal filter and every value of a linear pseudo hoop is normal, and every σ-complete linear pseudo hoop is commutative.     

Boundedness and closedness of linear relations

This paper focuses on boundedness and closedness of linear relations, which include both single-valued and multi-valued linear operators. A new (single-valued) linear operator induced by a linear relation is introduced, and its relationships with other two important induced linear operators are established. Several characterizations for closedness, closability, bundedness, relative boundedness and boundedness from below (above) of linear relations are given in terms of their induced linear operators. In particular, the closed graph theorem for linear relations in Banach spaces is completed, and stability of closedness of linear relations under bounded and relatively bounded perturbations is studied. The results obtained in the present paper generalize the corresponding results for single-valued linear operators to multi-valued linear operators, and some improve or relax certain assumptions of the related existing results.     

Equivalence of the Generalized Vertical Block Linear Complementarity Problems and Linear Complementarity Problems

In this paper, generalization of a vertical block linear complementarity problem associated with two different types of matrices, one of which is a square matrix and the other is a vertical block matrix, is proposed. The necessary and sufficient conditions for the existence of the solution of the generalized vertical block linear complementarity problem is derived and the relationship between the solution set of the generalized vertical block linear complementarity problem and the linear complementarity problem is established. It is proved that the generalized vertical block linear complementarity problem has the P-property if and only if the vertical block linear complementarity problem has the P-property.     

带有不完全椭球约束的线性模型中线性估计的可容许性

本文刻划了线性模型（Ｙ，Ｘβ，σ２Ｖ，Ｖ≥０）在不完全椭球约束：（β－β０）’Ｎ（β－ β Ｐ０）≤σ２，Ｎ ≥ ０下的线性估计的可容许性．本文的结果显示了一个有趣的现象，即一个线性估计在全体线性估计所组成的类中的可容许性与椭球的中心β０无关，而在全体齐次线性估计所组成的类中的可容许性与β０有关．     

Optimal finite-dimensional solution for a class of nonlinear observation problems

The filtering problem in a differential system with linear dynamics and observations described by an implicit equation linear in the state is solved in finite-dimensional recursive form. The original problem is posed as a deterministic fixed-interval optimization problem (FIOP) on a finite time interval. No stochastic concepts are used. Via Pontryagin's principle, the FIOP is converted into a linear, two-point boundary-value problem. The boundary-value problem is separated by using a linear Riccati transformation into two initial-value problems which give the equations for the optimal filter and filter gain. The optimal filter is linear in the state, but nonlinear with respect to the observation. Stability of the filter is considered on the basis of a related properly linear system. Three filtering examples are given.     

A structural connection between linear and 0–1 integer linear formulations

The connection between linear and 0–1 integer linear formulations has attracted the attention of many researchers. The main reason triggering this interest has been an availability of efficient computer programs for solving pure linear problems including the transportation problem. Also the optimality of linear problems is easily verifiable through existing algorithms. However, there is no efficient general technique available to solve 0–1 integer linear problems or to verify their optimality. This paper shows that in the case of one of the easier 0–1 integer linear problems, namely a single assignment problem, such a relation between linear and 0–1 integer linear formulation can be built. The theory behind the proposed ‘bridge’ is based on the combination of the absolute point principle and shadow price theory. The main practical benefit of this work is in providing an algorithm to find a MFL (more-for-less) solution for the assignment problem. To the best of our knowledge, this is one of the first efforts to provide a ‘more-for-less’ result for a 0–1 integer linear problem.     

Duality for nonconvex absolute value programming and a characterization of linear max-min programs

In this paper a dual problem for nonconvex linear programs with absolute value functionals is constructed by means of a max-min problem involving bivalent variables. A relationship between the classical linear max-min problem and a linear program with absolute value functionals is developed. This program is then used to compute the duality gap between some max-min and min-max linear problems.     

Linear facility location — Solving extensions of the basic problem

The basic problem is to locate a linear facility to minimize the sume of weighted shortest Euclidean distances from demand points to the facility. We extend the analysis to locating a constrained linear facility, a radial facility, a linear facility where distances are rectangular and a linear facility under the minimax criterion. Each case is shown to admit a simple solution technique.     

On a class of quadratic programs

This paper considers a class of quadratic programs where the constraints ae linear and the objective is a product of two linear functions. Assuming the two linear factors to be non-negative, maximization and minimization cases are considered. Each case is analyzed with the help of a bicriteria linear program obtained by replacing the quadratic objective with the two linear functions. Global minimum (maximum) is attained at an efficient extreme point (efficient point) of the feasible set in the solution space and corresponds to an efficient extreme point (efficient point) of the feasible set in the bicriteria space. Utilizing this fact and certain other properties, two finite algorithms, including validations are given for solving the respective problems. Each of these, essentially, consists of solving a sequence of linear programs. Finally, a method is provided for relaxing the non-negativity assumption on the two linear factors of the objective function.     

线搜索闭性的几个新结果

本文证明了回追步长搜索、Curry—Altman步长搜索及其改进形式、Goldstein—Armijo算法的闭性,并指出真正的Armijo步长搜索是回追步长搜索的特例,从而肯定了真正Armijo步长搜索的闭性.     

All admissible linear estimators of a regression coefficient under a balanced loss function

Admissibility of linear estimators of a regression coefficient in linear models with and without the assumption that the underlying distribution is normal is discussed under a balanced loss function. In the non-normal case, a necessary and sufficient condition is given for linear estimators to be admissible in the space of homogeneous linear estimators. In the normal case, a sufficient condition is provided for restricted linear estimators to be admissible in the space of all estimators having finite risks under the balanced loss function. Furthermore, the sufficient condition is proved to be necessary in the normal case if additional conditions are assumed.