Computing the Projection on the Intersection of Linear Equality and Cardinality Constraints

Abstract

In this paper, we introduce a novel approach to solve the vector projection problem under linear equality and cardinality constraints, termed the Quasi-Newton Lagrangian method. This approach employs a Lagrangian transformation to address linear equality constraints, leading to the formulation of a dual function. The equivalent form of the dual function is then solved using a closed-form solution specific to the cardinality-constrained projection problem. Finally, the Quasi-Newton method is applied to determine the optimal index function. Unlike traditional orthogonal projection methods, this method avoids direct computation of the projection matrix and instead employs a block-wise strategy to efficiently manage both linear equality and cardinality constraints, significantly broadening its applicability. Numerical experiments, involving 5000 trials on randomly generated problems of varying dimensions (ranging from 4 to 240), demonstrate that the algorithm achieves a success rate of up to 92% in projecting random problem instances. Furthermore, the computation time shows linear growth relative to the problem size as the dimensionality increases. The method is also effectively applied to the handling of quadratic programming problems, highlighting the significant advantages of the Quasi-Newton Lagrangian method in solving problems with both linear equality and cardinality constraints.

Keywords

• Linear equality constraints
• cardinality constraints
• projection
• Lagrange method
• quasi-newton method