Let \(\mathcal C_d\) denote the set of nonzero closed convex cones in \(\mathbb R^d\). Let \(A \in \mathbb {R}^{m \times n}\) and \((P,Q)\in \mathcal C_m\times \mathcal C_n\). The nonconvex optimization problem

\begin{equation} \label {eq:SVcones} \min _{\scriptsize \begin{array}{l}u\in P,\,\Vert u\Vert =1,\\v\in Q,\,\Vert v\Vert =1\end {array}}\langle u,Av\rangle , \end{equation}

has been studied in depth in [1], mainly from a theoretical point of view. Any critical (stationary) point \((u,v)\) of (1) satisfies the KKT optimality conditions

\begin{equation} \label {d1} \begin{cases} \,P\ni u\perp (A\,v-\sigma u) \;\,\in P^\ast ,& \\ \,Q\ni v\perp (A^\top u -\sigma v)\in Q^\ast , &\\ \Vert u\Vert =1,\;\Vert v\Vert =1, &\end {cases} \end{equation}

for some real Lagrange multiplier \(\sigma \), where \(P^\ast \) and \(Q^\ast \) are the dual cones of \(P\) and \(Q\), respectively. Observe that when \(P=\mathbb R^m\) and \(Q=\mathbb R^n\), (2) provides us the (classical) singular values of \(A\).

The model (1) covers many interesting optimization problems. Some of them are: maximal angle between two cones [2], obtained when \(m=n\) and \(A=I_n\), expressed by

\begin{equation*} \min _{\scriptsize \begin{array}{l}u\in P,\,\Vert u\Vert =1,\\v\in Q,\,\Vert v\Vert =1\end {array}}\langle u,v\rangle ; \end{equation*}

cone-constrained principal component analysis or Pareto singular values [3, 5], in which the two cones are the positive orthants of the respective spaces as in \(P = \mathbb R^m_+\) and \(Q = \mathbb R^n_+\), formalized as

\begin{equation*} \min _{\scriptsize \begin{array}{l}u\geq 0,\,\Vert u\Vert =1,\\v\geq 0,\,\Vert v\Vert =1\end {array}}\langle u,Av\rangle ; \end{equation*}

nonnegative rank-one factorization matrix [4], equivalent to the Pareto singular value problem, and written as

\begin{equation*} \min _{u\geq 0, v\geq 0} \|M - uv^\top \|_F. \end{equation*}

The above problems can be proven to be in a descending order of complexity. Since the last formulation in particular can be used to solve the Maximal Edge Biclique Problem, this leads to the conclusion that all the above models are NP-hard to solve.

We will discuss the linear algebra techniques used to reduce each problem to the following one, with a focus on sufficient conditions needed for each problem to be instead solved in polynomial time.

An exact (and thus necessarily exponential time) brute force active set algorithm is presented. Its proof of correctness is based on the observation in [1] that when we restrict the problem on the relative interior of the faces of the cones \(P\) and \(Q\), then the relations (2) reduces to a generalized eigenvalue problem with additional constraints. This can be solved with classical techniques, with some careful handling in case of eigenvalues with relative eigenspace of dimension more than one.

We will describe the algorithm with a focus on how to cut computational cost through the study of the stationary points of the problem in order to distinguish minima from saddle points.

We compare the active set algorithm with an exact non-convex quadratic programming solver, that relies on the McCornick relaxation to solve the problem, and thus performs well in case of sparse problems.

Moreover, we show two additional iterative algorithms to solve the general problem, an alternating method with extrapolation and a fractional programming method. These are methods that are only guaranteed to converge to stationary points, and cannot certify the minimality of the solution they find.

We discuss and illustrate the use of these algorithms on several examples, as in the computation of maximal angles between the Schur cone and other cones or the computation of maximal edge bicliques.

We show how they can lead to rigorous proofs or new conjectures in special cases, such as the maximal angle between the cone of positive semidefinite matrices and the cone of nonnegative symmetric matrices.

References

• [1]  Seeger, Alberto and Sossa, David. Singular value analysis of linear maps under conic constraints. Set-Valued and Variational Analysis, 31 (2023).

• [2]  Orlitzky, Michael. When a maximal angle among cones is nonobtuse. Computational and Applied Mathematics, 83 (2020).

• [3]  Montanari, Andrea and Richard, Emile. Non-negative principal component analysis: Message passing algorithms and sharp asymptotics. IEEE Trans. Informat. Th., 62: 1458-1484 (2016).

• [4]  Gillis, Nicolas and Glineur, Françoise. A continuous characterization of the maximum-edge biclique problem. Journal of Global Optimization, 58: 439-464 (2014).

• [5]  Seeger, Alberto and Sossa, David. Singular value problems under nonnegativity constraints. Positivity, 27 (2023).