Rank-Constrained Programming for Nonconvex Optimization

Rank-One Constrained Optimization: A general quadratically constrained quadratic program (QCQP) problem, in which the objective function and constraints are not necessarily convex, can be equivalently transformed into a linear matrix programming problem by introducing a to-be-determined rank-one matrix. As the general QCQP can be applied to the formulation of Boolean optimization, sensor network localization, polynomial programs, and many other optimization problems, the approach to rank-one constrained optimization is applicable to the solution of all of these challenging problems in the form of general QCQP. The open-source software for solving QCQPs is published at Link.

Rank-R Constrained Optimization: Rank-R (R ≥ l) constrained optimization has been used to represent signal processing, model reduction, and system identification, where the rank of the to-be-determined matrix is constrained to be less than or equal to R. More importantly, our recent findings have equivalently transformed a rank minimization problem into a rank-R constrained optimization problem (Link). This expands the application areas of rank-R constrained optimization to additional challenging problems, such as matrix completion or the design of a low-rank feedback controller.

Basic Approach

An iterative rank minimized approach, named IRM has been developed to solve general Rank-Constrained Optimization problems. The IRM method is inspired by the fact that for a matrix, X∈Sn+, with a rank less equal than R, the n-R smallest eigenvalues of X are all zero. Therefore, instead of putting a constraint on the rank, we focus on constraining the eigenvalues of X such that the n-R smallest eigenvalues of X are all zero, as shown below. It has been proven that, when X is a nonzero positive semidefinite matrix, rank(X)≤R if and only if eIn-R-VTXV≽0, where V∈ℝn×(n-R) are the eigenvectors corresponding to the n-R smallest eigenvalues of X, In-R is an identity matrix of size n-R, and e is a significantly small positive number. In other words, a substitute for the rank constraint on X is the semidefinite constraint eIn-R-VTXV≽0, where e→0. However, until we can find the solution for X, we cannot obtain the exact V matrix that is dependent on X. Therefore, the IRM method was proposed to gradually reduce the rank of X to the desired one. At each step, denoted with index k, we try to optimize the original objective function while at the same time minimize the weighted parameter ek such that, when ek=0, the rank-R constraint on Xk will be satisfied.