  This paper addresses the real structured controllability, stabilizability,
and stability radii (RSCR, RSSZR, and RSSR, respectively) of linear systems,
which involve determining the distance (in terms of matrix norms) between a
(possibly large-scale) system and its nearest uncontrollable, unstabilizable,
and unstable systems, respectively, with a prescribed affine structure. This
paper makes two main contributions. First, by demonstrating that determining
the feasibilities of RSCR and RSSZR is NP-hard when the perturbations have a
general affine parameterization, we prove that computing these radii is
NP-hard. Additionally, we prove the NP-hardness of a problem related to the
RSSR. These hardness results are independent of the matrix norm used. Second,
we develop unified rank-relaxation based algorithms for these problems, which
can handle both the Frobenius norm and the $2$-norm based problems and share
the same framework for the RSCR, RSSZR, and RSSR problems. These algorithms
utilize the low-rank structure of the original problems and relax the
corresponding rank constraints with a regularized truncated nuclear norm term.
Moreover, a modified version of these algorithms can find local optima with
performance specifications on the perturbations, under appropriate conditions.
Finally, simulations suggest that the proposed methods, despite being in a
simple framework, can find local optima as good as several existing methods.
