一类带指示变量的凸二次优化问题的研究

The Study of Convex Quadratic Optimization Problems with Indicator Variables

摘要: 本文研究一类带指示变量的凸二次优化问题。该问题在多个领域具有广泛应用，如投资组合选择、信号处理和资源分配等。作为混合整数二次优化问题，其NP-hard特性使得大规模实例求解面临较大挑战。本文分别提出了三种求解方法：启发式搜索下降法、精确分支定界法以及两者结合的混合方法。首先，启发式搜索下降法通过局部优化获得近似解，显著提高求解速度；其次，精确分支定界法通过逐步分解问题空间，保证了全局最优解的精确性。最后，结合启发式搜索下降法和分支定界法的优点，提出了一种新的混合方法，利用启发式方法提供的初始解加速分支定界法的收敛过程，减少计算资源消耗，同时确保解的精确性。实验表明，启发式搜索下降法在低维和高维问题上均具有显著的计算效率优势。与SCIP和Gurobi求解器相比，混合方法展现出了更优的求解效率。

Abstract: This paper studies a class of convex quadratic optimization problems with indicator variables, which have broad applications in various fields such as portfolio selection, signal processing, and resource allocation. As a mixed-integer quadratic optimization problem, its NP-hard nature makes solving large-scale instances challenging. This paper proposes three solution methods: a heuristic search descent method, an exact branch-and-bound method, and a hybrid method combining the two. First, the heuristic search descent method provides approximate solutions through local optimization, significantly improving solving speed. Second, the exact branch-and-bound method ensures global optimality by gradually decomposing the problem space. Finally, a new hybrid method is introduced, combining the advantages of both approaches by using the initial solution provided by the heuristic method to accelerate the convergence of the branch-and-bound method, reducing computational resource consumption while ensuring solution accuracy. Experimental results show that the heuristic search descent method exhibits significant computational efficiency advantages in both low-dimensional and high-dimensional problems. Compared with the Gurobi and SCIP solvers, the hybrid method demonstrates superior solving efficiency.