We investigate the solution of the Second-Order Cone Quadratic Eigenvalue Complementarity Problem (SOCQEiCP), which has a solution under reasonable assumptions on the matrices included in its definition. A Nonlinear Programming Problem (NLP) formulation of the SOCQEiCP is introduced. A necessary and sufficient condition for a stationary point (SP) of NLP to be a solution of SOCQEiCP is established. This condition indicates that, in many cases, the computation of a single SP of NLP is sufficient to solve SOCQEiCP. In order to compute a global minimum of NLP for the general case, we develop an enumerative method based on the Reformulation-Linearization Technique and prove its convergence. For computational effectiveness, we also introduce a hybrid method that combines the enumerative algorithm and a semi-smooth Newton method. Computational experience on the solution of a set of test problems demonstrates the efficacy of the proposed hybrid method for solving SOCQEiCP.