半定规划的预估校正内点算法

半定规划有着广泛的应用领域,例如系统论,控制论,模式识别等领域.为了更好地求解这些领域中遇到的半定规划问题,给出了半定规划的原始对偶预估校正内点算法.该算法由不同的搜索方向构成,利用牛顿法得到了3个搜索方向,数值实验表明:基于NT方向的算法最为稳健.     

基于内点算法的半定规划灵敏度分析

半定规划是线性规划的推广,内点算法是目前最有效的求解半定规划算法。研究了基于内点算法的半定规划的灵敏度分析,即右端向量和费用矩阵变化时对可行解的影响,并给出了在单步内点迭代时,保持可行域内和近似最优解时的参数变化的界限,以及一般情形的灵敏度分析。     

半定规划的一个扰动问题

构造半定规划的一个扰动问题.相比半定规划的标准问题,该扰动问题具有严格可行解.这对于设计和分析半定规划的不可行内点算法具有重要作用.     

基于新障碍参数更新的二阶Mehrotra型预估—校正算法

针对二阶Mehrotra型预估-校正算法的一种变型算法,本文介绍一种新的自适应障碍参数更新法。利用该更新方法提出了相应的算法。新算法与之前的二阶Mehrotra型预估-校正算法相比,不用根据预估步和校正步的步长来确定参数的更新,而是在每步迭代中都采用自适应更新。最后证明了该算法在没有引进任何＂保障措施＂的情况下也具有相同的多项式时间复杂度。     

解线性规划问题的预估-校正内点法

本文对线性规划问题提出一种跟踪中心路径的预估-校正内点法,证明了这种算法具有大范围线性收敛性和仅需O(n~(1/2)L),迭代。     

求解单调线性互补问题的邻域跟踪内点算法

把艾文宝的邻域跟踪算法推广到单调线性互补问题（LCP）,用2-范数代替1-范数来定义宽邻域。由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析比线性规划复杂。证明了算法的迭代复杂性为O（n～（1/2）L）。通过证明对偶间隙关于搜索步长的单调性,使得算法易于执行。数值实验显示了该算法的有效性。     

线性互补问题的邻域跟踪算法

文章把艾文宝的邻域跟踪算法推广到单调线性互补问题（LCP）,由于单调LCP的迭代方向不再具有正交性,因此算法的理论分析变得复杂。证明了算法的迭代复杂性为0（√nL）,并且通过证明对偶间隙的单调性,使得算法易于执行。     

聚碳酸酯表面铬酸预处理对涂层附着性能影响

半定规划基于特殊核函数的全牛顿步不可行内点算法

王亚丹¹,刘红卫¹,刘泽显^1,2

（1. 西安电子科技大学 数学与统计学院,西安 710126;

2. 贺州学院 数学与计算机学院,广西 贺州 542899）

创新点说明：

本文利用特殊的核函数改进算法的可行步,构造了相应的不可行内点算法,使得算法在每次迭代过程中只需一次全牛顿步,就能够得到接近中心路径的新的迭代点。

研究目的：

通过使用核函数改进可行步,提出一种新的全牛顿步不可行内点算法。

研究方法：

定量分析法;对比分析法; 数学实验法。

研究结果、结论：

1）通过使用特殊的核函数改进可行步,得到了一种新的半定规划不可行内点算法;

2）算法在每次迭代过程中仅使用一次可行步,就能够得到半定规划问题的近似最优解;

3）对算法进行复杂性分析,得到算法的迭代复杂度为 ,其中 ,结果表明：算法的迭代复杂度与目前半定规划最好的迭代复杂度一致。

关键词：半定规划,不可行内点算法,全牛顿步,核函数,多项式复杂度

     

推广的变量带上下界内点算法及其应用

对变量带上下界的内点算法进行了推广，介绍了推广算法的实现．还对推广算法在电力系统无功优化中的应用进行了探讨，并给出了无功优化的实例．数值计算显示该算法的应用是成功的．     

基于CICQ交换结构的低复杂度调度算法

针对CICQ权值仲裁策略复杂度高的不足,提出一种新的调度策略——LQP-RR（Long Queue Prioritized-Round Robin）。该算法利用VOQ队列局部变化的特性,简化了权值仲裁策略复杂的排序操作,只在输入端进行一次比较操作,并采用辅助轮询指针配合调度以保证算法的公平性,其算法复杂度仅为O（1）,硬件实现简单,扩展性能良好。通过流体模型证明该算法对满足强大数定律的许可输入流量能够达到100%的吞吐率性能。仿真结果进一步表明LQP-RR调度算法在各种流量模型下都能稳定运行,且具有良好的时延和吞吐率性能。     

求GF(3)上周期为3npm序列线性复杂度的快速算法

提出和证明了求周期为3npm的GF(3)上序列的线性复杂度和极小多项式的一个快速算法,这里p为素数,且3是模p2的本原根.该算法推广了求周期为pm的二元周期序列的线性复杂度的一个快速算法.     

变量带上下界内点算法的理论与实现

首先给出了变量带上下界的内点算法及其理论,并在计算机上实现了该算法。本文还提出了一个寻找初始内点的改进方法,数值计算表明改进后的方法能减少大多数情况下的迭代次数。