Convierta un QCQP no convexo en una contraparte convexa

Question

Problema

Consideramos que posiblemente no convexa QCQP, con no negativo de la variable $x\in \mathbb{R}^n$,

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f_0(x) \\ & \text{subject to} & & f_i(x) \leq 0, \; i = 1, \ldots, m\\ & & & x \geq 0 \end{aligned} \end{ecuación*}

donde $f_i(x)=\frac{1}{2}x^TP_ix+q_i^Tx+r_i$, con $P_i\in \mathbb{S}^n$, $q_i\in \mathbb{R}^n$, y $r_i \in \mathbb{R}$$i=0,\cdots,m$. Nosotros no asumimos que $P_i\geq0$, por lo que este no necesita ser un problema convexo.

Supongamos que $q_i\leq 0$ $P_i$ no positivo entradas fuera de la diagonal. Explicar cómo reformular este problema como un problema convexo.

Lo Que He Hecho

Dado que tanto la función objetivo y las restricciones son, posiblemente, no convexa, considero que su estructura común, que es $f_i(x)=\frac{1}{2}x^TP_ix+q_i^Tx+r_i, \ i=0,1,2,\cdots,m$. En esta estructura, $q_i^Tx+r_i$ parte es afín, por lo que no causa problema. Entonces yo sólo considere el $x^TP_ix$.

• La primera cosa que surge en mi mente es descomponer $P_i$ en cierta forma y hacer $x^TP_ix$ a ser algo así como $y^TQy$ donde $Q \geq 0$. Sin embargo, no he encontrado nada útil (en realidad parece que no debe o no-convexo de programación cuadrática podría ser resuelto de esta manera).
• Aunque el anterior pensamiento aleatorio no parece funcionar, todavía pienso en cierta transformación es necesario, y tal vez algunos no-lineal de la transformación de $y_i=\phi (x_i)$. Pero viniendo para arriba con esto puede necesitar un poco de "magia" y hasta ahora han encontrado nada de lo que ayuda.

Podría alguien ayudarme, gracias de antemano.

Answer 1

Finalmente llegué a una solución, que parece ser un válido reformulación.

Expandir $f_i(x) \ (i=0,1,\cdots,m)$ en el formulario (formulario de claridad, se me caerá el subíndice en $f_i(x), P_i$$q_i$. $$f(x)=\frac{1}{2}\sum_i^{n}P_{ii}x_i^2+\sum_{i\neq j}P_{ij}x_i x_j+ \sum_i^n q_i x_i + r$$

Observe que $x \geq 0$, aplicar el cambio de variable $y_i=x_i^2$, tenemos

$$f(y)=\frac{1}{2}\sum_i^{n}P_{ii}y_i+\sum_{i\neq j}P_{ij}\sqrt{y_i y_j}+ \sum_i^n q_i\sqrt{y_i} + r$$

El primer término $\sum_i^{n}P_{ii}y_i$ es afín en $y_i$. Lo que es más, ya que las entradas fuera de la diagonal de a $P$ son no positivos, y esto hace que el segundo término convexo. Del mismo modo, el último término de $\sum_i^n q_i\sqrt{y_i} + r$ también es convexo. A continuación, $f(y)$ es convexa.

La "sugerencia", directamente desde el problema es $x\geq 0$, lo que indica la posibilidad de tomar la raíz cuadrada.