A Spectral Projected Gradient Method for Computational Protein Design problem

In this paper, we consider the computational protein design (CPD) problem, which is usually modeled as 0/1 programming and is extremely challenging due to its combinatorial properties. As a quadratic semi-assignment problem (QSAP), the CPD problem has been proved to be equivalent to its continuous relaxation problem (RQSAP), in terms of sharing the same optimal objective value. However, since the current algorithm for solving this RQSAP uses the projected Newton method, which requires direct computation of the Hessian matrix, its computational cost remains quite high. Precisely for this reason, we choose to employ the spectral projected gradient (SPG) method to solve the CPD problem, whose effectiveness relies on choosing the step lengths according to novel ideas that are related to the spectrum of the underlying local Hessian. Specifically, we apply the SPG method in two distinct ways: direct solving the relaxation problem and applying a penalty method. Numerical results on benchmark instances verify the superior performance of our approach over the current algorithms in both quality and efficiency.