• PDF / 386,983 Bytes
• 20 Pages / 439.37 x 666.142 pts Page_size
• 10 Downloads / 187 Views

DOWNLOAD

REPORT

---

Two Relaxation Methods for Rank Minimization Problems April Sagan1 · Xin Shen2 · John E. Mitchell1 Received: 8 May 2020 / Accepted: 24 July 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract 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. 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 and show that constraint qualification holds at any stationary point of either relaxation of the rank minimization problem, and we explore the structure of the local minimizers. Keywords Constraint qualification · Optimality conditions · Rank minimization · Semidefinite programs with complementarity constraints Mathematics Subject Classification 90C33 · 90C53

1 Introduction to Rank Minimization Problems Rank constrained optimization problems have received increasing interest because of their wide application in many fields including statistics, communication and signal processing [1,2]. In this paper, we mainly consider one genre of the problems, whose objective is to minimize the rank of a matrix subject to a given set of con-

Communicated by Liqun Qi.

B

John E. Mitchell [email protected] https://www.rpi.edu/∼mitchj April Sagan [email protected] Xin Shen [email protected]

1

Department of Mathematical Sciences, Rensselaer Polytechnic Institute, Troy, NY 12180, USA

2

Yelp Inc., San Francisco, CA 94105, USA

123

Journal of Optimization Theory and Applications

straints. This class of problems has been considered as computationally challenging because of its nonconvex nature, particularly because the rank function is highly discontinuous. Many methods have been developed previously to solve the problem, including nuclear norm approximation [1,3–5]. The lack of theoretical guarantee for these convex approximations for general problems motivates us to turn to the exact formulation of the rank function, which can be constructed as a mathematical program with semidefinite cone complementarity constraints (SDCMPCC), as shown in Sect. 3. Analogously to the LPCC formulation for 0 minimization problem [6], the advantage of the SDCMPCC formulation is that it can be expressed as a smooth nonlinear program; thus it can be solved by general nonlinear programming algorithms. The purpose of this paper is to investigate the structure of the SDCMPCC formulation, especially stationary points for two relaxations of it. In general, a local minimizer of an SDCMPCC problem may not satisfy first order optimality conditions because of the complementarity constraints. We have previously shown [7] that the first order optimality conditions do indeed hold at local minimizers of the SDCMPCC lifting of the rank minimization. In the current paper, we show in Sect. 4 that these first order optimality conditions also hold at local minimizers o