DFT 的新算法

本文通过对离散富里叶变换(Discrete Fourier Transform,简记作DFT)矩阵的分解与FFT 算法相结合,提出了一个计算DFT 的新算法。由对矩阵的分解把求N=2~t 点的DFT 问题化为求16个N/16阶方阵与相应列向量相乘的问题(N≥16)。从而减少了乘法运算次数,且还具有良好的并行运算性质。     

变换自适应算法实现特征矢量谱

特征矢量法是分辨相关信号源的一种有效算法。该算法需求出阵列接收信号空间相关矩阵的最小特征矢量。本文在梯度法与空间三角格型法基础上,提出了一种新的算法:变换自适应法。此法通过一个变换,将求矩阵最小特征矢量的问题转换成求最大特征矢量,从而避免了矩阵求逆这一繁杂过程。理论分析以及计算机仿真结果均表明,该算法在计算量和收敛速度方面具有相当的优越性。     

消磁系统绕组调整计算

本文将求解超定方程组的有关理论用于消磁系统绕组的调整计算,根据消磁绕组调整的要求和特点,分别用直交化方法求最小二乘解和用波利亚算法或上升算法求极小极大解,试算均获成功。同时,为简化实船调整计算步骤,本文建议在首次调整时计算并记录广义逆矩阵,以备后续调整使用。对于减小测量误差的途径和最佳调整状态的估算等问题,也作出了若干探索。文末附有计算实例。     

超凸度量空间中KKM理论的一些应用

在超凸度量空间利用广义度量KKM映象原理的特性得到一类新的广义极大极小不等式,并进一步借助这类极大极小不等式,在更广泛的条件下,获得鞍点问题的一个新的存在性结果。     

模糊偏序关系的一种信息集成方法

以模糊超过关系、模糊不协调关系为例,就模糊偏序关系给出了一种基于分组加权极大(极小)算子的信息集成方法,讨论了该方法的一致性、非独裁性等性质.     

多传感器综合系统中的航迹相关算法

本文研究多传感器综合系统中的航迹相关问题。本文运用抽象代数和非贝叶斯决策理论并借鉴统计模式分类思想,提出一种新的航迹相关算法——K 近邻域(K—NN)航迹相关法,并把航迹相关化成了数学上的集合划分和商集构造问题。K—NN 算法把本次相关与其历史联系起来,把相关分成五个阶段,并采用了阈值的自适应技术,定义了相关函数、相关质量、相关向量、向量范数和以范数为基础的统计距离。仿真结果表明,它的效果明显好于最近邻域法,克服了极大似然(ML)和经典分配法的不足,并且也不象似然比(LR)法依赖于某些先验分布。它特别适合密集目标环境/交叉、分叉和机动航迹较多的场合,通常可在普通的计算和通讯资源上实时运行,并且比较便于工程实现。     

基于EMD和二叉树支持向量机的调制识别算法

针对数字调制模式识别问题,提出了一种基于经验模式分解(EMD)和二叉树支持向量机的识别算法。该算法通过对数字信号进行经验模式分解,利用分解得到的本征模式函数构造分类特征,再运用二叉树支持向量机作为分类器实现了6种信号的分类。仿真结果表明,该算法具有很好的识别性能。     

一类极小能控制与广义样条函数

本文讨论由一般微分方程确定的时不变线性系统的一类极小能控制问题。首先,通过引入降阶逆向系统揭示了原系统的输入与输出是由某个积分-微分算子联系着的,并利用该算子建立了极小能控制与广义样条的联系;然后在对于输出端的一类较广泛的约束条件下,导出了其输出空间与文[1]的输出空间具有类似的构造性质,从而建立了与文[1]类似的投影公式与递推公式。     

关于广义KKM定理的几点注记

本文在 H-空间中引入伪紧闭集的概念,得到一个广义 KKM 定理,从而获得了 KyFan 匹配定理以及极大极小不等式的一些新结果.     

自反Banach空间一类完全广义集值强非线性混合似变分不等式问题

研究了一类完全广义集值强非线性混合似变分不等式在自反Banach空间下的问题，借助一个极大极小不等式，证明了这类完全广义集值强非线性混合似变分不等式的解的存在唯一性定理。     

Concave minimization over a convex polyhedron

A general algorithm is developed for minimizing a well defined concave function over a convex polyhedron. The algorithm is basically a branch and bound technique which utilizes a special cutting plane procedure to' identify the global minimum extreme point of the convex polyhedron. The indicated cutting plane method is based on Glover's general theory for constructing legitimate cuts to identify certain points in a given convex polyhedron. It is shown that the crux of the algorithm is the development of a linear undrestimator for the constrained concave objective function. Applications of the algorithm to the fixed-charge problem, the separable concave programming problem, the quadratic problem, and the 0-1 mixed integer problem are discussed. Computer results for the fixed-charge problem are also presented.     

Algorithms for the minimax transportation problem

In this paper, we consider a variant of the classical transportation problem as well as of the bottleneck transportation problem, which we call the minimax transportation problem. The problem considered is to determine a feasible flow x_ij from a set of origins I to a set of destinations J for which max_(i,j)εIxJ{c_ijx_ij} is minimum. In this paper, we develop a parametric algorithm and a primal-dual algorithm to solve this problem. The parametric algorithm solves a transportation problem with parametric upper bounds and the primal-dual algorithm solves a sequence of related maximum flow problems. The primal-dual algorithm is shown to be polynomially bounded. Numerical investigations with both the algorithms are described in detail. The primal-dual algorithm is found to be computationally superior to the parametric algorithm and it can solve problems up to 1000 origins, 1000 destinations and 10,000 arcs in less than 1 minute on a DEC 10 computer system. The optimum solution of the minimax transportation problem may be noninteger. We also suggest a polynomial algorithm to convert this solution into an integer optimum solution.     

