director de "pseudo vector propio" de un real simétrica positiva semidefinite matriz

Question

Deje $A$ ser un real simétrica positiva semidefinite matriz y supongamos que $c>0$ es suficientemente pequeño número. Me pregunto si es posible resolver la no-convexo de optimización $$\arg\max_u\ u^\mathrm{T}Au\\ \mathrm{subject\ to\ }\left\Vert u\right\Vert_2\leq 1\\ \quad\quad\quad\quad\left\Vert u\right\Vert_1\leq c,$$ de manera eficiente.

Para la solución de la optimización, no podía llegar más lejos de lo que escribe condiciones KKT que no ayudan mucho en la especificación de los multiplicadores.

Dado que sin el $\ell_1$norma de restricción (es decir,$c\to\infty$), el problema se reduce a encontrar el principal vector propio de a $A$ que puede ser resuelto de manera eficiente (por ejemplo, usando el poder de iteración del método), podemos pensar que la solución para la optimización anterior como "pseudo vector propio".

Answer 1

No estoy seguro acerca de la función objetivo de la parte. Pero para las restricciones, Puede ser que esto va a ayudar. Escribir $u=u^{+}-u^{-}$ donde $u^{+}$ denota la parte positiva en $u$ $u^{-}$ denota la parte negativa. Ahora con esto, el problema anterior se convertirá en

\begin{align} \arg\max_{u^{+},u^{-}}\ {u^{+}}^{T}Au^{+}+{u^{-}}^{T}Au^{-}-2{u^{-}}^{T}Au^{+} \\ subject ~~to& [1,1\ldots,1]^{T}({u^{+}}+{u^{-}}) <= c \\ & (u^{+}-u^{-})^{T}(u^{+}-u^{-})<=1 \\ & u^{+}>=0, u^{-}>=0 \end{align}

Usted puede hacer la función objetivo lineal mediante la incorporación de una variable $t$ y, por tanto, la adición de un no-convexo cuadrática restricción. Todas las demás restricciones lineales puede ser reformulada como cuadrática restricciones. Creo que, a continuación, se puede reformular como un semi-definitiva del programa. En los detalles

\begin{align} \min_{t}~~ -t \\ subject~to~ &u^{H}Au \geq t \\ & [1,1\ldots,1]^{T}({u^{+}}+{u^{-}}) <= c \\ & (u^{+}-u^{-})^{T}(u^{+}-u^{-})<=1 \\ & u^{+}>=0, u^{-}>=0,t>=0 \end{align}

Tenga en cuenta que esto es equivalente al problema original. Ahora las variables $u^{+},u^{-},t$ pueden ser combinados para formar un único vector $x$ y yo creo que se puede escribir como un problema de optimización lineal objetivo y no convexa cuadrática restricciones. Si es posible, a continuación, Semi-definida de Relajación (SDR) es muy famosa técnica para lidiar con tal que no sean problemas convexos. También en su caso, SDR debe dar soluciones exactas. En los detalles, es un problema que debe ser algo como

\begin{align} \min_{x}~~ a^{T}x \\ subject~to~ &x^{H}F_{1}x \geq c_1 \\ & x^{H}F_{2}x \geq c_2\\ & x^{H}F_{3}x \geq c_3 \\ & x>=0 \end{align}

Si usted puede reformular el problema de esta manera que creo que es posible, a continuación, semi-definida relajación de trabajo.