首页 理论教育解决MINLP问题的高效策略在空间信息网络中的应用

解决MINLP问题的高效策略在空间信息网络中的应用

【摘要】:由于λ2的非线性和a ij的整数限制,因此原始问题可以认为是一个混合整型非线性规划问题,这是一个NP-hard问题。MINLP问题也可以通过将凸优化和分支定界法相结合来得到最优解,但在部署时通常需要采用中心式的策略耗费大量的计算资源,在空间信息网络中是不适用的。

在空间信息网络中构建最小生成树的最优化问题时,将在一系列网络实际约束条件的限制下,构建一个具有最小链路权重的生成树,该问题的原始最优化形式可以表示为

式中,第一个约束条件中λ2(A)指的是邻接矩阵为A的网络的代数连通度(关于代数连通度的概念在第3章中有详细介绍),因此它是一个凸函数,用以保证网络是连通的;第二个约束条件指的是网络中的链路数量为N-1,前两个约束条件保证构建的是一棵生成树;第三个约束条件确保生成树中各节点使用的天线数量不超出节点的自由度限制;第四个约束条件指的是构建的链路形成的邻接矩阵需要满足邻接条件的限制;第五个约束条件是邻接矩阵定义中的整型部分。

由于λ2(A)的非线性和a ij的整数限制,因此原始问题可以认为是一个混合整型非线性规划问题(MINLP),这是一个NP-hard问题。与上一章类似,通过移除问题中的整型约束能够得到问题的松弛形式,从而可解出对应的松弛解;然后根据问题的特点提出相应的迭代算法,应能在有限次的迭代后得到精度可保证的次优解。但是,这种基于松弛解和次优迭代得到的解,不仅有可能无法得到最优解,而且有可能得到的最优解是不可行的。MINLP问题也可以通过将凸优化和分支定界法相结合来得到最优解,但在部署时通常需要采用中心式的策略耗费大量的计算资源,在空间信息网络中是不适用的。所以,不能局限于传统的求解方法,需要提出一种低开销的、分布式的和链路权重持续变化的最小生成树算法,来适应网络的分布式环境