半定松弛与非凸二次约束二次规划研究

In many applications, there are a host of very difficult optimization problems which have the form of nonconvex quadratically constrained quadratic programs(QCQPs). For this kind of problem, the semidefinite relaxation(SDR）is a powerful computationally efficient approximation technique. Many study results indicated that SDR is capable of providing an exact optimal solution or an approximation solution to the original difficult optimization problem.. The main content of this study includes the following four aspects.(1)The study will concentrate on the tightess of SDR for some special QCQPs in certain or uncertain enviroment. The main purpose is to provide some conditions under which the tightness of SDR holds.(2)In stead of considering the worst case in many referrences when establishing the approximation accuracy, we will try to provide a deterministic approximation accuracy in which the information of the given parameter matrices in the certain QCQPs will be involved.(3)As part of the study,the robust duality theory will be developed for the robust QCQPs, and some conditions that the robust strong duality theorem holds will be presented. Another important issue is that what the relationship between the best of dual problem and the SDR problems is. (4) Based on the concave-reformulation function proposed by us, the formulation of the smallest concave-reformulation funciton and a new convex relaxation will be established. Then a global optimization algorithm based on the new convex relaxation will be proposed. In addition, there is a comparative research on the SDR technique and our new convex relaxation..A lot of simulations will be performed for many QCQPs with application background. The simulation results will be powerful evidence to the correctness and validity of the proposed theoretical results.

应用中许多优化问题都是大规模非凸二次约束二次规划问题(QCQP)，半定松弛（SDR）技术是求解此类问题有效可行的逼近方法，是一个前沿的研究方向.通过求解半定松弛规划，可以获得原问题的精确解或近似解.. 研究内容包括：（1）针对特殊的QCQP，分别在确定和不确定环境下，研究其SDR问题具有紧性的充分和必要条件;（2）讨论给定QCQP问题的SDR的近似比时,不去考虑最坏情况,而是充分利用问题中的参数矩阵信息,确定一个好的确定性近似比;（3）研究Robust QCQP问题的Robust对偶理论，分析对偶问题的最好问题与SDR问题之间的联系，给出Robust强对偶定理成立的条件;（4）基于申请者提出的凹式函数，研究最佳凹式函数的表达式，基于此来构造非凸QCQP问题的凸松弛，并设计分支定界法求全局最优解，最后与SDR技术进行对比研究.. 通过对应用模型的大量数值模拟，检验理论结果的正确性.

针对特殊优化问题的研究是非线性规划领域中一个重要的方面。本项目的研究，利用半定松弛、线性或非线性松弛、广义凸松弛、最优性条件等最新理论，在已取得良好工作的基础上，围绕QCQP优化、三次优化（CP）、多目标规划等特殊形式的问题，也考虑这些问题中有随机参数的不确定型优化问题，分别在各种松弛的紧性、松弛逼近及算法设计、全局最优性条件、Robust拉格朗日对偶、Robust正则对偶等方面，寻求新的理论结果及相关算法，并通过大量的数值实验对相关理论就行了验证分析。本项目也根据所得的研究成果，在金融领域进行相应的应用研究,已取得了一批有特色、有影响的结果，对相关领域的高科技发展也提供了重要的理论支持。