LP问题的λ算法

本给出了求LP问题的最优解的λ算法,并指出了此法旋转运算的次数,此算法不需要基本可行解或对偶基本可行解。     

含自由变量LP问题的改进单纯形法

对于含自由变量的LP问题,为了得到比单纯形法[1]更有效的算法,通过研究在单纯形法迭代过程中,将自由变量化为非负变量再实施运算的规律,提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。     

Toeplitz矩阵,Hankel矩阵求逆的固有复杂度

对于一类问题P,如果能找到一个算法(对串行计算而言)其计算复杂性为f_1(u),则称f_1(n)为问题P固有复杂度的上界,若问题P的所有算法(对串行计算而言)其计算复杂性不小于f_2(n),则称f_2(u)为问题P固有复杂度下界.问题P的固有复杂度介于上     

LP问题的λ算法

本文给出了求LP问题最优解的λ算法,并指出了此法旋转运算的次数.此算法不需要基本可行解或对偶基本可行解.     

一类特殊矩阵的逆特征值问题

本文主要讨论如下形式矩阵的逆特征值问题:即对给定n个实数λ_1>λ_2>…>λ_2与n-1个实数μ_1>μ_2>…>μ_(n-1),满足λ_1>μ_1>λ_2>…>λ_(n-1)>μ_(n-1)>λ_n,在α_2>α_3>…>α_(n-1)的条件下,存在唯一的一个矩阵A_n是以λ_i为其特征值;且其截边矩阵的特征值为μ_1,μ_2,…,μ_(n-1).     

LP问题的K算法

本文给出了求 LP问题最优解的λ算法 ,并指出了此法旋转运算的次数 .此算法不需要基本可行解或对偶基本可行解 .     

三对角矩阵求逆的快速算法和逆元素的表示式

本文给出了ｎ阶三对角矩阵求逆的快速算法，其四则运算的计算量只要ｎ＾２＋７ｎ－８。同时给出了逆元素的表示式，从而得到逆元素的准确估计，大大拓广和改进了［２］、［３］的结果。     

部分变量带非负约束的严格凸二次规划问题的新算法

本将正交校正共轭梯度法推广来解只有部分变量带非负约束而其它变量无约束的严格凸二次规划，所建立的新算法的优点是：在迭代过程中，不用求逆矩阵，这样能保持矩阵的稀疏性，数值结果表明，算法对大规模稀疏二次规划问题是可行和有效的。     

一类Cauchy型矩阵的求逆问题

直接地讨论一类Cauchy型矩阵R的求逆问题,将经典Cauchy矩阵S的求逆问题的结论视为它的推论.     

有界变量线性规划的基线算法

本文对有界变量线性规划的算法进行了研究，得到了一种解此问题的新算法。文中根据基线算法的算法原理，通过对BL表的旋转，在各变量满足界约束的条件下，使目标函数值不断增大，直至得到有界硬上界，从而得到问题的最优解。文中给出了有界变量线性规划基线算法的计算步骤，并给出了一个例子。与单纯形法相比，采用基线算法解有界变量线性规划操作更简单。迭代次数少，解题速度更快。     

On motivating the Mitchell-Todd modification of Karmarkar's algorithm for LP problems with free variables

In this note, we first observe that the Morshedi-Tapia interpretation of the Karmarkar algorithm naturally offers an extension of the Karmarkar subproblem scaling to problems with free variables. We then note that this extended scaling is precisely the scaling suggested by Mitchell and Todd for problems with free variables. Mitchell and Todd gave no motivation for or justification of this extended scaling.This research was sponsored by NSF Cooperative Agreement No. CCR-88-09615, AFOSR Grant 89-0363, DOE Grant DEFG05-86-ER25017, ARO Grant 9DAAL03-90-G-0093, and COLCIENCIAS CO: 1106-05-307-93.     

对线性规划单纯形法的注记

为了更有效地应用单纯形算法求解线性规划问题,本文提出了以下几点注记。(1)人工变量列不必参与数值计算,也不占存储空间,从而可大量节省计算量和存储量;(2)使用基变量指标集来判断人工变量是否离基,可避免舍人误差的影响;(3)虚设人工变量的最终非零值对于修改存在矛盾的数学模型将起着关键性作用;(4)可将大M法与两阶段法统一处理,且M可不取具体的数值,也不参与数值计算;(5)实际计算中宜将Dantzig算法与Bland算法结合起来使用,既可对一般问题达到快速收敛的目的,又可避免退化问题可能产生的循环现象,而且在软件设计与实现上要比字典序方法等简单容易;(6)对于大型稀疏矩阵的计算机数据录入,建议采用二元数组的数据结构逐行录入,则可节省三分之一的录入工作量。     

基于指数型核函数的线性规划原始对偶内点算法

给出线性规划原始对偶内点算法的一个单变量指数型核函数.首先研究了这个指数型核函数的性质以及其对应的障碍函数.其次,基于这个指数型核函数,设计了求解线性规划问题的原始对偶内点算法,得到了目前小步算法最好的理论迭代界.最后,通过数值算例比较了基于指数型核函数的原始对偶内点算法和基于对数型核函数的原始对偶内点算法的计算效果.     

A theoretical comparison between the simplex method and the basic line search algorithm

A theoretical comparison between the simplex method (SM) and the basic line search method (BLSA) is presented. The explicit formulae for the upper and lower bounds in the BLSA are provided using SM. Further, it is shown that both methods are operationally equivalent.     

A new algorithm for solving the general quadratic programming problem

For the general quadratic programming problem (including an equivalent form of the linear complementarity problem) a new solution method of branch and bound type is proposed. The branching procedure uses a well-known simplicial subdivision and the bound estimation is performed by solving certain linear programs.     

Hybrid inertial proximal algorithm for the split variational inclusion problem in Hilbert spaces with applications

In this paper, we present hybrid inertial proximal algorithms for the split variational inclusion problems in Hilbert spaces, and provide convergence theorems for the proposed algorithms. In fact, an inertial type algorithm was proposed as an acceleration process. As application, we study split minimization problem, split feasibility problem, relaxed split feasibility problem and linear inverse problem in real Hilbert spaces. Finally, numerical results are given for our main results.     

A primal-dual algorithm for the fermat-weber problem involving mixed gauges

We give a new algorithm for solving the Fermat-Weber location problem involving mixed gauges. This algorithm, which is derived from the partial inverse method developed by J.E. Spingarn, simultaneously generates two sequences globally converging to a primal and a dual solution respectively. In addition, the updating formulae are very simple; a stopping rule can be defined though the method is not dual feasible and the entire set of optimal locations can be obtained from the dual solution by making use of optimality conditions. When polyhedral gauges are used, we show that the algorithm terminates in a finite number of steps, provided that the set of optimal locations has nonepty interior and a counterexample to finite termination is given in a case where this property is violated. Finally, numerical results are reported and we discuss possible extensions of these results.     

A faster algorithm for the continuous bilevel knapsack problem

We construct a fast algorithm with time complexity $O(nlogn)$ for a continuous bilevel knapsack problem with interdiction constraints for $n$ items. This improves on a recent algorithm from the literature with quadratic time complexity $O\left(n^2\right)$.     

关于Jacobi矩阵的特征值反问题可解的充分必要条件的一个注记 (英)

本文讨论一类具有特殊结构的Jacobi矩阵的特征值反问题,该问题由描述变截面杆的微分方程离散化得到．我们得到了这个问题有解的一些必要条件,并且通过一些数值例子,说明了L．Lu和K．Michael给出的充分条件和算法在矩阵的阶数高于3的时候是错误的。