基于线性化技术的二次分配问题求解新方法

文章在对已有二次分配问题(QAP)线性化模型深入研究的基础上,提出一种二次分配问题线性化新方法,进而给出了对称二次分配问题的线性化模型.最后,通过求解二次分配基准问题库(QAPLIB)中的部分实例说明了该线性化新方法的有效性和重要性.     

一类特殊二次分配问题及其求解

二次分配问题(quadratic assignment problem,QAP)是应用于诸多领域的组合优化NP-难题,许多从实际问题中抽象出来的二次分配问题,其流矩阵与距离矩阵中存在大量零元素,如果在该类二次分配问题的求解中,能够充分利用这些零元素的信息,将大大缩减问题的规模,节省大量运算时间.本文以二次分配问题的线性松弛模型为基础,分别从理论和实验的角度对这类二次分配问题的求解进行了研究,说明了二次分配问题求解中,先行利用零元素信息减小问题规模的可行性和重要性.     

基于半定规划多用户检测问题的二次规划法

半定规划是解决极大似然多用户检测问题的一种重要方法,但当问题规模较大时,误码率较高。基于多用户检测问题的半定规划松弛模型,给出了一个二次规划松弛模型。该模型能得到比半定规划模型更好的界。根据这个模型,运用分枝定界方法,可以求得多用户检测问题的次优解。这种方法改善了用户多时半定规划方法误码率高的状况,是解决多用户检测问题的有效方法。仿真实验证实了这一点。     

求QoS路由的整数线性规划方法

QoS路由的任务是在网络中寻找一条满足多个约束条件的路径使网络资源的利用达到最优. 该问题是一个NP-完全问题. 提出了一种新的基于整数线性规划模型选择路由的方法. 思路是将复杂约束引入到目标函数作为罚项, 得到一个松弛整数线性规划问题. 因为约束系数矩阵是全幺模矩阵, 松弛问题可以通过线性规划很快地求解. 拉格朗日乘子的调整用罚函数的方法很容易计算. 数值实验表明提出的方法是有效的.     

三站无源定位系统数据关联算法

全局最优量测数据关联算法是无源定位技术中的关键问题。针对三站无源定位系统全局最优数据关联的三维（3-D）分配问题，提出一种新的直接求解算法——启发式消元算法。该算法通过直接对代价矩阵的元素进行启发式消元，得到分配问题的最优解。给出算法相关原理的分析和证明以及算法的具体步骤。并将其应用于三部光电被动传感器多目标无源定位系统两级数据关联算法的第二级关联过程中。对启发式消元算法和求解3一D分配问题的近似最优求解算法——拉格朗日松弛算法的算法复杂性进行了分析对比。理论分析和仿真实验均表明，该算法较适合与两级关联算法联合使用。与拉格朗日松弛算法相比。该算法计算量小。便于实现。是一种新的、有效的全局最优数据关联算法。     

一种带预处理的离散系数滤波器设计方法

提出了一种带预处理的离散系数滤波器设计方法。该方法基于离散系数滤波器设计问题的{-1,1}二次规划模型,利用{-1,1}二次规划的全局最优性条件,提出了一种最优解元素的判断准则,得到了一个规模较小的离散系数滤波器设计问题。结合随机扰动方法,得到了求解离散系数滤波器设计问题的一种带预处理的随机扰动算法。与随机扰动方法相比,带预处理的随机扰动方法得到的次优解的性能更好,需要的时间也大大减少。     

基数约束投资组合选择问题

投资者在进行投资组合选择时，通常希望得到的投资组合方案中，被选择资产数量可控，风险水平足够小。模型中通常以基数约束来控制投资组合方案中选择的资产数量。基于一类基数约束投资组合选择模型，该模型以最小化风险函数为目标，在不允许卖空前题下，考虑基数约束和预算约束。该模型应用极其广泛，但目前尚无商用软件可以直接精确求解。提出一种全局最优化算法，在分支定界法框架基础上，以一阶算法求解下界松弛问题。通过Fama-French产业投资组合基准测试数据集设计仿真实验，实验结果表明，本文提出方法能有效解决带基数约束的产业投资组合问题，能够给出任意基数要求的全局最优投资组合方案。     

基于线性近似和神经网络逼近的模型预测控制

针对非线性系统的模型预测控制问题,提出了一种基于线性近似和神经网络逼近的控制算法。用Taylor级数展开法对非线性系统进行线性近似时,要求对象系统中的非线性函数必须连续可微。为了突破这一限制,引入了Stirling插值公式线性近似法,拓展了可处理的非线性系统范围。通过对线性化过程中产生的非线性高阶项进行径向基函数(radial basis function, RBF)神经网络逼近,显著提高了对象系统模型精确度。为了降低数值计算复杂度,将控制性能指标函数重构为易于处理的二次型最优化问题,通过对该二次型最优化问题的求解得到了最优控制序列。控制过程考虑了约束条件的影响以模拟真实的工业生产过程。仿真结果证明了所提出预测控制方案的有效性。     

串置翼垂直起降无人机过渡机动飞行控制

针对新型串置翼布局推力矢量无人机在垂直起降、过渡机动飞行过程中强非线性、强耦合及控制冗余的问题,采用动态逆控制方法设计全局控制系统,无需针对不同飞行模式切换控制策略。在此基础上,提出二级递进式控制分配策略,将序列二次规划、链式递增方法相结合,对航迹回路和姿态回路的控制量进行综合优化分配。同时,根据任务需求及飞行状态,基于离线数据库在线实时更新直接力控制分配目标函数权值。采用松弛约束策略,局部放宽非线性优化问题约束,增加优化求解速度。仿真结果表明该控制器能够有效跟踪高机动目标航迹。     

动态武器目标分配问题中策略优化的改进算法

动态武器目标分配(Weapon Target Assignment,WTA)中的目标选择策略问题可以通过建立马尔可夫决策过程(Markov decision processes,MDP)模型进行研究,但目前尚无有效求解此类较大规模的MDP问题中最优策略的算法.通过分析动态WTA问题的MDP模型特点,给出了求解该问题最优策略的改进算法.该算法主要在初始策略选取规则、策略改进规则以及最优策略的判断准则等方面进行了改进.该算法具有计算量小,节省内存,并可得到最优解等优点.最后,通过算例将该算法与传统算法进行了比较.改进算法可以用于解决较大规模的动态WTA中的策略优化问题.