Quadratic bottleneck problems

We study the quadratic bottleneck problem (QBP) which generalizes several well‐studied optimization problems. A weak duality theorem is introduced along with a general purpose algorithm to solve QBP. An example is given which illustrates duality gap in the weak duality theorem. It is shown that the special case of QBP where feasible solutions are subsets of a finite set having the same cardinality is NP‐hard. Likewise the quadratic bottleneck spanning tree problem (QBST) is shown to be NP‐hard on a bipartite graph even if the cost function takes 0–1 values only. Two lower bounds for QBST are derived and compared. Efficient heuristic algorithms are presented for QBST along with computational results. When the cost function is decomposable, we show that QBP is solvable in polynomial time whenever an associated linear bottleneck problem can be solved in polynomial time. As a consequence, QBP with feasible solutions form spanning trees, s‐t paths, matchings, etc., of a graph are solvable in polynomial time with a decomposable cost function. We also show that QBP can be formulated as a quadratic minsum problem and establish some asymptotic results. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011     

Benders' partitioning scheme applied to a new formulation of the quadratic assignment problem

In this paper we present a new formulation of the quadratic assignment problem. This is done by transforming the quadratic objective function into a linear objective function by introducing a number of new variables and constraints. The resulting problem is a 0-1 linear integer program with a highly specialized structure. This permits the use of the partitioning scheme of Benders where only the original variables need be considered. The algorithm described thus iterates between two problems. The master problem is a pure 0-1 integer program, and the subproblem is a transportation problem whose optimal solution is shown to be readily available from the master problem in closed form. Computational experience on problems available in the literature is provided.     

支持向量顺序回归机的线性规划算法

支持向量顺序回归机是标准支持向量分类机的一个推广，它是一个凸的二次规划问题。本文根据l1范数与l2范数等价关系和优化问题的对偶原理，把凸的二次规划转化成线性规划。由此提了支持向量顺序回归机的线性规划算法，进一步用数值实验验证了此算法的可行性和有效性。并与支持向量顺序回归机相比，它的运行时间缩短了，而且误差i不超过支持向量顺序回归机；     

Determining optimal sizes of bounded batches with rejection via quadratic min‐cost flow

In this article, we consider a single machine scheduling problem, in which identical jobs are split into batches of bounded sizes. For each batch, it is allowed to produce less jobs than a given upper bound, that is, some jobs in a batch can be rejected, in which case a penalty is paid for each rejected job. The objective function is the sum of several components, including the sum of the completion times, total delivery cost, and total rejection cost. We reduce this problem to a min‐cost flow problem with a convex quadratic function and adapt Tamir's algorithm for its solution. © 2017 Wiley Periodicals, Inc. Naval Research Logistics 64: 217–224, 2017     

A quadratic assignment problem without column constraints

We convert a quadratic assignment problem [1] with a nonconvex objective function into an integer linear program. We then solve the equivalent integer program by a simple enumeration that produces global minima.     

基于协方差矩阵估计的稳健Capon波束形成算法

常规Capon波束形成器性能对模型误差或失配非常敏感,尤其是当期望信号包含在训练数据中,导向矢量失配将引起性能急剧下降。为解决这一问题,提出了一种采用干扰噪声协方差矩阵和导向矢量联合估计的稳健波束形成算法。该方法通过对Capon空间谱在非目标信号的方位区域内的积分,实现对干扰噪声协方差矩阵的估计,解决数据协方差矩阵包含有目标信号时引起信号自相消问题;其次为了克服导向矢量失配的影响,通过最大化输出功率,并增加二次型约束防止估计的导向矢量接近于干扰导向矢量,实现对导向矢量的估计。仿真实验表明:该算法能获得近似最优的输出信干噪比,与现有算法相比稳健性更强。     

The conjugate gradient technique for certain quadratic network problems

We consider a class of network flow problems with pure quadratic costs and demonstrate that the conjugate gradient technique is highly effective for large-scale versions. It is shown that finding a saddle point for the Lagrangian of an m constraint, n variable network problem requires only the solution of an unconstrained quadratic programming problem with only m variables. It is demonstrated that the number of iterations for the conjugate gradient algorithm is substantially smaller than the number of variables or constraints in the (primal) network problem. Forty quadratic minimum-cost flow problems of various sizes up to 100 nodes are solved. Solution time for the largest problems (4,950 variables and 99 linear constraints) averaged 4 seconds on the CBC Cyber 70 Model 72 computer.     

Minimax and maximin facility location problems on a sphere

The problem dealt with in this article is as follows. There are n “demand points” on a sphere. Each demand point has a weight which is a positive constant. A facility must be located so that the maximum of the weighted distances (distances are the shortest arcs on the surface of the sphere) is minimized; this is called the minimax problem. Alternatively, in the maximin problem, the minimum weighted distance is maximized. A setup cost associated with each demand point may be added for generality. It is shown that any maximin problem can be reparametrized into a minimax problem. A method for finding local minimax points is described and conditions under which these are global are derived. Finally, an efficient algorithm for finding the global minimax point is constructed.