‡Department of Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy, NY 12180, USA.
E-Mail:
sagana@...
*
Yelp Inc, San Francisco, CA 91405.
E-Mail:
shenxinhust@...
†Department of Mathematical Sciences, Rensselaer Polytechnic
Institute, Troy, NY 12180, USA. Supported in part by the National Science Foundation under
Grant Numbers CMMI-1334327 and DMS-1736326
and by the Air Force Office of Scientific Research under Grant Number
FA9550-11-1-0260. E-Mail:
mitchj@...
The problem of minimizing the rank of a symmetric
positive semidefinite matrix subject to
constraints can be lifted to give an equivalent semidefinite program
with complementarity constraints (SDCMPCC). The formulation
requires two positive semidefinite matrices to be complementary.
This is a continuous and nonconvex reformulation of the rank
minimization problem.
We develop two relaxations of the problem.
We show that constraint qualification holds at any stationary point
of either formulation
and we explore the structure of the local minimizers.
Keywords:
Rank minimization,
constraint qualification,
semidefinite programs with complementarity constraints
Two Relaxation Methods for Rank Minimization Problems (pdf)