Duality in quadratically-constrained quadratic program (QCQP)

Question

I have been given the primal quadratic program with a single quadratic constraint as given below:

$$ \begin{array}{ll} \min\limits_{x \in \mathbb{R}^n} & \frac12 x^{T} Q x \\ \text{subject to} & \frac12 x^{T} x \leq \frac12 \end{array} $$

where $Q$ is an indefinite, symmetric, rational matrix of size $n$. The task is to show that the optimal values of the primal problem as given and its dual agree. That is, there is no duality gap.

I have (perhaps incorrectly) determined the Lagrangian of this program to be $$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. $$

At this point, after chasing through some circular algebra attempting to solve the dual problem to maximize (over $u$) the infimum (over $x \in \mathbb{R}^n$) of $L(x,u)$ and doing some KKT analysis on the primal problem as given, I can't seem to arrive at the desired result. Further, I understand there is a theorem which says that if there exists a saddle point of the Lagrangian function, then there is no duality gap (Bazaraa, Sherali, and Shetty), yet I can't seem to reconcile any sort of "mathematically tight" guarantee that there exists a saddle point for $L$ (although I have a hunch that there ought to be since $Q$ is indefinite, that is, $Q$ is not PD, not PSD, not ND, not NSD).

If anyone happens to see something particularly insightful in all of this, I would really appreciate the input.

Answer 1

Hint: Your problem is partially addressed in this question

Note that this is one the rare non-convex problems that has a closed form solution and has zero duality gap.

Answer 2

Let $\lambda_{\min}$ be the minimum eigenvalue of $Q$.

The dual function is \begin{align} g(u) &= \inf_x L(x,u) \\ &= \begin{cases} -\infty \quad \text{if } u < -\lambda_{\min} , \\ -\frac12 u \quad \text{otherwise}. \end{cases} \end{align} The dual problem is \begin{align} \operatorname*{maximize}_{u} & \quad -\frac12 u \\ \text{subject to} & \quad u \geq -\lambda_{\min}. \end{align} The optimal value for the dual problem is \begin{equation*} d^\star = \frac12 \lambda_{\min}. \end{equation*}

And this is equal to the primal optimal value, according to the standard variational characterization of the eigenvalues of $Q$.

Note: To derive the dual function, I used the following facts.

1. The minimum eigenvalue of $Q + u I$ is $\lambda_\min + u$.
2. Let $M \in \mathbb R^{n \times n}$ be symmetric. The quadratic function $h(x) = \frac12 x^T M x$ is unbounded below if the minimum eigenvalue of $M$ is negative. Otherwise, the minimum value of $M$ is $0$.