A relaxation method for binary orthogonal optimization problems based on manifold gradient method and its applications

Abstract

This paper focuses on a class of binary orthogonal optimization problems frequently arising in semantic hashing. Consider the fact that this class of problems may have an empty feasible set, rendering the problem not well-defined, we introduce an equivalent model involving a restricted Stiefel manifold and a matrix box set, and then investigate its penalty problems induced by the ℓ1-distance from the box set and its Moreau envelope. We prove that two penalty problems are well-defined and serve as the global exact penalties provided that the original feasible set is non-empty. The penalty problem induced by the Moreau envelope is a smooth optimization over an embedded submanifold with a favorable structure. We develop a retraction-based line-search Riemannian gradient method to address the penalty problem. Finally, the proposed method is applied to supervised and unsupervised hashing tasks and is compared with several popular methods on real-world datasets. The numerical comparisons reveal that our algorithm is significantly superior to other solvers in terms of feasibility violation, and it is comparable even superior to others in terms of evaluation metrics related to the Hamming distance.