Computing cone-constrained singular values of matrices
For researchers in optimization and graph theory, this work establishes the computational complexity of cone-constrained singular values and offers practical algorithms, though the exact methods are limited to small instances.
This paper addresses the NP-hard problem of computing the least singular value of a matrix relative to a pair of closed convex cones, with applications in graph theory. It provides exact algorithms (non-convex quadratic programming and brute-force active-set) and heuristics (alternating projections and fractional programming) that compute globally or locally optimal solutions.
This paper deals with the numerical computation of the least singular value of a rectangular matrix $A$ relative to a pair of closed convex cones $(P,Q)$, which is defined as the optimal value of the non-convex optimization problem of minimizing $\langle u,Av\rangle$ such that $u$ and $v$ are unit vectors in $P$ and $Q$, respectively. When $A$ is the identity matrix, the least singular value coincides with the cosine of the largest angle between $P$ and $Q$. When $P$ and $Q$ are positive orthants, the least singular value is called the least Pareto singular value of $A$ and has applications, for instance, in graph theory. We prove the NP-hardness of all the above problems, while identifying cases when such problems can be solved in polynomial time. We then propose four algorithms. Two are exact algorithms, meaning that they are guaranteed to compute a globally optimal solution; one uses an exact non-convex quadratic programming solver, and the other a brute-force active-set method. The other two are heuristics, meaning that they rapidly compute locally optimal solutions; one uses an alternating projection algorithm with extrapolation, and the other a sequential partial linearization approach based on fractional programming. We illustrate the use of these algorithms on several examples.