Matrix rank related optimization problems comprise rank-constrained optimization
problems (RCOPs) and rank minimization problems, which involve the matrix rank function
in the objective or the constraints. General RCOPs are defined to optimize a convex objective
function subject to a set of convex constraints and rank constraints on unknown rectangular
matrices. RCOPs have received extensive attention due to their wide applications in signal
processing, model reduction, and system identification, just to name a few. Noteworthily,
The general/nonconvex quadratically constrained quadratic programming (QCQP) problem
with wide applications is a special category of RCOP. On the other hand, when the rank
function appears in the objective of an optimization problem, it turns out to be a rank
minimization problem (RMP), classified as another category of nonconvex optimization.
Applications of RMPs have been found in a variety of areas, such as matrix completion,
control system analysis and design, and machine learning.
At first, RMP and RCOPs are not isolated. Though we can transform a RMP into a
RCOP by introducing a slack variable, the reformulated RCOP, however, has an unknown
upper bound for the rank function. That is a big shortcoming. Provided that a given matrix
upper bounded is a prerequisite for most of the algorithms when solving RCOPs, we first
fill this gap by demonstrating that RMPs can be equivalently transformed into RCOPs by
introducing a quadratic matrix equality constraint. Furthermore, the wide application of
RMPs and RCOPs attract extensive studies aiming at developing efficient optimization algorithms to solve the challenging matrix-related optimization problems. Motivated by the
limitations of existing algorithms, we aim to develop effective and efficient algorithms to
solve rank-related optimization problems. Two classes of algorithms and their variants are
proposed here.
The first algorithm, based on the alternating minimization, is named iterative rank minimization (IRM). The IRM method, with each sequential problem formulated as a convex
optimization problem, aims to solve general RCOPs, where the constrained rank could be
any assigned integer number. Although IRM is primarily designed for RCOPs with rank
constraints on positive semidefinite matrices, a semidefinite embedding lemma is introduced
to extend IRM to RCOPs with rank constraints on general rectangular matrices. Moreover,
The proposed IRM method is applicable to RCOPs with rank inequalities constrained by
upper or lower bounds, as well as rank equality constraints. Convergence of IRM is proved
via the duality theory and the Karush-KuhnTucker conditions. Furthermore, the conversion
from RMPs to RCOPs and the proposed IRM method are applied to solve cardinality minimization problems and cardinality-constrained optimization problems, which are handled as
special cases of RMPs and RCOPs, respectively. To verify the effectiveness and improved
performance of the proposed IRM method, representative applications, including matrix
completion, system identification, output feedback stabilization, structured H2 controller
design, and cardinality minimization problems, UAV path planning, network identification,
are presented with comparative results. Moreover, for sparse QCQPs, a variant of IRM is
developed to enhance the efficiency by exploiting the sparsity.
The second algorithm, based on the framework of alternating direction method of multipliers (ADMM), aims to get simple subproblem solutions, even in closed forms. We
reformulate the rank constraint by matrix factorization and thus lead to the Burer-Monteiro form to achieve simpler subproblems. Despite the nonconvex constraint, we prove the
ADMM iterations converge to a stationary point in two types of formulations under mild
assumptions. Additionally, recent work suggests that in this latter form, when the matrix
factors are wide enough, local optimum with high probability is also the global optimum. To
demonstrate the scalability of our algorithm, we include results for MAX-CUT, community
detection, and image segmentation benchmark and simulated examples. A variant of our
algorithm reformulates the original RCOP using an approximate representation. The approximate formulation and the introduced bilinear constraint make each subproblem of ADMM
more computationally-efficient. In particular cases, the subproblems can even be solved in a
closed form. We then prove the global convergence of our proposed algorithm to a local
minimizer of the approximate problem. Another variant focuses on solving QCQPs with
both equality and inequality constraints. Based on inexact augmented Lagrangian method,
the subproblem also admits a simple closed-form solution. By exploiting the structure of
specific problems, such as network module detection, the computational efficiency can be
further improved.
Moreover, we also examine the simultaneous design of the network topology and the
corresponding edge weights in presence of a cardinality constraint on the edge set. Network
properties of interest for this design problem lead to optimization formulations with convex
objectives, convex constraint sets, and cardinality constraints. This class of problems
is referred to as cardinality-constrained optimization problem (CCOP); the cardinality
constraint generally makes CCOPs NP-hard. In this work, a customized ADMM algorithm
aiming to improve the scalability of the solution strategy for large-scale CCOPs is proposed.
This algorithm utilizes the special structure of the problem formulation to obtain closed-form
solutions for each iterative step of the corresponding ADMM updates. We also provide the convergence proof of the proposed customized ADMM to a stationary point under certain
conditions.
In conclusion, this dissertation developed the algorithmic frameworks to solve RCOPs
and RMPs with convergence analysis. Comparative simulation results with the state-of-art
algorithms are provided to validate the efficacy and effectiveness of proposed algorithms.