线性规划的单纯形法及其发展

本文给出了一种新的原对偶单纯形法,并通过它分析了隐藏在经典单纯形法中的对偶信息．我们重新评价经典单纯形法并详细讨论了它与现代单纯形法之间的联系．两个修改版本一并给出．新算法具有计算量小和实施简单等特点,计算效果也不错．初步数值实验表明现代单纯形法比经典方法具有明显的优越性．     

解非线性单调方程组的投影自调比对称秩1拟牛顿法

本文给出了求解非线性单调方程组的两个自调比对称秩1牛顿法,即投影SSR1法和投影有限储存SSR1法.这两个算法将自调比对称秩1校正参数进行了一个简单的修改并采用了保守策略.在非线性单调函数满足李普希茨连续的条件下,证明了算法的全局收敛性,并与相同类型的BFGS法进行了初步的数值比较试验,试验结果表明自调比对称秩1类投影算法求解非线性单调方程组与相同类型的BFGS数值结果相当.     

向量到子空间的距离及其应用

给出了向量到有限维子空间距离的定义及求法 ,并推广到向量到可数无限维子空间距离 .采用两种方法求距离并比较了它们的运算量 .揭示了 Cholesky分解法与 Schmidt正交化方法的内在联系 .最后利用向量到子空间距离给出了矛盾方程组最小二乘解的求法     

常微分方程初值问题的Legendre-tau谱方法

提出了一阶常微分方程初值问题的Legendre-tau方法,根据一阶微分算子不对称性的特点,tau方法选取检验函数不同于试探函数,有更好的逼近性质,改进了误差估计.文中给出了单步和多步Legendre-tau方法及算法实现,采用系数为未知量,可利用多项式的正交性减少运算量.数值结果与理论分析一致,并与相关方法进行比较,验证了本文方法的有效性.     

求反对称阵特征值的新算法

1971年,M.H.C.Paardekooper将对称阵的Jacobi思想推广到反对称阵,给出一个求反对称阵特征值的实用算法(简称P算法).但P算法仅考虑到矩阵的反对称性,未利用其纯虚数特征值共轭成对的性质,而且也未探讨特征值共轭对相重与否对运算量的影响.鉴于此,本文提出一个新算法,其运算量比P算法少得多. 我们先用Givens相似变换(其快速算法见§3之3.2)化反对称阵A为三对角反对称     

两类五阶解非线性方程组的迭代算法

本文首先根据Runge-Kutta方法的思想,结合Newton迭代法,提出了一类带参数的解非线性方程组F(x)=0的迭代算法,然后基于解非线性方程f(x)=0的King算法,给出第二类解非线性方程组的迭代算法,收敛性分析表明这两类算法都是五阶收敛的.其次给出了本文两类算法的效率指数,以及一些已知算法的效率指数,并且将本文算法的效率指数与其它方法进行详细的比较,通过效率比率R_(i,j)可知本文算法具有较高的计算效率.最后给出了四个数值实例,将本文两类算法与现有的几种算法进行比较,实验结果说明本文算法收敛速度快,迭代次数少,有明显的优势.     

适于短序列最大熵谱估计的一种快速算法

传统谱估计方法的分辨力受到数据长度的限制。Burg提出的最大熵谱估计存在着严重的谱线分裂和较大的估计偏差。Marple算法的判阶方法要求对随机过程有一定的先验知识,所以使用很不方便,其运算量在短序列时也远较Burg算法大。Fougere的方法,运算量更为可观。 本文提供一种新算法。这种算法使得运算量在短序列情况下大为减少.计算机模拟证明这种新算法具有较好的性能.文中对雷达应用的具体情况,给出一些模拟结果。     

求解对称鞍点问题的修正Uzawa方法

本文基于两个非线性逼近逆的非线性Uzawa方法,给出了一种新的修正非线性Uzawa方法,并对其收敛性进行了分析以及与已有算法的收敛性进行了比较.最后由数值试验说明了算法的正确性和有效性.     

求有限集合覆盖的构造方法

在近似算法领域,集合覆盖问题是研究的比较早和比较透彻的问题之一.文中解决与经典SCP不同的另一问题,针对有限集合覆盖的构造,提出一种构造有限集合上的集合覆盖的算法,并且给出了该算法的完备性证明.该算法简单有效,是一种用于构造集合覆盖的规范方法.     

第一阶段原有单纯形和对偶单纯形算法的计算比较

线性最优化广泛应用于经济与管理的各个领域.在线性规划问题的求解中,如果一个初始基本可行解没有直接给出,则常采用经典的两阶段法求解.对含有"≥"不等式约束的线性规划问题,讨论了第一阶段原有单纯形法和对偶单纯形法两种算法形式,并根据第一阶段问题的特点提出了改进的对偶单纯形枢轴准则.最后,通过大规模数值试验对两种算法进行计算比较,结果表明,改进后的对偶单纯形算法在计算效率上明显优于原有单纯形算法.     

Supernode processing of mixed-integer models

This paper discusses processing software for large scale mixed-integer optimization models. The software is part of the Mathematical OPtimization System MOPS [18] which contains algorithms for solving large-scale LP and mixed-integer programs. The processing techniques are implemented in such a way that they can be applied not only initially but also during the branch-and-bound algorithm.This paper discusses only a subset of the processing techniques included in MOPS. Algorithmic and software design aspects of the branch-and-bound process are not part of this paper.Dedicated to Professor George B. Dantzig on the occasion of his eightieth birthday.     

