基于变分不等式的支持向量机优化算法研究

由于标准支持向量机模型是一个二次规划问题,随着数据规模的增大,求解算法过程会越来越复杂.在K-SVCR算法结构的基础上,构造了严格凸的二次规划新模型,该模型的主要特点是可以将其一阶最优化条件转化为变分不等式问题,利用Fischer-Burmeister(FB)函数将互补问题转化为光滑方程组;建立光滑快速牛顿算法求解,并证明了该算法所产生的序列是全局收敛;利用标准数据集测试提出算法的有效性,在训练正确率和运行时间上与K-SVCR算法相比都有较好的表现,实验结果表明该算法可行且有效.     

An Arnoldi-Extrapolation algorithm for computing PageRank

The Arnoldi-type algorithm proposed by Golub and Greif [G. Golub, C. Greif, An Arnoldi-type algorithm for computing PageRank, BIT 46 (2006) 759-771] is a restarted Krylov subspace method for computing PageRank. However, this algorithm may not be efficient when the damping factor is high and the dimension of the search subspace is small. In this paper, we first develop an extrapolation method based on Ritz values. We then consider how to periodically knit this extrapolation method together with the Arnoldi-type algorithm. The resulting algorithm is the Arnoldi-Extrapolation algorithm. The convergence of the new algorithm is analyzed. Numerical experiments demonstrate the numerical behavior of this algorithm.     

一种修正的求总极值的积分—水平集方法的实现算法收敛性

1978年,郑权等提出了一个积分型求总极值的概念性算法及Monte-Carlo随机投点的实现算法,给出了概念性算法的总极值存在的充分必要条件,但是其实现算法收敛性仍未解决,1986年,张连生等给出离散均值－水平集的实现算法,并证明了它的收敛性。本文给出修正的积分－水平集方法,用一致分布搂九值积分逼近水平集构造实现算法,并证明了算法的收敛性。     

An algorithm for the capacitated vehicle routing problem with route balancing

In this paper, we present a multi-objective evolutionary algorithm for the capacitated vehicle routing problem with route balancing. The algorithm is based on a formerly developed multi-objective algorithm using an explicit collective memory method, namely the extended virtual loser (EVL). We adapted and improved the algorithm and the EVL method for this problem. We achieved good results with this simple technique. In case of this problem the quality of the results of the algorithm is similar to that of other evolutionary algorithms.     

Global minimization of a generalized linear multiplicative programming

This article presents a simplicial branch and bound algorithm for globally solving generalized linear multiplicative programming problem (GLMP). Since this problem does not seem to have been studied previously, the algorithm is apparently the first algorithm to be proposed for solving such problem. In this algorithm, a well known simplicial subdivision is used in the branching procedure and the bound estimation is performed by solving certain linear programs. Convergence of this algorithm is established, and some experiments are reported to show the feasibility of the proposed algorithm.     

基于核函数的混合C均值聚类算法

提出了一种基于核函数的混合C均值聚类算法.首先利用模糊C均值聚类算法和另一种类型的可能性C均值聚类算法的优点,设计出一种混合C均值聚类算法.然而鉴于该算法存在的不足,本文将Mercer核函数引入到该算法中,仿真实验结果证实了该方法的可行性和有效性.     

A Fitzpatrick algorithm for multivariate rational interpolation

In this paper, we first apply the Fitzpatrick algorithm to osculatory rational interpolation. Then based on a Fitzpatrick algorithm, we present a Neville-like algorithm for Cauchy interpolation. With this algorithm, we can determine the value of the interpolating function at a single point without computing the rational interpolating function.     

An algorithm for semi-infinite transportation problems

In this paper we consider a class of semi-infinite transportation problems. We develop an algorithm for this class of semi-infinite transportation problems. The algorithm is a primal dual method which is a generalization of the classical algorithm for finite transportation problems. The most important aspect of our paper is that we can prove the convergence result for the algorithm. Finally, we implement some examples to illustrate our algorithm.     

An algorithm for local continuous optimization of traffic signals

In this paper, an algorithm for sensitivity analysis for equilibrium traffic network flows with link interferences is proposed. Based on this sensitivity analysis algorithm, a general algorithm is provided for solving the optimal design and management problems for traffic networks. In particular, this algorithm is applied to the optimal traffic signal setting problem. A numerical example is given to demonstrate the effectiveness of our algorithm.     

A simplification of the double-sweep algorithm to solve the k-shortest path problem

