Efficient algorithms for solving rank two and rank three bilinear programming problems

Finitely convergent algorithms for solving rank two and three bilinear programming problems are proposed. A rank k bilinear programming problem is a nonconvex quadratic programming problem with the following structure: % MathType!MTEF!2!1!+-% feaafeart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4baFfea0dXde9vqpa0lb9% cq0dXdb9IqFHe9FjuP0-iq0dXdbba9pe0lb9hs0dXda91qaq-xfr-x% fj-hmeGabaqaciGacaGaaeqabaWaaeaaeaaakeaaieaacaWFTbGaa8% xAaiaa-5gacaWFPbGaa8xBaiaa-LgacaWF6bGaa8xzaiaa-bcacaWF% 7bacbiGaa43yamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+Hhaca% GFRaGaa4hzamaaDaaaleaacaGFWaaabaGaa4hDaaaakiaa+LhacaGF% RaWaaabuaeaacaGFJbWaa0baaSqaaiaa+PgaaeaacaGF0baaaOGaam% iEaiabl+y6NjaadsgadaqhaaWcbaGaamOAaaqaaiaadshaaaGccaWG% 5bGaaiiFaaWcbaGaa8NAaiaa-1dacaWFXaaabeqdcqGHris5aOGaa4% hEaiabgIGiolaa+HfacaGFSaGaa4xEaiabgIGiolaa+LfacaWF9bGa% a8hlaaaa!5D2E!\[minimize \{ c_0^t x + d_0^t y + \sum\limits_{j = 1} {c_j^t xd_j^t y|} x \in X,y \in Y\} ,\]where X Rⁿ¹ and Y R ⁿ² are non-empty and bounded polytopes. We show that a variant of parametric simplex algorithm can solve large scale rank two bilinear programming problems efficiently. Also, we show that a cutting-cake algorithm, a more elaborate variant of parametric simplex algorithm can solve medium scale rank three problems.This research was supported in part by Grant-in-Aid for Scientific Research of the Ministry of Education, Science and Culture, Grant No. 63490010.     

Global optimization of univariate Lipschitz functions: II. New algorithms and computational comparison

We consider the following global optimization problems for a Lipschitz functionf implicitly defined on an interval [a, b]. Problem P: find a globally-optimal value off and a corresponding point; Problem Q: find a set of disjoint subintervals of [a, b] containing only points with a globally-optimal value and the union of which contains all globally optimal points. A two-phase algorithm is proposed for Problem P. In phase I, this algorithm obtains rapidly a solution which is often globally-optimal. Moreover, a sufficient condition onf for this to be the case is given. In phase II, the algorithm proves the-optimality of the solution obtained in phase I or finds a sequence of points of increasing value containing one with a globally-optimal value. The new algorithm is empirically compared (on twenty problems from the literature) with a best possible algorithm (for which the optimal value is assumed to be known), with a passive algorithm and with the algorithms of Evtushenko, Galperin, Shen and Zhu, Piyavskii, Timonov and Schoen. For small, the new algorithm requires only a few percent more function evaluations than the best possible one. An extended version of Piyavskii's algorithm is proposed for problem Q. A sufficient condition onf is given for the globally optimal points to be in one-to-one correspondance with the obtained intervals. This result is achieved for all twenty test problems.The research of the authors has been supported by AFOSR grants 0271 and 0066 to Rutgers University. Research of the second author has been also supported by NSERC grant GP0036426, FCAR grant 89EQ4144 and partially by AFOSR grant 0066. We thank Nicole Paradis for her help in drawing the figures.     

On affine scaling algorithms for nonconvex quadratic programming

We investigate the use of interior algorithms, especially the affine-scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a hard problem, we show that the problem with an ellipsoidal constraint is easy. When the hard QP is solved by successively solving the easy QP, the sequence of points monotonically converge to a feasible point satisfying both the first and the second order optimality conditions.Research supported in part by NSF Grant DDM-8922636 and the College Summer Grant, College of Business Administration, The University of Iowa.     

Analytical and Numerical Treatment of Continuous Ageing in the Voter Model

The conventional voter model is modified so that an agent’s switching rate depends on the ‘age’ of the agent—that is, the time since the agent last switched opinion. In contrast to previous work, age is continuous in the present model. We show how the resulting individual-based system with non-Markovian dynamics and concentration-dependent rates can be handled both computationally and analytically. The thinning algorithm of Lewis and Shedler can be modified in order to provide an efficient simulation method. Analytically, we demonstrate how the asymptotic approach to an absorbing state (consensus) can be deduced. We discuss three special cases of the age-dependent switching rate: one in which the concentration of voters can be approximated by a fractional differential equation, another for which the approach to consensus is exponential in time, and a third case in which the system reaches a frozen state instead of consensus. Finally, we include the effects of a spontaneous change of opinion, i.e., we study a noisy voter model with continuous ageing. We demonstrate that this can give rise to a continuous transition between coexistence and consensus phases. We also show how the stationary probability distribution can be approximated, despite the fact that the system cannot be described by a conventional master equation.     

