A LINEAR-TIME ALGORITHM FOR COMPLEX TRUST REGION SUBPROBLEM WITH A LINEAR CUT

What the paper says

(Communicated by Xinwei Liu) In this paper, we study the trust region subproblem with a linear cut over the complex domain ${\rm (TL)}$. $\begin{eqnarray*}{\rm \left(TL\right)}~&\min_{w\in\Bbb C^n}&F(w)=\frac{1}{2}w^HAw+\mathcal{R}(b^Hw)\\~~~~~~~~~~~&{\rm s.t.}& w^Hw-1\leq 0,\\~~~~~~~~~~~&&\mathcal{R}(c^Hw)-d\leq 0,\end{eqnarray*}$ where $A\in\Bbb C^{n\times n}$ is an Hermitian matrix, whose eigenvalues are real numbers. We assume that $A\nsucceq 0$ and denote its eigenvalues by $\lambda_1\leq \lambda_2\leq...\leq\lambda_n$, where at least one of them is negative, i.e.,$\lambda_1<0$. We also assume that the Slater condition holds, i.e., there exists $\hat{w}$ such that $\hat{w}^H\hat{w}<1,~\mathcal{R}(c^H\hat{w}) $\begin{eqnarray*}{\rm \left(C\right)}~&\min_{w\in\Bbb C^{n}}& P(w)=\frac{1}{2}w^H(A-\lambda_1I)w+\mathcal{R}(b^Hw)+\frac{1}{2}\lambda_1\\~~~~~~~~~~~&{\rm s.t.}& w^Hw-1\leq 0,\\~~~~~~~~~~~&&\mathcal{R}(c^Hw)-d\leq 0.\end{eqnarray*}$ As an approximation of ${\rm (C)}$, we turn to solve the following convex programming problem $\begin{eqnarray*}&{\rm \left(AC\right)}&\min_{w\in\Bbb C^{n}} \frac{1}{2}w^H(A-\tilde{\lambda}_1 I)w+\mathcal{R}(b^Hw)+\frac{1}{2}\tilde{\lambda}_1\\~~~~~~~~~~~&{\rm s.t.}& w\in W:=\left\{w^Hw\leq 1,~\mathcal{R}(c^Hw)\leq d\right\},\end{eqnarray*}$ which can be further equivalently reformulated as the problem ${\rm (AC^r)}$: $\begin{eqnarray*}&{\rm \left(AC^r\right)}&\min_{z\in\Bbb R^{2n}} g(z):=\frac{1}{2}z^T(Q-\tilde{\lambda}_1I)z+q^Tz+\frac{1}{2}\tilde{\lambda}_1\\~~~~~~~~~~~&{\rm s.t.}& z\in S:=\left\{z^Tz-1\leq 0,~h^Tz-d\leq 0\right\}.\end{eqnarray*}$ Then we present a linear-time algorithm approximation scheme (in terms of the number of nonzero entries) for solving ${\rm (TL)}$ based on ${\rm (AC^r)}$. It mainly employs the eigenvalue approximation technique and Nesterov's accelerated gradient descent algorithm. Algorithm 1 (a) Choose $\theta_0=\theta_{-1}\in(0,1]$, $z_0=z_{-1}\in S$. Let $k:=0$. (b) Let $y_k=z_k+\theta_k(\theta_{k-1}^{-1}-1)(z_k-z_{k-1})$ and $\nabla g_k=\nabla g(y_k)$. Update \begin{align*}z_{k+1}=\arg \min_{z\in S}~G(z)=z^T\nabla g_k+\rho\|z-y_k\|^2.\label{1}\tag{1}\end{align*} (c) Choose $\theta_{k+1}\in(0,1]$ satisfying $\frac{1-\theta_{k+1}}{\theta_{k+1}^2}\leq \frac{1}{\theta_k^2}.$ If the stopping criterion does not hold, update $k:=k+1$ and go to step (b). Then given the parameters $\epsilon>0$, $\delta>0$, with probability at least $1-\delta$ over the randomization of an approximate eigenvector oracle, we can find an $\epsilon$-approximation solution of ${\rm (TL)}$ in total time $O\left(\frac{N\sqrt{\|A\|}}{\sqrt{\epsilon}}\log\frac{n}{\delta}\right).$We show the efficiency of the algorithm by comparing it with CVX solver in the numerical experiment. We can also see from Figure 1 that for the same dimension, the required time increases linearly with density. Figure 1: Computational time for different density with $\epsilon=10^{-6}$