¿Cómo puedo simplificar esta optimización cuadrática?

Question

Quiero minimizar $x^t P x + q^t x$ con la siguiente restricción:

Para todos $b \in B$ , $|x^b| \le C \sum_{b' \in B} |x^{b'}|$

donde $B = {1, ..., n}$ y $x^b$ es el $b$ de los componentes de la $n$ -vector de columnas de dimensión variable $x$ . $C$ es alguna constante positiva que, para evitar la trivialidad, debe satisfacer $1/|B| \le C \le 1$ .

La única forma que conozco de hacerlo es hacer $2^{|B|}$ optimizaciones sobre el cono convexo dado por:

Para todos $b \in B$ , $x^b \ge 0$ y $x^b \le C \sum_{b' \in B} x^{b'}$

y sus reflejos. ¿Existe una forma más eficaz de resolver este problema?

Para mis propósitos digamos $C = 1/5$ y $n = 100$ . No estoy seguro de tener muchas opciones en la estructura de $P$ y $q$ por lo que una solución eficiente para el $P$ y $q$ es deseable.

(Quizás una solución aproximada sea mucho más fácil de encontrar. También se agradecería la ayuda con eso).

Answer 1

Sus limitaciones son que $-C \|x\|_1 \leq x \leq C \|x\|_1$ de los componentes. Se puede transformar el $\|x\|_1$ introduciendo nuevas variables $x_+$ y $x_-$ , ambos $\geq 0$ y la división $x = x_+ - x_-$ . Con estas nuevas variables, $\|x\|_1 = \sum_{b \in B} (x_+^b + x_-^b)$ . Así que sus limitaciones se convierten en $$ -C \sum_{b \in B} (x_+^b + x_-^b) \leq x \leq C \sum_{b \in B} (x_+^b + x_-^b), $$ $$ x = x_+ - x_-, \quad (x_+, x_-) \geq 0. $$ Para forzar una de $x_-$ o $x_+$ sea cero, se podría añadir la restricción de complementariedad $$ x_- \cdot x_+ = 0 \quad \text{(or $ \N - 0 $)}. $$ El resultado es un programa cuadrático con restricciones de complementariedad (QPCC o QPEC). Hay varios enfoques para resolverlo, incluidos ciertos métodos de punto interior. Se necesita un método especializado para resolver el problema en esta forma porque es degenerado, es decir, no satisface la condición de cualificación de las restricciones de Mangasarian-Fromowitz.