论文部分内容阅读
在实际生活中,我们遇到的问题一般都是多目标问题。而文献[15]证明了这些多目标问题基本上都可以直接写成多目标半定规划问题,或者对变量的约束进行一定的放宽,间接化成多目标半定规划问题。因此针对多目标半定规划问题,提出一种快速有效的算法是十分有意义的。
在各类多目标半定规划问题中,线性型多目标半定规划占有十分重要的地位。这不仅是因为它与我们实际生活关系最为密切,也是因为这类问题有着更好的性质,例如凸性,可导性等等,所以更便于我们来研究这类问题。
而目前解决线性型多目标半定规划的方法大多是先将线性型多目标半定规划通过一些手段化成单目标半定规划,然后利用一些单目标规划中的内点算法来解决。这样做最大的弊端是只能得到一个有效解或弱有效解,并不能得到全部或者区域性的有效解,而且这样做并没有充分利用到线性型多目标半定规划的特殊性质。
本文首先证明了线性型多目标半定规划问题和单目标半定规划问题在最优性条件上有相似之处。然后基于这个结论,对于线性型多目标半定规划问题,借鉴单目标半定规划的中心路径法,提出了求解多目标半定规划问题的加权中心路径法,通过加权路径中心法得到对应一个权向量的有效解。但是一般来说多目标问题的有效解有很多,只是得到一个有效解并不能算很好的解决了这个问题,因此本文还提出了在这个已知有效解的基础上,通过一次迭代得到对应一定范围内其他任意权向量的有效解的一步修正方法。基于在本文提出的多目标半定规划的加权中心路径法的基础上,我们进而提出了一种交互式多目标半定规划问题内点算法。