Bayesian Variable Selection and Estimation in Semiparametric Simplex Mixed-Effects Models with Longitudinal Proportional Data

In the development of simplex mixed-effects models, random effects in these mixed-effects models are generally distributed in normal distribution. The normality assumption may be violated in an analysis of skewed and multimodal longitudinal data. In this paper, we adopt the centered Dirichlet process mixture model (CDPMM) to specify the random effects in the simplex mixed-effects models. Combining the block Gibbs sampler and the Metropolis–Hastings algorithm, we extend a Bayesian Lasso (BLasso) to simultaneously estimate unknown parameters of interest and select important covariates with nonzero effects in semiparametric simplex mixed-effects models. Several simulation studies and a real example are employed to illustrate the proposed methodologies.     

EGFAFS: A Novel Feature Selection Algorithm Based on Explosion Gravitation Field Algorithm

Feature selection (FS) is a vital step in data mining and machine learning, especially for analyzing the data in high-dimensional feature space. Gene expression data usually consist of a few samples characterized by high-dimensional feature space. As a result, they are not suitable to be processed by simple methods, such as the filter-based method. In this study, we propose a novel feature selection algorithm based on the Explosion Gravitation Field Algorithm, called EGFAFS. To reduce the dimensions of the feature space to acceptable dimensions, we constructed a recommended feature pool by a series of Random Forests based on the Gini index. Furthermore, by paying more attention to the features in the recommended feature pool, we can find the best subset more efficiently. To verify the performance of EGFAFS for FS, we tested EGFAFS on eight gene expression datasets compared with four heuristic-based FS methods (GA, PSO, SA, and DE) and four other FS methods (Boruta, HSICLasso, DNN-FS, and EGSG). The results show that EGFAFS has better performance for FS on gene expression data in terms of evaluation metrics, having more than the other eight FS algorithms. The genes selected by EGFAGS play an essential role in the differential co-expression network and some biological functions further demonstrate the success of EGFAFS for solving FS problems on gene expression data.     

基于光谱曲线形态的高光谱影像检索方法研究

随着传感器技术、数据通讯技术的飞速发展,利用各种机载和星载传感器,己经获取到各种不同的海量遥感影像数据。巨大的数据量带来了数据存储和管理的问题,如何实现从海量影像数据中检索出我们所需要的信息显得十分迫切。影像检索最早由Chang于1980年提出,是对传统信息检索的扩展。针对海量遥感影像高效检索的需求和高光谱遥感影像波段数目多的特点,分析了影像检索中的影像距离函数和相似性度量问题,基于经典的曲线简化Douglas-Peucke算法(简称DP算法)提取光谱曲线的形态特征,利用“提取特征”的思想,提出了基于DP算法的光谱曲线和影像检索(简称DPSR)方法,将光谱形态特征应用于影像检索当中。DPSR利用光谱曲线上的特征点,减小了计算量,实现了有效地匹配和检索,适合高光谱遥感影像的光谱检索。文章选择了OMISI高光谱数据的四种易混分地类进行了相似性度量的对比实验。通过与常规的分析方法光谱角匹配(SAM)、光谱信息散度(SID)的对比可以看到,DPSR在较少计算量的情况下能保持较高的计算精度,提供了一种新的影像光谱高效检索方法。此外,文章还提出了尚待进一步研究的问题。     

钝头机体用嵌入式大气数据传感系统的 改进三点式算法1)

针对传统的用于钝头体飞行器的嵌入式大气数据传感系统的经典三点式算法对测压孔配置约束性严格的特点,对经典三点式算法进行了改进及验证。首先,对于经典三点式算法及改进算法进行了论述;其次,针对不同测压孔配置对算法精度的影响进行了系统的评估;最后,对于传统的经典三点式算法与改进三点式算法的优劣进行了比较。结论为：(1)改进的三点式算法对于测压孔的配置敏感性变差,即对测压孔约束很宽松,可用测压孔数增加,从而使得算法的适用性更强;(2)改进的三点式算法的精度与三点式算法相当,但是需要对测压孔进行系统选取及对比验证。     

基于动力XFEM的结构内多缺陷三步反演法

论文进行缺陷反演时,利用损伤指标法,确定缺陷数目,针对损伤指标法中缺陷取值范围存在人为性,推导了缺陷搜索范围的合理取值并进一步缩减了搜索范围;同时提出了一种考虑非线性因子的改进型人工蜂群算法,加速了多缺陷反演时目标函数最小化迭代过程。最后,通过三个算例验证了该方法对结构内规则和不规则缺陷的反演均具有较好的识别效果。