论文摘要
多项式优化问题（POP）是一类在科学与工程中较为常见的优化问题，它具有多项式目标函数与约束，包括了常见的线性规划（LP）、二次规划（QP）等具有重要应用价值的优化问题。因此，对POP解法的研究是有意义的。近年来，Lasserre提出了一种新的求解多项式优化问题最优值的方法[1]。这种方法通过几个数论中的表示定理，对多项式进行分解，从而构造一系列半定规划（SDP）问题，它们的最优值单调逼近原多项式优化问题的最优值。这种方法的优势在于，将（可能）NP-难的多项式优化问题，转换成了多项式时间可解的SDP问题。并且，这种转换是一致的，对原POP没有特殊要求。这使得该方法适用面很广，且求解效果有理论保证。QP问题，是具有二次目标或二次约束的一类优化问题，在许多领域具有重要的应用价值。在供应链管理、博弈论、投资组合、图论、支持向量机等学科领域，QP都有十分重要的应用。作为POP的子问题，可以直接应用POP的求解方法对QP问题进行求解。因为这种新方法的理论基础与传统的QP方法不同，所以有可能得出优于传统方法的结果。基于以上考虑，本文采用这种新的POP方法，对几个QP问题进行实际求解。目前已有的POP相关文献，只给出了理论结果，没有实际的数值计算效果分析，本文的工作填补了这一空白。数值实验结果表明，这种新的POP方法，尽管在理论上结果很优美，但是实际求解效果不尽如人意。与用来对照的方法相比，POP方法求解最优值的效果更好，但是计算效率太低，导致只能求解较小规模的问题，从而不实用。本文主要应用Lasserre提出的POP方法，对几个具体的QP问题进行求解。文章大致分为两个部分：前一部分包括第2，3章，介绍POP的定义，以及各种约束情况下的求解方法；后一部分包括第4章，给出数值实验结果，采用前面介绍的POP方法，以及某些参照方法，对几个实际的QP问题进行求解，并对算出的结果进行简要分析，从求解效果、计算效率几个方面比较POP方法与其他求解方法。最后，对全文的分析和结果进行总结。