In this paper, we define the k-shortest path problem, which will be used to model the problem of routing aircraft through a network of airfields. This problem finds the optimal alternative routes from one or more origins to one or more destinations. We solve this problem using the double-sweep algorithm. We present a simplification to the double-sweep algorithm, and show that this simplification reduces the computational complexity of the algorithm by a factor of k. We prove that the simplified double-sweep algorithm converges. Finally, we demonstrate this algorithm on a small airlift network.     

An improved inexact Newton method

For unconstrained optimization, an inexact Newton algorithm is proposed recently, in which the preconditioned conjugate gradient method is applied to solve the Newton equations. In this paper, we improve this algorithm by efficiently using automatic differentiation and establish a new inexact Newton algorithm. Based on the efficiency coefficient defined by Brent, a theoretical efficiency ratio of the new algorithm to the old algorithm is introduced. It has been shown that this ratio is greater than 1, which implies that the new algorithm is always more efficient than the old one. Furthermore, this improvement is significant at least for some cases. This theoretical conclusion is supported by numerical experiments.      

The global and superlinear convergence of a new nonmonotone MBFGS algorithm on convex objective functions

In this paper, a new nonmonotone MBFGS algorithm for unconstrained optimization will be proposed. Under some suitable assumptions, the global and superlinear convergence of the new nonmonotone MBFGS algorithm on convex objective functions will be established. Some numerical experiments show that this new nonmonotone MBFGS algorithm is competitive to the MBFGS algorithm and the nonmonotone BFGS algorithm.     

含有等式约束非线性规划的全局优化算法

针对含有多个等式约束的非线性规划问题,提出一个全局优化算法.该方法基于可行集策略把改进的模拟退火方法与确定的局部算法方法相结合.对算法的收敛性进行了证明,数值结果表明算法的有效性及正确性.     

一个求大规模非负不可约稀疏矩阵的谱半径及特征向量的新算法

本文设计了一个计算非负不可约矩阵的谱半径及其特征向量的新算法,并证明了其收敛性.该算法计算晕不大,占用内存少,有相同的0元模式,从而在大规模稀疏矩阵的计算中优势明显.最后用实例验证了此算法的可行性.     

Tilted Correlation Screening Learning in High-Dimensional Data Analysis

Statistical inference can be over optimistic and even misleading based on a selected model due to the uncertainty of the model selection procedure, especially in the high-dimensional data analysis. In this article, we propose a bootstrap-based tilted correlation screening learning (TCSL) algorithm to alleviate this uncertainty. The algorithm is inspired by the recently proposed variable selection method, TCS algorithm, which screens variables via tilted correlation. Our algorithm can reduce the prediction error and make the interpretation more reliable. The other gain of our algorithm is the reduced computational cost compared with the TCS algorithm when the dimension is large. Extensive simulation examples and the analysis of one real dataset are conducted to exhibit the good performance of our algorithm. Supplementary materials for this article are available online.     

解线性等式约束优化问题的模式搜索过滤集方法

提出一个解线性等式约束无导数优化的模式搜索过滤集算法,该算法将过滤集技术嵌入无导数优化算法中以改善算法的效率. 建立了新算法的总体收敛性, 初步的数值试验结果表明新算法是有效的.     

求解阵列天线自适应滤波问题的一种调比随机逼近算法

提出了求解阵列天线自适应滤波问题的一种调比随机逼近算法.每一步迭代中,算法选取调比的带噪负梯度方向作为新的迭代方向.相比已有的其他随机逼近算法,这个算法不需要调整稳定性常数,在一定程度上解决了稳定性常数选取难的问题.数值仿真实验表明,算法优于已有的滤波算法,且比经典Robbins-Monro （RM）算法具有更好的稳定性.     

线性分式多乘积规划问题的完全多项式时间近似算法

本文针对线性分式多乘积规划问题,通过Charnes-Cooper转化将原问题转化为一个等价问题,借助此等价问题提出一个获得原问题全局近似最优解的算法,最终证明了算法的收敛性,且提供了算法运算时间的理论分析.     

一个关于二次规划问题的分段线性同伦算法

本文发展了一个关于二次规划问题的分段线性同伦算法。该算法可看作是外点罚函数法的一个变体。凡是符合外点罚函数法收敛条件的二次规划问题用该算法均可经有限次轮回运算得到稳定解。大量的关于随机的凸二次规划问题的数值实验结果表明它的计算效率是高的，在某些条件下可能是多项式时间算法。     

一类多乘积规划的加速算法

针对一类多乘积规划问题(MP),给出一个加速算法.首先导出一个与(MP)等价的逆凸问题(RCP),然后构造问题(RCP)的线性松弛化问题.算法的主要特点是提出了两个加速技巧,这些技巧可以用于改善算法的收敛速度.数值算例表明算法是可行的.