非凸二次优化的Lagrangian对偶理论与应用

We study the general NP-hard nonconvex quadratic optimization problem and its Lagrangian dual. More precisely, we focus on the following three points: equality, ratio and difference between the optimal values of the primal and Lagrangian dual problems. Firstly, the equality means that there is no duality gap, i.e., strong duality holds. The strong duality is based on the alternative theory. We will establish nonhomogeneous Finsler theorem and propose a unified theorem for the system of two nonhomogeneous quadratic functions. Secondly, suppose the primal problem is a maximization with a positive optimal objective value, according to the weak duality, the ratio between the optimal values of the primal and dual problems is always less than or equal to 1. We will follow the hot research topic to improve the lower bound of this ratio. As a by-product, we can obtain new approximation algorithms for solving the primal QP. Thirdly, when the difference between the primal minimization and dual optimal values is positive, we will develop new techniques to reduce the duality gap. Applications of this project include the generalized trust region subproblem, the robust least square, the Chebyshev center of the intersection of balls, the weighted maximin dispersion problem, the sparse PCA, the quadratic assignment problem and so on.

考虑NP-困难的非凸二次优化，基于原问题与其Lagrangian对偶问题的关系，本项目从等、商、差三大方面展开非凸二次优化的Lagrangian对偶理论和应用研究。第一，等号意味着强对偶，即没有对偶间隙。非凸二次优化强对偶的理论基础是择一性理论。我们志在推导非齐次Finsler定理，进一步统一两个一般非齐次二次函数系统的本质的择一性理论。第二，假定原问题为极大化且最优值大于0，根据弱对偶定理，原问题与对偶问题最优值的商总是小于等于1，本项目延续长期以来的国际研究热点：深入估计该商的下界，一个副产品是能同时提供原问题的近似算法。第三，在极小化的原问题与其对偶问题最优值之差大于0时，本项目深入发展缩减对偶间隙的技术。本项目中涉及的应用问题包括广义信赖域子问题、鲁棒最小二乘、多球交集的切比雪夫中心近似、加权最大最小分散问题、稀疏主成分分析、二次指派问题等。

本项目按计划围绕等、商、差三大方面对非凸二次优化的Lagrangian对偶理论和应用展开研究，在Lp球约束极大极小散度问题、预算约束0-1二次规划、双井势函数、p正则子问题、线性两比式和问题、矩阵线性比式和问题、极大化两个Rayleigh商之和的优化问题、Tikhonov正则化整体最小二乘问题、单一双边二次约束的分式二次优化问题、二次分配问题、GPS定位问题、两椭球交集的Chebyshev中心问题、球面上极大化二次型函数的平方和、线性互补约束二次规划问题、机组组合等问题上取得卓有成效的进展，解决了一些公开问题，提出了新的科学问题，也设计了创新性的全局优化算法。其中GPS定位问题的模型和算法以及机组组合问题有望成果转化。项目整体执行情况良好，完成了既定的研究目标，共计发表期刊论文30篇和会议论文1篇， 其中23篇SCI（待）检索，包括一篇优化顶级期刊Mathematical Programming和两篇优化顶级期刊SIAM Journal on Optimization论文。本项目共资助培养博士研究生毕业4名，硕士生毕业5名，在读博士生12名。本项目主持人2018年获批国家自然科学基金优秀青年科学基金项目。