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.     

On the validity of the counterpoise correction for the basis set superposition error including the fragment relaxation terms

It is demonstrated that relatively large geometrical changes make Emsley et al.'s assumption (J Am Chem Soc (1978) 100:3303) on the counterpoise correction for the basis set superposition error including the fragment relaxation terms unacceptable. Received: 23 September 1997 / Accepted: 31 October 1997     

基于遗传算法的PTP1B抑制剂的二维定量构效关系研究

利用遗传算法,并结合线性回归和交叉验证方法,对一系列43个苯并呋喃/噻吩联二苯类PTP1B抑制剂作了二维定量构效关系的研究.计算得到了一组效果较好的定量构效关系模型.模型不仅具有好的回归能力,而且还具有很好的预测能力.同时,通过分析在遗传优化过程中参数在精华种群中所占的比例,还得到了可能对活性影响较大的成分.计算结果表明,分子的4个参数:lgP(分配系数)、Area（表面积）、MW（分子量）以及Dip（偶极距）是影响化合物活性的最重要的参数,这对抑制剂的设计和改造提供了指导.     

HFC网上行信道时隙同步的性能分析

在分析HFC网络上行信道时隙同步过程的基础上,建立在系统故障恢复情况下上行信道时隙同步过程的数学建模,重点研究了HFC网完成上行信道时隙同步所需的平均时间.文中给出了不同网络规模、冲突解析算法参数值、上行信道带宽分配策略条件下的实验结果.最后提出了优化HFC网上行信道时隙同步性能的措施.     

用进化规划思想优化径向基函数神经网络结构的均衡器

针对训练径向基函数(RBF)神经网络均衡器的随机梯度算法(SG)中,神经网络的结构是指定的并且所用训练样本较长的问题,引入进化规划思想,用进化规划方法确定径向基函数神经网络的结构,用基于最小均方(LMS)误差准则的自适应算法调整神经元到输出端的连接权重.蒙特卡洛仿真表明,用这种方法确定的均衡器可以达到与SG算法相同的性能,而所用训练样本很少,网络结构不需要事先指定.     

一种眼动测量的图像分析方法

提出一种用于鸟类视觉行为学实验的眼动测量的图像分析方法.采用基于遗传算法的多级灰度值聚类法分割普通CCD捕捉的视频图像,用区域生长法标记连通域粗略定位瞳孔区域,并利用瞳孔的近似圆形的几何特性修补光源反射影像形成的孔洞.在此基础上进行边缘检测,利用边缘像素的灰度分布特点修正瞳孔轮廓,采用重心法定位瞳孔中心.用该方法对实验环境照度下捕捉的图像和红外光源辅助照明的图像进行了分析,并与主动轮廓线方法对比.实验结果表明,该方法对眼睛特征的先验知识依赖程度低,抗噪声能力强,瞳孔中心定位精确.     

遗传算法及神经网络在锅炉负荷优化分配中的应用

针对并列运行锅炉群的负荷优化分配问题,提出用遗传神经网络辨识给煤量-产气量模型,并用改进的遗传算法进行负荷优化分配.给出了改进遗传算法和遗传神经网络的辨识原理.负荷优化分配结果表明,该方法优于平均分配方法.     

一种修正的窄缝电磁耦合FDTD算法

电磁脉冲通过窄缝的耦合计算是电磁兼容研究中的一个重要问题,现有算法存在着一些局限或不足.为得到一种能够反映窄缝实际耦合特点的算法,研究了Wang的窄缝算法中的不足,并基于其提出了一种修正的窄缝电磁耦合FDTD算法,即假设窄缝所在网格上的电磁总场在面向入射场源的窄缝一侧是随离窄缝距离增加而增强的,而在背向入射场源的窄缝一侧是随离窄缝距离的增加而减弱的.用该算法对ESD电流注入细导线产生的电磁场与窄缝的耦合进行了计算.计算结果表明了该算法的正确性.