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

项目名称： 半定松弛与非凸二次约束二次规划研究

项目编号： No.11271243

项目类型： 面上项目

立项/批准年度： 2013

项目学科： 数理科学和化学

项目作者： 王燕军

作者单位： 上海财经大学

项目金额： 60万元

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

中文关键词： QCQP 问题；全局最优性条件；三次优化；鲁棒优化；

英文摘要： 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 b

英文关键词： QCQP problems；global optimality conditions；cubic programming；robust optimization；