In this paper we consider general rank minimization problems with rank
appearing in either objective function or constraint. We first show that a
class of matrix optimization problems can be solved as lower dimensional vector
optimization problems. As a consequence, we establish that a class of rank
minimization problems have closed form solutions. Using this result, we then
propose penalty decomposition methods for general rank minimization problems in
which each subproblem is solved by a block coordinate descend method. Under
some suitable assumptions, we show that any accumulation point of the sequence
generated by our method when applied to the rank constrained minimization
problem is a stationary point of a nonlinear reformulation of the problem.
Finally, we test the performance of our methods by applying them to matrix
completion and nearest low-rank correlation matrix problems. The computational
results demonstrate that our methods generally outperform the existing methods
in terms of solution quality and/or speed.