一种连续的谱聚类优化模型

聚类与图的划分问题在大数据分析中有着重要的应用.这类问题一般被描述为组合优化问题,因此较难快速求解.本文设计了一种新的连续优化模型,并提出了一种块坐标下降算法,数值实验显示我们的新方法在求解聚类与图的划分问题上很有潜力.我们还更进一步分析了我们的连续优化模型和组合优化模型的关系.     

求解非减上模集函数最小值问题的近似算法及其性能保证

上模集函数的优化问题在组合优化问题中有广泛应用,许多组合优化问题,如设备选址问题、p-中心问题等都可化为上模集函数的优化问题.本文给出了求解非减上模集函数最小值问题的一种近似算法,并讨论了所给算法的性能保证.     

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

双曲型和抛物型微分不等式解的三曲线定理及估计

本文对于系数满足条件(A)(见§3)的 Laplace 双曲型微分不等式(?)~2u/(?)_x(?)_y+a(x,y,)(?)_u/(?)_x+b(x,y)(?)~u/(?)~y+c(x,y)u≥0(c≤0)的解以及抛物型微分不等式(?)~2v/(?)x~2-(?)v/(?)t+c(x,t)v≥0(c≤0)的解,分别在 c≡0和 c(?)0的情形建立了各自的一般形式的三曲线定理;在 c(?)0,且所考虑的函数预先给定的初值-边值取非正值的情形,给出了一种建立更有效的估计的方法.此外,本文还改进了 Agmon-Nirenberg-Protter 关于 Laplace 双曲型微分不等式的一个最大值原理.     

双曲型和抛物型微分不等式解的三曲线定理及估计

本文对于系数满足条件(A)(见§3)的 Laplace 双曲型微分不等式(?)~2u/(?)_x(?)_y a(x,y,)(?)_u/(?)_x b(x,y)(?)~u/(?)~y c(x,y)u≥0(c≤0)的解以及抛物型微分不等式(?)~2v/(?)x~2-(?)v/(?)t c(x,t)v≥0(c≤0)的解,分别在 c≡0和 c(?)0的情形建立了各自的一般形式的三曲线定理;在 c(?)0,且所考虑的函数预先给定的初值-边值取非正值的情形,给出了一种建立更有效的估计的方法.此外,本文还改进了 Agmon-Nirenberg-Protter 关于 Laplace 双曲型微分不等式的一个最大值原理.     

约束粒子群算法求解自融资投资组合模型研究

在马克维茨投资组合的均值-方差模型框架下,给出限制投资数量的自融资投资组合优化模型.在金融市场上有广泛应用,为了有效地求解此类问题的最优解,采用一种基于广义学习策略的约束粒子群算法(CPSO).CPSO算法具有广义的学习策略,极大地提升了种群的多样性,进而提升种群跳出局部最优解的能力.在基准函数测试中,结果显示CPSO算法有较好的运行结果.在自融资投资组合优化模型上,优化结果表明CPSO算法是可行的,有效的,并有较好的优化结果.     

求解复杂优化问题的基于信息熵的自适应蚁群算法

针对基本蚁群算法存在收敛速度慢、易陷入局部最优、计算复杂且不易求解连续优化问题等缺陷 ,提出了一种基于信息熵的改进自适应蚁群算法 ,采用由信息熵控制的路径选择及随机扰动策略实现了算法的自适应调节 ,克服了基本蚁群算法的不足 .典型的 NP-hard问题的计算实例表明 ,该方法具有较好的收敛性、稳定性和鲁棒性 ,可用于离散及连续的组合优化问题求解中 ,其不失为求解复杂组合优化问题的一种较好的方法 .     

基于CVaR的债券投资组合模型

针对债券投资组合中的风险度量难题,用CVaR作为风险度量方法,构建了基于CVaR的债券投资组合优化模型.采用历史模拟算法处理模型中的随机收益率向量,将随机优化模型转化为确定性优化模型,并且证明了算法的收敛性.通过线性化技术处理CVaR中的非光滑函数,将该模型转化为一般的线性规划模型.结合10只债券的组合投资实例,验证了模型与算法的有效性.     

模糊投资组合选择问题的改进帝企鹅优化算法

