线性互补约束二次规划问题的一个全局算法研究

项目名称： 线性互补约束二次规划问题的一个全局算法研究

项目编号： No.11526186

项目类型： 专项基金项目

立项/批准年度： 2016

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

项目作者： 周晶

作者单位： 浙江工业大学

项目金额： 3万元

中文摘要： 线性互补约束二次规划模型包含了许多经典的组合优化问题，因此对该问题求解方法的研究具有很好的应用价值。该问题是一个NP难问题，所以不存在多项式时间算法除非P=NP。本项目旨在探讨在二阶锥松弛的基础上，应用分枝定界算法求解线性互补约束二次规划问题的全局最优解。在算法设计过程中，侧重研究：如何利用问题本身特点在松弛问题中添加有效的线性约束和二阶锥约束，从而提高问题的松弛效果；如何给出原问题的上界求解方法，进而提供减枝条件；对于目标函数也是非凸的情形如何进行预处理，从而提高算法的效率。

中文关键词： 二阶锥规划；半定规划；分枝定界算法；非负二次函数锥；锥重组

英文摘要： Quadratic optimization with linear complementarity constraints contains many classic combinational optimization problems, hence it deserves us to study how to solve the problem. It is NP-hard, thus there is no polynomial-time algorithm unless P=NP. In this project, we aim to study how to find a global optimal solution for quadratic optimization with linear complementarity constraints through branch-and-bound method. During the algorithm design, we focus on the following research items: Firstly, how to add valid linear constraints and second order cone constraints based on the characteristics of problem itself; secondly, how to provide an upper bound for the primal problem in order to give a cutting branches condition; and at last how to preprocess the primal problem if the objective function is nonconvex for purpose of improving the efficiency of the algorithm.

英文关键词： second-order cone programming；semidefinite programming；branch-and-bound algorithm；cone of nonnegative quadratic functions；conic reformulation