La dualidad en cuadráticamente limitada cuadrática programa

Question

Se me ha dado el primal cuadrática programa con una sola restricción cuadrática como se indica a continuación:

$$ \text{min} ~~~~~~~~~~~~~~~~~~~~~~~~~ \frac{1}{2}x^{T}Qx $$ \begin{align*} \text{subject to}~~~~~~~~~\frac{1}{2}x^{T}x &\leq \frac{1}{2}\\ x &\in \mathbb{R}^n \end{align*}

donde Q es indefinido, simétrica, racional matriz de tamaño n. La tarea es mostrar que los valores óptimos de las primordiales problema dado y su doble de acuerdo. Es decir, no existe la dualidad de la brecha.

Tengo (tal vez erróneamente) determina el Lagrangiano de este programa $$L(x,u) = \frac{1}{2}x^{T}Qx+\frac{1}{2}u(x^{T}x-1) = \frac{1}{2}x^{T}(Q+uI)x-\frac{1}{2}u. $$

En este punto, después de perseguir a través de algunas circular álgebra de intentar resolver el doble problema de maximizar ( $u$ ) el infimum ( $x \in \mathbb{R}^n$ ) $L(x,u)$ y hacer un poco de KKT análisis sobre el primordial problema dado, me parece que no puede llegar al resultado deseado. Además, entiendo que hay un teorema que dice que si no existe un punto de silla de la función de Lagrange, entonces no hay ninguna dualidad gap (Bazaraa, Sherali, y Shetty), sin embargo, me parece que no puede conciliar cualquier tipo de "matemáticamente apretado" garantía de que no existe un punto de silla para $L$ (aunque tengo un presentimiento de que no debería ser desde $Q$ es de carácter indefinido, es decir, $Q$ no es DP, no PSD, no se encuentra, no NSD).

Si alguien pasa a ver algo particularmente perspicaz en todo esto, yo realmente apreciaría la entrada.

Answer 1

Deje $\lambda_{\min}$ ser el mínimo autovalor de a $Q$.

La función dual se \begin{align} g(u) &= \inf_x L(x,u) \\ &= \begin{cases} -\infty \quad \text{if } u < -\lambda_{\min} , \\ -\frac12 u \quad \text{otherwise}. \end{casos} \end{align} El problema es doble \begin{align} \operatorname*{maximize}_{u} & \quad -\frac12 u \\ \text{subject to} & \quad u \geq -\lambda_{\min}. \end{align} El valor óptimo para el problema dual se \begin{equation*} d^\star = \frac12 \lambda_{\min}. \end{ecuación*}

Y esto es igual a lo principal, el valor óptimo, de acuerdo a la norma variacional caracterización de los autovalores de a $Q$.

Nota: Para derivar la función dual, he utilizado los siguientes hechos.

1. El mínimo autovalor de a$Q + u I$$\lambda_\min + u$.
2. Deje $M \in \mathbb R^{n \times n}$ ser simétrica. La función cuadrática $h(x) = \frac12 x^T M x$ es ilimitado a continuación si el mínimo autovalor de a $M$ es negativo. De lo contrario, el valor mínimo de $M$$0$.

Answer 2

Sugerencia: El problema es abordado de manera parcial en esta pregunta

Tenga en cuenta que este es uno de los raros no convexa de los problemas que tiene una solución de forma cerrada y tiene cero de la dualidad de la brecha.