Resolución de un problema QCQP con regularización dispersa

Question

Quiero resolver el siguiente problema de QCQP:

$$ \mbox{Minimize}\quad\beta^TA\beta+\mu\Omega(\beta)$$ $$ \mbox{s.t.}\quad\beta^TB\beta=1 \quad\mbox{and}\quad\beta\ge0 $$

donde $A$ y $B$ son ambas positivas definidas, y $\Omega(\cdot)$ es una norma dispersa (por tanto, no lisa, pero sí convexa), como $\ell_1$ norma o $\ell_1/\ell_2$ para un determinado conjunto de grupos.

Mi plan tentativo es combinar Algoritmo FISTA y Métodos de homotopía ( un documento relevante que he encontrado ) para $f(\beta)=\beta^TA\beta++\lambda(\beta^TB\beta-1)+\mu\Omega(\beta)$ que puede manejar tanto $\beta$ y el multiplicador de Lagrange $\lambda$ pero no he encontrado un algoritmo que considere la restricción $\beta\ge 0$ (en el sentido de entrada). Entonces, ¿puedo mejorar el algoritmo para abarcar las constantes cónicas? Gracias.

Answer 1

Hay varios métodos que se pueden aplicar a este problema. No tengo tiempo para escribir una solución completa, pero he aquí una idea rápida. Sustituir $\Omega$ por $\hat\Omega = \Omega + \delta_+$ , donde $\delta_+$ es la función indicadora del ortante no negativo. Ahora, si usted puede reducir su problema a un método de división proximal que funciona aproximadamente como (no exactamente esto debido a sus restricciones de igualdad)

$$ \beta^{k+1} \gets \mbox{prox}(\beta^k - \eta_k\nabla L(\beta^k)), $$ donde $L$ es la parte diferenciable del problema, y $\mbox{prox}$ es el operador de proximidad que maneja $\hat\Omega$ Entonces, ya está hecho.

Afortunadamente, el operador de proximidad de $\hat\Omega$ es simplemente la composición del operador de proximidad de $\Omega$ con proyección sobre el ortante no negativo. Por lo tanto, en cierto sentido, puede utilizar fácilmente los métodos del estilo FISTA.