模糊投资组合选择问题是在基本投资组合模型中引入模糊集理论,使所建立的模型与实际市场更加吻合,但同时也增加了模型求解难度.因此,本文针对两种不同的模糊投资组合模型,提出一种改进帝企鹅优化算法.算法首先引入可行性准则,处理模糊投资组合模型中的约束.其次,算法中加入变异机制,平衡算法的开发和探索能力,引导种群向最优个体收敛.通过对CEC 2006中的13个标准测试问题及两个模糊投资组合问题实例进行数值实验,并与其他群智能优化算法进行结果比较,发现本文所提出的算法具有较好的优化性能,并且对于求解模糊投资组合选择问题是有效的.     

K-q.c.的一些偏差性质和Mori常数的改进值

本文首先建立了 K～q.c.的一个新的角偏差定理;然后,用分析的方法,在单位圆盘到自身上且固定原点的 K-q.c.族中建立了一个 H(?)lder 连续性定理,它是关于 K-q.c.的 H(?)lder 连续性的 Mori 定理的加强.运用此定理,Mori 常数之现有估值得到了改进.在最后一部分,本文揭示了该族的另外一些偏差性质.     

Efficient Hybrid Algorithms for Finding Zeros of Convex Functions

We consider two hybrid algorithms for finding an ϵ-approximation of a root of a convex real function that is twice differentiable and satisfies a certain growth condition on the intervial [0, R]. The first algorithm combines a binary search procedure with Newton′s method. The binary search produces an interval contained in the region of quadratic convergence of Newton′s method. The computational cost of the binary search, as well as the computational cost of Newton′s method, is of order O(log log(R/ϵ)). The second algorithm combines a binary search with the secant method in a similar fashion. This results in a lower overall computational cost when the cost of evaluating the derivative is more than .44042 of the cost of evaluating the function. Our results generalize same recent results of Ye.     

An efficient fractal image coding algorithm using unified feature and DCT

Fractal image compression is a promising technique to improve the efficiency of image storage and image transmission with high compression ratio, however, the huge time consumption for the fractal image coding is a great obstacle to the practical applications. In order to improve the fractal image coding, efficient fractal image coding algorithms using a special unified feature and a DCT coder are proposed in this paper. Firstly, based on a necessary condition to the best matching search rule during fractal image coding, the fast algorithm using a special unified feature (UFC) is addressed, and it can reduce the search space obviously and exclude most inappropriate matching subblocks before the best matching search. Secondly, on the basis of UFC algorithm, in order to improve the quality of the reconstructed image, a DCT coder is combined to construct a hybrid fractal image algorithm (DUFC). Experimental results show that the proposed algorithms can obtain good quality of the reconstructed images and need much less time than the baseline fractal coding algorithm.     

Finding all nondominated points of multi-objective integer programs

We develop exact algorithms for multi-objective integer programming (MIP) problems. The algorithms iteratively generate nondominated points and exclude the regions that are dominated by the previously-generated nondominated points. One algorithm generates new points by solving models with additional binary variables and constraints. The other algorithm employs a search procedure and solves a number of models to find the next point avoiding any additional binary variables. Both algorithms guarantee to find all nondominated points for any MIP problem. We test the performance of the algorithms on randomly-generated instances of the multi-objective knapsack, multi-objective shortest path and multi-objective spanning tree problems. The computational results show that the algorithms work well.     

The rotation graph of binary trees is Hamiltonian

In this paper we study the rotation transformation on binary trees and consider the properties of binary trees under this operation. The rotation is the universal primitive used to rebalance dynamic binary search trees. New binary search tree algorithms have recently been introduced by Sleator and Tarjan. It has been conjectured that these algorithms are as efficient as any algorithm that dynamically restructures the tree using rotations. We hope that by studying rotations in binary trees we shall gain a better understanding of the nature of binary search trees, which in turn will lead to a proof of this “dynamic optimality conjecture”. We define a graph, RG(n), whose vertex set consists of all binary trees containing n nodes, and which has an edge between two trees if they differ by only one rotation. We shall introduce a new characterization of the structure of RG(n) and use it to demonstrate the existence of a Hamiltonian cycle in the graph. The proof is constructive and can be used to enumerate all binary trees with n nodes in constant time per tree.     

Analysis of recursive batched interpolation search

