  Low-rank methods for semidefinite programming (SDP) have gained a lot of
interest recently, especially in machine learning applications. Their analysis
often involves determinant-based or Schatten-norm penalties, which are hard to
implement in practice due to high computational efforts. In this paper, we
propose Entropy Penalized Semi-definite programming (EP-SDP) which provides a
unified framework for a wide class of penalty functions used in practice to
promote a low-rank solution. We show that EP-SDP problems admit efficient
numerical algorithm having (almost) linear time complexity of the gradient
iteration which makes it useful for many machine learning and optimization
problems. We illustrate the practical efficiency of our approach on several
combinatorial optimization and machine learning problems.