A de Casteljau algorithm for generalized Bernstein polynomials

This paper is concerned with a generalization of the classical Bernstein polynomials where the function is evaluated at intervals which are in geometric progression. It is shown that these polynomials can be generated by a de Casteljau algorithm, which is a generalization of that relating to the classical case. Dedicated to M. J. D. Powell on the occasion of his 60th birthday     

Transportation problem with nonlinear side constraints a branch and bound approach

In a container terminal management, we are often confronted with the following problem: how to assign a reasonable depositing position for an arriving container, so that the efficiency of searching for and loading of a container later can be increased. In this paper, the problem is modeled as a transportation problem with nonlinear side constraints (TPNSC). The reason of nonlinear side constraints arising is that some kinds of containers cannot be stacked in the same row (the space of storage yard is properly divided into several rows). A branch and bound algorithm is designed to solve this problem. The algorithm is based on the idea of using disjunctive arcs (branches) for resolving conflicts that are created whenever some conflicting kinds of containers are deposited in the same row. During the branch and bound, the candidate problems are transformed into classical transportation problems, so that the efficient transportation algorithm can be applied, at the same time the reoptimization technique is employed during the branch and bound. Further, we design a heuristic to obtain a feasible initial solution for TPNSC in order to prune some candidates as early and/or as much as possible. We report computational results on randomly generated problems.     

The part families problem in flexible manufacturing systems

Parts grouping into families can be performed in flexible manufacturing systems (FMSs) to simplify two classes of problems: long horizon planning and short horizon planning. In this paper the emphasis is on the part families problem applicable to the short horizon planning. Traditionally, parts grouping was based on classification and coding systems, some of which are reviewed in this paper. To overcome the drawbacks of the classical approach to parts grouping, two new methodologies are developed. The methodologies presented are very easy to implement because they take advantage of the information already stored in the CAD system. One of the basic elements of this system is the algorithm for solving the part families problem. Some of the existing clustering algorithms for solving this problem are discussed. A new clustering algorithm has been developed. The computational complexity and some of the computational results of solving the part families problem are also discussed.     

A note on the asymptotic behavior of global classical solutions of diagonalizable quasilinear hyperbolic systems

This paper is concerned with the asymptotic behavior of global classical solutions of diagonalizable quasilinear hyperbolic systems with linearly degenerate characteristic fields. On the basis of the existence result for the global classical solution, we prove that when t tends to the infinity, the solution approaches a combination of C¹ traveling wave solutions, provided that the C¹ norm and the BV norm of the initial data are bounded but possibly large. In contrast to former results obtained by Liu and Zhou [J. Liu, Y. Zhou, Asymptotic behaviour of global classical solutions of diagonalizable quasilinear hyperbolic systems, Math. Methods Appl. Sci. 30 (2007) 479-500], ours do not require their assumption that the system is rich in the sense of Serre. Applications include that to the one-dimensional Born-Infeld system arising in string theory and high energy physics.     

Asymptotic Behavior of Global Classical Solutions of Quasilinear Non-strictly Hyperbolic Systems with Weakly Linear Degeneracy

In this paper, we study the asymptotic behavior of global classical solutions of the Cauchy problem for general quasilinear hyperbolic systems with constant multiple and weakly linearly degenerate characteristic fields. Based on the existence of global classical solution proved by Zhou Yi et al., we show that, when t tends to infinity, the solution approaches a combination of C1 travelling wave solutions, provided that the total variation and the L1 norm of initial data are sufficiently small.     

A differential graded approach to the silting theorem

A silting theorem was established by Buan and Zhou as a generalisation of the classical tilting theorem of Brenner and Butler. In this paper, we give an alternative proof of the theorem by using differential graded algebras.     

Convergence of some algorithms for convex minimization

We present a simple and unified technique to establish convergence of various minimization methods. These contain the (conceptual) proximal point method, as well as implementable forms such as bundle algorithms, including the classical subgradient relaxation algorithm with divergent series.An important research work of Phil Wolfe's concerned convex minimization. This paper is dedicated to him, on the occasion of his 65th birthday, in appreciation of his creative and pioneering work.     

An efficient algorithm of logarithmic transformation to Hirota bilinear form of KdV-type bilinear equation

In this paper, an efficient algorithm of logarithmic transformation to Hirota bilinear form of the KdV-type bilinear equation is established. In the algorithm, some properties of Hirota operator and logarithmic transformation are successfully applied, which helps to prove that the linear terms of the nonlinear partial differential equation play a crucial role in finding the Hirota bilinear form. Experimented with various integro-differential equations, our algorithm is proven to be more efficient than the algorithm referred by Zhou, Fu, and Li in getting the Hirota bilinear form, especially in achieving the coefficient of the logarithmic transformation.     

Linear convergence of an algorithm for computing the largest eigenvalue of a nonnegative tensor

An iterative method for finding the largest eigenvalue of a nonnegative tensor was proposed by Ng, Qi, and Zhou in 2009. In this paper, we establish an explicit linear convergence rate of the Ng–Qi–Zhou method for essentially positive tensors. Numerical results are given to demonstrate linear convergence of the Ng–Qi–Zhou algorithm for essentially positive tensors. Copyright © 2011 John Wiley & Sons, Ltd.