For an ordered file of records with uniformly distributed key values, we examine an existing batched searching algorithm based on recursive use of interpolation searches. The algorithm, called Recursive Batched Interpolation Search (RBIS) in this paper, uses a divide-and-conquer technique for batched searching. The expected-case complexity of the algorithm is shown to beO(m loglog (2n/m) +m), wheren is the size of the file andm is the size of the query batch. Simulations are performed to demonstrate the savings of batched searching using RBIS. Also, simulations are performed to compare alternative batched searching algorithms which are based on either interpolation search or binary search. When the file's key values are uniformly distributed, the simulation results confirm that interpolation-search based algorithms are superior to binary-search based algorithms. However, when the file's key values are not uniformly distributed, a straight-forward batched interpolation search deteriorates quickly as the batch size increases, but algorithm RBIS still outperforms binary-search based algorithms when the batch size passes a threshold value.     

改进二元分布估计算法求解置换流水车间调度问题

针对置换流水车间调度这类组合最优化问题的求解,提出了一种改进二元分布估计算法(Improved binary estimation distribution algorithm, I-EDA)。算法以二元分布估计算法为架构,使用NEH(Nawaz-Enscore-Ham)启发式算法生成初始解,提高了初始解的质量;通过对优势解的统计采样构建位置矩阵模型和链接矩阵模型,依照两个矩阵模型的合并概率组合链接区块产生子代。提出了NEH插入式重组策略和基于位置概率的交换策略和两种全新局部搜索机制替代原二元分布估计算法的相邻交换法,以进一步筛选优势解。最后通过对Reeves标准测试集的仿真实验和算法比较验证了所提出算法的有效性。     

Decomposition Methods for Differentiable Optimization Problems over Cartesian Product Sets

This paper presents a unified analysis of decomposition algorithms for continuously differentiable optimization problems defined on Cartesian products of convex feasible sets. The decomposition algorithms are analyzed using the framework of cost approx imation algorithms. A convergence analysis is made for three decomposition algorithms: a sequential algorithm which extends the classical Gauss-Seidel scheme, a synchronized parallel algorithm which extends the Jacobi method, and a partially asynchronous parallel algorithm. The analysis validates inexact computations in both the subproblem and line search phases, and includes convergence rate results. The range of feasible step lengths within each algorithm is shown to have a direct correspondence to the increasing degree of parallelism and asynchronism, and the resulting usage of more outdated information in the algorithms.     

Faster construction of optimal binary split trees

A binary split tree is a search structure combining features of heaps and binary search trees. Building an optimal binary split tree was originally conjectured to be intractable due to difficulties in applying dynamic programming techniques to the problem. However, two algorithms have recently been published which generate optimal trees in O(n⁵) time, for records with distinct access probabilities. An extension allowing nondistinct access probabilities required exponential time. These algorithms consider a range of values when only a single value is possible. A dynamic programming method for determining the correct value is given, resulting in an algorithm which builds an optimal binary split tree in O(n⁵) time for nondistinct access probabilities and Θ(n⁴) time for distinct access probabilities.     

A discrete particle swarm optimization method for feature selection in binary classification problems

This paper investigates the feature subset selection problem for the binary classification problem using logistic regression model. We developed a modified discrete particle swarm optimization (PSO) algorithm for the feature subset selection problem. This approach embodies an adaptive feature selection procedure which dynamically accounts for the relevance and dependence of the features included the feature subset. We compare the proposed methodology with the tabu search and scatter search algorithms using publicly available datasets. The results show that the proposed discrete PSO algorithm is competitive in terms of both classification accuracy and computational performance.     

A new genetic approach to construct near-optimal binary search trees

Many definitive and approximate methods have been so far proposed for the construction of an optimal binary search tree. One such method is the use of evolutionary algorithms with satisfactorily improved cost efficiencies. This paper will propose a new genetic algorithm for making a near-optimal binary search tree. In this algorithm, a new greedy method is used for the crossover of chromosomes while a new way is also developed for inducing mutation in them. Practical results show a rapid and desirable convergence towards the near-optimal solution. The use of a heuristic to create not so costly chromosomes as the first offspring, the greediness of the crossover, and the application of elitism in the selection of future generation chromosomes are the most important factors leading to near-optimal solutions by the algorithm at desirably high speeds. Due to the practical results, increasing problem size does not cause any considerable difference between the solution obtained from the algorithm and exact solution.